Path: csiph.com!usenet.pasdenom.info!aioe.org!.POSTED!not-for-mail From: glen herrmannsfeldt Newsgroups: comp.lang.java.programmer Subject: Re: Quick n-th Square of BigInteger Date: Sat, 9 Jun 2012 01:06:06 +0000 (UTC) Organization: Aioe.org NNTP Server Lines: 39 Message-ID: References: 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:15143 Jan Burse wrote: (after I wrote) >> 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. > Yes this would be an alternative to the bitCount() suggestion > from Eric. Since BigInteger has bitCount(), I guess bitCount() > is the more efficient solution. > The bisection is probably slower than Newton. In Newton you > have to compute x^n-1 and divide in each iteration, in > bisection you have to compute x^n and compare in each iteration. > So I take it that the effort for the iteration step itself > is more or less the same for both methods. I will guess that it depends much on the size of x and n. I like the bisection because it avoided the divide, which might be slow, but might not be. Also, since he wants floor(), you have to be careful for the case where y is very close to an integer power of n, and Newton might round the wrong way. (It is interesting, the IBM 360/91 uses the Newton't method divide algorithm for floating point divide, returning the rounded quotient. The S/360 architecture specifies a truncated quotient, so this has to be stated as a deviation from the architecture.) > So that in the end the number of iterations will be dominant. > When Newton doubles the precision in each iteration, it will > use log m/n steps (right?), whereas bisection probably also > uses log m/n steps in the average (right?). and x^n takes O(log n) multiplies. -- glen