¿Cómo implementar división por adición?

Question

Una pregunta de entrevista.

¿Cómo implementar la división por adición? supongamos que todos son int.

Mi idea

1. Añadir divisor a sí mismo hasta que es más grande que los dividendos. Cada iteración, mantenga el resultado de la suma antes de la suma.
2. El cociente es el resultado de la suma antes de la última adición. el resto se puede contar agregando 1 hasta el quotient * divisor + reminder == dividend.

Es O(e^n), alguna idea? operación de bit?

Answer 1

En aritmética digital podemos nombrar los métodos de restauración y no restauración como simples algoritmos de división que se basan en sumas/restas. El número de iteraciones en estos métodos es de O(n) (donde n es el número de bits). Hay métodos como Newton-Raphson o cálculo recíproco que se basan en la multiplicación y el número de iteraciones en ellos son de O(log n). Echar un vistazo a http://en.wikipedia.org/wiki/Division_%28digital%29

Answer 2

dividiendo m por 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; 
} 

El resultado es q - cociente, r - resto.

La idea es que x+x es lo mismo que x*2.

UPD:

Algunos se quejan de que no es r -= x adición. Bien podemos actualizar el algoritmo de no usar la resta:

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; 
} 

El resultado es q - cociente.

Si necesitamos el resto continuación procedemos como sigue (p - salida de la anterior):

int r = 0; 

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

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

    r += x; 
    p += x; 
} 

El resultado es r - resto.

El algoritmo tiene obviamente un tiempo de ejecución polinomial (no exponencial).

Answer 3

Rompería la división en sus componentes logarítmicos y luego los calcularía.