Click here to Skip to main content
15,908,834 members
Please Sign up or sign in to vote.
2.71/5 (3 votes)
See more:
how i get sqrt() to biginteger number in c++
Posted

I don't know the subject thoroughly but since you are dealing with a type of integer, you probably will need to write the method yourself. Root functions generally provide floating point results (even for integer input), and I am not aware of a generalized large float type (or library).
 
Share this answer
 
Comments
Espen Harlinn 14-Apr-13 17:24pm    
The GNU MP: http://gmplib.org/
H.Brydon 14-Apr-13 17:40pm    
Yeah, good link, thanks. I owe you a +5 (watch for it)
Espen Harlinn 14-Apr-13 17:41pm    
Have a look at: http://www.codeproject.com/Articles/562109/DBTool-for-Oracle-Part-1
You might use the GMP library[^].
 
Share this answer
 
Comments
H.Brydon 13-Apr-13 19:45pm    
[edit]Yeah you're right, looks good. +5 ... I didn't know about that library[/edit]
nv3 14-Apr-13 16:53pm    
GMP would be my first stop as well. My 5.
Here my stab at porting the algorithm from Solution 2 to BigInteger.

C++
using namespace System;
using namespace System::Numerics;
...
        static BigInteger SQRT(BigInteger y)
        {
            if (y <= BigInteger::Zero)
            {
                if (y != BigInteger::Zero)
                {
                    return BigInteger::Negate(BigInteger::One);
                }
                return BigInteger::Zero;
            }

            /* select a good starting value using binary logarithms: */
            BigInteger x_old(4);
            BigInteger testy(16);   // testy = x_old ^ 2

            while(true)
            {
                if ( y <= testy)
                {
                    break;
                }
                testy <<= 2L;
                x_old <<= 1L;
            }
            /* x_old >= sqrt(y) */
            /* use the Babylonian method to arrive at the integer square root: */
            BigInteger x_new;
            while(true)
            {
                x_new = (BigInteger::Add( (y / x_old), x_old ) ) / 2L;
                if (x_old <= x_new)
                {
                    break;
                }
                x_old = x_new;
            }
            return x_old;
        }

Hope that helps.
 
Share this answer
 
v2
There are a lot of integer sqrt implementations, as a first step you should search for one that contains only very simple operations on integers - operations that you can easily implement for big integers (like addition, shift, ...). For example this site contains a few integer sqrt algorithms: http://www.codecodex.com/wiki/Calculate_an_integer_square_root[^]
Choose an algorithm and write it with big integers instead of normal integers using your own biginteger library. Writing a bigint library is fun if you have time and interest. Of course you can use a third party biginteger library if it's allowed.
 
Share this answer
 

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



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900