Algoritmo di divisione rapida per numeri binari

Question

Attualmente sto creando un ALU a 16 bit utilizzando Logisim (vale a dire solo porte logiche) e sono bloccato su un processo di divisione. Attualmente sto semplicemente utilizzando il semplice standard "algoritmo di divisione loop" (come illustrato di seguito):

1. leggere i valori di input;
2. Confrontare i valori di input. Attendere fino al termine del processo di confronto;
3. Se A < B andare al punto 10. Se A ≥ B, andare al passaggio successivo;
4. Sottrarre B da A;
5. Attendere fino al termine del processo di sottrazione;
6. Aggiungi uno a contare;
7. Attendere fino al termine del processo di conteggio;
8. Scrive il valore dal processo di sottrazione all'input;
9. Passare al punto 1;
10. risposta è conteggio restante Un

Questo, tuttavia, richiede un tempo molto lungo per processi con grandi risposte (ripetendo un ciclo di 300 tick 65.000 volte non è divertente). Mi chiedo se ci sono algoritmi simili che sono più veloci (che utilizzano esclusivamente addizione e/o sottrazione e/o moltiplicazione e qualsiasi logica booleana) che potrebbero essere implementati usando porte logiche. Qualsiasi aiuto o idea sarebbe molto apprezzato! Fraser

Answer 1

Utilizzare long-division. In binario, non vi è alcuna moltiplicazione, poiché il quoziente in ogni posizione di bit può essere solo 1 o 0. Quindi può essere implementato come sottrazione condizionale (sottrazione se risultato non negativo) e shift.

Questo è solo uno schema approssimativo, ovviamente.

Answer 2

Un approccio tipico per una divisione 32/16: 16 + 16 sarebbe avere il dividendo memorizzato in una coppia di registri a 16 bit (che vengono aggiornati durante l'operazione) e il divisore nel proprio registro (che non esegue t). Sedici volte, sottraete i 17 bit superiori del dividendo dal divisore; se un prestito risulta, scartare il risultato e spostare il divisore a sinistra di un posto, inserendo uno 0 nell'lsb. Se nessun risultato di prestito, memorizzare il risultato nel divisore mentre lo si sposta a sinistra, ma inserire un 1 nel lsb. Dopo sedici di questi passaggi, i 16 bit inferiori del registro dei dividendi manterranno il quoziente e i 16 bit superiori terranno il resto. Si noti che questa operazione funzionerà solo se il quoziente è rappresentabile in 16 bit. Si noti inoltre che su un processore che implementa la divisione 32/16: 16 + 16 in questo modo, si può convenientemente dividere arbitrariamente numeri grandi con una quantità di 16 bit, poiché i 16 bit superiori del dividendo per ogni passo dovrebbero essere il resto da il passaggio precedente.