[Arithmétique] - [Affichage] - [Addition] - [Soustraction] - [Multiplication] - [Division]

.:: Rubrique Arithmétique >> Division ::.

Comment on divise deux nombres?
J'ai 3 méthodes à vous proposer:

1. La méthode classique (scolaire):
   en gros c'est la méthode qu'on apprend à l'école. Je ne vais pas vous faire un dessin, je suis sur que vous vous rappelez ces formidables heures de maths à faire des divisions...
   - Les avantages: le résultat trouvé est toujours exacte et la taille des nombres qu'on utilise ne dépasse jamais celle du dénominateur.
   - Les inconvénients: c'est lent... très lent... il y a plein de petits calculs différents à effectuer.
2. La méthode bidouillage:
   le but est de faire la somme du dénominateur jusqu'à ce que cette somme soit supérieure ou égale au nominateur. On trouve le résultat en comptant le nombre de fois qu'on à fait cette somme - 1.
   Un petit exemple:
   n=7000 et d=1234, on cherche q=n/d, normalement on devrait trouvé q=5 (on cherche la valeur entière).
   Et c'est parti !
   1. 0+1234 < n
   2. 1234+1234=2468 < n
   3. 2468+1234=3702 < n
   4. 3702+1234=4936 < n
   5. 4936+1234=6170 < n
   6. 6170+1234=7404 > n
   donc on s'arrête et on compte le nombre de fois qu'on à sommé d, ici 6 fois, on retranche 1 et on trouve le bon résultat.
   - Les avantages: le résultat trouvé est toujours exacte et la taille des nombres qu'on utilise ne dépasse jamais celle du nominateur.
   - Les inconvénients: quand l'écart entre le nominateur et le dénominateur et trop grand, le calcul devient très long... trop long.
3. La méthode "de Newton":
   Le but est de remarquer que diviser un nombre par un autre revient à le multiplier par l'inverse de cet autre nombre.
   Oui mais comment on calcule l'inverse d'un nombre? et bien on utilise l'algorithme de Newton pardi! là on se dit qu'il n'est pas mort pour rien.
   Et voici ce que vous attendez tous... rapide et ingénieux... j'ai nommé... l'algorithme de Newton !!!
   c'est en fait une suite récurente de la forme:

   xn+1=2*xn-a*xn²

   avec a qui est le nombre à inverser, quand n tend vers l'infini, xn tend vers 1/a. Et donc une fois qu'on a une approximation correcte de 1/a, il suffit de multiplier 1/a par le nominateur et c'est gagné!
   Mais ya juste un p'tit problème: il faut partir d'une valeur de x0 qui ne soit pas trop éloigné du résultat pour rendre le calcul rapide. On réfléchit...
   a<10a.longueur
   1/a>10-a.longueur
   donc on peut poser x0 = 10-a.longueur.

   - Les avantages: une approximation du résultat est effectuée très rapidement.
   - Les inconvénients: le résultat n'est qu'approximatif.

mais que faire de tout ça ???!!!!

Et bien don't panic!, une bonne méthode est d'utiliser la méthode 3 en la combinant avec la seconde méthode:
Pour une division du type b/a, on cherche d'abord une valeur approchée de 1/a, on la multiplie par b puis on ajuste cette valeur grâce à la méthode 2.

Ce qui devrait donner algorithmiquement pour b/a:

|- * On pose x0 = 10-a.longueur;
|- * On calcule xn jusqu'à ce qu'on trouve une valeur de xn ~ xn-1;
|- * On multiplie xn par b et on sauve cette valeur dans Q (le quotient);
|- * On pose R = Q*a; ce qui sera notre valeur initiale pour la méthode 2 et qui devrait être relativement proche de b.

-------Si R > b------------------------ | -------Sinon---------------------------
|- * On boucle tant que R > b | |- * On boucle tant que R < b
____|- * R reçoit R - a; | ____|- * R reçoit R + a;
____|- * Q reçoit Q - 1; | ____|- * Q reçoit Q + 1;
| |- * Si R != a
| ____|- * Q reçoit Q - 1;

|- * On affiche Q, qui est le résultat, si on veut :-)

On commence donc par calculer une approximation de 1/a par l'algorithme de newton,
Comme nos nombres sont des entiers uniquement, on va calculer 1/a*(X+4) avec X une puissance de 16 car on travaille en hexa et +4 car on va enregistrer le résultat obtenu dans un registre 16 bits. Passons au code:

