Square Root Of java.math.BigInteger

Discussion in 'Java' started by j1mb0jay, May 21, 2008.

  1. j1mb0jay

    j1mb0jay Guest

    I was very surprised to see that java did not have a square root method
    at all of the java.math.BigInteger class, why is this?

    I have tried to write a simple trial and error Square Root function that
    works with BigIntegers. It does not return decimal values and instead
    returns null if the number is decimal, or rounds the numbers depending.

    The code is below, i am currently trying to re-implement my prime checker
    using BigIntegers and require this method, it seems to find the square
    root of several thousand digit numbers in just over a second which i
    think is pretty good, please can i have some thoughts on how to improve
    the code.

    Regards j1mb0jay.

    --------------------Some Code-------------------------------------

    /**
    * A number is square free if it is divisible by no perfect
    square (except 1).
    *
    * @param testSubject
    * @return - true if the "testSubject" is a square free number.
    */
    public static boolean isSquareFree(double testSubject)
    {
    double answer;
    for(int i = 1; i < testSubject; i++)
    {
    answer = Math.sqrt(testSubject / (double)i);
    if(answer < 1)
    return false;
    if(answer % 1.0 == 0)
    return false;
    }
    return true;
    }
    j1mb0jay, May 21, 2008
    #1
    1. Advertising

  2. j1mb0jay

    j1mb0jay Guest

    On Wed, 21 May 2008 12:40:58 +0100, bugbear wrote:

    > j1mb0jay wrote:
    >> I was very surprised to see that java did not have a square root method
    >> at all of the java.math.BigInteger class, why is this?

    >
    > Probably because the result isn't a BigInteger
    >
    >
    >> I have tried to write a simple trial and error Square Root function
    >> that works with BigIntegers. It does not return decimal values and
    >> instead returns null if the number is decimal, or rounds the numbers
    >> depending.
    >>
    >> The code is below, i am currently trying to re-implement my prime
    >> checker using BigIntegers and require this method, it seems to find the
    >> square root of several thousand digit numbers in just over a second
    >> which i think is pretty good, please can i have some thoughts on how to
    >> improve the code.

    >
    > Look up "numerical analysis". It's what you're doing, albeit
    > unknowingly.
    >
    > BugBear


    Why would the result of square rooting an BigInteger not be a BigInteger
    does that not depend on the number you are square rooting, what is the
    square root of 2^132874985327329875329 is that not a BigInteger itself ???

    I will look up numerical analysis and see if i missed anything out.

    Regards j1mb0jay
    j1mb0jay, May 21, 2008
    #2
    1. Advertising

  3. j1mb0jay

    j1mb0jay Guest

    Posted the wring code, the code is below LOL !!!!


    -------------Square Root Code --------------------

    package math;

    import java.math.BigInteger;
    public class SquareRoot
    {
    public static BigInteger squareRoot(BigInteger testSubject,
    boolean round)
    {
    int digitsInTestSubject = testSubject.toString().length();

    double sPoint = (double)digitsInTestSubject / 2.0;

    BigInteger startPoint = BigInteger.valueOf(Math.round
    (sPoint));
    BigInteger lastGuess = null;
    BigInteger guess = null;

    BigInteger lower= null;
    BigInteger upper = null;

    if(digitsInTestSubject < 3)
    {
    lastGuess = BigInteger.valueOf(0L);
    lower = lastGuess;
    guess = BigInteger.valueOf(5L);
    upper = BigInteger.valueOf(10L);

    }
    else
    {
    startPoint = startPoint.subtract
    (BigInteger.valueOf(1L));
    startPoint = pow(BigInteger.valueOf
    (10L),startPoint);

    lastGuess = startPoint;
    lower = lastGuess;

    guess = startPoint.multiply(BigInteger.valueOf
    (5L));

    upper= startPoint.multiply(BigInteger.valueOf
    (10L));
    }

    int guesses = 0;
    while(true)
    {
    guesses++;
    BigInteger ans = guess.pow(2);

    if(ans.compareTo(testSubject) == 0)
    {
    break;
    }

    if(lastGuess.compareTo(guess) == 0)
    {
    if(round)
    {
    if(guess.compareTo(testSubject)
    == 1)
    {
    guess = guess.subtract
    (BigInteger.valueOf(1));
    }
    else
    {
    guess = guess.add
    (BigInteger.valueOf(1));
    }
    }
    else
    {
    guess = null;
    }
    break;
    }

    if(ans.compareTo(testSubject) == 1)
    {
    BigInteger tmp;

    if(guess.compareTo(lastGuess) == 1)
    {
    upper = guess;
    tmp = upper.subtract(lower);
    tmp = tmp.divide
    (BigInteger.valueOf(2L));
    tmp = lower.add(tmp);
    }
    else
    {
    upper = guess;
    tmp = upper.subtract
    ( upper.subtract(lower).divide(BigInteger.valueOf(2L) ));
    }

    lastGuess = guess;
    guess = tmp;
    }
    else
    {
    BigInteger tmp;
    if(guess.compareTo(lastGuess) == 1)
    {
    lower = guess;
    tmp = upper.subtract(lower);
    tmp = tmp.divide
    (BigInteger.valueOf(2L));
    tmp = upper.subtract(tmp);
    }
    else
    {
    lower = guess;
    tmp = lower.add( upper.subtract
    (lower).divide(BigInteger.valueOf(2L) ));
    }

    lastGuess = guess;
    guess = tmp;
    }
    }

    return guess;
    }

    public static BigInteger pow(BigInteger testSubject, BigInteger
    pow)
    {
    BigInteger index = BigInteger.valueOf(1L);
    BigInteger retVal = BigInteger.valueOf(10L);

    while(index.compareTo(pow) != 0)
    {
    retVal = retVal.multiply(testSubject);
    index = index.add(BigInteger.valueOf(1L));
    }

    return retVal;
    }
    }
    j1mb0jay, May 21, 2008
    #3
  4. j1mb0jay

    j1mb0jay Guest

    On Wed, 21 May 2008 08:06:47 -0400, Larry A Barowski wrote:

    > "j1mb0jay" <> wrote in message
    > news:...
    >>I was very surprised to see that java did not have a square root method
    >> at all of the java.math.BigInteger class, why is this?
    >>
    >> I have tried to write a simple trial and error Square Root function
    >> that works with BigIntegers. It does not return decimal values and
    >> instead returns null if the number is decimal, or rounds the numbers
    >> depending.

    >
    > Find the approximate square root using the first few significant bits
    > and the magnitude, then use Newton's method starting there.
    >
    > But if all you need is a working implementation, I'm sure you can find
    > several with a web search.


    Whats the first few significant bits of a number that is made up of
    several thousand if not a few million bits. I sure i could find a few on
    the Internet, but would like to try and build my own. I already have a an
    implementation that works, just would like to try and make it a little
    more efficient.

    Regards j1mb0jay
    j1mb0jay, May 21, 2008
    #4
  5. j1mb0jay

    j1mb0jay Guest

    On Wed, 21 May 2008 07:59:26 -0400, Lew wrote:

    > j1mb0jay wrote:
    >> Why would the result of square rooting an BigInteger not be a
    >> BigInteger does that not depend on the number you are square rooting,
    >> what is the square root of 2^132874985327329875329 is that not a
    >> BigInteger itself ???

    >
    > What is the square root of 2?
    >
    > What should be the square root of BigInteger.valueOf( 2 )?


    If the number is less than (2^64)-1 then i wouldn't use a BigInteger
    Object to calculate the square root. I would just use a long.

    But in the case of my program it would return null as i am only
    interested if the number has a perfect square not an accurate decimal
    answer. Although their is an option to return 1 as that is the correct
    rounded answer.

    Square root of 2 is 1.414213562. which rounds to 1.

    Regards j1mb0jay
    j1mb0jay, May 21, 2008
    #5
  6. j1mb0jay

    j1mb0jay Guest

    On Wed, 21 May 2008 08:46:15 -0400, Eric Sosman wrote:

    > j1mb0jay wrote:
    >>
    >> Why would the result of square rooting an BigInteger not be a
    >> BigInteger

    >
    > Your mission, should you choose to accept it, is to find
    > a value for `root' that keeps the `assert' in this fragment from firing:
    >
    > BigInteger square = new BigInteger("-1000"); BigInteger root = /*
    > supply your candidate value here */ ; assert
    > root.multiply(root).equals(square);
    >
    > As usual, if you or any of your team are killed or captured, the
    > Secretary will declare the whole enterprise irrational and imaginary.


    A square number is a number multiplied by itself. When you multiply two
    identical numbers you always get a positive number !!! - When we are not
    in the matix (the real world)

    But if you are going all imaginary on me then maybe the answer might be
    31.622776602i - rather complex !!!!

    Although you did use the Object.equals() rather than the BI.compareTo()
    which makes me wonder !!

    Regards j1mb0jay
    j1mb0jay, May 21, 2008
    #6
  7. j1mb0jay

    Tom Anderson Guest

    On Wed, 21 May 2008, j1mb0jay wrote:

    > I was very surprised to see that java did not have a square root method
    > at all of the java.math.BigInteger class, why is this?


    People don't often do roots on integers. Roots tend to be a continuous
    maths thing.

    > I have tried to write a simple trial and error Square Root function that
    > works with BigIntegers. It does not return decimal values and instead
    > returns null if the number is decimal, or rounds the numbers depending.


    You could look and see if anyone's made a bigint maths library for java
    that does square roots. There's been plenty of work on this kind of thing
    - look up "integer square root".

    The standard approach is to use an iterative process based on Newton's
    method to find roots. You can use 1 for the initial guess, or speed things
    up by using 1 << ((x.bitLength()) / 2).

    Although this guy's figured out something faster, with no multiplies:

    http://lists.apple.com/archives/Java-dev/2004/Dec/msg00302.html

    > The code is below, i am currently trying to re-implement my prime
    > checker using BigIntegers and require this method, it seems to find the
    > square root of several thousand digit numbers in just over a second
    > which i think is pretty good, please can i have some thoughts on how to
    > improve the code.
    >
    > --------------------Some Code-------------------------------------
    >
    > /**
    > * A number is square free if it is divisible by no perfect
    > square (except 1).
    > *
    > * @param testSubject
    > * @return - true if the "testSubject" is a square free number.
    > */
    > public static boolean isSquareFree(double testSubject)
    > {
    > double answer;
    > for(int i = 1; i < testSubject; i++)
    > {
    > answer = Math.sqrt(testSubject / (double)i);
    > if(answer < 1)
    > return false;
    > if(answer % 1.0 == 0)
    > return false;
    > }
    > return true;
    > }
    >


    Okay, firstly, this isn't a square root algorithm. Is this the right code?

    Secondly, you're using doubles to represent integers. Stop that. A double
    is effectively a 53-bit integer with a scale field. It's got less useful
    bits than a long. This code *will* be incorrect for large enough numbers.
    And god alone knows how modulus of floating-point numbers works (if he's
    read the IEEE 754 spec, that is).

    tom

    --
    I need a proper outlet for my tendency towards analytical thought. --
    Geneva Melzack
    Tom Anderson, May 21, 2008
    #7
  8. j1mb0jay

    j1mb0jay Guest

    On Wed, 21 May 2008 14:41:01 +0100, Tom Anderson wrote:

    > On Wed, 21 May 2008, j1mb0jay wrote:
    >
    >> I was very surprised to see that java did not have a square root method
    >> at all of the java.math.BigInteger class, why is this?

    >
    > People don't often do roots on integers. Roots tend to be a continuous
    > maths thing.
    >
    >> I have tried to write a simple trial and error Square Root function
    >> that works with BigIntegers. It does not return decimal values and
    >> instead returns null if the number is decimal, or rounds the numbers
    >> depending.

    >
    > You could look and see if anyone's made a bigint maths library for java
    > that does square roots. There's been plenty of work on this kind of
    > thing - look up "integer square root".
    >
    > The standard approach is to use an iterative process based on Newton's
    > method to find roots. You can use 1 for the initial guess, or speed
    > things up by using 1 << ((x.bitLength()) / 2).
    >
    > Although this guy's figured out something faster, with no multiplies:
    >
    > http://lists.apple.com/archives/Java-dev/2004/Dec/msg00302.html
    >
    >> The code is below, i am currently trying to re-implement my prime
    >> checker using BigIntegers and require this method, it seems to find the
    >> square root of several thousand digit numbers in just over a second
    >> which i think is pretty good, please can i have some thoughts on how to
    >> improve the code.
    >>
    >> --------------------Some Code-------------------------------------
    >>
    >> /**
    >> * A number is square free if it is divisible by no perfect
    >> square (except 1).
    >> *
    >> * @param testSubject
    >> * @return - true if the "testSubject" is a square free number. */
    >> public static boolean isSquareFree(double testSubject) {
    >> double answer;
    >> for(int i = 1; i < testSubject; i++)
    >> {
    >> answer = Math.sqrt(testSubject / (double)i); if

    (answer < 1)
    >> return false;
    >> if(answer % 1.0 == 0)
    >> return false;
    >> }
    >> return true;
    >> }
    >>
    >>

    > Okay, firstly, this isn't a square root algorithm. Is this the right
    > code?
    >
    > Secondly, you're using doubles to represent integers. Stop that. A
    > double is effectively a 53-bit integer with a scale field. It's got less
    > useful bits than a long. This code *will* be incorrect for large enough
    > numbers. And god alone knows how modulus of floating-point numbers works
    > (if he's read the IEEE 754 spec, that is).
    >
    > tom


    No this was not the correct code, i did re-post the correct code, had the
    wrong code on the clipboard !!, i will have a look for some pre built
    packages but really did want my own method for this.

    j1mb0jay
    j1mb0jay, May 21, 2008
    #8
  9. j1mb0jay wrote:
    > On Wed, 21 May 2008 08:06:47 -0400, Larry A Barowski wrote:
    >
    >> "j1mb0jay" <> wrote in message
    >> news:...
    >>> I was very surprised to see that java did not have a square root method
    >>> at all of the java.math.BigInteger class, why is this?
    >>>
    >>> I have tried to write a simple trial and error Square Root function
    >>> that works with BigIntegers. It does not return decimal values and
    >>> instead returns null if the number is decimal, or rounds the numbers
    >>> depending.

    >> Find the approximate square root using the first few significant bits
    >> and the magnitude, then use Newton's method starting there.
    >>
    >> But if all you need is a working implementation, I'm sure you can find
    >> several with a web search.

    >
    > Whats the first few significant bits of a number that is made up of
    > several thousand if not a few million bits. I sure i could find a few on
    > the Internet, but would like to try and build my own. I already have a an
    > implementation that works, just would like to try and make it a little
    > more efficient.


    I strongly agree with Larry's recommendation. However, some aspects will
    be easier if you work with BigDecimal in the actual Newton's method, and
    only round when you have enough digits to be confident of the answer.
    Alternatively, in the late stages Newton's method will get you down to a
    small candidate range, and you can just check each number in that range
    for being the square root.

    Suppose your number has a million bits, and the first four are 1011,
    equivalent to decimal 11. There are 999,996 bits we are going to ignore
    in the initial approximation step. The square root of 2^999,996 is
    2^499998 so the approximate answer is three, the approximate square root
    of 1011, times 2^499998.

    Now suppose your input as 1001 bits, and still has 1011 as the first
    four. The answer will be the square root of 2^1000 times the square root
    of 10110. Or you can take the first five bits if the number of bits is
    odd, the first four if even.

    Patricia
    Patricia Shanahan, May 21, 2008
    #9
  10. j1mb0jay wrote:
    > On Wed, 21 May 2008 08:06:47 -0400, Larry A Barowski wrote:
    >
    >> "j1mb0jay" <> wrote in message
    >> news:...
    >>> I was very surprised to see that java did not have a square root method
    >>> at all of the java.math.BigInteger class, why is this?
    >>>
    >>> I have tried to write a simple trial and error Square Root function
    >>> that works with BigIntegers. It does not return decimal values and
    >>> instead returns null if the number is decimal, or rounds the numbers
    >>> depending.

    >> Find the approximate square root using the first few significant bits
    >> and the magnitude, then use Newton's method starting there.
    >>
    >> But if all you need is a working implementation, I'm sure you can find
    >> several with a web search.

    >
    > Whats the first few significant bits of a number that is made up of
    > several thousand if not a few million bits. I sure i could find a few on
    > the Internet, but would like to try and build my own. I already have a an
    > implementation that works, just would like to try and make it a little
    > more efficient.


    Here's an alternative approach to getting the initial approximation.
    First convert to BigDecimal. Use movePointLeft by an even number of
    digits, 2*n, to get a BigDecimal in the double precision range. Use
    Math.sqrt to get the square root of the double. Use movePointRight by n
    digits to get your initial approximation. Proceed with Newton's method
    starting from that approximation.

    In effect, this does several iterations of Newton's method on an
    approximation to the number you want using double, which tends to be
    very fast due to hardware support.

    Patricia
    Patricia Shanahan, May 21, 2008
    #10
  11. j1mb0jay

    Tom Anderson Guest

    On Wed, 21 May 2008, Eric Sosman wrote:

    > j1mb0jay wrote:
    >
    >> Why would the result of square rooting an BigInteger not be a BigInteger

    >
    > Your mission, should you choose to accept it, is to find
    > a value for `root' that keeps the `assert' in this fragment
    > from firing:
    >
    > BigInteger square = new BigInteger("-1000");
    > BigInteger root = /* supply your candidate value here */ ;
    > assert root.multiply(root).equals(square);
    >
    > As usual, if you or any of your team are killed or captured, the
    > Secretary will declare the whole enterprise irrational and imaginary.


    ALGEBRAIC!

    http://youtube.com/watch?v=LNVYWJOEy9A

    But seriously, i kind of took it as read that j1mb0 was talking about
    integer square root, int(floor(sqrt(x))), which is not an uncommon thing
    to need when doing various bits of discrete maths.

    tom

    --
    [Philosophy] is kind of like being driven behind the sofa by Dr Who -
    scary, but still entertaining. -- itchyfidget
    Tom Anderson, May 21, 2008
    #11
  12. j1mb0jay

    john Guest

    On May 21, 4:57 am, j1mb0jay <> wrote:
    > I was very surprised to see that java did not have a square root method
    > at all of the java.math.BigInteger class, why is this?
    >
    > I have tried to write a simple trial and error Square Root function that
    > works with BigIntegers. It does not return decimal values and instead
    > returns null if the number is decimal, or rounds the numbers depending.
    >
    > The code is below, i am currently trying to re-implement my prime checker
    > using BigIntegers and require this method, it seems to find the square
    > root of several thousand digit numbers in just over a second which i
    > think is pretty good, please can i have some thoughts on how to improve
    > the code.
    >
    > Regards j1mb0jay.
    >
    > --------------------Some Code-------------------------------------
    >
    > /**
    > * A number is square free if it is divisible by no perfect
    > square (except 1).
    > *
    > * @param testSubject
    > * @return - true if the "testSubject" is a square free number.
    > */
    > public static boolean isSquareFree(double testSubject)
    > {
    > double answer;
    > for(int i = 1; i < testSubject; i++)
    > {
    > answer = Math.sqrt(testSubject / (double)i);
    > if(answer < 1)
    > return false;
    > if(answer % 1.0 == 0)
    > return false;
    > }
    > return true;
    > }


    Disclaimer: My familiarity with BigInteger is mostly looking at the
    API just now and I have no meaningful knowledge of the detailed
    representation of a double in Java other than a vague belief that
    about half the bits are just an integer representing the leading
    digits and about half are just an integer representing an exponent.

    Newtons method is pretty hard to beat, I think the person who
    recommended it was giving the right suggestion. If you aren't familiar
    with it here: To get the square root of b you start with a beginning
    guess x_0 and then take successive guesses by using
    x_(n+1) = (x_n / 2) + (b / (2 * x_n)). Given that both of these are
    rounded you should probably do
    x_(n+1) = ( x_n + b/x_n ) / 2

    A lot of newtons method time is narrowing in on a good first guess so
    even though even a first guess of x_0 = 1 will work, here are some
    better first guesses. They probably don't need to be too
    sophisticated:

    To get a first guess for b just take anything which takes about half
    as many bits to represent as b does. It looks like you can do this by
    using bitlength to count the bits, then start with a biginteger which
    is 0 and set the bit at position bitlength/2 and that gives you an x_0
    that is decent and will hone in fairly quickly.

    Here is probably a not very good idea which does give you a high
    quality first guess, but I doubt it is worth your while:
    If you want a better first guess x_0, then let L be the bitlength of b
    and let M = (L/2)*2. The point of M is that it makes L even, which
    will be useful as we will need M/2 to be an integer. Say you want
    about the first 16 bits to be correct, then you could start by
    dividing b by 2^N where N = M - 32. This value c = b/(2^N) is now a
    big integer which only has 32 or 33 bits. Then cast c to a double and
    take its square root to get sqrt(c). Now truncate the result, cast it
    to a string, create a BigInteger out of that string and multiply by
    the BigInteger 2^(M/2-16). That is your first guess x_0 and its first
    16 or so decimal places should already be correct. Wew! That sounds
    like a pain! Probably better to just go with the easier first guess.
    Compute 2^N and 2^(M/2-16) in the above by starting with BigInteger
    zero and setting the appropriate bit to 1 (i.e. the bit in position N
    to get 2^N and in position M/2-16 to get 2^(M/2-16) ). Just use
    hexidecimal (or binary if you want) literals for 2^16 (0x10000) and
    2^32 (0x100000000). In case you want to know, what we did here was
    scale b down so it would fit into a double, took the square root of
    the double, truncated it so the result was an integer. Constructed a
    BigInteger out of it and multiplied by a scaling factor to correct for
    the effect of scaling b down.


    Some math footnotes:
    There is an algorithm which looks strangely like long division for
    calculating a square root one decimal place at a time, however newtons
    method is probably much faster.

    Since we are using a BigInteger we are actually rounding the result at
    each application of newtons method. That is not really unusual since
    we always round even when taking the square root of a float or double,
    we just round further down in the decimal representation for these.
    However in this case we really care about that last digit or two near
    where we are rounding so one might wonder whether newtons method might
    get caught near but not at the right answer due to the effects of
    rounding. For this particular problem when b has an integer square
    root you can actually write out a proof that this does not happen.
    john, May 21, 2008
    #12
  13. j1mb0jay

    john Guest

    On May 21, 10:33 am, Eric Sosman <> wrote:
    > j1mb0jay wrote:
    > > [...]
    > > But if you are going all imaginary on me then maybe the answer might be
    > > 31.622776602i - rather complex !!!!

    >
    > Exactly: An irrational and imaginary value, not something
    > a BigInteger can represent.
    >
    > Note that if you're willing to live with approximations
    > to irrationals (and with NaN for imaginaries), you can get a
    > pretty good square root with the tools already available:
    >
    > BigInteger big = ...;
    > double approximateRoot = Math.sqrt(big.doubleValue());
    >
    > I say "pretty good" because if the value of `big' is greater
    > than Double.MAX_VALUE, `big.doubleValue()' will produce
    > Double.POSITIVE_INFINITY and the square root calculation
    > will be doomed before it starts. So for `big' values of more
    > than about 1025 bits you'll need to roll your own, probably
    > using Newton-Raphson and getting an initial estimate by just
    > right-shifting `big' by half its bit count.
    >
    > --
    >


    Well, looks like while I was writing you got several much slicker
    versions of what I was suggesting. I shouldn't have bothered. :) A
    couple of notes though:

    While large primes are reasonably common, very very large perfect
    squares are much rarer. If you pick a number at random with n digits
    then your odds of it being a perfect square are about 1 out of 2*10^(n/
    2), so for a hundred digit number that is
    1/200000000000000000000000000000000000000000000000000. For a 50 digit
    number they are more reasonable, a mere
    1/20000000000000000000000000. :) Also if you want to quickly eliminate
    a number as nonsquare you might just check and see whether it ends
    with 2,3,7 or 9, in which case it isn't square. Given how very rare
    they are there should be a faster way to eliminate "many" numbers as
    nonsquare quickly and then just run your algorithm for the rest, but I
    can't think of a better one offhand.

    -John
    john, May 21, 2008
    #13
  14. j1mb0jay

    john Guest

    On May 21, 10:50 am, john <> wrote:
    > On May 21, 10:33 am, Eric Sosman <> wrote:
    >
    >
    >
    > > j1mb0jay wrote:
    > > > [...]
    > > > But if you are going all imaginary on me then maybe the answer might be
    > > > 31.622776602i - rather complex !!!!

    >
    > > Exactly: An irrational and imaginary value, not something
    > > a BigInteger can represent.

    >
    > > Note that if you're willing to live with approximations
    > > to irrationals (and with NaN for imaginaries), you can get a
    > > pretty good square root with the tools already available:

    >
    > > BigInteger big = ...;
    > > double approximateRoot = Math.sqrt(big.doubleValue());

    >
    > > I say "pretty good" because if the value of `big' is greater
    > > than Double.MAX_VALUE, `big.doubleValue()' will produce
    > > Double.POSITIVE_INFINITY and the square root calculation
    > > will be doomed before it starts. So for `big' values of more
    > > than about 1025 bits you'll need to roll your own, probably
    > > using Newton-Raphson and getting an initial estimate by just
    > > right-shifting `big' by half its bit count.

    >
    > > --
    > >

    >
    > Well, looks like while I was writing you got several much slicker
    > versions of what I was suggesting. I shouldn't have bothered. :) A
    > couple of notes though:
    >
    > While large primes are reasonably common, very very large perfect
    > squares are much rarer. If you pick a number at random with n digits
    > then your odds of it being a perfect square are about 1 out of 2*10^(n/
    > 2), so for a hundred digit number that is
    > 1/200000000000000000000000000000000000000000000000000. For a 50 digit
    > number they are more reasonable, a mere
    > 1/20000000000000000000000000. :) Also if you want to quickly eliminate
    > a number as nonsquare you might just check and see whether it ends
    > with 2,3,7 or 9, in which case it isn't square. Given how very rare
    > they are there should be a faster way to eliminate "many" numbers as
    > nonsquare quickly and then just run your algorithm for the rest, but I
    > can't think of a better one offhand.
    >
    > -John


    Woops, make that "ends in 2,3,7 or 8. Perfect squares can end in 9
    (e.g. 3^2).

    -John
    john, May 21, 2008
    #14
  15. j1mb0jay

    john Guest

    On May 21, 10:50 am, john <> wrote:
    > On May 21, 10:33 am, Eric Sosman <> wrote:
    >
    >
    >
    > > j1mb0jay wrote:
    > > > [...]
    > > > But if you are going all imaginary on me then maybe the answer might be
    > > > 31.622776602i - rather complex !!!!

    >
    > > Exactly: An irrational and imaginary value, not something
    > > a BigInteger can represent.

    >
    > > Note that if you're willing to live with approximations
    > > to irrationals (and with NaN for imaginaries), you can get a
    > > pretty good square root with the tools already available:

    >
    > > BigInteger big = ...;
    > > double approximateRoot = Math.sqrt(big.doubleValue());

    >
    > > I say "pretty good" because if the value of `big' is greater
    > > than Double.MAX_VALUE, `big.doubleValue()' will produce
    > > Double.POSITIVE_INFINITY and the square root calculation
    > > will be doomed before it starts. So for `big' values of more
    > > than about 1025 bits you'll need to roll your own, probably
    > > using Newton-Raphson and getting an initial estimate by just
    > > right-shifting `big' by half its bit count.

    >
    > > --
    > >

    >
    > Well, looks like while I was writing you got several much slicker
    > versions of what I was suggesting. I shouldn't have bothered. :) A
    > couple of notes though:
    >
    > While large primes are reasonably common, very very large perfect
    > squares are much rarer. If you pick a number at random with n digits
    > then your odds of it being a perfect square are about 1 out of 2*10^(n/
    > 2), so for a hundred digit number that is
    > 1/200000000000000000000000000000000000000000000000000. For a 50 digit
    > number they are more reasonable, a mere
    > 1/20000000000000000000000000. :) Also if you want to quickly eliminate
    > a number as nonsquare you might just check and see whether it ends
    > with 2,3,7 or 9, in which case it isn't square. Given how very rare
    > they are there should be a faster way to eliminate "many" numbers as
    > nonsquare quickly and then just run your algorithm for the rest, but I
    > can't think of a better one offhand.
    >
    > -John


    I meant they can't end in 2,3, 7 or 8. Perfect squares can end in 9.
    john, May 21, 2008
    #15
  16. j1mb0jay

    Tom Anderson Guest

    On Wed, 21 May 2008, john wrote:

    > There is an algorithm which looks strangely like long division for
    > calculating a square root one decimal place at a time, however newtons
    > method is probably much faster.


    I wonder. The thing about Newton is that it involves doing arithmetic on
    whole BigIntegers, which means creating and destroying a bunch of
    potentially quite large objects. This is not a good way to get high
    performance.

    The long division algorithm, on the other hand, works through the number,
    dealing with it in small chunks, and generating digits as it goes. That
    means you can create one array to hold your computed digits (which would
    probably be in base 256, ie bytes), work through, and then construct one
    single BigInteger at the end. You might spend more cycles on arithmetic,
    but you'd spend fewer on memory management.

    tom

    --
    [Philosophy] is kind of like being driven behind the sofa by Dr Who -
    scary, but still entertaining. -- itchyfidget
    Tom Anderson, May 21, 2008
    #16
  17. j1mb0jay

    Roedy Green Guest

    On Wed, 21 May 2008 11:57:32 +0100, j1mb0jay <>
    wrote, quoted or indirectly quoted someone who said :

    >I was very surprised to see that java did not have a square root method
    >at all of the java.math.BigInteger class, why is this?


    Square root is normally considered to be a floating point operation
    since most roots are not perfect integers.

    --

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
    Roedy Green, May 21, 2008
    #17
  18. Lew <> wrote:
    > j1mb0jay wrote:
    >> Why would the result of square rooting an BigInteger not be a BigInteger
    >> does that not depend on the number you are square rooting, what is the
    >> square root of 2^132874985327329875329 is that not a BigInteger itself ???

    > What is the square root of 2?
    > What should be the square root of BigInteger.valueOf( 2 )?


    In integral contexts, the "integer square root" of a nonnegative integer
    n is (afaik) usually defined as the largest integer i, for which i*i<=n.

    Tcl (since 8.5) has such a function and calls it "isqrt". I think
    it calculates it by starting with the floating-point approximation
    and then gradually exactifying it with a couple iterations of Newton's
    approximation algorithm (I've been told that with that start it
    converges really fast). On my rather aged machine (1.2GHz), the
    isqrt of a number of 150 randomly typed digits takes about
    120 microseconds, double length takes about 380 microseconds, and
    4times the length takes almost a millisecond.

    That would make the roots of 2 and 3 to be both 1 (unlike rounding)

    I'm aware that the OP asked for different behaviour than that.
    Andreas Leitgeb, May 21, 2008
    #18
  19. j1mb0jay wrote:
    > On Wed, 21 May 2008 12:40:58 +0100, bugbear wrote:
    >> j1mb0jay wrote:
    >>> I was very surprised to see that java did not have a square root method
    >>> at all of the java.math.BigInteger class, why is this?

    >> Probably because the result isn't a BigInteger

    > Why would the result of square rooting an BigInteger not be a BigInteger


    BigInteger's is surprisingly like int's.

    3 is an int.

    sqrt(3) is not an int.

    QED

    Arne
    Arne Vajhøj, May 22, 2008
    #19
  20. j1mb0jay

    j1mb0jay Guest

    On Wed, 21 May 2008 21:49:30 +0000, Roedy Green wrote:

    > On Wed, 21 May 2008 11:57:32 +0100, j1mb0jay <> wrote,
    > quoted or indirectly quoted someone who said :
    >
    >>I was very surprised to see that java did not have a square root method
    >>at all of the java.math.BigInteger class, why is this?

    >
    > Square root is normally considered to be a floating point operation
    > since most roots are not perfect integers.


    I understand this but the main use for the code that i have written is to
    find out is a number has a perfect square, i use this to see if a number
    is prime.

    The method that I have written is very quick and will find the square
    root of a thousand digit number of my newish laptop in just over 1000
    milliseconds.
    j1mb0jay, May 22, 2008
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    0
    Views:
    1,213
  2. nick
    Replies:
    0
    Views:
    893
  3. nick
    Replies:
    1
    Views:
    31,746
    Eric Sosman
    Oct 26, 2004
  4. VK
    Replies:
    15
    Views:
    1,154
    Dr J R Stockton
    May 2, 2010
  5. Jan Burse

    Quick n-th Square of BigInteger

    Jan Burse, Jun 8, 2012, in forum: Java
    Replies:
    60
    Views:
    1,284
    Jan Burse
    Jun 17, 2012
Loading...

Share This Page