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 !