expr에서의 오버플로를 회피하는 방법.A * B - C * D

expr에서의 오버플로를 회피하는 방법.A * B - C * D

요.A*B - C*D'하다, 하다, 하다'가 있습니다signed long long int A, B, C, D;각 숫자는 매우 클 수 있습니다(타입이 오버플로하지 않음).한편, 「 」는, 「 」, 「 」의 사이에A*B오버플로를 수 에, 「오버플로우라고 하는 표현도 .동시에 표현A*B - C*D★★★★★★★★★★★★★★★★★★★★★★★★★★어떻게 하면 정확하게 계산할 수 있을까요?

를 들면, '먹다'와 같이요.MAX * MAX - (MAX - 1) * (MAX + 1) == 1서, snowledge.MAX = LLONG_MAX - nn - n - 부수수수 。

E = max(A,B,C,D)
A1 = A -E;
B1 = B -E;
C1 = C -E;
D1 = D -E;

그리고나서

A*B - C*D = (A1+E)*(B1+E)-(C1+E)(D1+E) = (A1+B1-C1-D1)*E + A1*B1 -C1*D1

모든 엣지 케이스를 다루지 않았을 수도 있고, 엄밀하게 테스트하지도 않았지만, 이것은 80년대에 16비트 CPU로 32비트 정수연산을 시도할 때 사용한 것으로 기억되는 기술을 구현하고 있습니다.기본적으로 32비트를 2개의 16비트 단위로 분할하여 개별적으로 작업합니다.

public class DoubleMaths {
  private static class SplitLong {
    // High half (or integral part).
    private final long h;
    // Low half.
    private final long l;
    // Split.
    private static final int SPLIT = (Long.SIZE / 2);

    // Make from an existing pair.
    private SplitLong(long h, long l) {
      // Let l overflow into h.
      this.h = h + (l >> SPLIT);
      this.l = l % (1l << SPLIT);
    }

    public SplitLong(long v) {
      h = v >> SPLIT;
      l = v % (1l << SPLIT);
    }

    public long longValue() {
      return (h << SPLIT) + l;
    }

    public SplitLong add ( SplitLong b ) {
      // TODO: Check for overflow.
      return new SplitLong ( longValue() + b.longValue() );
    }

    public SplitLong sub ( SplitLong b ) {
      // TODO: Check for overflow.
      return new SplitLong ( longValue() - b.longValue() );
    }

    public SplitLong mul ( SplitLong b ) {
      /*
       * e.g. 10 * 15 = 150
       * 
       * Divide 10 and 15 by 5
       * 
       * 2 * 3 = 5
       * 
       * Must therefore multiply up by 5 * 5 = 25
       * 
       * 5 * 25 = 150
       */
      long lbl = l * b.l;
      long hbh = h * b.h;
      long lbh = l * b.h;
      long hbl = h * b.l;
      return new SplitLong ( lbh + hbl, lbl + hbh );
    }

    @Override
    public String toString () {
      return Long.toHexString(h)+"|"+Long.toHexString(l);
    }
  }

  // I'll use long and int but this can apply just as easily to long-long and long.
  // The aim is to calculate A*B - C*D without overflow.
  static final long A = Long.MAX_VALUE;
  static final long B = Long.MAX_VALUE - 1;
  static final long C = Long.MAX_VALUE;
  static final long D = Long.MAX_VALUE - 2;

