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

Question

de Wikipedia. division fourier

Voici une capture d'écran du même: ( vue pleine résolution)

Quelle est la logique derrière cet algorithme?

Je sais qu'il peut être utilisé pour diviser un très grand nombre, mais Comment ça marche exactement?

Answer 1

cela semble être une transformation intelligente de l'algorithme de longue division. Les parties intelligentes semble être qu'ils sont seulement en utilisant l'opération de division pour le premier « digit », a1, et éviter d'avoir à utiliser l'autre a (x) de la même manière en les appliquant dans l'étape suivante en soustrayant leur produit (contre le quotient partiel) du reste provisoire.

Que peut être valablement faite et que cela fonctionne toujours est probablement dû au fait que les « chiffres » (dans ce cas, la base 100,) ne sont pas les chiffres réels et peuvent légitimement supposer des valeurs à la fois supérieures à leur base (c.-à- , plus de 100) et même inférieur à zéro. Ceci permet une plus grande flexibilité dans la synchronisation de l'application de chaque « chiffres » pour le fonctionnement comme, par exemple, de différer l'application des caractères secondaires du diviseur (a (x> 1)) jusqu'à ce que la suite d'un quotient partiel est créé à partir de la la division de l'étape préalable d'un (1), qui à son tour leur permet d'être appliqués en tant que soustraction du produit, plutôt que d'une opération de division.

Answer 2

Il est un algorithme extrêmement intelligent. Je ne peux pas imaginer comment ol » JF a réussi à obtenir HLD depuis relation therecurrence est extrêmement difficile à voir, même si vous kknow il existe. À mon avis, il a formalisé une méthode qu'il utilisait pour faire la division longhand - il doit avoir fait un très grand nombre de calculs à la main dans l'âge avant les calculatrices numériques, et il étant préféré probable exacte sur l'aide d'une règle de diapositives, juste pour être sûr.

Il est vrai que l'on peut vaguement voir les grandes lignes de la méthode dans le début de l'algorithme standard de division longue, mais qui est le seul indice. Vous pouvez chercher longtemps pour cette récidive sans le voir. Il y a tellement de chiffres impliqués - il devient confus 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 écrivez dans le matériel informatique, vous pouvez voir qu'un tableau carré d'unités multiplicatif 8 bits prend deux numéros 32 bits disposés le long de leur fond et les côtés droit et déplace les données et à gauche, sortant sur le bord supérieur de la dans une matrice de réponse de 64 bits. L'unité la plus à gauche supérieure délivre les deux premiers chiffres (8 bits) du produit, en utilisant les chiffres supérieurs des multiplicandes et porter dans du reste de la matrice à sa droite. D'accord? Bien, imaginer le réseau en cours d'exécution en sens inverse pour prendre en entrée le divident 64 bits le long du bord supérieur et un diviseur de 32 bits, par exemple le long du bord de droite du tableau. Ensuite, il sort le quotient 32 bits le long du bord inférieur (un reste doit être généré trop .. oublier aboutIt pour le mo). Maintenant, la plus haute unité de gauche de la matrice prend dans les deux chiffres supérieurs du dividende par le haut du tableau, la partie supérieure chiffre du diviseur du côté droit de la matrice, et émet le top chiffre du quotient vers le bas dans la réseau (et par le bas) et un reste VERS lA DROITE dans le tableau.

Ouf! C'était juste pour la première sortie de chiffres. Il est seulement le début. Le génie de Fourier est de voir comment on peut se nourrir dans l'accumulation des reliquats afin de garder les entrées limitées à seulement trois chiffres (par exemple 8 bits) et le outut à seulement deux chiffres (par exemple 8 bits) pour chaque unité modifié tableau multiplicatif en cours d'exécution dans le sens inverse (que nous pouvons appeler un tableau de division maintenant).

Et bien sûr, c'est la façon dont nous pouvons faire dans la division matériel, aucun microcode nécessaire, dans un ordinateur ALU.

Au moins, je suppose que cette méthode est utilisée lorsque microcode a été évité en faveur de quelques milliards de transistors. Je ne suis pas au courant de l'intérieur des derniers processeurs, mais ils ont des transistors à brûler.