을 감안할 때 세 개의 정수, 나는 값이 잘못된 결과를 제공하는, 너무 큰 경우 (a * b) % c하지만 a * b 오버 플로우 수를 계산해야하는 a,b <= c < INT_MAX와 a, b 및 c 모듈로.곱하기이 개 넘치는 정수는 세 번째
직접 처리를 통해 즉, 해당 값에 대해 오버플로하지 않는 유형을 사용하지 않고 직접 계산할 수있는 방법이 있습니까?
Karatsuba의 알고리즘은 여기에 실제로 필요하지 않습니다. 피연산자를 한 번만 분리하면 충분합니다.
간단히 말해서 숫자가 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 즉시 계산 될 수 있고, 나머지는 교대 x <<= 1와 x %= c 32 또는 64 시간 (사람 (유 * V) % C = ((U %의 온도) * V) %를 수행함으로써 계산 될 수있다 기음). c >= 2^63 인 경우 표면 상으로는 넘칠 수 있습니다. 그러나 좋은 점은이 작업 쌍이 문자 그대로 수행 될 필요가 없다는 것입니다. 어느 x < c/2은 다음 만의 변화를 필요로 (거기에 오버 플로우는 없다), 또는 x >= c/2 및
2*x % c = 2*x - c = x - (c-x).
(및 오버 플로우 다시 없다).
일부 주요 컴파일러는 오버플로없이이 계산을 수행 할 수있는 128 비트 정수 유형을 제공합니다.
Ivella와 같은 클래스에 있어야합니다. http://stackoverflow.com/questions/14857702/specific-modular-multiplication-algorithm –
아니요, 숙제처럼 들릴 때까지 문제를 줄입니다. Katabusa는 상당히 복잡해 보입니다. , 나는 ('% c) * (b % c) % c'와 같이 링크에 언급 된, 내가 놓친 명백한 비트 해킹이 있었으면한다. 내 문제에는 적용되지 않는다 ...) – pascal
@MatsPetersson a