Journal d'un terrien

Web log de Serge Boisse

On line depuis 1992 !

Recherche personnalisée

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 particulier peut-on trouver un morphisme d'anneau entre ces deux structures ?

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

Home Mes livres Mes tableaux Plan du site

Partagez / votez pour cette page :

Commentaires (0) :

Page :



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 fait par les autres. L'auteur du site se réserve le droit de supprimer un ou plusieurs posts à tout moment. Merci !
Ah oui : le html genre <a href=...>, <b>b etc. ne fonctionne pas dans les commentaires. C'est voulu.
< Retour en haut de la page