  public static void main(String[] args) throws InterruptedException {
    // First do it with BigIntegers to get what the result should be.
    BigInteger a = BigInteger.valueOf(A);
    BigInteger b = BigInteger.valueOf(B);
    BigInteger c = BigInteger.valueOf(C);
    BigInteger d = BigInteger.valueOf(D);
    BigInteger answer = a.multiply(b).subtract(c.multiply(d));
    System.out.println("A*B - C*D = "+answer+" = "+answer.toString(16));

    // Make one and test its integrity.
    SplitLong sla = new SplitLong(A);
    System.out.println("A="+Long.toHexString(A)+" ("+sla.toString()+") = "+Long.toHexString(sla.longValue()));

    // Start small.
    SplitLong sl10 = new SplitLong(10);
    SplitLong sl15 = new SplitLong(15);
    SplitLong sl150 = sl10.mul(sl15);
    System.out.println("10="+sl10.longValue()+"("+sl10.toString()+") * 15="+sl15.longValue()+"("+sl15.toString()+") = "+sl150.longValue() + " ("+sl150.toString()+")");

    // The real thing.
    SplitLong slb = new SplitLong(B);
    SplitLong slc = new SplitLong(C);
    SplitLong sld = new SplitLong(D);
    System.out.println("B="+Long.toHexString(B)+" ("+slb.toString()+") = "+Long.toHexString(slb.longValue()));
    System.out.println("C="+Long.toHexString(C)+" ("+slc.toString()+") = "+Long.toHexString(slc.longValue()));
    System.out.println("D="+Long.toHexString(D)+" ("+sld.toString()+") = "+Long.toHexString(sld.longValue()));
    SplitLong sanswer = sla.mul(slb).sub(slc.mul(sld));
    System.out.println("A*B - C*D = "+sanswer+" = "+sanswer.longValue());

  }

}

인쇄:

A*B - C*D = 9223372036854775807 = 7fffffffffffffff
A=7fffffffffffffff (7fffffff|ffffffff) = 7fffffffffffffff
10=10(0|a) * 15=15(0|f) = 150 (0|96)
B=7ffffffffffffffe (7fffffff|fffffffe) = 7ffffffffffffffe
C=7fffffffffffffff (7fffffff|ffffffff) = 7fffffffffffffff
D=7ffffffffffffffd (7fffffff|fffffffd) = 7ffffffffffffffd
A*B - C*D = 7fffffff|ffffffff = 9223372036854775807

효과가 있는 것처럼 보이는데요

간판 오버플로 등 세세한 부분까지 놓쳤겠지만, 본질은 거기에 있다고 생각합니다.

★★★★★★★★★★★★★★★★★」 ★★★★★★★★★★★★★★★★★.A*B★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

정확성을 잃지 않고 다음을 수행할 수 있습니다.

A*B - C*D = A(D+E) - (A+F)D
          = AD + AE - AD - DF
          = AE - DF
             ^smaller quantities E & F

E = B - D (hence, far smaller than B)
F = C - A (hence, far smaller than C)

이 분해는 더 진행할 수 있습니다.
@Gian이 지적한 바와 같이, 타입이 긴 부호일 경우 감산 조작에 주의가 필요할 수 있습니다.

---

예를 들어 질문의 경우 반복은 한 번만 하면 됩니다.

 MAX * MAX - (MAX - 1) * (MAX + 1)
  A     B       C           D

E = B - D = -1
F = C - A = -1

AE - DF = {MAX * -1} - {(MAX + 1) * -1} = -MAX + MAX + 1 = 1

