追加による除算の実装方法は？

Question

インタビュー質問です。

加算による除算の実装方法は？それらがすべてintであると仮定してください。

私の考え

1. それは配当よりも大きくなるまで、それ自体に除数を追加します。 各反復は、加算前に合計結果を保持します。
2. 商は最後の加算前の合計結果です。残りの数は、quotient * divisor + reminder == dividendまで1を加算することでカウントできます。

O(e^n)、より良いアイデアですか？ビット操作？

Answer 1

ディジタル演算では、加算/減算に基づく簡単な除算アルゴリズムとして、復元方法と復元方法を指定できます。これらのメソッドの反復回数はO(n)です（nはビット数）。ニュートン・ラフソン（Newton-Raphson）や逆数計算（reciprocal calculation）のように、乗算と反復回数に基づくメソッドはO(log n)です。 nによってmを分割http://en.wikipedia.org/wiki/Division_%28digital%29

Answer 2

を見てみましょう：

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

結果がqある - 商、r - 余り。

x+xはx*2と同じです。

UPD：

一部がr -= xを加えないことを不平を言うことがあります。 まあ我々は減算を使用しないようにアルゴリズムを更新することがあります。

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

結果がqある - 商。

我々は残りを必要とする場合、我々のように進行は（p - 上記からの出力）以下：

int r = 0; 

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

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

    r += x; 
    p += x; 
} 

結果はrある - 余り。

アルゴリズムには明らかに多項式（指数関数的ではない）の実行時間があります。

Answer 3

分割を対数成分に分解し、それらを計算します。