ビットシフトの加減算を使用した対数時間の整数除算

ビットシフト、加算、減算のみを使用して対数時間複雑度で整数除算を実装するように求められました。ビットシフトの加減算を使用した対数時間の整数除算

私は2の威力である除数にどのように対処できるのか分かりますが、時間が対数であるように、どうすれば奇数除数に対処できますか？

それは可能ですか？

EDIT：対数ではないが線形よりも優れた時間複雑さを実現する方法も歓迎されます。

おかげ

2017-09-20 Tylor Durden

一般的なケースでは可能ではありません。除算は、乗算、すなわち、O（M（n））の時間複雑度と同じくらい効率的であり、Schönhage-Strassenに基づく乗算は複雑さO（n log n log log n）を有する。定数は大きいので、このアプローチは通常、数千ビットのオペランドに対してのみ意味があります。あなたの質問は理論的なものですか？もしそうなら、私は[Computer Science Stackexchange]（https://cs.stackexchange.com/）の質問をすることをお勧めします。実用的なアプリケーション（ユースケース）があれば、オペランドはどれくらいの大きさですか？ – njuffa

こんにちは、そのアセンブリの練習。私は以下に示唆された方法が対数時間を持っていると思う。 –

以下の答えに概説されているアプローチは、O（n）の時間複雑さを持っています。 – njuffa

それはちょうど紙の上ではなく、バイナリで長い除算を行うようなものです。分割したものからアキュムレータにビットをシフトして少なくとも除数と同じ大きさにしてから、アキュムレータから除数を減算し、すべてのビットをすべて処理してすべてのシフトw /あなたが減算するたびに1。

15/5 (1111/101) 
dividend accumulator result 
1111  0000  0 - can't subtract, shift 
1110  0001  0 - can't subtract, shift 
1100  0011  0 - can't subtract, shift 
1000  0111  0 - can subtract, set 1 
1000  0010  1 - can't subtract, shift 
0000  0101  10 - can subtract, set 1 
0000  0000  11 - we're done since we shifted 4 times

答えは3（11）です。

配当の最上位ビットがアキュムレータの底にシフトします。結果は、被除数/アキュムレータがシフトされるたびにシフトされます。

これは、被除数のビット数ではなく、被除数の値が時間的に対数です。

出典

2017-09-21 17:19:37

私はそれをアセンブリで実装することができましたが、うまくいくようです。ありがとう！ –

ビットシフトの加減算を使用した対数時間の整数除算

答えて

関連する問題