Path: csiph.com!usenet.pasdenom.info!gegeweb.org!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail
From: Eric Sosman <esosman@ieee-dot-org.invalid>
Newsgroups: comp.lang.java.programmer
Subject: Re: Quick n-th Square of BigInteger
Date: Fri, 08 Jun 2012 17:04:28 -0400
Organization: A noiseless patient Spider
Lines: 47
Message-ID: <jqtpd1$jda$1@dont-email.me>
References: <jqtian$er7$1@news.albasani.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 8 Jun 2012 21:04:33 +0000 (UTC)
Injection-Info: mx04.eternal-september.org; posting-host="03ebLEozl+tXCe7JS60Feg"; logging-data="19882"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX197SOMD492nJRsMgtwu4/zk"
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:12.0) Gecko/20120428 Thunderbird/12.0.1
In-Reply-To: <jqtian$er7$1@news.albasani.net>
Cancel-Lock: sha1:QWlxSq+rQzuN9klc1pQLpBWvkvQ=
Xref: csiph.com comp.lang.java.programmer: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