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 entiere comme suit : (on a  a@b > a si a > 1) :

   div(n,d)=rd(n,d,n) 
  rd(n,d,x)=(x<=1)?1:(m(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ême 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) tq n=a@a + 2*b@b
par exemple 14 = 2@2 + 2(3@3) = 4 + 2*5 avec a = 2 et b =3
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 particulie peut on trouver un morphisme d'anneau entre ces deux structures ?
Voila, il reste  plein de choses à étudier, à vous de jouer !

Partagez / votez pour cette page :