Quelle est la logique derrière l'algorithme de la division de Fourier?

Question

de Wikipedia: fourier division.

Voici une capture d'écran du même: (view in full-resolution)

Quelle est la logique derrière cet algorithme?

Je sais qu'il peut être utilisé pour diviser de très grands nombres, mais comment cela fonctionne-t-il exactement?

Answer 1

Cela semble être une transformation intelligente de l'algorithme Long Division. Les parties intelligentes semblent être qu'elles n'utilisent que l'opération de division pour le premier "chiffre", a1, et évitent d'utiliser les autres a (x) de la même manière en les appliquant à l'étape suivante en soustrayant leur produit (par rapport au quotient partiel) du reste provisoire. Cela peut être fait et cela fonctionne probablement probablement parce que les "chiffres" (base 100, dans ce cas) ne sont pas des chiffres réels et peuvent légitimement supposer des valeurs supérieures à leur base (c'est-à-dire plus de 100) et même moins que zéro. Ceci permet une plus grande flexibilité dans le timing de l'application de chaque "chiffre" à l'opération comme, par exemple, le report de l'application des chiffres secondaires du diviseur (a (x> 1)) jusqu'à ce qu'un quotient partiel soit créé à partir du la division de l'étape précédente par un (1), qui à son tour leur permet d'être appliquées comme une soustraction de produit, plutôt qu'une opération de division.

Answer 2

C'est un algorithme extrêmement intelligent. Je ne peux pas imaginer comment JF a réussi à en obtenir parce que la relation de récurrence est extrêmement difficile à voir même quand vous savez qu'il existe. À mon avis, il a formalisé une méthode qu'il utilisait pour faire la division à la main - il a dû faire un grand nombre de calculs à la main avant les calculatrices numériques, et il préférait probablement être plus précis en utilisant une règle à calcul, pour être sûr.

Il est vrai qu'on peut vaguement voir le contour de la méthode au début de l'algorithme standard de division longue, mais c'est le seul indice. Vous pourriez chercher longtemps et dur pour cette récurrence sans le voir. Il y a tellement de nombres impliqués - cela devient confus en regardant les relations.

Il y a une autre intuition à tirer de l'étude du flux de données dans l'algorithme de multiplication standard. Si vous l'écrivez dans du matériel informatique, vous pouvez voir qu'un tableau carré d'unités multiplicatives de 8 bits prend deux nombres de 32 bits disposés le long de leurs côtés inférieur et droit et déplace les données vers le haut et à gauche, en sortant sur le bord supérieur du tableau dans une réponse 64 bits. L'unité la plus à l'extrême gauche délivre les deux premiers chiffres (8 bits) du produit, en utilisant les chiffres supérieurs des multiplicandes et en provenance du reste du tableau à sa droite. D'accord? Eh bien, imaginez que le tableau fonctionne en sens inverse pour prendre en entrée le diviseur de 64 bits le long du bord supérieur et un diviseur de 32 bits, disons le long du bord droit du tableau. Ensuite, il génère le quotient de 32 bits le long du bord inférieur (un reste doit être généré aussi .. oublier pour le mo). Maintenant, l'unité la plus en haut à gauche dans le tableau prend les deux premiers chiffres du dividende du haut du tableau, le chiffre supérieur du diviseur du côté droit du tableau, et émet le chiffre supérieur du quotient DOWNWARDS dans le array (et en bas) et un reste à DROITE dans le tableau.

Ouf! C'était juste pour la sortie du premier chiffre. Ce n'est que le début. Le génie de Fourier était de voir comment on pouvait alimenter les restes accumulés afin de limiter les entrées à trois chiffres (disons 8 bits), et la sortie à seulement deux chiffres (disons 8 bits) pour chaque unité de la modification. tableau multiplicatif fonctionnant en sens inverse (que nous pouvons appeler un tableau de division maintenant).

Et bien sûr, c'est ainsi que nous pouvons faire la division du matériel, pas de microcode requis, dans un ALU d'ordinateur. Au moins, je présume que cette méthode est utilisée lorsque le microcode a été évité en faveur de quelques milliards de transistors de plus. Je ne suis pas au courant de l'intérieur des derniers processeurs, mais ils ont des transistors à graver.