Magazine Environnement

Propriétés de la multiplication binaire sans retenue

Publié le 18 janvier 2011 par Serdj

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 :
http://www.wikio.fr
PUBLIER CETTE PAGE OU VOTER POUR CET ARTICLE SUR DIGG-FRANCE.COM

Vous pourriez être intéressé par :

Retour à La Une de Logo Paperblog

Ces articles peuvent vous intéresser :

A propos de l’auteur


Serdj 10414 partages Voir son profil
Voir son blog

l'auteur n'a pas encore renseigné son compte l'auteur n'a pas encore renseigné son compte l'auteur n'a pas encore renseigné son compte

Dossier Paperblog