compression du calcul binaire

yoshi · 17-09-2008 12:24:58

Bonjour,

Et bien en base seize, tu ajoutes les "chiffres" A, B, C, D, E, F..
Et comme le langage de programmation ne peut importer les lettres comme des chiffres directement, il faut commencer par extraire chaque "chiffre" des nombres les ranger dans deux tableaux (ou des listes avec Python)...
Ensuite il faut les additionner un par un et il y a 128 possibilités à chaque fois.
On peut raccourcir un peu en testant si la somme est inférieure à 10 auquel, on la fait telle quelle...
Sinon il faut tester chaque cas un par un via une boucle et, une fois l'occurence trouvée, extraire la bonne somme, tester s'il y a une retenue et la reporter sur la somme suivante, stocker le résultat dans une 3e liste...
Travail de Romains... A mon avis : le temps de fonctionnement sera prohibitif...
Si j'ai pu le faire en base dix, c'est que je me limitais à l'addition, la soustraction, la multiplication de nombres à 1 chiffre dont les résultats étaient obtenus instantanément...
J'ai plusieurs fers au feu, lorsque j'aurai épongé ce que j'ai à faire, je tenterai la programmation (en attendant je vais y réfléchir à mes moments perdus).

@+

yoshi · 17-09-2008 12:27:47

Bonjour,

Et bien en base seize, tu ajoutes les "chiffres" A, B, C, D, E, F..
Et comme le langage de programmation ne peut importer les lettres comme des chiffres directement, il faut commencer par extraire chaque "chiffre" des nombres les ranger dans deux tableaux (ou des listes avec Python)...
Ensuite il faut les additionner un par un et il y a 128 possibilités à chaque fois.
On peut raccourcir un peu en testant si la somme est inférieure à 10 auquel, on la fait telle quelle...
Sinon il faut tester chaque cas un par un via une boucle et, une fois l'occurence trouvée, extraire la bonne somme, tester s'il y a une retenue et la reporter sur la somme suivante...
Travail de Romains... A mon avis : le temps de fonctionnement sera prohibitif, trop de tests...
Si j'ai pu le faire en base dix, c'est que je me limitais à l'addition, la soustraction, la multiplication de nombres à 1 chiffre dont les résultats étaient obtenus instantanément...
J'ai plusieurs fers au feu, lorsque j'aurai épongé ce que j'ai à faire, je tenterai la programmation (en attendant je vais y réfléchir à mes moments perdus).

@+

sinuspax · 18-09-2008 14:08:13

Un travail de romain, certes, mais combien gratifiant. 128 opérations basiques à mémoriser par type d'opération, ce n'est pas la mer à boire, d'autant plus que la grandeur des nombres n'influe pas sur la table. Un processeur pourrait peut-être enfin calculer à notre image.
Pour l'opération 17 x 18 en base 16, on aurait :

00010001 x 00010010 =

1) 0010 x 0001 = 0010 (table)
2) 0010 x 0001 = 0010 (table)

3) 0001 x 0001 = 0001 (table)
4) 0001 x 0001 = 0001 (table)

000000100010
00010001

000100110010 = 132 (306).

Evidemment, pas de retenue ici. En base 16, voire en base 256, la vitesse de calcul des processeurs serait bien supérieure (en dépit des retenues). Reste à résoudre le problème du stockage des grands nombres. Mais là aussi des solutions seront trouvées (je suis un optimiste).

yoshi · 18-09-2008 14:15:06

Re,

Encore une fois, ce que tu fais c'est de la base deux....
Voilà des calculs en base seize :
Ton exemple Autre exemple
11 3AF (943)
x 12 X E5D (3677)
--------- ---------------
22 2FE3
11 126B
-------- 3392
132 -------------
34E893 (3467411)
Quant à "ça n'est pas la mer à boire", tu ne dois avoir aucune idée du temps pris par les tests avant de tomber sur le bon produit, puis de la bonne somme dans l'exécution d'un programme...
Si tu en doutes, vas-y, lance-toi !

@+

Dernière modification par yoshi (18-09-2008 15:56:04)

sinuspax · 19-09-2008 09:17:38

Salut,

Je crois qu'il y a un quiproquo. Il me semble qu'on parle de langage machine (écriture binaire). Je parle de base 16 en langage machine, non en langage alphanumérique.
Dans l'opération :

00000001 x 00010010 (11 x 12)

J'ai multiplié entre eux les quartets, non les bits, c'est donc bien de base 16 dont il s'agit (j'ai pris exprès un exemple simple). En base 2, j'aurais multiplié entre eux seulement les bits. L'opération aurait été beaucoup plus longue.

Base 16 en binaire :

