如何避免pow函数用数字除法时出现整数溢出

Question

我有以下语句。

d = (pow(a,2*l+1)+1)/(val+1);  

这里，

• val、a和l是与问题无关的变量
• 分子可以超过长整型范围
• 分母是分子的除数

但最终答案d肯定会在long longint范围内。如何在不损失精度的情况下计算d？我更喜欢一个不将它们转换为数组并使用小学乘法和除法的答案。

Answer 1

我现在没有时间写一个正确的答案；如果有机会的话，我稍后会扩大这个范围。其基本思想是使用小学算法，使用分母幂的"数字"。在谷歌上搜索"Schrage乘法"或在这里查找参考资料。

Answer 2

我希望操作数也是整数

1. 我会通过平方来使用功率，而不是pow

   见平方的整数幂

2. 在迭代#1时

   每次booth子结果和分母都可以被2整除，以保持pow结果较小，同时不损失精度或结果的正确性。所以每次subsult和Denominator的LSB位都是零右移1位。