需要一种提供“余数”的平方根算法
我正在编写一个不使用小数的计算器（仅支持有理数），但我希望能够执行平方根的版本。
当平方根函数被按下（例如）数字 12 时，我想简化/“减少”平方根并返回 2*sqrt(3) - 将其转换为 (2*2) * 3 并将 sqrt(2*2) 提取为 2。
我使用 biginteger，它有一个非常好的 gcd() 方法和一个仅限于正参数的 pow() 方法（除非您试图完全按照我的方式进行操作，否则这是有意义的）我 我
我可以想出一些迭代的方法来做到这一点，但它们可能需要一段时间来处理数百位数字范围内的数字，
希望有一些可爱的、简单的、非迭代的技巧。只是
为了澄清：我打算添加虚数，所以我计划这样的结果：
17 + 4i √3
-----------
9
没有长的小数流。
I'm writing a calculator without using decimals (supports only Rational numbers), but I'd like to be able to do a version of square root.
When a square root function is pressed for (say) the number 12, I'd like to just simplify/"reduce" the square root and return 2*sqrt(3)--by it into (2*2) * 3 and extracting the sqrt(2*2) as 2.
I'm using biginteger which has a very nice gcd() method and a pow() method that is restricted to positive parameters (which makes sense unless you are trying to do exactly what I'm trying to do.
I could come up with a few iterative ways to do this but they may take a while with numbers in the hundreds-of-digits range.
I'm hoping there is some cute, simple, non-iterative trick I haven't been exposed to.
Just to clarify: I have the intent to add imaginary numbers so I'm planning on results like this:
17 + 4i √3
-----------
9
Without long streams of decimals.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
本质上，您所要求的是找到所有重复的素因数。由于您处理的是数百位数字范围内的数字，因此我将在这里大胆猜测，一般来说没有好的方法可以做到这一点。否则公钥密码学将突然变得有些不稳定。
有多种计算平方根的方法。通过这些，您可以将结果表示为整数加上小于 1 的余数。
What you're asking, in essence, is to find all repeated prime factors. Since you're dealing with numbers in the hundreds-of-digits range, I'm going to venture a guess here that there are no good ways to do this in general. Otherwise public key cryptography will all of a sudden be on somewhat shaky ground.
There are a number of methods of computing the square root. With those, you can express the result as an integer plus a remainder less than 1.
也许尝试找到小于您的数字的最高完美平方。这将为您提供方程的一部分，然后您只需要处理余数部分，即您的数字与您找到的完美平方之间的差。随着数字变大，这种情况也会降低，但速度可能不会那么快。
Maybe try finding the highest perfect square that is less than your number. That will give you part of the equation, then you would only need to handle the remainder part which is the difference between your number and the perfect square you found. This would degrade as numbers get large as well, but perhaps not as fast.