가장 심플하고 일반적인 솔루션은 긴 정수 라이브러리(http://gmplib.org/) 등)를 사용하거나 구조체 또는 어레이를 사용하여 표현하고 긴 곱셈의 일종(각 숫자를 2개의 32비트 반으로 구분하여 다음과 같이 곱셈을 수행하는 방법)을 사용하여 오버플로하지 않는 표현을 사용하는 것입니다.

(R1 + R2 * 2^32 + R3 * 2^64 + R4 * 2^96) = R = A*B = (A1 + A2 * 2^32) * (B1 + B2 * 2^32) 
R1 = (A1*B1) % 2^32
R2 = ((A1*B1) / 2^32 + (A1*B2) % 2^32 + (A2*B1) % 2^32) % 2^32
R3 = (((A1*B1) / 2^32 + (A1*B2) % 2^32 + (A2*B1) % 2^32) / 2^32 + (A1*B2) / 2^32 + (A2*B1) / 2^32 + (A2*B2) % 2^32) %2^32
R4 = ((((A1*B1) / 2^32 + (A1*B2) % 2^32 + (A2*B1) % 2^32) / 2^32 + (A1*B2) / 2^32 + (A2*B1) / 2^32 + (A2*B2) % 2^32) / 2^32) + (A2*B2) / 2^32

최종 결과가 64비트에 적합하다고 가정하면 실제로는 R3의 대부분의 비트는 필요하지 않으며 R4의 비트는 필요하지 않습니다.

이것은 랩 어라운드 서명 오버플로우에 의존하기 때문에 표준이 아닙니다.(GCC에는 이를 유효하게 하는 컴파일러 플래그가 있습니다.)

그냥 요.long long"CHANGE: "CHANGE: " 。
(A * B - C * D)합니다.long long.

---

여기에서는 부호 없는 정수를 부호 있는 정수로 캐스팅하는 구현 정의 동작에만 의존하는 해결 방법을 보여 줍니다.그러나 이는 오늘날 거의 모든 시스템에서 작동할 것으로 예상할 수 있습니다.

(long long)((unsigned long long)A * B - (unsigned long long)C * D)

이 '아까', '아까', '아까', '아까'로 .unsigned long long오버플로 동작이 표준으로 랩어라운드로 보증됩니다.마지막에 부호 있는 정수로 되돌리는 것은 구현 정의 부분이지만 오늘날 거의 모든 환경에서 작동합니다.

---

현학적인 해법이 더 필요하다면, "긴 산수"를 사용해야 한다고 생각합니다.

이것은 동작할 것입니다(제 생각에는).

signed long long int a = 0x7ffffffffffffffd;
signed long long int b = 0x7ffffffffffffffd;
signed long long int c = 0x7ffffffffffffffc;
signed long long int d = 0x7ffffffffffffffe;
signed long long int bd = b / d;
signed long long int bdmod = b % d;
signed long long int ca = c / a;
signed long long int camod = c % a;
signed long long int x = (bd - ca) * a * d - (camod * d - bdmod * a);

제 결론은 이렇습니다.

x = a * b - c * d
x / (a * d) = (a * b - c * d) / (a * d)
x / (a * d) = b / d - c / a

now, the integer/mod stuff:
x / (a * d) = (b / d + ( b % d ) / d) - (c / a + ( c % a ) / a )
x / (a * d) = (b / d - c / a) - ( ( c % a ) / a - ( b % d ) / d)
x = (b / d - c / a) * a * d - ( ( c % a ) * d - ( b % d ) * a)

모든 값에 대해 가장 큰 공통 계수를 계산한 다음 산술 연산을 수행하기 전에 해당 계수로 나눈 다음 다시 곱하는 것을 고려할 수 있습니다.를 들어,단, 는, 는, 이, 를, 를, 를, 를, 를, 를, 를, 를, 를 등).A,B,C ★★★★★★★★★★★★★★★★★」D공교롭게도 비교적 소수이기 때문에 공통 인자를 갖지 않습니다.)

마찬가지로 로그 스케일링에 대한 작업을 고려할 수 있지만, 이는 수치 정밀도에 따라 약간 무시무시합니다.

그 결과가 롱 int에 들어맞으면 연산모드 2^64를 실행하므로 A*B-C*D 식도 OK이며, 올바른 결과를 얻을 수 있다.문제는 그 결과가 장기간에 걸쳐 맞는지 확인하는 것이다.이를 감지하기 위해 이중을 사용하여 다음 트릭을 사용할 수 있습니다.

if( abs( (double)A*B - (double)C*D ) > MAX_LLONG ) 
    Overflow
else 
    return A*B-C*D;

이 접근방식의 문제는 2배(54비트?)의 가수 정밀도에 의해 제한되므로 제품 A*B 및 C*D를 63+54비트(또는 조금 더 작을 수 있음)로 제한해야 한다는 것입니다.

배열의 각 숫자를 쓰고, 각 요소는 숫자이고, 계산을 다항식으로 수행할 수 있습니다.결과 다항식(배열)을 취하여 배열의 각 요소에 10을 곱하여 결과를 계산합니다(첫 번째 위치는 가장 크고 마지막 위치는 0).

★★123을 사용하다

123 = 100 * 1 + 10 * 2 + 3

.[1 2 3].

모든 숫자 A, B, C, D에 대해 이 작업을 수행한 다음 이들을 다항식으로 곱합니다.결과 다항식을 얻으면 숫자만 재구성할 수 있습니다.

