Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 27-07-2008 09:22:23

sinus pax
Invité

compression du calcul binaire

Bonjour,

Pourquoi coder en binaire tous les nombres décimaux ?  Si on codait seulement les dix premiers chiffres décimaux, on aurait des nombres binaires tout juste un peu plus long que les nombres décimaux.

Ex :

0 = 0
1 = 1
2 = 00
3 = 01
4 = 10
5 = 11
6 = 000
7 = 010
8 = 101
9 = 111

Ainsi, le nombre 543 287 654 se traduirait :

11 10 01 00 101 010 000 11 10

ce qui est quand même un peu plus court que son équivalence binaire.

Autre avantage : les bases supérieures à 10.

#2 27-07-2008 09:49:07

galdinx
Modo gentil
Inscription : 21-06-2006
Messages : 506
Site Web

Re : compression du calcul binaire

Bonjour,

Si on code en binaire, c'est pas pour le plaisir de le faire mais parce que cela a une cause sous-jacente : être lu et utilisé par un ordinateur.

Le problème de ta proposition de codage est que les chiffres sont codé en longueur variables.

Lorsque tu envoies un flux de données a un ordinateur, tous les bits sont mis côte à côte (sans espace possible).


Ainsi lorsque l'ordinateur va recevoir 101, comment saura-t-il déterminer s'il doit lire 101=8 ou 10 1=41 ou 1 01 =13...


Ainsi le nombre que tu proposes pourrait être décodé de pleins de facons.


J'espère que ça répond à ta question. Si besoin, n'hésite pas à redemander


++

Hors ligne

#3 27-07-2008 13:17:24

vbnul
Membre
Inscription : 06-02-2007
Messages : 67

Re : compression du calcul binaire

C'est bien beau de les coder, mais après il faut encore les manipuler.

Essaies un peu de trouver un algo pour additionner 2 nombres avec ton codage ^^

Hors ligne

#4 27-07-2008 23:59:50

sinus pax
Invité

Re : compression du calcul binaire

Merci des réponses. Evidemment, ma méthode est valable moyennant la possibilité d'espacement des données. Question : cet espacement est-il réellement impossible ? Il doit exister un moyen (personne n'y a vraiment réfléchi jusqu'à présent).
Par ailleurs, le système binaire n'utilise pas les formes commençant par "0" (par exemple, "010", "0001"). Si c'était le cas, les nombres binaires seraient diminués de moitié.

#5 28-07-2008 08:10:58

galdinx
Modo gentil
Inscription : 21-06-2006
Messages : 506
Site Web

Re : compression du calcul binaire

Bonjour,

Comme je t'ai dit, un ordinateur ne reçoit que des 0 et des 1 (c'est un phénomène électrique, pas arbitraire ; les processeurs sont fait comme ça, ils reçoivent 2 niveau de tension). Pour mettre un espace, il faudrait pouvoir le coder, AVEC DES 0 et des 1 ; le problème serait le même, avec des entiers de longueur variable il ne pourrait pas faire la différence entre ceux ci.

La remarque de vbnul est aussi très pertinente, il faut pouvoir en faire quelque chose de ces entiers, comment additionner (car on sait pas faire grand chose de plus) des nombres de longueur variable?

Donc, pour ta question l'espacement est effectivement impossible et rassure toi, contrairement à ce que tu penses, il y a à mon avis déjà beaucoup de monde qui y ont réfléchi (même s'ils ont pas publié dans wikipedia).

Pour ce qui est de ta 2ème remarque, pour une machine ayant un processeur cadencé a 32 bits, TOUS les entiers sont codés avec 32 bits (soit 32 caractères 0 ou 1), par conséquent la moitié d'entre eux, commence par 0, le quart par 00 etc...


A te lire


++

Hors ligne

#6 28-07-2008 17:21:03

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

Re : compression du calcul binaire

Bonjour,

je rappel que le "codage" en binaire n'a pas été donné par hasard, mais c'est un simple changement de base 10 en base 2 (de dix caractères 0,1,2,3,4,5,6,7,8,9 à deux caractères 0 et 1).
La manipulations des nombes en base 2 te parait peut-être dificile, mais si la base 10 te parait si simple à manipuler, c'est parce que depuis ta naissance tu ne connais que ça (sauf quand tu dis l'heure et encore...). Mais les calculs en base 2 sont exactement les mêmes qu'en base 10. Et d'ailleurs, la base 10 a été très peu utilisé dans l'Histoire: les egyptiens utilisaent la base 12, les mayas et Aztèque la base 20, les Babyloniens la base 60, ... dont on a de multiples héritages.
(Si quelqu'un  a une explication de pourquoi on a retenu la base 10 qui est loin d'être la plus pratique)


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

