モジュロ乗算（C言語）

Question

具体的には、2つの符号なし整数（a、b）があり、％UINT_MAX（UINT_MAXは最大符号なし整数として定義されます）を計算します。そうする最善の方法は何ですか？

背景：幾何学的シーケンスをエミュレートするためのモジュールをLinux用に書く必要があります。そこから読み取ると、次の要素（モジュロUINT_MAX）が得られます。私が見つけた唯一の解決策は、添加しながら、次のロジックを使用して行われる：（Iは、演算シーケンスのために使用すること）

for(int i=0; i<b; ++i){ 
    if(UINT_MAX - current_value > difference) { 
    current_value += difference; 
    } else { 
    current_value = difference - (UINT_MAX - current_value); 
    } 

最初の反復における現在の値は、A =（およびすべての反復において更新され、差が（常に=） 。明らかに、これは知的な解決策ではありません。 インテリジェントな人はどのようにこれを達成しますか？

ありがとう！前述したように、使用可能な幅の2倍の種類を持っている場合

Answer 1

、ちょうどintは、32ビットおよび64 long long（またはそれ以上）である

(unsigned int)(((unsigned long long)a * b) % UINT_MAX) 

場合は、ここで、それを使用。より大きなタイプがない場合は、係数をビット幅の半分に分割し、乗算してパーツを減らして最終的に組み立てることができます。 @Toadを前提としていて何が必要なの、実際に削減モジュロUINT_MAX + 1であれば、もちろん

a_low = a & 0xFFFF; // low 16 bits of a 
a_high = a >> 16; // high 16 bits of a, shifted in low half 
b_low = b & 0xFFFF; 
b_high = b >> 16; 
/* 
* Now a = (a_high * 65536 + a_low), b = (b_high * 65536 + b_low) 
* Thus a*b = (a_high * b_high) * 65536 * 65536 
*   + (a_high * b_low + a_low * b_high) * 65536 
*   + a_low * b_low 
* 
* All products a_i * b_j are at most (65536 - 1) * (65536 - 1) = UINT_MAX - 2 * 65536 + 2 
* The high product reduces to 
* (a_high * b_high) * (UINT_MAX + 1) = (a_high * b_high) 
* The middle products are a bit trickier, but splitting again solves: 
* m1 = a_high * b_low; 
* m1_low = m1 & 0xFFFF; 
* m1_high = m1 >> 16; 
* Then m1 * 65536 = m1_high * (UINT_MAX + 1) + m1_low * 65536 = m1_high + m1_low * 65536 
* Similar for a_low * b_high 
* Finally, add the parts and take care of overflow 
*/ 
m1 = a_high * b_low; 
m2 = a_low * b_high; 
m1_low = m1 & 0xFFFF; 
m1_high = m1 >> 16; 
m2_low = m2 & 0xFFFF; 
m2_high = m2 >> 16; 
result = a_high * b_high; 
temp = result + ((m1_low << 16) | m1_high); 
if (temp < result) // overflow 
{ 
    result = temp+1; 
} 
else 
{ 
    result = temp; 
} 
if (result == UINT_MAX) 
{ 
    result = 0; 
} 
// I'm too lazy to type out the rest, you get the gist, I suppose. 

、そしてそれはunsigned intの乗算が何をするかだけです。ここで、32ビットの符号なしのために示します。

Answer 2

EDIT：コメントで指摘されているように...この回答はモジュロMAX_INT + 1に適用されます 今後の参考として、ここではそのままにしておきます。

それはそれよりもはるかにsimpelerです：

わずか2つの符号なし整数型を掛け、結果もunsigned int型になります。 unsigned intに収まらないものはすべて基本的に存在しません。 だから剰余演算を行うには必要：

See example here

#include <stdio.h> 

void main() 
{ 
    unsigned int a,b; 
    a = 0x90000000; 
    b = 2; 

    unsigned int c = a*b; 

    printf("Answer is %X\r\n", c); 
} 

答えはありません：0x20000000（あなたはモジュロ演算を望んでいただけで何、それは0x120000000されている必要がありますが、答えは切り捨てられましたので）