整数不溢出

-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

回答

相关问题