Re: Square Root Of java.math.BigInteger

On May 21, 10:33 am, Eric Sosman <Eric.Sos...@xxxxxxx> 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.

--
Eric.Sos...@xxxxxxx

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


.

Relevant Pages

  • Re: Square Root Of java.math.BigInteger
    ... to irrationals (and with NaN for imaginaries), ... Double.POSITIVE_INFINITY and the square root calculation ... so for a hundred digit number that is ... nonsquare quickly and then just run your algorithm for the rest, ...
    (comp.lang.java.programmer)
  • Re: Square Root Of java.math.BigInteger
    ... to irrationals (and with NaN for imaginaries), ... Double.POSITIVE_INFINITY and the square root calculation ... so for a hundred digit number that is ... nonsquare quickly and then just run your algorithm for the rest, ...
    (comp.lang.java.programmer)
  • Re: Church-Turing compared to Zuse-Fredkin thesis (two new papers)
    ... Did you mean to write "square roots"? ... > irrationals we have constructibles that appear to me to represent ... > also have non constructible irrationals referred to as transcendentals ...
    (comp.theory)
  • Re: proposed coinage
    ... three independent imaginaries). ... A surd is a particular type of irrational number, but not by any means the ... are therefore "algebraic" irrationals, i.e. they can be the solutions of ...
    (alt.usage.english)
  • Re: proposed coinage
    ... three independent imaginaries). ... A surd is a particular type of irrational number, but not by any means the ... are therefore "algebraic" irrationals, i.e. they can be the solutions of ...
    (alt.usage.english)