Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #15105 > unrolled thread

Quick n-th Square of BigInteger

Back to article view | Back to comp.lang.java.programmer

Contents

  Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 21:03 +0200
    Re: Quick n-th Square of BigInteger Gene Wirchenko <genew@ocis.net> - 2012-06-08 13:34 -0700
      Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 22:36 +0200
        Re: Quick n-th Root of BigInteger markspace <-@.> - 2012-06-08 13:55 -0700
          Re: Quick n-th Root of BigInteger glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-06-08 21:06 +0000
            Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:21 +0200
          Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:34 +0200
            Re: Quick n-th Root of BigInteger Lew <lewbloch@gmail.com> - 2012-06-08 14:43 -0700
              Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:47 +0200
                Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:47 +0200
                Re: Quick n-th Root of BigInteger Lew <lewbloch@gmail.com> - 2012-06-08 14:55 -0700
                  Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 00:00 +0200
                    Re: Quick n-th Root of BigInteger Lew <lewbloch@gmail.com> - 2012-06-08 15:10 -0700
                      Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 00:12 +0200
                        Re: Quick n-th Root of BigInteger Lew <lewbloch@gmail.com> - 2012-06-08 15:18 -0700
              Re: Quick n-th Root of BigInteger glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-06-08 22:59 +0000
                Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 01:05 +0200
              Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 01:00 +0200
                Re: Quick n-th Root of BigInteger Lew <lewbloch@gmail.com> - 2012-06-08 16:15 -0700
                  Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 01:51 +0200
                  Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 02:32 +0200
    Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:00 +0200
    Re: Quick n-th Square of BigInteger Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-06-08 17:04 -0400
      Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:19 +0200
        Re: Quick n-th Square of BigInteger Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-06-08 17:40 -0400
          Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:43 +0200
            Re: Quick n-th Square of BigInteger Lew <lewbloch@gmail.com> - 2012-06-08 14:52 -0700
              Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 00:30 +0200
                Re: Quick n-th Square of BigInteger glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-06-08 23:05 +0000
      Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-11 14:53 +0200
    Re: Quick n-th Square of BigInteger Roedy Green <see_website@mindprod.com.invalid> - 2012-06-08 15:32 -0700
      Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 00:37 +0200
        Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 00:39 +0200
        Re: Quick n-th Square of BigInteger glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-06-08 23:34 +0000
          Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 01:44 +0200
            Re: Quick n-th Square of BigInteger glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-06-09 01:06 +0000
      Re: Quick n-th Square of BigInteger glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-06-08 23:25 +0000
        Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 01:29 +0200
          Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 01:29 +0200
      Re: Quick n-th Square of BigInteger Wanja Gayk <brixomatic@yahoo.com> - 2012-06-17 15:00 +0200
    Re: Quick n-th Square of BigInteger Leif Roar Moldskred <leifm@dimnakorr.com> - 2012-06-09 08:42 -0500
      Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 16:54 +0200
        Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 17:56 +0200
          Re: Quick n-th Square of BigInteger Leif Roar Moldskred <leifm@dimnakorr.com> - 2012-06-09 12:52 -0500
        Re: Quick n-th Square of BigInteger Joshua Cranmer <Pidgeot18@verizon.invalid> - 2012-06-09 12:55 -0400
          Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 21:23 +0200
        Re: Quick n-th Square of BigInteger Leif Roar Moldskred <leifm@dimnakorr.com> - 2012-06-09 12:44 -0500
          Re: Quick n-th Square of BigInteger markspace <-@.> - 2012-06-09 11:50 -0700
            Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 21:13 +0200
              Re: Quick n-th Square of BigInteger markspace <-@.> - 2012-06-09 12:25 -0700
                Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 21:29 +0200
          Re: Quick n-th Square of BigInteger Joshua Cranmer <Pidgeot18@verizon.invalid> - 2012-06-09 21:27 -0400
            Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-10 12:08 +0200
              Re: Quick n-th Square of BigInteger Joshua Cranmer <Pidgeot18@verizon.invalid> - 2012-06-10 08:23 -0400
            Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-10 13:31 +0200
              Re: Quick n-th Square of BigInteger Wanja Gayk <brixomatic@yahoo.com> - 2012-06-17 15:11 +0200
          Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-10 12:04 +0200
        Re: Quick n-th Square of BigInteger Roedy Green <see_website@mindprod.com.invalid> - 2012-06-16 17:45 -0700
          Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-17 03:17 +0200
          Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-17 03:38 +0200
    Troll Parade Closing, Award Ceremony Jan Burse <janburse@fastmail.fm> - 2012-06-10 12:31 +0200
      Re: Troll Parade Closing, Award Ceremony Jan Burse <janburse@fastmail.fm> - 2012-06-10 12:35 +0200
      Re: Troll Parade Closing, Award Ceremony Leif Roar Moldskred <leifm@dimnakorr.com> - 2012-06-10 06:28 -0500
        Re: Troll Parade Closing, Award Ceremony Jan Burse <janburse@fastmail.fm> - 2012-06-10 13:30 +0200
      Re: Troll Parade Closing, Award Ceremony Joshua Cranmer <Pidgeot18@verizon.invalid> - 2012-06-10 08:25 -0400
        Re: Troll Parade Closing, Award Ceremony Jan Burse <janburse@fastmail.fm> - 2012-06-10 14:48 +0200
      Re: Troll Parade Closing, Award Ceremony Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-06-10 11:49 -0700

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

#15142 — Re: Quick n-th Root of BigInteger

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

[toc] | [prev] | [next] | [standalone]