Instructions x86 | X

    	_ALGO_NEWTON:
    		;on récupère la longueur exacte du nombre
    		;et non la longueur du nombre à +-1 chiffre près
    		xor ax, ax
    		mov si, _NOMBRE2
    		mov al, [ds:si]
    		add si, ax
    		shl ax, 1
    		mov cl, [ds:si]
    		test cl, 0xF0
    		je _IMPAIRE1			;saute si le nombre est paire
    		inc ax
    	_IMPAIRE1:				;récupère la taille exacte de _NOMBRE2 dans ax
    		push ax			;on empile TAILLE_NOMBRE2

    		mov cx, 0x10			;0x10 est ici x0
    	_BOUCLENEWTON:
    		push cx

    		mov al, cl
    		mov bl, al
    		mul bl			;ax=bl² on obitent donc ici xn²
    		mov si, _MEM2			;_MEM2 est les donnés du nombre temporaire (il est définit sur 3 octets
    						;c'est donc un stockage sur 16 bits)
    		mov [ds:si], ax
    	    	push word _NOMBRE3		;[sp-4] => résultat
    	    	push word _NOMBRE2		;[sp-2]
    	    	push word _MEM		;[sp] _MEM est le nombre qui contient les données _MEM2
    	    	call _MULTIPLICATION		;on multiplie xn² par a
    	    	add sp, 6			;pour "supprimer" de la pile les arguments envoyés à _MULTIPLICATION

    		pop cx

    		;recupère dans ax le résultat de la division
    		;et ajuste sa longueur
    		pop bx			;récupère TAILLE_NOMBRE2
    		push bx
    		mov si, _NOMBRE3
    		inc si
    		shr bx, 1			;divise TAILLE_NOMBRE2 par 2
    		jnc _PAIRE1
    		add si, bx
    		mov ax, [ds:si]
    		shr ax, 4
    		jmp _SUITEPAIRE1
    	_PAIRE1:
    		add si, bx
    		mov ax, [ds:si]
    	_SUITEPAIRE1:

    		mov dx, cx			;sauve dans dx la valeur de x(n-1)
    		shl cx, 1			;multiplie cx par 2
    		sub cx, ax			;cx contient ici une approximation de 1/_NOMBRE2
    		mov bx, cx
    		shr bl, 1
    		shr dl, 1
    		cmp bl, dl			;boucle tant que x(n-1) != x(n)
    		jne _BOUCLENEWTON
    	; en sortie cx contient une approximation de 1/_NOMBRE2 et la pile contient TAILLE_NOMBRE2

Voilà maintenant qu'on a une approximation de 1/a il va falloir passer à la phase 2 de l'algo:
"La 2ème méthode" (je ne lui est pas encore trouvé de nom, si vous avez des idées de nom ou bien si cet algorithme en porte déjà un vous pouvez me faire parvenir vos idées par mail, merci d'avance je sais que c'est pas le moment mais y a t'il quelqu'un qui vendrait un narguilé avec 4 embouts et pour moins de 100 euros? idem, repondez moi, ça parait pas mais c'est sérieux.)
Bon, où en étais-je?
ah oui, la 2ème méthode...on va devoir multiplier b par l'approximation de 1/a puis multiplier cette valeur par le "vrai" a et enfin sauver ce nombre. Ce qui se traduit par de l'assembleur à peu près comme ça:

    		;cx contient une approximation de 1/_NOMBRE2 et la pile contient TAILLE_NOMBRE2
    		mov si, _MEM2
    		mov [ds:si], cx

    	    	push word _NOMBRE3	;[sp-4] => résultat
    	    	push word _NOMBRE1	;[sp-2]
    	    	push word _MEM		;[sp]
    	    	call _MULTIPLICATION	;On multiplie b par 1/a et on sauve le résultat dans _NOMBRE3
    	    	add sp, 6

    		pop ax
    		push ax

    		;maitenant il faut ajuster la longueur du resultat car on avait multipilier le nombre
    		;précédent par une puissance de 16 pour se débarasser de la virgule
    		mov si, _NOMBRE3
    		mov cl, [ds:si]
    		inc si
    		mov di, si
    		shr cl, 1
    		shr ax, 1
    		jnc _PAIRE2
    		add si, ax
    	_SUITEDIV1:
    		mov ax, [ds:si]
    		shr ax, 4
    		mov [ds:di], ax
    		add si, 2
    		add di, 2
    		dec cl
    		test cl, cl
    		jne _SUITEDIV1
    		jmp _FINDIV
    	_PAIRE2:
    		add si, ax
    	_SUITEDIV2:
    		mov ax, [ds:si]
    		mov [ds:di], ax
    		add si, 2
    		add di, 2
    		dec cl
    		test cl, cl
    		jne _SUITEDIV2
    	_FINDIV:
    		pop bx
    		xor cx, cx
    		mov si, _NOMBRE3
    		mov di, si
    		mov cl, [ds:si]
    		shr bx, 1
    		sub cl, bl
    	        add di, cx
    	        mov al, [ds:di]
    	        test al, al
    	        jne _SUITEDIV3
    	        dec cl
    	_SUITEDIV3:
    		mov [ds:si], cl
    		;Fiiiooouuuuffffff.... on a terminé d'ajuster la longueur du résultat.
    		;On doit probablement pouvoir trouver une méthode plus rapide mais comme
    		;cette partie de code ne contient qu'une petite boucle elle est très rapidement exécuté.
    		;(2 boucle en fait mais le prog ne passera que par une des 2 suivant la parité d'un nombre)
    		xor cx, cx
    		mov si, _NOMBRE3
    		mov cl, [ds:si]
    		inc si
    		add si, cx		;si contient l'adresse du nombre temporaire
    		;ce nombre temporaire est R
    		;il va être comparé à b pour ajuster la valeur du quotient
    	    	mov di, _NOMBRE1	;initialise le nombre temporaire
    	    	mov cl, [es:di]
    	    	mov di, si
    	    	inc di
    	    	xor ax, ax
    	    	rep stosb

    	    	push si		       	;[sp-4] => résultat
    	    	push word _NOMBRE3      	;[sp-2]
    	    	push word _NOMBRE2     	;[sp]
    	    	call _MULTIPLICATION
    	    	add sp, 6

    	    	mov di, _NOMBRE1	;initialise la longueur du nombre temporaire
    	    	mov cl, [es:di]
    	    	mov [ds:si], cl

C'est pas plus compliqué que ça :-)
Maintenant il ne vous reste plus qu'à faire la boucle pour ajuster la valeur et c'est gagné.
je vais quand même vous aider un peu, je vous ai fait la fonction qui permet de comparer deux nombre (c'est un peu prise de tête , alors merci qui?).
ça c'est cadeau:

    	_CMP:
    		xor cx, cx
    		xor dl, dl
    		mov cl, [ds:di]		;cx contient la taille de NOMBRE1
    		add si, cx
    		add di, cx
    	_BOUCLE_CMP:
    		mov al, [ds:di]		;al contient NOMBRE1
    		mov bl, [ds:si]		;bl contient NOMBRE2
    		dec si
    		dec di
    		test cx, cx
    		je _DI_SUP_SI
    		dec cx
    		cmp al, bl
    		je _BOUCLE_CMP		;reboucle si NOMBRE1 == NOMBRE2

    		cmp al, bl
    		jc _DI_INF_SI			;saute si NOMBRE1 < NOMBRE2

    	_DI_SUP_SI:
    	        jmp _CMP_SUITE		;lorsqu'on reboucle
    	_DI_INF_SI:
    		jmp _FIN_DIVI			;quand le on tient l'bon quotient

Puis on teste le programme final:

C'est bon !!!
YYYYYYYEEEEEEEEEEEAAAAAAAAAAAAAAAAAAHHHHHHHHHHHHHHHHHHHHH !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Et voilà c'est terminé pour la division et pour cette rubrique aussi... une petite larme?
Si vous êtes courageux vous pouvez vous amuser à coder des logarithmes & co pour le plaisir pour ça je vous conseille de jeter un coup d'oeil sur les séries entières.

Bon code et bon hack/crack :-)

Voici les différentes rubriques:

- Instructions des x86.

- Arithmétique.
  - Affichage.
  - Addition.
  - Soustraction.
  - Multiplication.
  - Division.

Daemonium Albus,
blaizard@caramail.com