두 개의 큰 정수를 곱하는 동안 오버플로우 포착 및 계산
저는 비교적 큰 수를 곱하여 결과를 하나 또는 여러 정수로 저장할 수 있는 효율적인(옵션으로 표준적이고 우아하며 구현하기 쉬운) 솔루션을 찾고 있습니다.
예를 들어 다음과 같이 선언된2개의 64비트 정수가 있다고 칩니다.
uint64_t a = xxx, b = yyy;
가 할 때a * b작업 결과 오버플로가 발생하고 이 경우 캐리어를 어디에 보관하려면 어떻게 해야 합니까?
번호의 보존 방법에 제약이 있기 때문에, 큰 번호의 라이브러리는 사용하고 싶지 않습니다.
1. 오버플로우 검출:
x = a * b;
if (a != 0 && x / a != b) {
// overflow handling
}
by에 의한 고정 분할: 할 by by by by 。0 마크
2. 캐리 계산은 상당히 복잡합니다.한 가지 방법은 두 오퍼랜드를 반단어로 분할한 후 반단어에 긴 곱셈을 적용하는 것입니다.
uint64_t hi(uint64_t x) {
return x >> 32;
}
uint64_t lo(uint64_t x) {
return ((1ULL << 32) - 1) & x;
}
void multiply(uint64_t a, uint64_t b) {
// actually uint32_t would do, but the casting is annoying
uint64_t s0, s1, s2, s3;
uint64_t x = lo(a) * lo(b);
s0 = lo(x);
x = hi(a) * lo(b) + hi(x);
s1 = lo(x);
s2 = hi(x);
x = s1 + lo(a) * hi(b);
s1 = lo(x);
x = s2 + hi(a) * hi(b) + hi(x);
s2 = lo(x);
s3 = hi(x);
uint64_t result = s1 << 32 | s0;
uint64_t carry = s3 << 32 | s2;
}
부분 합계 자체가 오버플로하지 않도록 하기 위해 최악의 경우를 고려합니다.
x = s2 + hi(a) * hi(b) + hi(x)
let let 렛츠고B = 1 << 32 ,,가 있습니다
x <= (B - 1) + (B - 1)(B - 1) + (B - 1)
<= B*B - 1
< B*B
나는 이것이 효과가 있을 것이라고 믿는다 - 적어도 Sjlver의 테스트 케이스를 처리한다.그 외에는 테스트되지 않았습니다(C++ 컴파일러가 없기 때문에 컴파일도 할 수 없습니다).
이 개념은 통합 연산에 참인 다음 사실을 사용하는 것입니다.
a*b > c()a > c/b
/여기서 적분분할입니다.
오버플로우로부터 양의 번호를 체크하는 의사 코드는 다음과 같습니다.
(a > max_int64 / b)의 경우는, 「displicate」, 그 이외의 경우는 「ok」입니다.
0과 음수를 처리하려면 체크를 추가해야 합니다.
이 아닌 의 C a ★★★★★★★★★★★★★★★★★」b음음음같 뭇매하다
if (b > 0 && a > 18446744073709551615 / b) {
// overflow handling
}; else {
c = a * b;
}
주의:
18446744073709551615 == (1<<64)-1
이행을 계산하기 위해서는 32자릿수 두 자릿수로 숫자를 나누어 종이에 곱하는 방법을 사용할 수 있습니다.넘치지 않으려면 숫자를 나눠야 해요.
코드는 다음과 같습니다.
// split input numbers into 32-bit digits
uint64_t a0 = a & ((1LL<<32)-1);
uint64_t a1 = a >> 32;
uint64_t b0 = b & ((1LL<<32)-1);
uint64_t b1 = b >> 32;
// The following 3 lines of code is to calculate the carry of d1
// (d1 - 32-bit second digit of result, and it can be calculated as d1=d11+d12),
// but to avoid overflow.
// Actually rewriting the following 2 lines:
// uint64_t d1 = (a0 * b0 >> 32) + a1 * b0 + a0 * b1;
// uint64_t c1 = d1 >> 32;
uint64_t d11 = a1 * b0 + (a0 * b0 >> 32);
uint64_t d12 = a0 * b1;
uint64_t c1 = (d11 > 18446744073709551615 - d12) ? 1 : 0;
uint64_t d2 = a1 * b1 + c1;
uint64_t carry = d2; // needed carry stored here
쨍그랑 소리와 gcc로 쉽고 빠르게:
unsigned long long t a, b, result;
if (__builtin_umulll_overflow(a, b, &result)) {
// overflow!!
}
이를 통해 가능한 경우 오버플로우 검출에 대한 하드웨어 지원이 사용됩니다.컴파일러 확장기능으로 부호화된 정수 오버플로(umul을 smul로 대체), C++에서 정의되지 않은 동작도 처리할 수 있습니다.
이 질문에는 그 밖에도 몇 가지 답변이 있었지만, 그 중 몇 가지는 전혀 검증되지 않은 코드를 가지고 있기 때문에, 지금까지 어느 누구도 다른 옵션을 충분히 비교하고 있지 않습니다.
그 때문에, 가능한 몇개의 실장을 작성해 테스트했습니다(마지막 실장은 여기 Reddit에서 논의된 OpenBSD의 코드를 기반으로 하고 있습니다).코드는 다음과 같습니다.
/* Multiply with overflow checking, emulating clang's builtin function
*
* __builtin_umull_overflow
*
* This code benchmarks five possible schemes for doing so.
*/
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <limits.h>
#ifndef BOOL
#define BOOL int
#endif
// Option 1, check for overflow a wider type
// - Often fastest and the least code, especially on modern compilers
// - When long is a 64-bit int, requires compiler support for 128-bits
// ints (requires GCC >= 3.0 or Clang)
#if LONG_BIT > 32
typedef __uint128_t long_overflow_t ;
#else
typedef uint64_t long_overflow_t;
#endif
BOOL
umull_overflow1(unsigned long lhs, unsigned long rhs, unsigned long* result)
{
long_overflow_t prod = (long_overflow_t)lhs * (long_overflow_t)rhs;
*result = (unsigned long) prod;
return (prod >> LONG_BIT) != 0;
}
// Option 2, perform long multiplication using a smaller type
// - Sometimes the fastest (e.g., when mulitply on longs is a library
// call).
// - Performs at most three multiplies, and sometimes only performs one.
// - Highly portable code; works no matter how many bits unsigned long is
BOOL
umull_overflow2(unsigned long lhs, unsigned long rhs, unsigned long* result)
{
const unsigned long HALFSIZE_MAX = (1ul << LONG_BIT/2) - 1ul;
unsigned long lhs_high = lhs >> LONG_BIT/2;
unsigned long lhs_low = lhs & HALFSIZE_MAX;
unsigned long rhs_high = rhs >> LONG_BIT/2;
unsigned long rhs_low = rhs & HALFSIZE_MAX;
unsigned long bot_bits = lhs_low * rhs_low;
if (!(lhs_high || rhs_high)) {
*result = bot_bits;
return 0;
}
BOOL overflowed = lhs_high && rhs_high;
unsigned long mid_bits1 = lhs_low * rhs_high;
unsigned long mid_bits2 = lhs_high * rhs_low;
*result = bot_bits + ((mid_bits1+mid_bits2) << LONG_BIT/2);
return overflowed || *result < bot_bits
|| (mid_bits1 >> LONG_BIT/2) != 0
|| (mid_bits2 >> LONG_BIT/2) != 0;
}
// Option 3, perform long multiplication using a smaller type (this code is
// very similar to option 2, but calculates overflow using a different but
// equivalent method).
// - Sometimes the fastest (e.g., when mulitply on longs is a library
// call; clang likes this code).
// - Performs at most three multiplies, and sometimes only performs one.
// - Highly portable code; works no matter how many bits unsigned long is
BOOL
umull_overflow3(unsigned long lhs, unsigned long rhs, unsigned long* result)
{
const unsigned long HALFSIZE_MAX = (1ul << LONG_BIT/2) - 1ul;
unsigned long lhs_high = lhs >> LONG_BIT/2;
unsigned long lhs_low = lhs & HALFSIZE_MAX;
unsigned long rhs_high = rhs >> LONG_BIT/2;
unsigned long rhs_low = rhs & HALFSIZE_MAX;
unsigned long lowbits = lhs_low * rhs_low;
if (!(lhs_high || rhs_high)) {
*result = lowbits;
return 0;
}
BOOL overflowed = lhs_high && rhs_high;
unsigned long midbits1 = lhs_low * rhs_high;
unsigned long midbits2 = lhs_high * rhs_low;
unsigned long midbits = midbits1 + midbits2;
overflowed = overflowed || midbits < midbits1 || midbits > HALFSIZE_MAX;
unsigned long product = lowbits + (midbits << LONG_BIT/2);
overflowed = overflowed || product < lowbits;
*result = product;
return overflowed;
}
// Option 4, checks for overflow using division
// - Checks for overflow using division
// - Division is slow, especially if it is a library call
BOOL
umull_overflow4(unsigned long lhs, unsigned long rhs, unsigned long* result)
{
*result = lhs * rhs;
return rhs > 0 && (SIZE_MAX / rhs) < lhs;
}
// Option 5, checks for overflow using division
// - Checks for overflow using division
// - Avoids division when the numbers are "small enough" to trivially
// rule out overflow
// - Division is slow, especially if it is a library call
BOOL
umull_overflow5(unsigned long lhs, unsigned long rhs, unsigned long* result)
{
const unsigned long MUL_NO_OVERFLOW = (1ul << LONG_BIT/2) - 1ul;
*result = lhs * rhs;
return (lhs >= MUL_NO_OVERFLOW || rhs >= MUL_NO_OVERFLOW) &&
rhs > 0 && SIZE_MAX / rhs < lhs;
}
#ifndef umull_overflow
#define umull_overflow2
#endif
/*
* This benchmark code performs a multiply at all bit sizes,
* essentially assuming that sizes are logarithmically distributed.
*/
int main()
{
unsigned long i, j, k;
int count = 0;
unsigned long mult;
unsigned long total = 0;
for (k = 0; k < 0x40000000 / LONG_BIT / LONG_BIT; ++k)
for (i = 0; i != LONG_MAX; i = i*2+1)
for (j = 0; j != LONG_MAX; j = j*2+1) {
count += umull_overflow(i+k, j+k, &mult);
total += mult;
}
printf("%d overflows (total %lu)\n", count, total);
}
사용하고 있는 각종 컴파일러 및 시스템에서 테스트한 결과를 다음에 나타냅니다(이 경우 모든 테스트는 OS X에서 이루어졌지만 결과는 BSD 또는 Linux 시스템에서 비슷합니다).
+------------------+----------+----------+----------+----------+----------+
| | Option 1 | Option 2 | Option 3 | Option 4 | Option 5 |
| | BigInt | LngMult1 | LngMult2 | Div | OptDiv |
+------------------+----------+----------+----------+----------+----------+
| Clang 3.5 i386 | 1.610 | 3.217 | 3.129 | 4.405 | 4.398 |
| GCC 4.9.0 i386 | 1.488 | 3.469 | 5.853 | 4.704 | 4.712 |
| GCC 4.2.1 i386 | 2.842 | 4.022 | 3.629 | 4.160 | 4.696 |
| GCC 4.2.1 PPC32 | 8.227 | 7.756 | 7.242 | 20.632 | 20.481 |
| GCC 3.3 PPC32 | 5.684 | 9.804 | 11.525 | 21.734 | 22.517 |
+------------------+----------+----------+----------+----------+----------+
| Clang 3.5 x86_64 | 1.584 | 2.472 | 2.449 | 9.246 | 7.280 |
| GCC 4.9 x86_64 | 1.414 | 2.623 | 4.327 | 9.047 | 7.538 |
| GCC 4.2.1 x86_64 | 2.143 | 2.618 | 2.750 | 9.510 | 7.389 |
| GCC 4.2.1 PPC64 | 13.178 | 8.994 | 8.567 | 37.504 | 29.851 |
+------------------+----------+----------+----------+----------+----------+
이러한 결과를 바탕으로 몇 가지 결론을 도출할 수 있습니다.
- 확실히, 부문 베이스의 어프로치는, 심플하고 휴대성이 뛰어나지만, 느립니다.
- 어떤 기술도 모든 경우에 확실한 승자는 아니다.
- 최신 컴파일러에서는 use-a-large-int 접근법이 가장 적합합니다.
- 오래된 컴파일러에서는 장기 곱셈 방식이 가장 적합합니다.
- 놀랍게도 GCC 4.9.0은 GCC 4.2.1보다 퍼포먼스가 저하되고 GCC 4.2.1은 GCC 3.3보다 퍼포먼스가 저하됩니다.
a == 0인 경우에도 작동하는 버전:
x = a * b;
if (a != 0 && x / a != b) {
// overflow handling
}
GNU Portability Library(Gnulib)에는 모듈 intprops가 포함되어 있습니다.이 intprops에는 산술 연산이 오버플로우하는지 여부를 효율적으로 테스트하는 매크로가 있습니다.
, 「」, 「」, 「」, 「」, 「」, 「」와 같이 됩니다.INT_MULTIPLY_OVERFLOW (a, b) 낳다1.
아직 언급되지 않은 간단한 솔루션(대개 매우 빠른 솔루션)이 있습니다.이 솔루션은 n+m비트 이상의 제품 폭에서는 n-bit 곱하기 m-bit 곱셈이 오버플로하지 않지만 n+m-1보다 작은 모든 결과 폭에서는 오버플로가 발생한다는 사실에 기초하고 있습니다.
이전 설명을 읽는 것이 너무 어려웠기 때문에 다시 시도합니다.필요한 것은 양쪽 오퍼랜드의 선행 제로 합계를 확인하는 것입니다.수학적으로 증명하는 것은 매우 쉬울 것이다.x자, y자, y자, y자, y자, y자, y자, y자, y자, y자, y자. z = x * yk 입니다.비트입니다.상품은 최대 n+m 크기이기 때문에 넘칠 수 있습니다.예를 들어보자. x*y long제로 ).p-bit bit ( 0 음 ) 。의 선두 은 0이다.clz(x * y) = n+m - p로그와 . clz는 로그와 같이 동작합니다.을 사용하다clz(x * y) = clz(x) + clz(y) + c with c = either 1 or 0. (댓글에 c=1 조언을 해주셔서 감사합니다!)이 넘치면 넘칩니다.k < p <= n+m <=> n+m - k > n+m - p = clz(x * y).
이제 다음 알고리즘을 사용할 수 있습니다.
if max(clz(x * y)) = clz(x) + clz(y) +1 < (n+m - k) --> overflow
if max(clz(x * y)) = clz(x) + clz(y) +1 == (n+m - k) --> overflow if c = 0
else --> no overflow
중간 케이스에서 오버플로우 확인 방법곱셈 지시는 있으시겠죠?그러면 결과의 선두 0을 쉽게 확인할 수 있습니다. 즉, 다음과 같습니다.
if clz(x * y / 2) == (n+m - k) <=> msb(x * y/2) == 1 --> overflow
else --> no overflow
곱셈은 x/2를 고정점, y를 정규 정수로 처리하여 수행합니다.
msb(x * y/2) = msb(floor(x * y / 2))
floor(x * y/2) = floor(x/2) * y + (lsb(x) * floor(y/2)) = (x >> 1)*y + (x & 1)*(y >> 1)
는 (이러한 에는) 않습니다).clz(x)+clz(y)+1 == (n+m -k))
비결은 빌트인/인트라닉을 사용하는 것입니다.GCC에서는 다음과 같이 표시됩니다.
static inline int clz(int a) {
if (a == 0) return 32; //only needed for x86 architecture
return __builtin_clz(a);
}
/**@fn static inline _Bool chk_mul_ov(uint32_t f1, uint32_t f2)
* @return one, if a 32-Bit-overflow occurs when unsigned-unsigned-multipliying f1 with f2 otherwise zero. */
static inline _Bool chk_mul_ov(uint32_t f1, uint32_t f2) {
int lzsum = clz(f1) + clz(f2); //leading zero sum
return
lzsum < sizeof(f1)*8-1 || ( //if too small, overflow guaranteed
lzsum == sizeof(f1)*8-1 && //if special case, do further check
(int32_t)((f1 >> 1)*f2 + (f1 & 1)*(f2 >> 1)) < 0 //check product rightshifted by one
);
}
...
if (chk_mul_ov(f1, f2)) {
//error handling
}
...
n = m = k = 32비트 부호 없음-부호 없음-승수에 대한 예제입니다.이를 부호화/서명 해제 또는 부호화 곱셈으로 일반화할 수 있습니다.또한 멀티비트 시프트도 필요하지 않습니다(일부 마이크로 컨트롤러는 1비트 시프트만 구현하지만 Atmega!와 같은 단일 명령으로 2분할 제품을 지원하는 경우도 있습니다).그러나 count-leading-zero 명령이 없고 긴 곱셈만 있는 경우에는 이 방법이 더 낫지 않을 수 있습니다.
다른 컴파일러에서는 CLZ 연산을 위한 내장 함수를 지정하는 독자적인 방법이 있습니다.clz-method는 곱셈의 상단을 체크하는 것에 비해 (최악의 경우) 64비트 오버플로를 체크하기 위해 고도로 최적화된 128비트 곱셈을 사용하는 것보다 더 잘 확장해야 합니다.선형 오버헤드에 대한 곱셈이 필요한 반면, 카운트 비트에는 선형 오버헤드만 필요합니다.이 코드는 시도했을 때 바로 사용할 수 있었습니다.
오버플로를 검출할 뿐만 아니라 캐리도 캡처할 필요가 있는 경우는 32비트의 수치로 분할하는 것이 가장 좋습니다.코드는 악몽입니다.다음은 스케치일 뿐입니다.
#include <stdint.h>
uint64_t mul(uint64_t a, uint64_t b) {
uint32_t ah = a >> 32;
uint32_t al = a; // truncates: now a = al + 2**32 * ah
uint32_t bh = b >> 32;
uint32_t bl = b; // truncates: now b = bl + 2**32 * bh
// a * b = 2**64 * ah * bh + 2**32 * (ah * bl + bh * al) + al * bl
uint64_t partial = (uint64_t) al * (uint64_t) bl;
uint64_t mid1 = (uint64_t) ah * (uint64_t) bl;
uint64_t mid2 = (uint64_t) al * (uint64_t) bh;
uint64_t carry = (uint64_t) ah * (uint64_t) bh;
// add high parts of mid1 and mid2 to carry
// add low parts of mid1 and mid2 to partial, carrying
// any carry bits into carry...
}
문제는 부분적인 제품뿐만 아니라 그 중 어느 것이든 넘칠 수 있다는 사실이다.
만약 내가 이것을 정말로 해야 한다면, 나는 지역 의회 언어로 확장-배율 루틴을 쓸 것이다.즉, 예를 들어 2개의 64비트 정수를 곱하여 128비트 결과를 얻으면 2개의 64비트 레지스터에 저장됩니다.합리적인 하드웨어는 모두 이 기능을 하나의 네이티브 멀티플 명령으로 제공합니다.C에서만 액세스 할 수 있는 것은 아닙니다.
이것은 가장 우아하고 프로그래밍하기 쉬운 솔루션이 실제로 어셈블리 언어를 사용하는 드문 사례 중 하나입니다.단, 휴대성은 확실히 아닙니다.
아마도 이 문제를 해결하는 가장 좋은 방법은 함수를 갖는 것입니다.이 함수는 2개의 UInt64를 곱하여 UInt128 결과의 위쪽과 아래쪽의 UInt64 쌍을 생성합니다.다음은 결과를 16진수로 표시하는 함수를 포함한 해법입니다.당신은 C++ 솔루션을 선호할 것입니다만, 저는 Swift-Solution을 사용하고 있습니다.이 솔루션에는 문제를 관리하는 방법이 나와 있습니다.
func hex128 (_ hi: UInt64, _ lo: UInt64) -> String
{
var s: String = String(format: "%08X", hi >> 32)
+ String(format: "%08X", hi & 0xFFFFFFFF)
+ String(format: "%08X", lo >> 32)
+ String(format: "%08X", lo & 0xFFFFFFFF)
return (s)
}
func mul64to128 (_ multiplier: UInt64, _ multiplicand : UInt64)
-> (result_hi: UInt64, result_lo: UInt64)
{
let x: UInt64 = multiplier
let x_lo: UInt64 = (x & 0xffffffff)
let x_hi: UInt64 = x >> 32
let y: UInt64 = multiplicand
let y_lo: UInt64 = (y & 0xffffffff)
let y_hi: UInt64 = y >> 32
let mul_lo: UInt64 = (x_lo * y_lo)
let mul_hi: UInt64 = (x_hi * y_lo) + (mul_lo >> 32)
let mul_carry: UInt64 = (x_lo * y_hi) + (mul_hi & 0xffffffff)
let result_hi: UInt64 = (x_hi * y_hi) + (mul_hi >> 32) + (mul_carry >> 32)
let result_lo: UInt64 = (mul_carry << 32) + (mul_lo & 0xffffffff)
return (result_hi, result_lo)
}
다음으로 기능이 기능하는 것을 확인하는 예를 나타냅니다.
var c: UInt64 = 0
var d: UInt64 = 0
(c, d) = mul64to128(0x1234567890123456, 0x9876543210987654)
// 0AD77D742CE3C72E45FD10D81D28D038 is the result of the above example
print(hex128(c, d))
(c, d) = mul64to128(0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF)
// FFFFFFFFFFFFFFFE0000000000000001 is the result of the above example
print(hex128(c, d))
오버플로를 검출하고 싶다면 더블로 변환하여 곱셈을 하고,
|x| < 2^53, int64로 변환
|x| < 2^63, int64를 사용하여 곱합니다.
그렇지 않으면 원하는 오류를 생성할 수 있습니까?
이것은 효과가 있는 것 같습니다.
int64_t safemult(int64_t a, int64_t b) {
double dx;
dx = (double)a * (double)b;
if ( fabs(dx) < (double)9007199254740992 )
return (int64_t)dx;
if ( (double)INT64_MAX < fabs(dx) )
return INT64_MAX;
return a*b;
}
저는 요즘 이 문제에 대해 연구하고 있는데, 사람들이 오버플로우가 있었는지 알 수 있는 가장 좋은 방법은 결과를 나누는 것이라고 말하는 것을 여러 번 본 적이 있습니다.그것은 전혀 비효율적이고 불필요합니다.이 기능의 포인트는 가능한 한 빨라야 한다는 것입니다.
오버플로우 검출에는, 다음의 2개의 옵션이 있습니다.
1µ- 가능한 경우 승수보다 두 배 큰 결과 변수를 만듭니다. 예를 들어 다음과 같습니다.
struct INT32struct {INT16 high, low;};
typedef union
{
struct INT32struct s;
INT32 ll;
} INT32union;
INT16 mulFunction(INT16 a, INT16 b)
{
INT32union result.ll = a * b; //32Bits result
if(result.s.high > 0)
Overflow();
return (result.s.low)
}
오버플로우 발생 여부를 바로 알 수 있으며, 기계코드로 작성하지 않아도 코드가 가장 빠릅니다.컴파일러에 따라서는, 이 코드는 머신 코드로 개선될 수 있습니다.
2'- 승수 변수보다 두 배 큰 결과 변수를 생성할 수 없습니다.그런 다음 최적의 경로를 결정하기 위한 조건을 사용하여 플레이해야 합니다.다음 예시로 넘어갑니다.
INT32 mulFunction(INT32 a, INT32 b)
{
INT32union s_a.ll = abs(a);
INT32union s_b.ll = abs(b); //32Bits result
INT32union result;
if(s_a.s.hi > 0 && s_b.s.hi > 0)
{
Overflow();
}
else if (s_a.s.hi > 0)
{
INT32union res1.ll = s_a.s.hi * s_b.s.lo;
INT32union res2.ll = s_a.s.lo * s_b.s.lo;
if (res1.hi == 0)
{
result.s.lo = res1.s.lo + res2.s.hi;
if (result.s.hi == 0)
{
result.s.ll = result.s.lo << 16 + res2.s.lo;
if ((a.s.hi >> 15) ^ (b.s.hi >> 15) == 1)
{
result.s.ll = -result.s.ll;
}
return result.s.ll
}else
{
Overflow();
}
}else
{
Overflow();
}
}else if (s_b.s.hi > 0)
{
//Same code changing a with b
}else
{
return (s_a.lo * s_b.lo);
}
}
이 코드가 매우 효율적인 프로그램을 만드는 데 도움이 되길 바라며, 코드가 명확하기를 바랍니다. 그렇지 않다면 몇 가지 동의서를 넣겠습니다.
안부 전합니다.
여기에서는 부호 없는 두 정수의 곱셈이 오버플로우 여부를 검출하기 위한 트릭을 나타냅니다.
N비트 폭의 2진수와 M비트 폭의 2진수를 곱하면 N+M비트를 넘지 않는 것으로 관찰하고 있습니다.
예를 들어 3비트 숫자와 29비트 숫자를 곱하도록 요구받았을 경우 32비트가 오버플로하지 않음을 알 수 있습니다.
#include <stdlib.h>
#include <stdio.h>
int might_be_mul_oflow(unsigned long a, unsigned long b)
{
if (!a || !b)
return 0;
a = a | (a >> 1) | (a >> 2) | (a >> 4) | (a >> 8) | (a >> 16) | (a >> 32);
b = b | (b >> 1) | (b >> 2) | (b >> 4) | (b >> 8) | (b >> 16) | (b >> 32);
for (;;) {
unsigned long na = a << 1;
if (na <= a)
break;
a = na;
}
return (a & b) ? 1 : 0;
}
int main(int argc, char **argv)
{
unsigned long a, b;
char *endptr;
if (argc < 3) {
printf("supply two unsigned long integers in C form\n");
return EXIT_FAILURE;
}
a = strtoul(argv[1], &endptr, 0);
if (*endptr != 0) {
printf("%s is garbage\n", argv[1]);
return EXIT_FAILURE;
}
b = strtoul(argv[2], &endptr, 0);
if (*endptr != 0) {
printf("%s is garbage\n", argv[2]);
return EXIT_FAILURE;
}
if (might_be_mul_oflow(a, b))
printf("might be multiplication overflow\n");
{
unsigned long c = a * b;
printf("%lu * %lu = %lu\n", a, b, c);
if (a != 0 && c / a != b)
printf("confirmed multiplication overflow\n");
}
return 0;
}
약간의 테스트: (64비트 시스템의 경우):
$ . / uflow 0x3 0x3FFFFFFFFFFFFFFFFFFFFFF3 * 4611686018427387903 = 13835058055282163709 $ . / uflow 0x7 0x3FFFFFFFFFFFFFFFFFFFF곱셈 오버플로일 수 있음7 * 4611686018427387903 = 13835058055282163705확인 곱셈 오버플로 $ . / uflow 0x4 0x3FFFFFFFFFFFFFFFFFFFFFF곱셈 오버플로일 수 있음4 * 4611686018427387903 = 18446744073709551612 $ . / uflow 0x5 0x3FFFFFFFFFFFFFFFFFFFF곱셈 오버플로일 수 있음5 * 4611686018427387903 = 4611686018427387899확인 곱셈 오버플로
의 순서might_be_mul_oflow적어도 데스크톱 워크스테이션, 서버 및 모바일 디바이스에 사용되는 메인스트림 프로세서에서는 분할 테스트보다 속도가 느리다는 것은 거의 확실합니다.적절한 분할 지원이 없는 칩에서는 도움이 될 수 있습니다.
이 조기 거부 테스트를 할 수 있는 다른 방법이 있다는 생각이 듭니다.
숫자 한 쌍으로 시작하죠
arng그리고.brng에 초기화되어 있습니다.0x7FFF...FFFF그리고.1.한다면
a <= arng그리고.b <= brng우리는 오버플로가 없다고 결론지을 수 있다.그렇지 않으면, 우리는
arng오른쪽으로, 그리고 시프트brng왼쪽에 1비트 추가brng그 때문에,0x3FFF...FFFF그리고.3.한다면
arng0, 종료, 그렇지 않으면 2에서 반복합니다.
이 기능은 다음과 같습니다.
int might_be_mul_oflow(unsigned long a, unsigned long b)
{
if (!a || !b)
return 0;
{
unsigned long arng = ULONG_MAX >> 1;
unsigned long brng = 1;
while (arng != 0) {
if (a <= arng && b <= brng)
return 0;
arng >>= 1;
brng <<= 1;
brng |= 1;
}
return 1;
}
}
64비트 변수를 사용하는 경우 nsb(var) = { 64 - clz(var); }인 '유효 비트 수'를 구현합니다.
clz(var) = GCC 및 Clang에 대한 기본 제공 명령인 var에서 선행 0을 카운트하거나 CPU의 인라인 어셈블리에서 사용할 수 있습니다.
이제 nsb(a * b) <= nsb(a) + nsb(b)라는 사실을 사용하여 오버플로우를 확인합니다.작을 때는 항상 1개 작습니다.
참조 GCC: 내장 함수: int __builtin_clz(부호 없는 int x) 최상위 비트 위치에서 시작하는 x의 선행 0비트 수를 반환합니다.x가 0이면 결과는 정의되지 않습니다.
저는 오늘 이 문제에 대해 고민하다가 우연히 이 질문을 하게 되었고, 저의 생각이 이 결과로 이어졌습니다.TLDR은 코드 몇 줄(라이너 하나일 수도 있음)만 사용하고 개념적으로 비교적 단순한 것으로 간단한 수학이 있다는 점에서 "고급"이지만, 이것은 대부분 "흥미롭다"고 저는 테스트하지 않았습니다.
부호 없는 정수를 기수 2^n이 있는 단일 자릿수로 간주하는 경우, 여기서 n은 정수 내의 비트 수이며, 이러한 숫자를 단위 원 주위의 라디안에 매핑할 수 있습니다.
radians(x) = x * (2 * pi * rad / 2^n)
정수가 넘치면 원을 감싸는 것과 같습니다.따라서 이행을 계산하는 것은 곱셈이 원을 감싸는 횟수를 계산하는 것과 같습니다.원을 감싸는 횟수를 계산하기 위해 라디안(x)을 2pi 라디안으로 나눕니다.
wrap(x) = radians(x) / (2*pi*rad)
= (x * (2*pi*rad / 2^n)) / (2*pi*rad / 1)
= (x * (2*pi*rad / 2^n)) * (1 / 2*pi*rad)
= x * 1 / 2^n
= x / 2^n
그 때문에, 이하와 같이
wrap(x) = x / 2^n
말이 되네.예를 들어 기수 10을 가진 15의 숫자가 감기는 횟수는 다음과 같습니다.15 / 10 = 1.5 1.단, 여기서는2 자리수를 사용할 수 없습니다(단일 2^64 자리수로 제한되어 있다고 가정합니다).
예를 들어 a * b가 있다고 가정하면 기수 R을 사용하여 캐리어를 다음과 같이 계산할 수 있습니다.
Consider that: wrap(a * b) = a * wrap(b)
wrap(a * b) = (a * b) / R
a * wrap(b) = a * (b / R)
a * (b / R) = (a * b) / R
carry = floor(a * wrap(b))
, 「」를 예로 들어 .a = 9 ★★★★★★★★★★★★★★★★★」b = 5 45)의9 * 5 = 45를 참조해 주세요.
wrap(5) = 5 / 10 = 0.5
a * wrap(5) = 9 * 0.5 = 4.5
carry = floor(9 * wrap(5)) = floor(4.5) = 4
오버플로가 를 들어 0일 경우).예를 들어 다음과 같습니다.a = 2,b=2.
C/C++(컴파일러와 아키텍처가 지원하는 경우)에서는 롱 더블을 사용해야 합니다.
다음과 같은 것이 있습니다.
long double wrap = b / 18446744073709551616.0L; // this is b / 2^64
unsigned long carry = (unsigned long)(a * wrap); // floor(a * wrap(b))
bool overflow = carry > 0;
unsigned long c = a * b;
10c의 로, 즉, 밑면 10c의 '자리'입니다.9 * 9 = 81,carry = 8 , , , , 입니다.c = 1.
이론적으로는 흥미롭기 때문에 공유하려고 했습니다만, 컴퓨터의 부동소수점 정밀도에 관한 중요한 주의사항이 있습니다.더블을 하면, 수치에 수 .wrap변수: 컴파일러/아카이브가 롱 더블에 얼마나 많은 유효 숫자를 사용하는지에 따라 다릅니다.확실하기 위해서는 20자리가 더 필요합니다.이 결과의 또 다른 문제는 부동소수점이나 나눗셈을 사용하는 것만으로 다른 솔루션과 같은 성능을 발휘하지 못할 수 있다는 것입니다.
언급URL : https://stackoverflow.com/questions/1815367/catch-and-compute-overflow-during-multiplication-of-two-large-integers
'IT이야기' 카테고리의 다른 글
| Vuelidate를 사용하는 상위 구성 요소의 하위 구성 요소에서 양식 입력 필드 검증 (0) | 2022.05.28 |
|---|---|
| VueJS v-bind가 kebab-case와 함께 작동하지 않음 (0) | 2022.05.28 |
| vuex의 저장 상태가 localStorage에 저장되지 않는 이유는 무엇입니까? (0) | 2022.05.28 |
| Optional.of.OfNullable보다 Optional.of를 사용하는 이유 (0) | 2022.05.28 |
| x86_64 어셈블러에서 RBP 레지스터의 목적은 무엇입니까? (0) | 2022.05.28 |