Jak zaimplementować podział przez dodanie?

Question

Pytanie dotyczące wywiadu.

Jak wprowadzić podział przez dodanie? załóżmy, że wszystkie są int.

Mój pomysł

1. Dodaj dzielnik do siebie, dopóki nie jest większa niż dywidendy. Każda iteracja, zachowaj wynik sumy przed dodaniem.
2. Iloraz jest sumą wyniku przed ostatnim dodaniem. pozostała część może być policzona przez dodanie 1 do quotient * divisor + reminder == dividend.

Czy są jakieś lepsze pomysły na O(e^n)? operacja bitowa?

Answer 1

W arytmetyce cyfrowej możemy nazwać metody przywracania i nieodzyskiwania jako proste algorytmy dzielenia, które są oparte na dodawaniu/odejmowaniu. Liczba iteracji w tych metodach to O(n) (gdzie n to liczba bitów). Istnieją metody takie jak Newton-Raphson lub wzajemne obliczenia, które są oparte na mnożeniu, a liczba iteracji w nich wynosi O(log n). Przyjrzeć http://en.wikipedia.org/wiki/Division_%28digital%29

Answer 2

podzielenie m przez 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; 
} 

W rezultacie q - iloraz r - resztę.

Chodzi o to, że x+x jest taki sam jak x*2.

UPD:

Niektórzy mogą narzekać, że r -= x nie jest dodatkiem. Cóż możemy zaktualizować algorytmu nie używać odejmowanie:

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

Rezultatem jest q - iloraz.

Jeśli trzeba pozostałą następnie postępować w następujący sposób (p - wyjście z powyższych):

int r = 0; 

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

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

    r += x; 
    p += x; 
} 

W rezultacie r - reszta.

Algorytm ma oczywiście przebieg wielomianowy (nie wykładniczy).

Answer 3

Przerwałbyś podział na jego składniki logarytmiczne, a następnie obliczał je.