Quick n-th Square of BigInteger

Dear All,

What is your favorite algorithm to compute the n-th Square of
a BigInteger, i.e.

Given: x, n
Compute: y = max { z | z^n =< x }

Bye

On Fri, 08 Jun 2012 21:03:56 +0200, Jan Burse <janburse@fastmail.fm>
wrote:

>Dear All,
>
>What is your favorite algorithm to compute the n-th Square of
>a BigInteger, i.e.
>
> Given: x, n
> Compute: y = max { z | z^n =< x }

Do you mean the integer part of the nth *root* of z given integer
x and n?

I do not have a favourite or even an algorithm. If I had to come
up with something, I would probably try a first approximation with
logarithms.

Sincerely,

Gene Wirchenko

Gene Wirchenko schrieb:
> On Fri, 08 Jun 2012 21:03:56 +0200, Jan Burse <janburse@fastmail.fm>
> wrote:
>
>> Dear All,
>>
>> What is your favorite algorithm to compute the n-th Square of
>> a BigInteger, i.e.
>>
>> Given: x, n
>> Compute: y = max { z | z^n =< x }
>
> Do you mean the integer part of the nth *root* of z given integer
> x and n?
>
> I do not have a favourite or even an algorithm. If I had to come
> up with something, I would probably try a first approximation with
> logarithms.
>
> Sincerely,
>
> Gene Wirchenko
>

Sorry, yes root, and z integer.

On 6/8/2012 1:36 PM, Jan Burse wrote:
> Gene Wirchenko schrieb:
>> On Fri, 08 Jun 2012 21:03:56 +0200, Jan Burse <janburse@fastmail.fm>
>> wrote:
>>
>>> Dear All,
>>>
>>> What is your favorite algorithm to compute the n-th Square of
>>> a BigInteger, i.e.
>>>
>>> Given: x, n
>>> Compute: y = max { z | z^n =< x }
>>
>> Do you mean the integer part of the nth *root* of z given integer
>> x and n?

> Sorry, yes root, and z integer.


Positive integers? Do you want the complex roots too? ;-) You ask big
questions Jan, but I think you need to ask them a little more thoughtfully.

I'm confused about the max, the z |, and the =< x. Care to explain
what those signify in your question? If you want something besides the
real, positive nth root of A=z^n, what do you want? I think "nth root
of A" is the correct phrasing, which leads to the wonder what the other
mathematical verbiage signifies.

Jan Burse schrieb:
> Dear All,
>
> What is your favorite algorithm to compute the n-th Square of
> a BigInteger, i.e.
>
> Given: x, n
> Compute: y = max { z | z^n =< x }
>
> Bye

Clarification:

Given: x BigInteger positive non-zero, n int positive non-zero

Compute: y BigInteger = max { z BigInteger | z^n =< x }

(In words: y is the biggest BigInteger z such that
z raised to the power of n is less or equal x)

(Mathematically this is would be floor(root(x,n)))

Bye

On 6/8/2012 3:03 PM, Jan Burse wrote:
> Dear All,
>
> What is your favorite algorithm to compute the n-th Square of
> a BigInteger, i.e.
>
> Given: x, n
> Compute: y = max { z | z^n =< x }

(I'm assuming you mean n'th root, which is what your final
line seems to imply.)

It's not something I've found a need to do, so I have no
"favorite" algorithm. For positive `x' I think I'd start
by observing that

x.bitCount()-1 <= lg(x) < x.bitCount()

hence the lg() of the desired root is between

floor((x.bitCount()-1)/n) <= lg(root) < ceil(x.bitCount()/n)

From this you can get lower and upper bounds on the root itself,
something like (just typed in free-hand)

BigInteger lo = BigInteger.ONE.shiftLeft(
Math.floor((x.bitCount()-1)/n));
BitInteger hi = BigInteger.ONE.shiftLeft(
Math.ceil(x.bitCount()/n));

.... and then do a binary search between those extrema. (Looks like
they'd differ by a factor of two usually, maybe a factor of four
occasionally -- but I might be wrong about that.)

Simplifications might be possible if `n' is known to be an
integer.

For negative `x' and odd integer `n' you could find the bounds
for -x, negate and interchange them, and then do the same binary
search.

For negative `x' and `n' even or non-integer, I think you're
out of luck.

--
Eric Sosman
esosman@ieee-dot-org.invalid

