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

Re: Quick n-th Square of BigInteger
 

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

Quick n-th Root of BigInteger
 

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.

Re: Quick n-th Root of BigInteger
 

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.

Re: Quick n-th Square of BigInteger
 

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

Re: Quick n-th Square of BigInteger
 

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

Re: Quick n-th Root of BigInteger
 

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

Re: Quick n-th Square of BigInteger
 

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?

Re: Quick n-th Root of BigInteger
 

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

Re: Quick n-th Root of BigInteger
 

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