整數不溢出

-1

如何計算hypot兩個整數，每個小於2^63，這樣在任何中間計算都不會溢出64位？（如傳統方法中的x^2+y^2）。整數不溢出

鏈接的文章提到了一個浮點算法，由於整數爲0，所以不可以使用，因爲它是t = t/x;。

我能找到的最接近的算法是從here但不幸的是它不夠精確：

int ihypot(xd1, yd1) 
    double xd1, yd1; 
{ 
    register  x1 = (int)xd1, 
       y1 = (int)yd1, 
       x2 = 0, 
       y2 = 0; 

    if ((x2 -= x1) < 0) x2 = -x2; 
    if ((y2 -= y1) < 0) y2 = -y2; 
    return (x2 + y2 - (((x2>y2) ? y2 : x2) >> 1)); 
}

來源

2017-05-10 user22698

你改變什麼，問題是現在約64位整數？！ –

@PascalCuoq它從來就不是32位的，它是關於溢出的，而32位只是一個例子。 – user22698

爲什麼你這樣聲明函數參數？ –

與整數實現時，你總是可以從相當於數學公式開始：

R = 2 ^-30 *（X * SQRT（2 + 2 * Y/X））

甲典型的32位處理器應該允許您訪問64/32 - > 32分頻器，並在兩個寄存器中提供輸入。這個除法可以用來計算* y/x。您的編程語言可能會或不會讓您訪問它。在生成涉及64位中間結果的計算的32位代碼時，不要低估優化編譯器的技能。

類似地，典型的32位處理器應該爲「x * ...」提供一個32 * 32-> 64的乘法，結果在兩個寄存器中。

最後乘以2 ^-30相當於移位和控制32 * 32-> 64乘法結果的兩個寄存器。

GCC almost管理僅使用32位指令來產生簡單的代碼，但它丟棄該球在一個點，並調用一個外部多精度除法功能：

#include <stdint.h> 

uint32_t integer_sqrt(uint32_t); 

/*@ requires x >= y; */ 
uint32_t hypot(uint32_t x, uint32_t y){ 
    return integer_sqrt(0x40000000 + (uint32_t) ((uint64_t)y * 0x40000000/x)) * (uint64_t) x/0x40000000 ; 
}

32位組件結果：

hypot: 
     pushl %edi 
     pushl %esi 
     xorl %edi, %edi 
     pushl %ebx 
     movl 16(%esp), %ebx 
     movl %edi, %edx 
     xorl %edi, %edi 
     subl $16, %esp 
     movl 36(%esp), %esi 
     pushl %edi 
     pushl %ebx 
     shldl $30, %esi, %edx 
     movl %esi, %eax 
     sall $30, %eax 
     pushl %edx 
     pushl %eax 
     call __udivdi3 
     addl $20, %esp 
     addl $1073741824, %eax 
     pushl %eax 
     call integer_sqrt 
     mull %ebx 
     addl $16, %esp 
     popl %ebx 
     popl %esi 
     shrdl $30, %edx, %eax 
     popl %edi 
     ret

編輯：

如果你只想使用32 * 32> 32乘法，你必須計算N = LOG 2（x）和，如果N> 15，normaliz ex和由N-15它們右移Y（移位相同的量留下的最終結果），實際上實現下式：

R = 2 ^N-15 * SQRT（（X/2 ^{Ñ -15}） +（Y/2 ^N-15））

如果N≤1，只要使用通常的公式R = SQRT（X + Y ）

來源

2017-05-10 12:13:48

非常感謝！但是，我不確定這對我有用：是不是'2^30 * y'問題？如果我可以乘以'y'以使它溢出32位，我可以很好地使用'y * y'，我儘量避免。我的意思是'2^30 * 2^30 + 2^30 * 2^30 <2^64'。而32位僅僅是一個例子，如果我需要64位呢？但它可能是我沒有完全理解你的答案... – user22698

@ user22698如果你從普通公式sqrt（y \ * y + x \ * x）開始，並且始終使用64位操作，位加法和64位sqrt。該解決方案僅依賴於32 * 32-> 64乘法和64/32-> 32除法（以及位操作），這是每個實際的32位處理器所具有的。唯一的問題是從高級編程語言訪問這些32 * 32 - > 64和64/32 - > 32操作。 GCC幾乎設法將我的C代碼轉換爲簡單的32位操作，儘管它使用了64位類型。 –

@ user22698另外，如果您始終使用64位操作，並從公式sqrt（y \ * y + x \ * x）開始，那麼您將有添加中溢出的風險。 –

我認爲你可以重寫給定的表達式，以便每個操作之後的每個操作都小於2^64。例如：

通過乘法之前取平方根，就可以確保個人數字不會超過2^64。

來源

2017-05-19 05:19:56 TheChetan

如果你沒事使用浮點，可以使用表達

a/cos(atan2(b,a))

其中a和b是輸入

來源

2017-05-19 08:45:13 ceilingcat

回答

相關問題