markspace <-@.> wrote:
(snip)
>>> On Fri, 08 Jun 2012 21:03:56 +0200, Jan Burse <janburse@fastmail.fm>

>>>> What is your favorite algorithm to compute the n-th Square of
>>>> a BigInteger, i.e.

>>>> Given: x, n
>>>> Compute: y = max { z | z^n =< x }

(snip)
>> Sorry, yes root, and z integer.

> Positive integers? Do you want the complex roots too? ;-)
> You ask big questions Jan, but I think you need to ask them
> a little more thoughtfully.

I will guess that the OP isn't a native English speaker, and
is not translating so well.

I had to look it up as I didn't know, .fm seems to be Micronesia.

It looks like he wants the nth root rounded down to the next
integer value.

I do remember when first learning Fortran wondering why no
ISQRT function.

One possibility is to do exactly as written, binary search
for the largest z such that z**n <= x. (No exclusive or operators
are needed here.)

-- glen

Eric Sosman schrieb:
> ... and then do a binary search between those extrema. (Looks like
> they'd differ by a factor of two usually, maybe a factor of four
> occasionally -- but I might be wrong about that.)

Binary search would use (x.bitCount()-1)/n steps in the
extrem, and in each step calculating pow(). Is this
effective?

glen herrmannsfeldt schrieb:
> I will guess that the OP isn't a native English speaker, and
> is not translating so well. I had to look it up as I didn't know,
> .fm seems to be Micronesia.

Ha Ha

fastmail.fm = messagingengine.com

markspace schrieb:
> I'm confused about the max, the z |, and the =< x.

For those who don't know, there exists a set builder notation:

http://en.wikipedia.org/wiki/Set-bui...ion#Z_notation

max is then a higher order function from a set to an element.

Forgot where this is taught, in elementary school?

Bye

On 6/8/2012 5:19 PM, Jan Burse wrote:
> Eric Sosman schrieb:
>> ... and then do a binary search between those extrema. (Looks like
>> they'd differ by a factor of two usually, maybe a factor of four
>> occasionally -- but I might be wrong about that.)
>
> Binary search would use (x.bitCount()-1)/n steps in the
> extrem, and in each step calculating pow(). Is this
> effective?

In light of your abusiveness in responding to other people who've
tried to help, I decline to assist you any further. Have a nice life.

--
Eric Sosman
esosman@ieee-dot-org.invalid

Eric Sosman schrieb:
> In light of your abusiveness in responding to other people who've
> tried to help, I decline to assist you any further. Have a nice life.

Problem is I scribbled the exact same solution on
a back of an envelope, but I have doubt that it is
a good solution for small n, like n=2.

Bye

On Friday, June 8, 2012 2:34:40 PM UTC-7, Jan Burse wrote:
> markspace schrieb:
> > I'm confused about the max, the z |, and the =< x.
>
> For those who don't know, there exists a set builder notation:
>
> http://en.wikipedia.org/wiki/Set-bui...ion#Z_notation
>
> max is then a higher order function from a set to an element.
>
> Forgot where this is taught, in elementary school?

Riiiight. As nations and smaller school districts remove evolution from
their textbooks, they're going to teach mathematical logic and set
theory in elementary school?

In any event, this being a Java forum, the notation '=<' (shown nowhere
in your reference link, BTW) is rather odd, as we are used to '<='. Given
that '=<' apparently is not part of the "Set Builder" notation, how about
we stick with the Java (also C, Fortran, C++, C#, Javascript, BASIC, SQL,
Python, shell, ...) idiom?

--
Lew

Jan Burse schrieb:
> Do you want me to start counting the trolls that will
> now make their appearance in this thread? You are
> number 3 so far. I guess there will follow some more...

But still comp.lang.java.programmer is too small
I guess so that a shitstorm will rise. And there are
still some that want to profit.

Bye

On Friday, June 8, 2012 2:43:37 PM UTC-7, Jan Burse wrote:
> Eric Sosman schrieb:
> > In light of your abusiveness in responding to other people who've
> > tried to help, I decline to assist you any further. Have a nice life.
>
> Problem is I scribbled the exact same solution on
> a back of an envelope, but I have doubt that it is
> a good solution for small n, like n=2.

For n == 2, just use any of the standard algorithms for square root, like
<http://stackoverflow.com/questions/3432412/calculate-square-root-of-a-biginteger-system-numerics-biginteger?rq=1>
found in about 10 minutes of online searching.

--
Lew