Path: csiph.com!usenet.pasdenom.info!aioe.org!.POSTED!not-for-mail
From: glen herrmannsfeldt <gah@ugcs.caltech.edu>
Newsgroups: comp.lang.java.programmer
Subject: Re: Quick n-th Square of BigInteger
Date: Fri, 8 Jun 2012 23:05:50 +0000 (UTC)
Organization: Aioe.org NNTP Server
Lines: 31
Message-ID: <jqu0gd$3ag$1@speranza.aioe.org>
References: <jqtian$er7$1@news.albasani.net> <jqtpd1$jda$1@dont-email.me> <jqtq8d$vv6$1@news.albasani.net> <jqtrgt$vp9$2@dont-email.me> <jqtrm4$2k4$2@news.albasani.net> <2c0e8fd7-c593-439f-953f-ad1dfc735937@googlegroups.com> <jqtudr$9b1$1@news.albasani.net>
NNTP-Posting-Host: H0vc4U5LIRkRHNPyGCs2dA.user.speranza.aioe.org
X-Complaints-To: abuse@aioe.org
User-Agent: tin/1.9.6-20100522 ("Lochruan") (UNIX) (Linux/2.6.32-5-amd64 (x86_64))
X-Notice: Filtered by postfilter v. 0.8.2
Xref: csiph.com comp.lang.java.programmer: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