java - 需要一个提供 "remainder"的平方根算法

Question

我正在编写一个不使用小数的计算器(仅支持有理数)，但我希望能够计算平方根的版本。

当平方根函数被按下(例如)数字 12 时，我想简化/“减少”平方根并返回 2*sqrt(3) - 将其转换为 (2*2) * 3 并提取 sqrt(2*2) 作为 2。

我正在使用 biginteger，它有一个非常好的 gcd() 方法和一个仅限于正参数的 pow() 方法(这是有意义的，除非您试图完全按照我想要做的方式进行。

我可以想出一些迭代方法来做到这一点，但对于数百位数字范围内的数字，它们可能需要一段时间。

我希望有一些我没有接触过的可爱、简单、非迭代的技巧。

只是澄清一下:我打算添加虚数，因此我计划得到这样的结果:

17 + 4i √3  
-----------  
     9

没有长串的小数。

Answer 1

本质上，您所要求的是找到所有重复的素因数。由于您处理的是数百位数字范围内的数字，因此我将在这里大胆猜测，一般来说没有好的方法可以做到这一点。否则公钥密码学将突然变得有些不稳定。

有多个 methods of computing the square root 。通过这些，您可以将结果表示为整数加上小于 1 的余数。