Square root algorithm for BigInteger

Question

0.00/5 (No votes)

See more:

.NET4.5

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:

VB

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

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

Posted 2-Sep-12 12:01pm

Kenneth Haugland

Updated 2-Sep-12 13:29pm

v3

Add a Solution

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Peter_in_2780 · Accepted Answer · 2012-09-02T14:04:00

Solution 1

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

Posted 2-Sep-12 14:04pm

Peter_in_2780

Comments

Kenneth Haugland 2-Sep-12 21:07pm

Yes, there is some gems among the earlyer computer programming, but I suspect that what you are talking about is stored deep inside some hardware, especially with GPU and 3D rendering. But Im deling primarialy with really big numbers, and I assumed that if I could cast the BigInteger to an normal integer I could simply use the Math.Sqrt function. That is simple to just use Integer.TryCast and see if it is possible to use the Math class library.

Peter_in_2780 2-Sep-12 21:36pm

Yes, what we did in code 40-odd years ago is now well and truly buried inside CPU/GPU hardware. My point is that the same general considerations apply in your scaled-up problem.
How big are the numbers you are dealing with? The answer has a big bearing on whether it's worth trying to do something other than N-R all the way.

Kenneth Haugland 2-Sep-12 21:46pm

The problem is I dont really know, as I would be using it to find prime numbers:
http://www.codeproject.com/Articles/429694/Finding-prime-numbers
But I didnt realise that the Math.Sqrt() made an implicid casting of the BigInteger to an Integer. So they could be huge for all I know.

Peter_in_2780 2-Sep-12 22:14pm

Just googled a bit and found a couple you should take a look at.
This one http://bigintegers.blogspot.com.au/2010/11/square-division-power-square-root.html looks like they have put a lot of effort into tuning (and the code's all there to see!)
http://www.extremeoptimization.com/Documentation/Reference/Extreme.Mathematics.BigInteger.Sqrt.aspx looks like a pretty comprehensive BigInteger math package

Kenneth Haugland 2-Sep-12 22:36pm

Thanks, I expected somthing like that. It lacks some explination of why its so, but so does this:
http://www.codeproject.com/Articles/69941/Best-Square-Root-Method-Algorithm-Function-Precisi
Guess I have some work to do ;)