Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

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
 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
 
 
 
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?

 
Reply With Quote
 
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

 
Reply With Quote
 
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

 
Reply With Quote
 
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
 
Reply With Quote
 
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
 
Reply With Quote
 
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
 
Reply With Quote
 
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
us more about your application domain, we are sorry, we can't
answer your question without more context information".

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

 
Reply With Quote
 
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
be: "Why are you angry, he only wants to help you
that is why he is asking for context, if you refuse
help you don't deserve help".

This forum is like a platform for troll ballerinas,
that are adicted to show their rhetorik pirouette.
Please go on and show us your figures, I will update
the counter but I will not applaude, since I have
seen them already.

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
> answer your question without more context information".
>
> 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
>



 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Square Root Of java.math.BigInteger j1mb0jay Java 25 05-25-2008 03:46 AM
how to convert "BigInteger" into "Integer"? how to print out a BigInteger binary value? nick Java 1 10-26-2004 02:45 PM
how to convert "BigInteger" into "Integer"? how to print out a BigInteger binary value? nick Java 0 10-26-2004 08:18 AM
SRT DIvision, Square root and reciprocal square root alghazo@siu.edu VHDL 0 05-27-2004 06:23 AM
Anyone want a higher performance not-quite-so BigInteger pete kirkham Java 5 08-13-2003 10:32 PM



Advertisments