signed long long int 수 없다A*B그래서...A*B는 서로 다른으로 분해할 수 , 그중가 하나의 지수로 하다, 하나의 지수로 할 수 있습니다.signed long long int.

A1=A>>32;
A0=A & 0xffffffff;
B1=B>>32;
B0=B & 0xffffffff;

AB_0=A0*B0;
AB_1=A0*B1+A1*B0;
AB_2=A1*B1;

일일도 입니다.C*D.

, 할 수 .AB_i그리고.CD_i마찬가지로 각각에 대해 추가 캐리어 비트(정확히 1비트 정수)를 사용합니다.E=A*B-C*D라고 하면 다음과 같은 결과가 나옵니다.

E_00=AB_0-CD_0 
E_01=(AB_0 > CD_0) == (AB_0 - CD_0 < 0) ? 0 : 1  // carry bit if overflow
E_10=AB_1-CD_1 
...

상부를 이전하는 것으로 속행합니다.E_10로.E_20(시프트를 32로 한 후 더하기, 지우기)E_10).

이제 캐리어 비트를 제거할 수 있습니다.E_11올바른 기호(비반송 부분에서 제외)와 함께 추가함으로써E_20이로 인해 오버플로가 발생하면 결과도 맞지 않습니다.

E_10이제 윗부분을 차지하기에 충분한 '공간'E_00(시프트, 추가, 삭제) 및 반송 비트E_01.

E_10이제 다시 커질 수 있기 때문에 로의 전송을 반복합니다.E_20

이 「 」는E_200으로 하다의 E_10전송 결과도 비어 있습니다.

입니다.E_20E_10 또.

라는 E=A*B+C*D would the signed long long int은 보유 중), "holds(보류)"

E_20=0
E_10=0
E_00=E

최종 결과가 정수 유형으로 표시될 수 있는 경우 아래 코드를 사용하여 이 계산을 빠르게 수행할 수 있습니다.C 표준에서는 부호 없는 산술은 모듈로 산술이며 오버플로하지 않도록 규정되어 있으므로 부호 없는 유형을 사용하여 계산을 수행할 수 있습니다.

다음 코드에서는 같은 폭의 부호 없는 타입이 존재하며 부호 있는 타입이 모든 비트패턴을 사용하여 값을 나타내고 있는 것을 전제로 하고 있습니다(트랩 표현은 없습니다.서명된 타입의 최소값은 부호 없는 타입의 계수의 절반의 마이너스입니다).이것이 C 실장 내에서 유지되지 않는 경우 ConvertToSigned 루틴을 간단하게 조정할 수 있습니다.

은 '먹다'를 사용해요.signed char ★★★★★★★★★★★★★★★★★」unsigned char코드를 시연합니다. 경우, 사용법을 바꿀 때 '사용하다'의 수 .Signed로로 합니다.typedef signed long long int Signed; 의 Unsigned로로 합니다.typedef unsigned long long int Unsigned;.

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>


//  Define the signed and unsigned types we wish to use.
typedef signed char   Signed;
typedef unsigned char Unsigned;

//  uHalfModulus is half the modulus of the unsigned type.
static const Unsigned uHalfModulus = UCHAR_MAX/2+1;

//  sHalfModulus is the negation of half the modulus of the unsigned type.
static const Signed   sHalfModulus = -1 - (Signed) (UCHAR_MAX/2);


/*  Map the unsigned value to the signed value that is the same modulo the
    modulus of the unsigned type.  If the input x maps to a positive value, we
    simply return x.  If it maps to a negative value, we return x minus the
    modulus of the unsigned type.

    In most C implementations, this routine could simply be "return x;".
    However, this version uses several steps to convert x to a negative value
    so that overflow is avoided.
*/
static Signed ConvertToSigned(Unsigned x)
{
    /*  If x is representable in the signed type, return it.  (In some
        implementations, 
    */
    if (x < uHalfModulus)
        return x;

    /*  Otherwise, return x minus the modulus of the unsigned type, taking
        care not to overflow the signed type.
    */
    return (Signed) (x - uHalfModulus) - sHalfModulus;
}


