Qual è la logica dietro l'algoritmo di divisione di Fourier?

Question

da Wikipedia: fourier division.

Ecco uno screenshot della stessa: (view in full-resolution)

Qual è la logica alla base di questo algoritmo?

So che può essere utilizzato per dividere numeri molto grandi, ma come funziona esattamente?

Answer 1

questa sembra essere una trasformazione intelligente dell'algoritmo di divisione lunga. Le parti intelligenti sembrano essere che usano solo l'operazione di divisione per la prima "cifra", a1, ed evitano di dover usare l'altra a (x) nello stesso modo applicandole nella fase successiva sottraendo loro prodotto (contro il quoziente parziale) dal resto provvisorio.

Che questo possa essere fatto validamente e che funzioni sempre è probabilmente dovuto al fatto che le "cifre" (base 100, in questo caso) non sono cifre reali e possono legittimamente assumere valori sia superiori alla loro base (vale a dire, oltre 100) e anche meno di zero. Ciò consente una maggiore flessibilità nei tempi dell'applicazione di ciascuna "cifra" all'operazione, ad esempio rimandando l'applicazione delle cifre secondarie del divisore (a (x> 1)) fino a dopo la creazione di un quoziente parziale dal divisione del passo precedente con un (1), che a sua volta consente loro di essere applicati come sottrazione del prodotto, piuttosto che un'operazione di divisione.

Answer 2

È un algoritmo estremamente intelligente. Non riesco a immaginare come il vecchio JF sia riuscito a farne a meno, dal momento che la relazione di thereseventence è estremamente difficile da vedere anche quando sai che esiste. A mio parere, ha formalizzato un metodo che stava usando per eseguire una divisione a mano - doveva aver fatto un numero enorme di calcoli a mano nell'era precedente ai calcolatori digitali, e probabilmente avrebbe preferito essere esatto usando una regola di diapositive, solo per essere sicuro.

È vero che si può vedere vagamente il profilo del metodo all'inizio dell'algoritmo di divisione lunga standard, ma questo è l'unico indizio. Potresti cercare a lungo e duramente per questa ricorrenza senza vederla. Ci sono così tanti numeri coinvolti - diventa confuso guardando le relazioni.

C'è un'altra intuizione da acquisire studiando il flusso di dati nell'algoritmo di moltiplicazione standard. Se lo scrivi nell'hardware del computer, puoi vedere che una matrice quadrata di unità moltiplicative a 8 bit prende due numeri a 32 bit disposti lungo i loro lati inferiore e destro e sposta i dati verso l'alto e verso sinistra, uscendo dal bordo superiore del array in una risposta a 64 bit. L'unità più in alto a sinistra fornisce le prime due cifre (8 bit) del prodotto, utilizzando le cifre più alte dei moltiplicativi e portati dal resto dell'array alla sua destra. ok? Bene, immagina la matrice che gira al contrario per prendere come input il divisore a 64 bit lungo il bordo superiore e un divisore a 32 bit, ad esempio lungo il bordo destro dell'array. Quindi emette il quoziente a 32 bit lungo il bordo inferiore (deve essere generato anche un resto .. dimenticatene per il mo). Ora l'unità in alto a sinistra nell'array prende IN le prime due cifre del dividendo dalla cima dell'array, la prima cifra del divisore dal lato destro dell'array, ed emette la prima cifra del quoziente DOWNWARD nel array (e fuori dal fondo) e un resto RIGHTWARD nell'array.

Whew! Era solo per la prima uscita di cifre. È solo l'inizio. Il genio di Fourier era nel vedere come si può nutrire i resti accumulati per mantenere gli input limitati a solo tre cifre (ad esempio a 8 bit), e l'outut a due cifre (ad esempio a 8 bit) per ogni unità nella modifica array moltiplicativo in esecuzione al contrario (che ora possiamo chiamare array di divisione).

E naturalmente, è così che possiamo eseguire la divisione in hardware, nessun microcodice richiesto, in un ALU computer.

Almeno, presumo che questo metodo venga utilizzato dove il microcodice è stato evitato a favore di qualche miliardo di transistor. Non sono al corrente delle ultime CPU, ma hanno dei transistor da masterizzare.