c - オーバーフローする 2 つの整数を 3 分の 1 を法として乗算する

Question

3 つの整数を指定するとa、を計算する必要がありますが、値が大きすぎるとオーバーフローする可能性があり、間違った結果が得られます。bca,b <= c < INT_MAX(a * b) % ca * b

問題の値にオーバーフローしない型を使用せずに、ビットハックを介してこれを直接計算する方法はありますか?

Answer 1

ここではカラツバのアルゴリズムはあまり必要ありません。オペランドを一度だけ分割するだけで十分です。

簡単にするために、数値が 64 ビットの符号なし整数であるとしましょう。k=2^32 とします。それで

a=a1+k*a2
b=b1+k*b2
(a1+k*a2)*(b1+k*b2) % c = 
   a1*b1 % c + k*a1*b2 % c + k*a2*b1 % c + k*k*a2*b2 % c

a1*b1 % cすぐに計算できるようになりました。残りは と を 32 回または 64 回交互に実行することで計算できます( x <<= 1( x %= cu*v)%c=((u%c)*v)%c から)。の場合、これは表向きはオーバーフローする可能性がありc >= 2^63ます。ただし、この 2 つの操作は文字どおりに実行する必要がないという利点があります。そしてx < c/2、シフトだけが必要です（そしてオーバーフローはありません）、またはx >= c/2そして

2*x % c = 2*x - c = x - (c-x).

(そして再びオーバーフローはありません)。