java - 需要一种提供“余数”的平方根算法

Question

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

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

我正在使用 biginteger，它有一个非常好的 gcd() 方法和一个仅限于正参数的 pow() 方法（这是有道理的，除非你试图完全按照我想做的事情去做。

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

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

澄清一下：我打算添加虚数，所以我计划这样的结果：

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

没有长长的小数流。

Answer 1

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

有许多计算平方根的方法。有了这些，您可以将结果表示为整数加上小于 1 的余数。

Answer 2

也许尝试找到小于您的数字的最高完美平方。这将为您提供等式的一部分，然后您只需要处理剩余部分，即您的数字与您找到的完美平方之间的差异。随着数字变大，这也会降低，但可能不会那么快。