Quick n-th Square of BigInteger

[Lew]

Stop your peer pressure. I told you already once:

Suck my d**k, shut up and f**k off.

Who's the troll?

The request was to *stop* being nasty, not to elevate your bad
behavior to obscenity. What is wrong with you?

Since you resort to such slimy and insulting verbiage, you show
that you have nothing worthwhile to contribute.

For this to be peer pressure, we'd have to be peers.

The slime mold is closer to being your peer.

You are behaving badly, Jan Burse. There is no justification for your
behavior.

 

[Jan Burse]

For n == 2, just use any of the standard algorithms for square root, like
<http://stackoverflow.com/questions/...-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?

 

[Roedy Green]

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
..

 

[Jan Burse]

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

 

[Jan Burse]

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

 

[glen herrmannsfeldt]

(snip)

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?

For whatever reason, yes, I believe sets are not taught much
in school, maybe not until calculus where you need them for
continuity proofs. Maybe in geometry, but not as far as I know.

Some years ago we had "new math" which included a little set
theory and, as I remember number bases (radix) but I believe
even that is gone now.

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?

I still feel funny using the exclusive or operator as an
exponential operator. Math.pow seems even worse, so I mostly
use the Fortran ** operator in posts, even though I don't write
so much in Fortran these days. There might be some programming
language that allows for =< though I don't remember which one.

-- glen

 

[Jan Burse]

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: And here comes some education why =< is necessary. The link I
gave refers to set builder notation in the Z specification language.
And not to builder notation in a programming language.

In a specification language the set builder notation reads:

{ variable | condition }

Since the condition can be a first order formula, it might contain
the logical implication. This is sometimes denoted by <= or =>. Therefor
in mathematical specification the comparators are often
written as =< and >= so that they can be distinguished.

This problem doesn't pose itself for language such as Java that do
not have a logical implication.

Best Regards

 

[Jan Burse]

I still feel funny using the exclusive or operator as an
exponential operator. Math.pow seems even worse, so I mostly
use the Fortran ** operator in posts, even though I don't write
so much in Fortran these days. There might be some programming
language that allows for =< though I don't remember which one.

@Glen: It would be a use of the exclusive or operator, if
it were Java. But since it isn't Java, it is not the exclusive
or operator. The ** operator would also be legit, but ^ is
for example used in LaTeX for superscript, so it makes sense
to use ^ for pow().

If you carefully observe your mail reader, depending on the
mail reader you have, you will also see that x ^ 2 is shown
as x with superscripted 2, provide the ^ directly follows
the x.

Bye

 

[glen herrmannsfeldt]

(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

 

[Lew]

@Lew: And here comes some education why =< is necessary. The link I
gave refers to set builder notation in the Z specification language.
And not to builder notation in a programming language.

And you couldn't say that the first four times people asked?
Instead you had to rant and curse and abuse them?

And the link you gave never mentioned '=<'.

As for "necessary", not hardly.

In a specification language the set builder notation reads:

{ variable | condition }

Since the condition can be a first order formula, it might contain
the logical implication. This is sometimes denoted by <= or =>. Therefor[e]
in mathematical specification the comparators are often
written as =< and >= so that they can be distinguished.

This problem doesn't pose itself for language such as Java that do
not have a logical implication.

And since this is Java, and not every Java programmer is intimately
familiar with Z notation, a question about the notation is natural and
should have been answered politely instead of abusively, and immediately
instead of after all the nonsense you imposed.

Go to.

 

[glen herrmannsfeldt]

(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]

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]

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

Efficiently?

 

[glen herrmannsfeldt]

(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]

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]

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]

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]

(after I wrote)

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]

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

 

[Jan Burse]

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