Journal d'un Terrien

Web log de Serge Boisse

On line depuis 1992 !

Publicité

Si cette page vous a plu, Copiez son adresse et partagez-la !
http://sboisse.free.fr/science/maths/proprietes-multiplication-sans-retenue.php

proprietes-multiplication-sans-retenue
Metadata
Serge Boisse
Le 27/03/2023 à 13:03
web/MOC
oui
oui

Propriétés de la multiplication binaire sans retenue

Qu'est ce qu'une multiplication binaire sans retenue ? cela consiste à poser une multiplication binaire comme on le fait d'habitude, mais au lieu de faire l'addition des sous-produits, on en fait le XOR. Dans ce qui suit, on notera "*" la multiplication ordinaire et "@" la multiplication sans retenue. Par exemple :

       1 1 1 0 1   (29)  
      @    1 0 1    (5)  
      -----------  
       1 1 1 0 1  
     0 0 0 0 0  
   1 1 1 0 1  
 ----------------  
   1 1 0 1 0 0 1   (105)`

Donc 29@5 = 105, alors que 29*5 = 145

Voici une table de multiplication binaire sans retenue pour les opérandes de 1 à 10 :

 @    1    2    3    4    5    6    7    8    9    10   
 1    1    2    3    4    5    6    7    8    9    10      
 2    2    4    6    8   10   12   14   16   18    20  
 3    3    6    5   12   15   10    9   24   27    30  
 4    4    8   12   16   20   24   28   32   36    40  
 5    5   10   15   20   17   30   27   40   45    34  
 6    6   12   10   24   30   20   18   48   54    60  
 7    7   14    9   28   27   18   21   56   63    54  
 8    8   16   24   32   40   48   56   64   72    80  
 9    9   18   27   36   45   54   63   72   65    90  
10   10   20   30   40   34   60   54   80   90    68

Il est trivial de démontrer que la multiplication binaire sans retenue est commutative. Elle est également associative : (a@b)@c = a@(b@c) pour tous les  entiers positifs (a,b,c).  Elle possède un élément neutre (1) et un élément absorbant (0). Jusqu'ici, cela ressemble beaucoup à la multiplication classique.

Avec le logiciel gnuplot on implemente @ ainsi :

    mul(a,b) = (b==0)?0:(b==1)?a:((b&1)*a)^(mul(a,b/2)*2)
ou comme suit :

   mul(a,b) = (b<2)?(b&1)*a:((b&1)*a)^(mul(a,b/2)*2)

On peut aussi implémenter la division binaire sans retenue comme suit (algorithme très peu efficace): remarque: on a  a@b > a si a > 1) :

   div(n,d)=rd(n,d,n)   
    rd(n,d,x)= (x<=1)? 1 : (mul(x,d)==n) ? x : rd(n,d,x-1)   
    //le résultat est 1 si n et d sont premiers entre eux

Mais @ est distributive, non par rapport à l'addition, mais par rapport à XOR. Si l'on note ^ le ou exclusif, comme dans les langages de programmation C ou Java,  on a :

(a ^ b) @ c =  (a@c) ^ (b@c)

d'où trivialement(a^b)@(c^d) = a@c ^ a@d ^ b@c ^ b@d

On remarque aussi que 2 @ b = 2b  et  3 @ b = b ^ 2b ; par exemple 3@31 = 33 !

Comme (N,^) est un groupe commutatif (où chaque entier est son propre inverse), il s'en suit que (N, ^, @) est un anneau commutatif unitaire.  Le seul élement inversible est 1. Il n'y a pas de diviseurs de zéro, l'anneau est intègre.

Les "nombres premiers" (éléments irréductibles) dans la multiplication binaire sans retenue, c'est à dire ceux qui ne sont divisibles que par eux-mêmes et par 1,  sont :
3, 7, 11, 13, 19, 25, 31, 37, 41, 47, 55...
Ce sont les  polynômes binaire irréductibles, ou encore les éléments de l'anneau GF(2)[ X ]   (anneau des polynômes sur le corps de Galois à deux éléments 0 et 1) évalués pour X=2. On les trouve dans l'enyclopedia of integer sequence sous la référence A014580

Quelques décompositions en facteurs "premiers" (irréductibles) via @ :
(on pose a@@2 = a@a, a@@3 = a@a@a etc.)

2 est irréductible  
3 est irréductible  
5 = 3@3 = 3@@2  
7 est irréductible  
9 = 3@7  
11 est irréductible  
13 est irréductible  
15 = 3@@3  
17 = 3@@4  
19 est irréductible  
21 = 7@@2  
23 = 3@13  
25 est irréductible  
27 = 3@@2 @ 7  
29 = 3@11  
31 est irréductible  
33 = 3@31  
35 = 7@13  
37 est irréductible  
39 = 3@@2 @ 11  
41 est irréductible  
43 = 3@25  

La décomposition semble unique : (N, ^, @)  est il un anneau factoriel ? Je ne sais pas (je crois que oui)  Est-il euclidien ? Je ne sais pas non plus. Il faudrait définir une norme. Ces questions m'intéressent au plus haut point. Si vous avez la réponse, dites le moi !

Les "carrés" a@a sont :

n    1,2,3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15, 16, 17, 18, 19, 20, 21, 22, 23
n@n  1,4,5,16,17,20,21,64,65,68,69,80,81,84,85,256,257,260,261,272,273,276,277

Ce sont les nombres qui s'ecrivent en base 4 seulement avec 0 et 1 (sloane's A000695)
ou encore Numbers n such that sum of base 2 digits of n = sum of base 4 digits of n
ou Numbers having the same representation in both binary and negabinary

Remarquons que :

2a @ 2a = 4 * (a @ a)  
(2a+1)@(2a+1) = 4 (a@a) + 1  
(2a)@(2a+1) = 2(a@(2a+1))  

A noter que tout entier n correspond à un unique couple (a,b) tel que n = a@a + 2*b@b
par exemple 14 = 2@2 + 2(3@3) = 4 + 2*5 avec a = 2 et b =3

Ces nombres a et b sont respectivement ceux formés avec les bits pairs et impairs de n
avec gnuplot:

pairs(b)= (b<=0)?0:(b%2)+pairs(b/4)*2  
impairs(a)= (a<=1)?0:((a/2)%2)+impairs(a/4)*2  

remarque : Si a=i^j alors i=a^j et n=(a^j)@(a^j) + 2(j@j) = (a@a ^ j@j) + 2(j@j)

Evidemment en étudiant la fonction "@" j'ai une idée derrière la tête : construire une méthode de factorisation rapide en exploitant les ressemblances entre (N,+,*) et (N,@,^). En particulier peut-on trouver un morphisme d'anneau entre ces deux structures ?

Voila, il reste  plein de choses à étudier, à vous de jouer !

Publicité
Commentaires

Commentaires (1) :

Page : [1] 

euclide
Le 21/04/2021 à 21h45
très intéressant. A suivre !


Ajouter un commentaire (pas besoin de s'enregistrer)

Pseudo :
Message :


image de protection
En cliquant sur le bouton "Envoyer" vous acceptez les conditions suivantes : Ne pas poster de message injurieux, obscène ou contraire à la loi, ni de liens vers de tels sites. Respecter la "netiquette", ne pas usurper le pseudo d'une autre personne, respecter les posts faits par les autres. L'auteur du site se réserve le droit de supprimer un ou plusieurs posts à tout moment. Merci !
Ah oui : le bbcode et le html genre <br>, <a href=...>, <b>b etc. ne fonctionnent pas dans les commentaires. C'est voulu.
< Retour en haut de la page