作为一个个人项目,我正在为我的一个宠物项目实现一个任意精度数字类型。
我已经知道所有流行的、经过测试的、健壮的库都是这样做的。
我正在研究该区域,并试图弄清楚是否有某种方法可以大致预测操作是否会在我实际进行计算之前导致溢出。我也不太关心假阳性。
我希望能够使用适合计算的最小空间。如果计算将保持在其本地边界内,我将保留它。
例如:Multiplying two 64 bit Integers if each are large enough will cause an overflow.
我想检测到这一点,只有当结果可能超过64位分辨率时,才将数字上转换为我的数字类型。在这个实验中,我将使用带符号的数字。
什么是检测溢出/下流的最合理、最有效的方法?
只取两个数的最高位,左移一位,如果结果(例如:乘法)这些数会导致溢出,你有一个很好的机会溢出
虽然它不精确,但它非常快,并且是一个很好的指示符,表明您需要为结果使用更大的数据类型。
这可能只对运算符昂贵的大型数据类型有意义,对于简单的事情(即使是64位数字),我认为您可以依赖CPU的内置算术。当超过64位
这是John Regehr关于这个的论文
进行朴素计算并检测是否发生溢出几乎总是更容易(而且通常更快)。在进行计算之前,您想要检测的可能性是否有特定的原因?
一旦计算完成,通常很容易检测到是否发生溢出。因为朴素操作很便宜,所以即使发生溢出,这也不会增加太多的计算成本,即使最终需要重做一些工作。(通常,你甚至不需要这样做)。
这里有一个(非常)简单的例子:如果我将两个无符号64位数字相加,我可以通过将总和与其中一个加数进行比较来检查溢出—如果它小于,则发生溢出。因此,在计算之后检测溢出只需要一次比较(确实非常便宜)。