BigInteger的平方根算法 [英] Square root algorithm for BigInteger

问题描述

我在System.Numerics中使用BigInteger类，而我的问题是该类中没有Sqrt的内置函数.所以我必须设计自己的，而我用了这个:

Im using the BigInteger class in System.Numerics, and my problem is that there is no build in function for Sqrt in the class. So I would have to design my own, and I used this:

Private Function SqrtN(ByVal N As BigInteger) As BigInteger
    If (0 = N) Then Return 0
    Dim n1 As BigInteger = (N >> 1) + 1
    Dim n2 As BigInteger = (n1 + (N / n1)) >> 1
    While (n2 < n1)
        n1 = n2
        n2 = (n1 + (N / n1)) >> 1
    End While
    Return n1
End Function

这是 Newton–Raphson [ ^ ]方法.问题是，现在有人在寻找整数的平方根时有更快或更佳的方法吗?

Which is the Newton–Raphson[^] method. The question is, does anyone now of a faster or better way for finding square root of integers?

推荐答案

我能从中记住的所有sqrt()最佳方法在数学运行时库(如恐龙所称的！)上进行的工作涉及初始有理函数逼近(几个三次方或大约三次方的商)，然后进行一次(或两个)NR迭代以进行清理.每次迭代都将答案中有效位的数量加倍(二次收敛)，因此在我们所生活的56位16位尾数的世界中，它们都运行良好.多精度除法是非常昂贵的操作，为节省除法而进行的其他多次乘法得到了回报.在您的情况下，我怀疑初始近似不会有太大帮助，因为您将要进行很多N-R迭代.当然，这取决于您的电话号码大小.例如，如果您使用的位数少于128位，那么有理函数可能会有所值，但是如果您使用的是非常大的数字，则无济于事.

祝您玩得开心，并感谢您有幸怀念！

彼得

All the best methods for sqrt() that I can remember from working on math runtime libraries (as the dinosaurs called them!) involved an initial rational function approximation (the quotient of a couple of cubics or thereabouts) followed by one (or maybe two) N-R iteration to clean up. Each iteration approximately doubles the number of significant bits in the answer (quadratic convergence), so in the 56-bit-mantissa-on-16-bit-hardware world we lived in then it all worked well. Multiple precision division was the very expensive operation, and a few more multiplications to save a division paid off. In your case, I suspect that initial approximation won''t help much, because you''re going to be doing so many N-R iterations. Depends on the size of your numbers, of course. If you''re playing with, say, less than 128 bits, then the rational function might be worth a bit, but if you''re playing with really big numbers, nothing much will help.

Have fun, and thanks for the opportunity to reminisce!

Peter

这篇关于BigInteger的平方根算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！