#7 28-07-2008 17:53:48

vbnul
Membre
Inscription : 06-02-2007
Messages : 67

Re : compression du calcul binaire

Autre remarque, l'idée de diminuer la longueur de codage à des fins de compression est utilisée dans le codage de Huffman :
http://fr.wikipedia.org/wiki/Codage_de_Huffman

Hors ligne

#8 31-07-2008 16:49:14

sinus pax
Invité

Re : compression du calcul binaire

Merci à galdinx pour ses précisions.
On ne peut scinder une forme binaire, mais on peut considérer la suite de formes :

101
01
000

comme s'il s'agissait de 3 nombres différents (3 flux). Ne peut-on faire comprendre à la machine que leur réunion donne le nombre 836 (101/01/000) ?

#9 31-07-2008 18:13:50

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

Re : compression du calcul binaire

Bonjour,

Au risque de répéter Galdinx, la machine traduit des "impulsions électriques" par des 0 ou des 1. Plus exactement, la machine recoit en continue un courant életriques et tout les miliardièmes de seconde (je dis un nombre au pif et je crois que c'est beaucoup plus) la machine "vérifie": si tension > x (fixé par le créateur de la machine), je note 1, sinon je note 0. En la machine "découpe" tout les 4, 8 ou 16 de manière à traduire chaque groupe par un chiffre (en général hexadécimal).

Ton codage est beaucoup plus court certe, mais le principal problème réside dans le fait que la machine ne peut pas savoir où découper la chaine de 0 et 1. Poser autrement, comment traduit tu en impultion électrique les "/"?

Je vais me répéter mais pour résumer, la machine ne connait que le 0 et le 1. Pas de "/", pas d'espace... et il faut coder avec ça.

Enfin pour reprendre la remarque de vbnul, ton codage est trop difficile à manipuler.

Dernière modification par tibo (31-07-2008 18:31:41)


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

#10 31-07-2008 18:27:53

galdinx
Modo gentil
Inscription : 21-06-2006
Messages : 506
Site Web

Re : compression du calcul binaire

Bonjour,

La base 10 est pratique pour l'homme qui a 10 doigts mais les machines n'ont que 2 niveau.

La base 2 est beaucoup plus adaptée et c'est d'ailleurs pour ca qu'on l'utilise, je ne vois pas ce que tu cherches a montrer sinux mais arrete de te triturer l'esprit avec ca.

En plus tu oublies chaque fois l'argument que des nombres c'est bien joli mais il faut pouvoir les manipuler et les additionner ou les décaler... avec ton système de flux ca n'a encore une fois aucun sens.


Place toi a la place d'une machine qui n'a aucune intelligence et cherche à savoir s'il y a une utilité quelconque à tes questions.


++

Hors ligne

#11 31-07-2008 18:34:13

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

Re : compression du calcul binaire

A qui sont destiné chacun des paragraphes? les deux premiers pour moi, les autres aussi?



Edit@Galdinx : tout est pour sinux

Dernière modification par tibo (31-07-2008 18:34:58)


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

#12 31-07-2008 18:44:35

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

Re : compression du calcul binaire

Donc d'après toi, si l'homme avais eu 11 doigts, il aurait compté en base 11?
De plus, la base 10 n'est arrivé que très tard et a été très peu utilisé (avant sa "mondialisation").

Je sais bien que la base 2 est plus pratique pour la machine (et pour cause, c'est la seule base qu'elle connait). Je montrais juste à sinus pax que le codage binaire n'a pas été choisit au hasard, mais de manière la plus logique et pratique.


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

#13 31-07-2008 19:01:06

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : compression du calcul binaire

Bonjour,

Si je ne me trompe pas un octet = 8 bits = de quoi coder 256 nombres entre 0 et 255 (en principe, parce que les nombres sont signés. J'avais appris dans le temps que le 8 bit était pour le signe, donc un octet --->  -128<= nombre <=127. Peut-être la technologie a-t-elle évolué, Galdinx nous dira ça)
Pour coder le nombre 836, on a besoin de 2 octets soit 16 bits (c'est le plus petit nombre d'octets mobilisable pour les nombres
Là où 836 occupe 2 octets, toi tu occupes 6 octets parce que tu utilise 3 nombres. Et il te faut encore ensuite deux octet pour indiquer à la machine où elle doit réunir tes flux....
Résultat des courses : pour coder le nombre 836, là où il faut 2 malheureux octets, tu en mobilises 8, plus du temps machine pour effectuer ta "réunion". Répété des milliards de fois, ça finit par chiffrer...

En fait quand on code en Assembleur (="langage machine"), on ne code même pas en base deux mais en base seize. Les seize symboles utilisés sont 0,1,2,3,5,6,7,8,9,A,B,C,D,E,F : ce serait trop pénible de coder directement en binaire.
3542 en binaire : 110111010110, en base seize : DD6...

@tibo : il n'y a aucune certitude concernant le pourquoi de la base dix... Il est généralement admis que c'est parce qu'on a dix doigts sur une main. En fait dans tout système de numération, il y a deux choses à considérer : la base bien sûr, mais aussi la méthode d'écriture des nombres. Les Romains étaient en base dix, mais n'utilisaient pas la numération de position : va donc additionner LVIII et XXXIX.... D'où l'utilisation des abaques ! Et la survivance du mot calcul chez nous. Calcul : du latin calculus, petit caillou. D'où ma conscience professionnelle d'ex prof de maths poussée à l'extrême : j'ai été aux prises en janvier/février avec des calculs l'un rénal et l'autre biliaire :-) .


@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#14 02-08-2008 08:12:50

sinus pax
Invité

Re : compression du calcul binaire

Galdinx, il y a toujours une utilité à se poser des questions, même idiotes (apparemment). Ce qui est un non-sens, pour moi, est de ne jamais s'en poser, autrement dit de tout accepter sans broncher, comme si les choses avaient toujours été comme ça depuis l'aube des temps.
Je suis parfaitement réceptif à vos différents messages, tous plein de bon sens. Mais je reste persuadé qu'il existe quelque part un moyen plus rapide de compter en langage machine. Il y a toujours un moyen de faire autrement quelque chose. Le tout est de croire que c'est possible.

Amicalement

#15 31-08-2008 14:38:44

sinuspax
Membre
Inscription : 19-08-2008
Messages : 47

Re : compression du calcul binaire

Bonjour,

Peut-on me dire comment je fais pour additionner en binaire : 17 + 19 :

10001 + 10011

Merci.

Sinus

Hors ligne

#16 31-08-2008 14:52:11

galdinx
Modo gentil
Inscription : 21-06-2006
Messages : 506
Site Web

Re : compression du calcul binaire

Salut,


Tout dépend sur combien de bits tes entiers sont codés.

Supposons qu'ils soient codés sur 32 bit comme la plupart des processeurs actuels.


retenus :                                        1    11   
17 : 00000000000000000000000000010001
+
19 : 00000000000000000000000000010011
-----------------------------------------------------
       00000000000000000000000000100100 : 36


Rq : tant que les entiers sont codés sur 6 bits ou plus, ca marche.


S'ils sont codés sur moins, 5 par exemple, tu peux pas les ajouter il y a "overflow" ou dépassement de capacité.


Si tu n'as pas compris, fais signe.


++

Hors ligne

#17 31-08-2008 16:15:50

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : compression du calcul binaire

Bonjour,

Juste une petite précision.
S'il s'agit d'un calcul mathématique absolu, sans rapport avec l'informatique, c'est toujours possible.

Il suffit d'utiliser une table d'addition en base deux (ou de faire le calcul mental)
+  | 0   |  1  |
---|-----|-----|
0  | 0   |  1   | puis faire comme d'hab' en reportant la retenue...
---|-- --|-----|
1  |  1  | 10  |

Le cas évoqué par Galdinx est celui d'une somme de 2 entiers effectuée par un processeur...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#18 01-09-2008 09:42:37

sinuspax
Membre
Inscription : 19-08-2008
Messages : 47

Re : compression du calcul binaire

Re,

Merci à tous deux. Je pensais que l'ordi faisait autrement qu'utiliser le système des retenues.
Cela représente quoi environ comme nombre d'opérations ou de capacité ? Par exemple, pour l'opération 17 + 19 ?

Hors ligne

#19 01-09-2008 09:49:41

galdinx
Modo gentil
Inscription : 21-06-2006
Messages : 506
Site Web

Re : compression du calcul binaire

Bonjour,

A l'intérieur d'un processeur, sauf erreur de ma part, les retenus sont gérées par des registres à décalages.

Un processeur contient plusieurs "unités de calcul" comme un additionneur fait a base de porte ET OU et XOR.

Il recoit les entiers et les additionne ; selon la technologie du processeur (bien que cette opération soit bien élémentaire et optimisée) cela peut utiliser plus ou moins de portes.

Pour ce qui est du nombre d'opérations, pour moi l'addition est UNE seule opération élémentaire ; subdiviser n'aurait pas grand sens...


++

Hors ligne

#20 02-09-2008 01:47:33

Barbichu
Membre actif
Inscription : 15-12-2007
Messages : 405

Re : compression du calcul binaire

Brèves salutations,
En terme de théorie de la complexité, en étudiant le calcul de l'addition par une machine de turing, l'addition de n et de m se fait en fait en temps max(log(n), log(m)).
Après le calcul de l'addition sur une machine concrète (un ordinateur quoi) n'est pas un calcul d'addition dans les entiers mais dans Z/32Z et se fait alors en temps constant (qu'on peut poser comme unité)
++


Barbichu

Hors ligne

#21 03-09-2008 16:54:34

sinuspax
Membre
Inscription : 19-08-2008
Messages : 47

Re : compression du calcul binaire

Bien reçu. Peut-on, à défaut d'agir directement sur le processus du calcul binaire, agir via le calcul en décimal (ou toute autre base) dans le but d'accélérer le calcul final ?
Par exemple, poser (3 x 10^2 + 6 x 10 + 5) x (4 x 10 + 7) (au lieu de 365 x 47) est-il plus efficace pour la machine ?

Hors ligne

#22 05-09-2008 21:32:44

Barbichu
Membre actif
Inscription : 15-12-2007
Messages : 405

Re : compression du calcul binaire

Salut,
en terme d'ordre de grandeur, ça ne change rien (à une constante multiplicative près)
++


Barbichu

Hors ligne

#23 16-09-2008 14:27:21

sinuspax
Membre
Inscription : 19-08-2008
Messages : 47

Re : compression du calcul binaire

Bonjour,

Soit l'addition 00010001 + 00010010 (17 + 18) en base 16. Dans ce cas, on ne peut additionner les termes bit par bit, car nous serions en base 2. Il faut additionner les sections 0001 et 0010 puis 0001 et 0001. L'opération doit se faire en deux temps, comme en base 10. Pour cela, nous devons mémoriser des tables d'addition et de multiplication en base 16.
Est-ce possible ? Si ce n'est pas possible, on ne peut parler de base 16, mais seulement de base 2.

Hors ligne

#24 16-09-2008 15:30:21

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : compression du calcul binaire

Bonjour,

sinuspax a écrit :

Soit l'addition 00010001 + 00010010 (17 + 18) en base 16

Pour mémoire en base seize, 17 --> 11 et 18 --> 12.
Les adressages, via le "langage machine", se font bien en base seize par commodité pour le programmeur, mais la machine, elle, reconvertit le tout en base deux, aucun calcul n'est fait en base seize.
Donc, pour répondre à ta question, non ce n'est pas possible : le processeur ne fait que "ouvrir et fermer des portes", point ! Donc, lui ne stocke pas de tables de base seize.
Si on utilisait un langage de programmation, qu'on stocke en mémoire lesdites bases, et qu'on réécrive les opérations pour shunter tout calcul via le processeur, alors on pourrait calculer en base seize.
Je l'avais fait, en base dix, pour calculer [tex]\frac{1+\sqrt 5}{2}[/tex] avec 100 décimales sur un Amstrad CPC 6128 : il faudrait réadapter la méthode...
MAIS, ce sera incommensurablement plus long, que de passer par le processeur via la base deux.

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#25 17-09-2008 08:54:04

sinuspax
Membre
Inscription : 19-08-2008
Messages : 47

Re : compression du calcul binaire

Re,

Qu'est-ce qui serait incommensurablement plus long ? La programmation du processeur d'accord, mais pas le calcul lui-même, qui serait bien plus rapide en base 16 qu'en base 2 (une fois les tables programmées). Si tu l'as fait pour la base 10, on peut le faire pour la base 16, et même pour des bases beaucoup plus grandes (256 par ex).

Hors ligne

Pied de page des forums