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 Root of BigInteger
Date: Fri, 8 Jun 2012 21:06:31 +0000 (UTC)
Organization: Aioe.org NNTP Server
Lines: 33
Message-ID: <jqtpgn$iuq$1@speranza.aioe.org>
References: <jqtian$er7$1@news.albasani.net> <kao4t7t4enn17mgmvv5lectdhhvdglfrcj@4ax.com> <jqtnoq$r0p$1@news.albasani.net> <jqtosd$g5b$1@dont-email.me>
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:15111

markspace <-@.> wrote:
(snip)
>>> On Fri, 08 Jun 2012 21:03:56 +0200, Jan Burse <janburse@fastmail.fm>

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

(snip)
>> Sorry, yes root, and z integer.

> Positive integers?  Do you want the complex roots too? ;-)  
> You ask big questions Jan, but I think you need to ask them 
> a little more thoughtfully.

I will guess that the OP isn't a native English speaker, and
is not translating so well.

I had to look it up as I didn't know, .fm seems to be Micronesia.

It looks like he wants the nth root rounded down to the next
integer value.

I do remember when first learning Fortran wondering why no
ISQRT function.

One possibility is to do exactly as written, binary search
for the largest z such that z**n <= x. (No exclusive or operators
are needed here.)

-- glen