Velocity Reviews > Java > Quick n-th Square of BigInteger

# Quick n-th Square of BigInteger

glen herrmannsfeldt
Guest
Posts: n/a

 06-08-2012
Roedy Green <(E-Mail Removed)> wrote:

(snip on BigInteger, powers, and roots)

> What are the bounds on z and n?

> Here are some noodlings of an idea:

> z ^ 6

> prime factors of 6 are 2 and 3.
> so compute this as (z * z) ^3

Well, there is a standard method, that traces back to the
Chinese Remainder Theorem and works off the binary representation.

http://en.wikipedia.org/wiki/Binary_exponentiation

In some cases it isn't quite as good as factoring the power, but
mostly close enough.

> e.g. 2^6 = 64

> ( 2 * 2 ) ^ 3 = 4 * 4 * 4 = 64

-- glen

Jan Burse
Guest
Posts: n/a

 06-08-2012
glen herrmannsfeldt schrieb:
> Well, there is a standard method, that traces back to the
> Chinese Remainder Theorem and works off the binary representation.
>
> http://en.wikipedia.org/wiki/Binary_exponentiation
>
> In some cases it isn't quite as good as factoring the power, but
> mostly close enough.

How do you factor the exponent if it is not
a constant you know in advance? Question is
a function where:

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

So both x and n are parameters of the functions.
The code I am seeking should take x and n
variably.

Bye

Jan Burse
Guest
Posts: n/a

 06-08-2012
Jan Burse schrieb:
> How do you factor the exponent if it is not
> a constant you know in advance?

Efficiently?

glen herrmannsfeldt
Guest
Posts: n/a

 06-08-2012
Jan Burse <(E-Mail Removed)> wrote:

(snip)
> x^(2*n+1) = (x^n)^2*x

> From the Java source code of Oracle JDK 1.7:
> // Perform exponentiation using repeated squaring trick
> They even do it in a loop.

Yes.

> But question is about floor(root(x,n)), which
> might profit from a fast pow() of course.

The suggestion is to do binary search, computing x**n until
you find the appropriate n.

It depends much on the size of x and n, though. I suppose
you can save some multiplies by saving the largest previously
found x**n that is less than y.

Well, start the loop by squaring until you get a value larger
than y, then you have two powers that you know n is between,
saving the lower value each time. Now binary search over that
range, each time saving the highest known power such that the
result doesn't exceed y.

-- glen

Jan Burse
Guest
Posts: n/a

 06-08-2012
glen herrmannsfeldt schrieb:
> Well, start the loop by squaring until you get a value larger
> than y, then you have two powers that you know n is between,
> saving the lower value each time. Now binary search over that
> range, each time saving the highest known power such that the
> result doesn't exceed y.

Yes this would be an alternative to the bitCount() suggestion
from Eric. Since BigInteger has bitCount(), I guess bitCount()
is the more efficient solution.

The bisection is probably slower than Newton. In Newton you
have to compute x^n-1 and divide in each iteration, in
bisection you have to compute x^n and compare in each iteration.
So I take it that the effort for the iteration step itself
is more or less the same for both methods.

So that in the end the number of iterations will be dominant.
When Newton doubles the precision in each iteration, it will
use log m/n steps (right?), whereas bisection probably also
uses log m/n steps in the average (right?).

Hm

Jan Burse
Guest
Posts: n/a

 06-08-2012
Lew schrieb:
> And since this is Java, and not every Java programmer is intimately
> familiar with Z notation, a question about the notation is natural and

The problem with you Lew is, that you have a very
narrow view of what it means to program Java and
what a Java programming newsgroup is about. I will
not give in and lower the bar for the readers of
this newsgroup only because of your trolling.

In my opinion I can assume that a programmer has
heard about such things as loop invariants etc..
and that he/she has already seen mathematical
notation. If you insists Lew that the readers of
this newsgroup are totally uneducated then I think
you are doing them wrong.

Bye

Jan Burse
Guest
Posts: n/a

 06-09-2012
Lew schrieb:
> And the link you gave never mentioned '=<'.

I didn' give the link for '=<', I gave the link for
set builder notation.

Inside the Z specification language there is no
'=<'. We find in the ISO standard for the Z
specification:

A.3.4.4 Section number toolkit
E-mail string Z character
<= Unicode less than or equal

But =< is simply the mirror of >=, so should be
that hard to decipher.

Bye

glen herrmannsfeldt
Guest
Posts: n/a

 06-09-2012
Jan Burse <(E-Mail Removed)> wrote:

(after I wrote)
>> Well, start the loop by squaring until you get a value larger
>> than y, then you have two powers that you know n is between,
>> saving the lower value each time. Now binary search over that
>> range, each time saving the highest known power such that the
>> result doesn't exceed y.

> Yes this would be an alternative to the bitCount() suggestion
> from Eric. Since BigInteger has bitCount(), I guess bitCount()
> is the more efficient solution.

> The bisection is probably slower than Newton. In Newton you
> have to compute x^n-1 and divide in each iteration, in
> bisection you have to compute x^n and compare in each iteration.
> So I take it that the effort for the iteration step itself
> is more or less the same for both methods.

I will guess that it depends much on the size of x and n.
I like the bisection because it avoided the divide, which
might be slow, but might not be. Also, since he wants floor(),
you have to be careful for the case where y is very close to
an integer power of n, and Newton might round the wrong way.

(It is interesting, the IBM 360/91 uses the Newton't method
divide algorithm for floating point divide, returning the
rounded quotient. The S/360 architecture specifies a truncated
quotient, so this has to be stated as a deviation from the
architecture.)

> So that in the end the number of iterations will be dominant.
> When Newton doubles the precision in each iteration, it will
> use log m/n steps (right?), whereas bisection probably also
> uses log m/n steps in the average (right?).

and x^n takes O(log n) multiplies.

-- glen

Jan Burse
Guest
Posts: n/a

 06-09-2012
Leif Roar Moldskred schrieb:
> Jan Burse <(E-Mail Removed)> wrote:
>> Dear All,
>>
>> What is your favorite algorithm to compute the n-th Square of
>> a BigInteger, i.e.

>
> Whichever algorithm happens to be the best suited to the specific
> context the problem occurs in, of course.
>

I was actually waiting for this troll meme: "Could you tell

It is even more astonishing that this troll meme only pops
up after already a couple of solutions have pured in, and even
nobody on stackoverflow was throughing up the meme.

Anyway, the troll count goes up from 3 to 4, since I didn't
count Roedy. But your impudence deserves it.

Bye

Jan Burse
Guest
Posts: n/a

 06-09-2012
Hi Trolls,

Let me make a prediction how the troll parade will
continue. The next troll meme that will pop up will
that is why he is asking for context, if you refuse

This forum is like a platform for troll ballerinas,
that are adicted to show their rhetorik pirouette.
the counter but I will not applaude, since I have

Bye

Jan Burse schrieb:
> Leif Roar Moldskred schrieb:
>> Jan Burse <(E-Mail Removed)> wrote:
>>> Dear All,
>>>
>>> What is your favorite algorithm to compute the n-th Square of
>>> a BigInteger, i.e.

>>
>> Whichever algorithm happens to be the best suited to the specific
>> context the problem occurs in, of course.
>>

>
> I was actually waiting for this troll meme: "Could you tell
> us more about your application domain, we are sorry, we can't
>
> It is even more astonishing that this troll meme only pops
> up after already a couple of solutions have pured in, and even
> nobody on stackoverflow was throughing up the meme.
>
> Anyway, the troll count goes up from 3 to 4, since I didn't
> count Roedy. But your impudence deserves it.
>
> Bye
>