#15109

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

[toc] | [prev] | [next] | [standalone]

#15110

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

[toc] | [prev] | [next] | [standalone]

#15112

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?

[toc] | [prev] | [next] | [standalone]

#15115

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

[toc] | [prev] | [next] | [standalone]

#15116

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

[toc] | [prev] | [next] | [standalone]

#15120

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

[toc] | [prev] | [next] | [standalone]

#15127

Lew schrieb:
>> 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.
>

It took me only one second to find it. But it doesn't
solve the question.

Should we now also apply Newton to n<>2? What can we
do about that Newton might oscillate for integers?
Is the lowerBound and upperBound fence trick of isSqrt
also good for n<>2?

Given the fence trick, we can probably abandon max-
iteration approaches, or not?

CORDIC methods, are they appropriate on CPUs that have
multiplication?

[toc] | [prev] | [next] | [standalone]

#15134

Jan Burse <janburse@fastmail.fm> wrote:

(snip)
> It took me only one second to find it. But it doesn't
> solve the question.

> Should we now also apply Newton to n<>2? What can we
> do about that Newton might oscillate for integers?
> Is the lowerBound and upperBound fence trick of isSqrt
> also good for n<>2?

Yes you can use Newton for n other than 2. There are
processor that divide using Newton's method and n=-1.
It pipelines very well, and converges quadratically,
as is common for Newton's method. If you have a fast
multiplier it is the way to go.

> Given the fence trick, we can probably abandon max-
> iteration approaches, or not?

It probably depends on how big n and x are, but I believe
that a binary search computing x**n should converge fast
enough, for some values of n and x.

> CORDIC methods, are they appropriate on CPUs that have
> multiplication?

For large enough n and x, it might make sense.

-- glen

[toc] | [prev] | [next] | [standalone]

#15204

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

I guess you mean bitLength() and not bitCount()
in the above. bitCount() counts the number of
non-zero bits. bitLength() gives the index of
the highest non-zero bit.

Math.floor/Math.ceil are not really needed in the
above since (int)/(int) gives anyway (int). But
I am now going for. Also correcting BitInteger
to BigInteger:

       BigInteger lo = BigInteger.ONE.shiftLeft(
           (x.bitLength()-1)/n);
       BigInteger hi = BigInteger.ONE.shiftLeft(
           (x.bitLength()+n-1)/n);

I am not yet done with testing. Bisection works
already, but would like to compare with Newton.
Here is an example run showing determination of
lo and hi:

   x=1000000000
   n=3
   lo=512
   hi=1024

Bye

[toc] | [prev] | [next] | [standalone]

#15128

On Fri, 08 Jun 2012 21:03:56 +0200, Jan Burse <janburse@fastmail.fm>
wrote, quoted or indirectly quoted someone who said :

>    Compute: y = max { z | z^n =< x }
 You are using a notation that is not widely known.  Please spell this
out longhand.

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


e.g. 2^6 = 64   

( 2 * 2 ) ^ 3 = 4 * 4 * 4 = 64
-- 
Roedy Green Canadian Mind Products
http://mindprod.com
Controlling complexity is the essence of computer programming.
~ Brian W. Kernighan 1942-01-01
.

[toc] | [prev] | [next] | [standalone]

#15129

Roedy Green schrieb:
> Here are some noodlings of an idea:
>
>    z  ^ 6
>
> prime factors of 6 are 2 and 3.
>
> so compute this as  (z * z) ^3
>
>
> e.g. 2^6  = 64
>
> ( 2 * 2 ) ^ 3 = 4 * 4 * 4 = 64

I don't have seen some pow() implementation
that uses prime factors. The usual BigInteger
implementation of pow() uses:

    x^(2*n) = (x^n)^2

    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.

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

Bye

[toc] | [prev] | [next] | [standalone]

#15130

Jan Burse schrieb:
>
>     x^(2*n) = (x^n)^2
>
>     x^(2*n+1) = (x^n)^2*x

Better I guess:

    x^(2*n) = (x^2)^n

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

[toc] | [prev] | [next] | [standalone]

#15138

Jan Burse <janburse@fastmail.fm> 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

[toc] | [prev] | [next] | [standalone]

#15140

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

[toc] | [prev] | [next] | [standalone]

#15143

Jan Burse <janburse@fastmail.fm> 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

[toc] | [prev] | [next] | [standalone]

#15135

Roedy Green <see_website@mindprod.com.invalid> 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

[toc] | [prev] | [next] | [standalone]

#15136

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

[toc] | [prev] | [next] | [standalone]

#15137

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

[toc] | [prev] | [next] | [standalone]

#15357

In article <dlu4t7llbfgb1n8esgs5hbjhn7t2hb6ft8@4ax.com>, 
see_website@mindprod.com.invalid says...
> 
> On Fri, 08 Jun 2012 21:03:56 +0200, Jan Burse <janburse@fastmail.fm>
> wrote, quoted or indirectly quoted someone who said :
> 
> >    Compute: y = max { z | z^n =< x }

>  You are using a notation that is not widely known. 

Just like the metric system, eh?

Gruß,
-Wanja-

-- 
..Alesi's problem was that the back of the car was jumping up and down 
dangerously - and I can assure you from having been teammate to 
Jean Alesi and knowing what kind of cars that he can pull up with, 
when Jean Alesi says that a car is dangerous - it is. [Jonathan Palmer]

--- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---

[toc] | [prev] | [next] | [standalone]

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

Back to top | Article view | comp.lang.java.programmer

csiph-web