0000 = 0
0001 = 1
0010 = 2
0011 = 3
0100 = 4
0101 = 5
0110 = 6
0111 = 7
1000 = 8
1001 = 9
1010 = A
1011 = B
1100 = C
1101 = D
1110 = E
1111 = F
00010000 = 10
...

Donc, ton opération s'écrit (en langage machine) :

001110101111 x 111001011101

Là aussi, je multiplierai entre eux les quartets, non les bits. D'où la nécessité de mémoriser toutes les opérations de quartet à quartet. Mais peut-être que c'est impossible.
Désolé pour "la mer à boire".

Dernière modification par sinuspax (19-09-2008 18:07:27)

yoshi · 19-09-2008 12:01:57

Bonjour,

Et moi je parle de calculs en base seize pure, sans autre recours à une base quelconque, d'où la nécessité de stocker la table de X et celle de +...

Encore une fois lorsqu'on programme en assembleur, tout est écrit en base seize, nombres comme instructions, le processeur n'effectue aucun calcul autre qu'en base deux, la base seize est juste une "commodité" d'écriture pour le programmeur.
Le processeur dispose d'un jeu d'instructions (ce que j'appelle routine) stockées dans une ou plusieurs zones (regitres) accessibles en lecture seule et d'autres zones dévolues au stockage temporaire.
Un exemple de langage machine (pour le processeur Z80 qui équipait notamment l'Amstrad CPC 6128) :
Adresse Code Mnémonique (en Assembleur) Commentaire
43000 3E,53 LD A,83 d Charge le code ASCII (décimal) de S
43002 CD,5A,BB CALL BB5A Appelle la routine d'affichage
43005 3E,41 LD A,65 d Charge le code ASCII de A
43007 CD,5A,BB CALL BB5A Appelle la routine d'affichage
43010 3E,4C LD A,76 d Charge le code ASCII (hexa) de L
43012 CD,5A,BB CALL BB5A Appelle la routine d'affichage
43015 3E,55 LD A,85 d Charge le code ASCII de U
43017 CD,5A,BB CALL BB5A Appelle la routine d'affichage
43020 3E,54 LD A,84 d Charge le code ASCII (hexa) de T
43022 CD,5A,BB CALL BB5A Appelle la routine d'affichage
43005 C9 RET Retour au programme appelantortie

En utilisant un éditeur Hexadécimal pour explorer les octets du n° 43000 au 43005, on voyait à l'écran :
3E 53 CD 5A BB 3E 41 CD 5A BB 3E 4C CD 5A BB 3E 55 CD 5A BB 3E 54 CD 5A BB C9
On réservait les adresses à partir de 43000, puis à l'aide d'une instruction du BASIC (Poke) on allait déposer ces valeurs aux adresses indiquées, puis en BASIC, on "appelait" l'adresse 43000 avec CALL 43000
Et on avait l'affichage de SALUT, en haut et à gauche de l'écran...
Le programmeur sur papier, utilise les mnémoniques, puis code le tout en Hexa

Ce que je me propose de faire (j'ai déjà mis au point une présentation des tables de X et de + ainsi qu'un moyen d'y accéder, tout se traite en "chaînes de caractères". Reste à mettre au point la technique de la multiplication et celle de l'addition.
Remarque : tout ceci est illusoire, parce que pour fonctionner, Python, fait appel au processeur et tout ce que je demande de faire est interprété...

Voudrais-tu dire que tu proposes d'implanter les tables de x et de + en base seize, en Assembleur, directement dans les zones ad hoc, puis de récrire les différentes opérations moyennant manipulation des instructions adéquates ?
Si oui, alors je n'avais pas compris ce que tu voulais dire et là, ça dépasse et de loin mes capacités...
Un commentaire toutefois ce que tu proposes ci-dessus c'est quand même du recours au binaire... D'autre part, si cela présentait un intérêt de rapidité accrue (et crois-moi, les concepteurs de processeurs y pensent sans arrêt), cela serait déjà fait...
Concernant les tests
Pour les mutiplications de caractères hexadécimaux, j'ai 136 cas (doubles : je stocke par exemple, 5*A et A*5 avec le résultat 32). De même pour l'addition.
Ce que je fais en Python pourrait certainement être fait directement en Assembleur : qui programme de nos jours en Assembleur ? Je crois que Windows est écrit en C, Firefox en XUL... etc
Je dois ensuite à partir d'un produit par exemple 5A * E
1. retrouver d'abord dans ma table E * A (136 tests maximum)
2. tester s'il y a une retenue au résultat, la stocker ou stocker 0
3. passer à 5*E, tester si j'ai deux chiffres au résultat
a) si oui stocker, celui le + à gauche
b) reprendre les le chiffre de droite, ajouter la retenue :
- identification de la bonne somme, l'effectuer stocker le chiffre de gauche ou 0
- effectuer la somme.
Ca en fait des tests !
Si je travaille directement avec des quartets, il faudra comparer quand même ces quartets, et pas d'autre solution que... bit à bit !

@+

sinuspax · 19-09-2008 13:30:42

Merci pour tes précisions. Je vais potasser là-dessus. Pour comparer d'éventuels quartets de bits 2 à 2, je m'étais dit qu'on pouvait mémoriser à chaque fois leur somme et leur produit. C'est dommage qu'une super programmation telle que la tienne ne puisse être adaptée au langage machine. Mais probablement mes connaissances en informatique sont insuffisantes pour avoir une idée nette de la chose.

@+

Dernière modification par sinuspax (19-09-2008 13:43:32)

sinuspax · 19-09-2008 18:46:23

L'idée est de faire calculer le processeur non plus bit par bit, mais 2 ^ n par 2 ^ n bits.
Par exemple, en base 16, le processeur calculera 4 bits par 4 bits (avec des zéros et des uns, bien sûr, mais ce n'est pas vraiment du binaire).

Reprenons ton opération (X) en binaire, bit par bit :

001110101111
111001011101

001110101111
000000000000
001110101111
001110101111
001110101111
000000000000
001110101111
000000000000
000000000000
001110101111
001110101111
001110101111

001101000101100010010011

Même opération en binaire 4 bits par 4 bits (base 16) :

0011 1010 1111
1110 0101 1101

0010 1111 1110 0011
0001 0010 0110 1011
0011 0011 1001 0010

0011 0100 0101 1000 1001 0011

La deuxième opération me semble quand même plus rapide. Evidemment, il nous faut mémoriser (comme tu le fais en hexa) tous les couples (+ et X) de quartets de bits avec leur résultat.
Est-ce idiot ?

sinuspax · 20-09-2008 08:39:24

On pourrait avoir un processeur à plusieurs vitesses. Enfin bon ...
En attendant, pourquoi s'embarrasser de retenues ? Cela fait du stockage, surtout quand la base augmente.

Soit l'opération (+) :

3721
+ 2995

Il suffit d'additionner tel quel en superposant et en décalant de droite à gauche. Si n => 10 on intègre le chiffre qui suit :

6
11
16
5

Ensuite on pose : 5 + 1 / 6 + 1 / 1 / 6 = 6716. Pas de stockage, seulement des opérations simples.

Soit la multiplication :

476
x 35

On multiplie tel quel :

30
35
20

2380

18
21
12

1428

2380
+14280

0
16
5
6
1

16660

On peut effacer les chaînes intermédiaires au fur et à mesure.

yoshi · 20-09-2008 12:23:51

Bonjour,

Ta proposition d'absence de retenue dans la multiplication est connue depuis assez longtemps sous le non de "multiplication arabe". Soit à multiplier 732 par 435 (en base 10) :

x | 4 | 3 | 5 |
---|-------|--------|-------|---------
| \ 8 | \ 6 | \ 0 | \
2 | \ | \ | \ | \
| 0 \ | 0 \ | 1 \ | 0 \
---|-------\-------\--------|-----
| \ 2| \ 9 | \ 5 |\
3 | \ | \ | \ | \
| 1 \ | 0 \ | 1 \ | 2 \
---|------\|-------\-------|-------
| \ 8 | \ 1 |\ 5 | \
7 | \ | \ | \ | \
| 2 \ | 2 \ | 3 \ | 4 \
---|------\------\-------- |--------
= | 3 |\ 1 \| 8 | \

Additions (avec retenues en diagonales)
Résultat : 318420

sinuspax · 20-09-2008 14:30:06

Merci pour l'info (on n'invente que ce qui existe).
Pour la soustraction, c'est un tout petit peu moins simple, mais simple aussi.

3721
- 2995

Si a > b, on fait comme pour l'addition (si n => 10 on intègre le chiffre suivant). Si a > b, pas de problème.

2x10 - (5-1) = 16
2x10 - (9-2) = 13
2x10 - (9-7) = 18
3 - 2 = 1

16
13
18
1

1-1 = 0
8-1 = 7
3-1 = 2
6-0 = 6

726

Est-ce arabe ou chinois ?

Amicalement

yoshi · 21-09-2008 19:47:56

Bonsoir,

Ca s'appellera "Méthode sinus pax"... ;-)

Bon, j'ai écrit ma multiplication en base seize via le langage Python, en faisant appel auxtables de X et de + en base seize : aucun appel à la base dix ou la base deux...
Pour l'instant, c'est assez mal écrit, et ça fonctionne tant que dans la somme des produits partiels (technique classique) je n'ai pas de retenue à deux chiffres, ce qui laisse une marge...

Je vais maintenant me pencher sur le gain de temps et l'optimisation du code...

Intéressé ?

@+

sinuspax · 22-09-2008 13:07:38

Intéressé ? Et comment !! (préviens-moi quand ça tournera).

@+

Dernière modification par sinuspax (22-09-2008 13:10:14)

yoshi · 22-09-2008 14:17:23

Bonjour,

Pas de problème, ça tourne proprement...
J'ai ajouté une petite interface avec vérification de la validité des entrées.
On entre multiplicande (1er nombre) et multiplicateur (2e nombre)...
J'ai commenté mon programme pour faciliter sa compréhension.
J'ai testé une multiplication 8 chiffres x 8 chiffres : le résultat vérifié à la calculette windows est bon.
Le programme doit être sans faille, pour autant que dans la somme des produits partiels on n'ait pas une retenue à 2 chiffres...

Ce programme fonctionne via le langage de programmation libre et gratuit : Python, à installer sur sa machine...
Il ne fonctionne pas en assembleur, en binaire, ou autre, mais tout en "chaînes de caractères".
Il commence par créer les tables d'addition et d'addition dans un format exploitable par la suite...
Puis on rentre les nombres...
Il construit alors les produits partiels en commençant par le plus à gauche, et ajoute le nombre de zéros ad hoc à leur droite.
Je cherche en même temps la longueur maximale de ces produits partiels et j'ajoute à gauche le nombre de zéros, pour régler toutes les longueurs sur le maxi.
Ces produits sont concaténés de gauche à droite dans une seule chaîne.
Pour illustrer mon propos, voilà la chaîne finale dans le cas de l'opération présentée en #29 : 392000126B0002FE3
Avec la chaîne finale donnée en exemple :
longueur maxi : 6
nombre de produits : 3
Je pars du caractère n° 6 (de gauche à droite) et je lui ajoute le 12e et le 18e...
Puis je recule d'un cran, j'ajoute le 5e, le 11e et le 17e et la retenue précédente qui si elle n'existe pas vaut 0 par défaut.
En fait, c'est cette addition qui ma fait le plus transpirer...
Bon, si t'en veux, il te faut te procurer Python et l'installer :
http://www.python.org/download/
et cliquer sur cette ligne : Python 2.5.2 (February 22, 2008)
Cela fait, un icône du nom de : IDLE(Python GUI) est créé sur ton bureau...
Déposer le programme Mult_base16.py dans le dossier C:\Python25.
Là deux options :
- soit double-cliquer sur Mult_Base16.py (via l'explorateur)
- soit double-cliquer sur l'icône IDLE, ouvrir File, Cliquer sur Open, double-cliquer sur Mult_base16.py, puis soit clic Run, puis Run Module, soit F5 direct.
Avec IDLE, tu vois la source sans autre forme de procès...

J'ai donc réinventé la roue, puisque la calculette Windows fait ça aussi très bien, mais elle, elle fait du vrai calcul...

J'attends ton feu vert pour te le faire parvenir (pas lourd 2 ko).

@+

sinuspax · 27-09-2008 19:21:53

Désolé pour le retard (contretemps bien involontaire). Mais c'est OK pour le programme.

@ +

yoshi · 27-09-2008 20:42:16

Re,

C'est parti...
(Il a légèrement grossi depuis : 5,6 ko)

@+

[EDIT]
Je viens de terminer de passer ce programme de multiplication en mode graphique...
Fais-moi signe si tu ne reçois rien... n'attends pas !

Dernière modification par yoshi (28-09-2008 19:24:14)

Forum de mathématiques - Bibm@th.net

#26 17-09-2008 12:24:58

Re : compression du calcul binaire

#27 17-09-2008 12:27:47

Re : compression du calcul binaire

#28 18-09-2008 14:08:13

Re : compression du calcul binaire

#29 18-09-2008 14:15:06

Re : compression du calcul binaire

#30 19-09-2008 09:17:38

Re : compression du calcul binaire

#31 19-09-2008 12:01:57

Re : compression du calcul binaire

#32 19-09-2008 13:30:42

Re : compression du calcul binaire

#33 19-09-2008 18:46:23

Re : compression du calcul binaire

#34 20-09-2008 08:39:24

Re : compression du calcul binaire

#35 20-09-2008 12:23:51

Re : compression du calcul binaire

#36 20-09-2008 14:30:06

Re : compression du calcul binaire

#37 21-09-2008 19:47:56

Re : compression du calcul binaire

#38 22-09-2008 13:07:38

Re : compression du calcul binaire

#39 22-09-2008 14:17:23

Re : compression du calcul binaire

#40 27-09-2008 19:21:53

Re : compression du calcul binaire

#41 27-09-2008 20:42:16

Re : compression du calcul binaire

Pied de page des forums