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

# Quick n-th Square of BigInteger

Lew
Guest
Posts: n/a

 06-08-2012
Jan Burse wrote:
> Lew schrieb:
> > Stop being so nasty and confrontational, Jan. If you can't play
> > nice, stay off the playground. You're being mean without any
> > need.

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

--
Lew

Jan Burse
Guest
Posts: n/a

 06-08-2012
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?

Roedy Green
Guest
Posts: n/a

 06-08-2012
On Fri, 08 Jun 2012 21:03:56 +0200, Jan Burse <(E-Mail Removed)>
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
..

Jan Burse
Guest
Posts: n/a

 06-08-2012
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

Jan Burse
Guest
Posts: n/a

 06-08-2012
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

glen herrmannsfeldt
Guest
Posts: n/a

 06-08-2012
Lew <(E-Mail Removed)> wrote:
> On Friday, June 8, 2012 2:34:40 PM UTC-7, Jan Burse wrote:

>> For those who don't know, there exists a set builder notation:

>> http://en.wikipedia.org/wiki/Set-bui...ion#Z_notation

(snip)
>> Forgot where this is taught, in elementary school?

> 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
Guest
Posts: n/a

 06-08-2012
Lew schrieb:
> 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
Guest
Posts: n/a

 06-08-2012
glen herrmannsfeldt schrieb:
> 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
Guest
Posts: n/a

 06-08-2012
Jan Burse <(E-Mail Removed)> 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

Lew
Guest
Posts: n/a

 06-08-2012
Jan Burse wrote:
> Lew schrieb:
> > 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.

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.

--
Lew

 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 OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post j1mb0jay Java 25 05-25-2008 03:46 AM nick Java 1 10-26-2004 02:45 PM nick Java 0 10-26-2004 08:18 AM alghazo@siu.edu VHDL 0 05-27-2004 06:23 AM pete kirkham Java 5 08-13-2003 10:32 PM

Advertisments