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:34:12 +0000 (UTC)
Organization: Aioe.org NNTP Server
Lines: 29
Message-ID: <jqu25k$6f4$1@speranza.aioe.org>
References: <jqtian$er7$1@news.albasani.net> <dlu4t7llbfgb1n8esgs5hbjhn7t2hb6ft8@4ax.com> <jqtuqh$9uo$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: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