Conversion d'un nombre en bits dans un algorithme

Al-Kashi

Chers informaticiens

Dans le cadre de mes recherches, je sèche sur une une question d'informatique théorique, domaine dont je n'ai que de très maigres bagages. On considère l'algorithme très simple où un utilisateur entre deux valeurs entières $p$ et $q$ et on renvoie le résultat $p+q$, le tout dans notre base $10$ habituelle. Bien évidemment, je sais convertir un nombre en base $2$, mais la question qui m'empêche d'avancer dans mes comparaisons de complexités est la suivante :

Que se passe-t-il réellement au niveau de la machine pour que notre entrée, $p$ par exemple, soit interprétée en bits?

Merci d'avance pour votre contribution,
Al-Kashi

philou22

Tu veux savoir s’il est plus complexe d’additionner des nombres écrits en base 2 ou en base 10 ? Cela dépend du contexte. Pour un humain davantage d’opérations élémentaires seront nécessaires en base 2 ce qui rend le calcul plus coûteux, mais pour un automate électronique c’est plus simple en base 2 même avec davantage d’opérations élémentaires. Il est plus simple pour l’humain de conclure 2+3=5 en s’appuyant sur sa mémoire élémentaire de somme d’entiers inférieure à 9 que de produire l’écriture 010+011=101 alors que c’est l’inverse pour un circuit électronique dont la mémoire élémentaire ne contient que 0+0=0, 1+0=0+1=1 et 1+1=0 mais dont l’articulation logique est plus simple que celle de l’humain qui additionne en base 10.

gerard0

Bonjour Al-kashi. 
Les deux chaînes de caractères qui sont tapées au clavier sont simplement transformées en deux nombres codés en binaire ou en binaire codé décimal (BCD) puis l'algorithme d'addition est effectué et une chaîne de caractères est produite. En binaire, c'est la dernière étape qui est la plus coûteuse. Diviser par 10 est plus compliqué que multiplier par 10. 

Cordialement. 

Al-Kashi

Bonjour
Merci pour vos retours. C'est justement cette transformation dont parle Gérard0 que je voudrais comprendre. Pour transformer notre entrée en binaire,quelles sont les étapes successives que la machine exécute pour arriver à des bits occupés par un courant ouvert ou fermé ?
Al-Kashi

gerard0

Je peux te décrire la partie informatique, pour la réalisation électronique (des bits occupés par un courant ouvert ou fermé), vois avec un forum de physique.

Je suppose même qu'on a un langage de haut niveau (ou qu'on sait programmer en assembleur du microprocesseur concerné - je l'ai eu fait, mais ça dépend trop du micro-processeur). Donc en fait, le langage considère la chaîne de caractères, par exemple "5426" qui a été tapée, la lit à l'envers, traduit 5 en binaire (101), multiplie par 10 (1010) - ce qui se fait par des décalages et additions de registres - additionne 4, multiplie par 10, additionne 2, multiplie par 10 additionne 6; et place cet élément dans une mémoire de taille convenable. Même chose pour le deuxième nombre.

Difficile d'aller plus loin, le travail effectif étant très dépendant de la façon dont le langage a été programmé. C'est pour cela que la durée réelle du calcul dépend fortement du langage et de l'ordinateur. Et qu'en analyse de complexité on oublie cette partie pour ne retenir que les opérations élémentaires (éventuellement tenant compte de la taille des données) et même souvent seulement des multiplications, divisions et opérations plus complexes.

Je ne connais plus les parutions récentes, mais naguère on trouvait des ouvrages de type "programmer en assembleur", ou "le binaire pour les nuls" où tu trouverais des renseignements détaillés. Pour aller plus loin, il faut étudier l'architecture des micro-processeurs qui réalisent la partie électronique du processus (additions, décalages, mise en mémoire ou récupération en mémoire,...). Dans une librairie scientifique d'occasions, on doit pouvoir trouver encore ce genre d'ouvrages, en particulier sur le Z80, très utilisé aux temps des pionniers de la micro-informatique.

Cordialement.

PetitLutinMalicieux

Bonjour

Pour transformer notre entrée en binaire, quelles sont les étapes successives que la machine exécute pour arriver à des bits occupés par un courant ouvert ou fermé ?

Les mêmes que toi.

Après, il n'y a pas un seul additionneur; il y en a plusieurs sortes. Si tu veux un rapide, il te coûtera plus cher en composants électroniques. Si tu veux un moins cher, tu auras besoin de plus de temps. La propagation de la retenue est une vraie question. Voici une page d'exemples.

Quel est ton sujet ? L'addition ? Ou l'entrée/sortie ? Car, dans ta question initiale, il me semble qu'il y a confusion. La complexité de l'addition se moque de l'entrée/sortie; et la complexité de l'entrée/sortie se moque de l'addition.

lourrran

Dans un processus standard,
1) le programme va 'recevoir' un input lisible par un humain ( le nombre 5426 )
1bis) Il va convertir ce nombre en un format interne (binaire très souvent, je pense que le décimal codé binaire est en voie de disparition)
2) Il va faire les calculs qu'on lui demande, souvent beaucoup de calculs, tout ça dans son format interne, le binaire ou le DCB
3) Il va retranscrire les résultats en format lisible par l'humain.

La partie coûteuse, c'est celle qui est exécutée plein de fois, c'est l'étape 2.
Les étapes 1bis et 3 sont tellement marginales que maintenant, on voit énormément de fichiers Json : la puissance de calcul est telle qu'on accepte de gaspiller énormément pour ces étapes 1bis et 3

Il y a 40 ans, on se restraignait beaucoup sur les calculs, l'étape 2 était moins lourde, les 3 étapes 1bis, 2 et 3 étaient significatives. D'où l'utilisation du DCB, plus facile à convertir vers le décimal.
Si on travaille avec des nombres réels (pas uniquement des entiers), le DCB a aussi l'avantage que les nombre décimaux se traitent sans problème, alors que ce n'est pas le cas en binaire. 
Mais c'est totalement marginal.

Pour la conversion de 5426 en DCB, je corrigerais :
Il traduit 5 en binaire :  0000 0101
Il multiplie par 10 :  0101 0000  : une multiplication par 10 se traduit par un décalage de 4 bits.
Il additionne 4 
etc

Il y a 40 ou 50 ans, ta question avait un intérêt, tu aurais pu obtenir une réponse.

gerard0

Lourrran,

Je ne préjugeais rien sur le format. Et 50 ne donne pas 0101 0000 (80 en décimal) :  "une multiplication par 10 se traduit par un décalage de 4 bits" tu as confondu 10 en hexa avec 10 en décimal; 10_d = A_h = 0000 1 0 1_b$.

Cordialement.

Al-Kashi

Bonjour

Merci de nouveau pour vos retours. Je pense que @PetitLutinMalicieux a raison, j'ai eu une confusion. C'est en lisant le dossier calcul de l'APMEP n°445 en pièce jointe que j'ai pu commencer à comprendre la méthodologie utilisée et en particulier celle des coûts bilinéaires qui semblent être celle qui traduit le mieux la réalité calculatoire.

Bonne journée,
Al-Kashi