/*  Calculate A*B - C*D given that the result is representable as a Signed
    value.
*/
static signed char Calculate(Signed A, Signed B, Signed C, Signed D)
{
    /*  Map signed values to unsigned values.  Positive values are unaltered.
        Negative values have the modulus of the unsigned type added.  Because
        we do modulo arithmetic below, adding the modulus does not change the
        final result.
    */
    Unsigned a = A;
    Unsigned b = B;
    Unsigned c = C;
    Unsigned d = D;

    //  Calculate with modulo arithmetic.
    Unsigned t = a*b - c*d;

    //  Map the unsigned value to the corresponding signed value.
    return ConvertToSigned(t);
}


int main()
{
    //  Test every combination of inputs for signed char.
    for (int A = SCHAR_MIN; A <= SCHAR_MAX; ++A)
    for (int B = SCHAR_MIN; B <= SCHAR_MAX; ++B)
    for (int C = SCHAR_MIN; C <= SCHAR_MAX; ++C)
    for (int D = SCHAR_MIN; D <= SCHAR_MAX; ++D)
    {
        //  Use int to calculate the expected result.
        int t0 = A*B - C*D;

        //  If the result is not representable in signed char, skip this case.
        if (t0 < SCHAR_MIN || SCHAR_MAX < t0)
            continue;

        //  Calculate the result with the sample code.
        int t1 = Calculate(A, B, C, D);

        //  Test the result for errors.
        if (t0 != t1)
        {
            printf("%d*%d - %d*%d = %d, but %d was returned.\n",
                A, B, C, D, t0, t1);
            exit(EXIT_FAILURE);
        }
    }
    return 0;
}

방정식을 넘치지 않는 작은 성분으로 분할해 볼 수 있습니다.

AB - CD
= [ A(B - N) - C( D - M )] + [AN - CM]

= ( AK - CJ ) + ( AN - CM)

    where K = B - N
          J = D - M

컴포넌트가 여전히 오버플로우인 경우 컴포넌트를 더 작은 컴포넌트로 재귀적으로 분할하여 재결합할 수 있습니다.

완전성을 위해, 아무도 언급하지 않았기 때문에, 일부 컴파일러(GCC 등)는 실제로 128비트 정수를 제공하고 있습니다.

따라서 다음과 같은 간단한 해결책이 있습니다.

(long long)((__int128)A * B - (__int128)C * D)

AB-CD = (AB-CD) * AC / AC = (B/C-D/A)*A*C둘 다 아니다.B/C 않다D/A할 수 있으므로 .(B/C-D/A) 최종 결과는 않기 때문에 .(B/C-D/A)*A*C필요한 결과입니다.

주의: 입력 내용이 매우 작을 수 있는 경우B/C ★★★★★★★★★★★★★★★★★」D/A넘칠 수 있습니다.가능하면 입력 검사에 따라 더 복잡한 조작이 필요할 수 있습니다.

[ ] 를 합니다.K = a big numberK = A - sqrt(A))

A*B - C*D = (A-K)*(B-K) - (C-K)*(D-K) + K*(A-C+B-D); // Avoid overflow.

---

왜요?

(A-K)*(B-K) = A*B - K*(A+B) + K^2
(C-K)*(D-K) = C*D - K*(C+D) + K^2

=>
(A-K)*(B-K) - (C-K)*(D-K) = A*B - K*(A+B) + K^2 - {C*D - K*(C+D) + K^2}
(A-K)*(B-K) - (C-K)*(D-K) = A*B - C*D - K*(A+B) + K*(C+D) + K^2 - K^2
(A-K)*(B-K) - (C-K)*(D-K) = A*B - C*D - K*(A+B-C-D)

=>
A*B - C*D = (A-K)*(B-K) - (C-K)*(D-K) + K*(A+B-C-D)

=>
A*B - C*D = (A-K)*(B-K) - (C-K)*(D-K) + K*(A-C+B-D)

C및이므로 A, B, C는 D로 되어 있습니다.A-C ★★★★★★★★★★★★★★★★★」B-D작은 숫자입니다.

언급URL : https://stackoverflow.com/questions/13237046/how-to-avoid-overflow-in-expr-a-b-c-d