Come implementare la divisione per aggiunta?

Question

Una domanda di intervista.

Come implementare la divisione per aggiunta? supponiamo che siano tutti int.

La mia idea

1. Aggiungi divisore a se stessa fino a quando non è più grande di dividendo. Ogni iterazione, mantiene il risultato della somma prima dell'aggiunta.
2. Il quoziente è il risultato della somma prima dell'ultima aggiunta. il resto può essere contato aggiungendo 1 fino allo quotient * divisor + reminder == dividend.

È O(e^n), qualche idea migliore? operazione bit?

Answer 1

Nell'aritmetica digitale è possibile denominare metodi di ripristino e non ripristino come semplici algoritmi di divisione basati su addizione/sottrazione. Il numero di iterazioni in questi metodi è O(n) (dove n è il numero di bit). Ci sono metodi come Newton-Raphson o calcolo reciproco che si basano sulla moltiplicazione e il numero di iterazioni in essi sono di O(log n). Date un'occhiata a http://en.wikipedia.org/wiki/Division_%28digital%29

Answer 2

dividendo m da n:

int r = m; 
int q = 0; 

while(r >= n) 
{ 
    int k = 1; 
    int x = n; 
    int t; 

    while((t = x+x) < r) 
    { 
     x = t; 
     k += k; 
    } 

    q += k; 
    r -= x; 
} 

Il risultato è q - quoziente, r - resto.

L'idea è che x+x è lo stesso di x*2.

UPD:

Alcuni possono lamentano che r -= x non è aggiunta. Beh potremmo aggiornare l'algoritmo di non usare la sottrazione:

int p = 0; 
int q = 0; 

while(p+n <= m) 
{ 
    int k = 1; 
    int x = n; 
    int t; 

    while(p + (t = x+x) < m) 
    { 
     x = t; 
     k += k; 
    } 

    q += k; 
    p += x; 
} 

Il risultato è q - quoziente.

Se dobbiamo il resto poi si procede come segue (p - uscita dal sopra):

int r = 0; 

while(p < m) 
{ 
    int x = 1; 
    int t; 

    while(p + (t = x+x) < m) 
    { 
     x = t; 
    } 

    r += x; 
    p += x; 
} 

Il risultato è r - resto.

L'algoritmo ha ovviamente un tempo di esecuzione polinomiale (non esponenziale).

Answer 3

Si interromperà la divisione nei suoi componenti logaritmici e quindi li calcolerà.