Auteur: Serge Boisse
Date: Le 27/03/2023 à 13:03
Type: web/MOC
Tags: maths,nombres,factorisation,XOR
pub: oui
commentaires: ouiCopier

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)`
Copier

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
Copier

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
Copier

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  
Copier

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))  
Copier

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  
Copier

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 !