다음과 같습니다 C에서 내가 수식을 가지고 (는 * X)에서 두 개의 가능성이 더 큰 숫자를 사용하는 int/B 공식

Question

크기를 조정하는 방법 :

X = (a * X)/b; 

이 a/b와 X 크기를 조정하는 데 사용됩니다. 그러나 X은 16 비트 부호없는 int이며 a을 통한 곱하기가 쉽게 오버플로 될 수 있습니다. 어떻게하면 정확한 결과를 가진 정수 만 사용하여이 계산을 수행 할 수 있습니까?

물론 부동 소수점 연산을 사용할 수 있지만이 연산은 부동 소수점 하드웨어가없는 프로세서에서 작동 할 가능성이 높습니다.

편집 : 나는 a와 b가 모두 32 비트 부호없는 정수라고 말하는 것을 잊었습니다. 내 대답은 모두 16 비트로 맞을 때까지 a과 b으로 변경되었습니다. 그런 식으로 a * X은 최대 32 비트이며 최종 계산은 정확합니다.

Answer 1

할 수 있습니다 홍보를 가능하다면 나는 더 큰 정밀도 컴퓨팅을 추천 할 것입니다

X = ((long)a * X)/b; 

Answer 2

당신이처럼 다시 작성할 수 있습니다 :

X = (a/b)*X + (a%b)*(X/b) + (a%b)*(X%b)/b 

을 당신이 그 중 하나가 오버 플로우하지 않습니다 확신 할 수있는 경우 (약 결과 첫 번째, 두 번째는 결과보다 작은, 세 번째 배당금 약 b^2) .

왜 유효한 (제공되지 오버 플로우는/일반 부문을 의미 DIV 정수 나누기 발생하지) 것을 :

: 우리는 (사업자의 C 의미로)이 두 번 사용하는 경우, 지금

X div Y =def floor(X/Y) 
X =def (X div Y) * Y + X mod Y 

(X*Y) div Z = floor(X*[(Y div Z) * Z + Y mod Z]/Z) 
    = floor(X*(Y div Z)*Z/Z + X*(Y mod Z)/Z) 
    = X*(Y div Z) + X*(Y mod Z) div Z 

을

X = (a*X)/b = X*(a/b) + X*(a%b)/b = 
      = X*(a/b) + (a%b)*(X/b) + (a%b)*(X%b)/b 

하지만 그건

X = ((int)X*a)/b