Pocket a écrit :36 bits divisé par 16 bits.
Comme on connait par avance la taille maximale des deux nombres, on peut donc efficacement utiliser la méthode de la division binaire par dichotomie, et se passant de la première phase, à savoir que l'on a pas nécessairement à déterminer la borne supérieure du diviseur, elle sera quoi qu'il arrive inférieure à 36.
Prenons un exemple : divisons X par Y
#CE4D3A5D6_h divisé par #9672_h
Les deux bornes initiales sont a=0 et b=36
Etape 1.1 : la dichotomie m’incite donc à tester d = (a+b)/2 = 36/2 = 18
Je décale donc Y de 18 bit vers la gauche : on obtient #259C80000_h
Or #259C80000_h est plus petit que #CE4D3A5D6_h donc 18 est un minorant.
Les nouvelles bornes sont donc a= 18 et b = 36.
Etape1.2 : on utilise à nouveau la dichotomie : d = (18+36)/2 = 27.
Je décale donc Y de 27 bit vers la gauche (soit un décalage de 9 bits supplémentaires vers la gauche par rapport à l’étape précédente).
On obtient #4B 390000000_h qui est est plus grand que #CE4D3A5D6_h, (d’ailleurs on dépasse les 36bits soit #FFFFFFFFF_h ) c’est unpoint à surveiller en fonction des capacité de calculs du processeur.
Donc 27 est un majorant strict.
Les nouvelles bornes sont donc a=18 et b = 27
Etape n°1.3 : dichotomie : d = (18+27)/2 = 22, décalage de 22 bits (soit 4 de moins).
On obtient #25 9C800000_h qui est toujours plus grand que X (ou que la limite des 36 bits d’ailleurs).
Donc 22 est un majorant strict, le nouvel intervalle est donc a = 18 et b = 22. Il fait plus d’une unité, je continue donc.
Etape n°1.4 : dichotomie : d = (18 +22)/2 = 20, décalage de 20 bits (soit deux de moins que précèdemment). On obtient cette fois un nombre de 36bits ; #967200000_h que l’on compare avec X = #CE4D3A5D6_h qui est le plus grand. Donc 20 est un minorant. Les bornes sont donc a=20 et b=22.
On continue.
Etape n°1.5 : dichotomie d =(20 + 22)/2 = 21, décalage global de 21 bits, soit un décalage vers la droite de la valeur actuelle. On obtient #1 2CE400000_h qui est plus grand que X (et plus de 36bits). Donc 21 est un majorant strict. L’intervalle est donc réduit à a=20 et b=21.
On arrête donc là cette première phase de dichotomie car l’intervalle est unitaire.
On a donc déterminé le bit de point fort du quotient :
Q = # 0001?????_h
On retire donc Y.2^20 à X :
#CE4D3A5D6_h - #967200000_h = # 37DB3A5D6_h qui devient le nouveau dividende. Le diviseur étant toujours Y = # 9672_h.
Pour cette seconde phase, les bornes de l’intervalle sont a= 0 et b = 20. Et oui, on sait déjà que le nouveau dividende (qui est en fait le reste de la première phase) est inférieur à Y.2^20 !).
Code : Tout sélectionner
Etape Interv d X shifted Y Q
#CE4D3A5D6_h # 9672_h
1.1 0 36 18 18+ #CE4D3A5D6_h #259C80000_h <
1.2 18 36 27 9+ #CE4D3A5D6_h 4B#390000000_h >> overflw
1.3 18 27 22 5- #CE4D3A5D6_h 2#59C800000_h >> overflw
1.4 18 22 20 2- #CE4D3A5D6_h #967200000_h <
1.5 20 22 21 1+ #CE4D3A5D6_h 1#2CE400000_h >> overflw
20 21 20 1- #37DB3A5D6_h #967200000_h #0001?????_h
2.1 0 20 10 10- #37DB3A5D6_h # 259C800_h <
2.2 10 20 15 5+ #37DB3A5D6_h # 4B390000_h <
2.3 15 20 17 2+ #37DB3A5D6_h #12CE40000_h <
2.4 17 20 18 1+ #37DB3A5D6_h #259C80000_h <
2.5 18 20 19 1+ #37DB3A5D6_h #4B3900000_h >
18 19 18 1- #123EBA5D6_h #259C80000_h #00014????_h
3.1 0 18 9 #123EBA5D6_h # 12CE400_h <
3.2 9 18 13 4+ #123EBA5D6_h # 12CE4000_h <
3.3 13 18 15 2+ #123EBA5D6_h # 4B390000_h <
3.4 15 18 16 1+ #123EBA5D6_h # 96720000_h <
3.5 16 18 17 1+ #123EBA5D6_h #12CE40000_h >
16 17 16 1- # 8D79A5D6_h # 96720000_h #00015????_h
4.1 0 16 8 # 8D79A5D6_h # 967200_h <
4.2 8 16 12 4+ # 8D79A5D6_h # 9672000_h <
4.3 12 16 14 2+ # 8D79A5D6_h # 259C8000_h <
4.4 14 16 15 1+ # 8D79A5D6_h # 4B390000_h <
15 16 15 1+ # 4240A5D6_h # 4B390000_h #000158???_h
5.1 0 15 7 # 4240A5D6_h # 4B3900_h <
5.2 7 15 11 4+ # 4240A5D6_h # 4B39000_h <
5.3 11 15 13 2+ # 4240A5D6_h # 12CE4000_h <
5.4 13 15 14 1+ # 4240A5D6_h # 259C8000_h <
14 15 14 # 1CA425D6_h # 259C8000_h #00015C???_h
6.1 0 14 7 7- # 1CA425D6_h # 4B3900_h <
6.2 7 14 10 3+ # 1CA425D6_h # 259C800_h <
6.3 10 14 12 2+ # 1CA425D6_h # 9672000_h <
6.3 12 14 13 1+ # 1CA425D6_h # 12CE4000_h <
13 14 13 # 9D5E5D6_h # 12CE4000_h #00015E???_h
7.1 0 13 7 6- # 9D5E5D6_h # 4B3900_h <
7.2 7 13 10 3+ # 9D5E5D6_h # 259C800_h <
7.3 10 13 11 1+ # 9D5E5D6_h # 4B39000_h <
7.4 11 13 12 1+ # 9D5E5D6_h # 9672000_h <
12 13 12 # 6EC5D6_h # 9672000_h #00015F???_h
8.1 0 12 6 6- # 6EC5D6_h # 259C80_h <
8.2 6 12 9 3+ # 6EC5D6_h # 12CE400_h >
8.3 6 9 7 2- # 6EC5D6_h # 4B3900_h <
8.4 7 9 8 1+ # 6EC5D6_h # 967200_h >
7 8 7 # 238CD6_h # 4B3900_h #00015F08?_h
9.1 0 7 3 4- # 238CD6_h # 4B390_h <
9.2 3 7 5 2+ # 238CD6_h # 12CE40_h <
9.3 5 7 6 1+ # 238CD6_h # 259C80_h >
5 6 # 10BE96_h # 12CE40_h #00015F0A?_h
A.1 0 5 2 4- # 10BE96_h # 12CE4_h <
A.2 2 5 3 1+ # 10BE96_h # 4B390_h <
A.2 3 5 4 1+ # 10BE96_h # 96720_h <
4 5 # 75776_h # 96720_h #00015F0B?_h
B.1 0 4 2 2- # 75776_h # 12CE4_h <
B.2 2 4 3 1+ # 75776_h # 4B390_h <
3 4 # 2A3E6_h # 4B390_h #00015F0B8_h
C.1 0 3 1 2- # 2A3E6_h # 12CE4_h <
C.2 1 3 2 1+ # 2A3E6_h # 259C8_h <
2 3 2 # 4A1E_h # 259C8_h < #00015F0BC_h
D.1 0 2 1 # 4A1E_h # 9672_h >
D.2 0 1 0 # 4A1E_h e.o.d.
Conclusion :
-------------
#CE4D3A5D6_h = #9672_h * #15F0BC_h + #4A1E_h
Soit 55378683350 = 38514 x 1437884 + 18974
Le principe de le recherche du décalage binaire correct est répété jusqu’à obtenir un reste suffisamment petit. A chaque phase, la borne majorée stricte diminue et la borne minoré est remise à zéro pour le cas où le dividende serait un multiple (et qu’il "tomberait" rapidement à zéro).
On note qu’à chaque phase, on détermine le quotient des bits forts vers les bits faibles. Ce qui peut constituer un critère d’arrêt, si l’on ne cherche pas à déterminer le reste, mais que l’on cherche à calculer le quotient avec une certaine "incertitude".
