From ah@elan.Princeton.EDU Thu Apr 21 12:05:51 PDT 1994 Article: 4866 of comp.graphics.algorithms Newsgroups: comp.graphics.algorithms Path: kpc!news.kpc.com!sgiblab!swrinde!emory!europa.eng.gtefsd.com!news.umbc.edu!eff!usenet.ins.cwru.edu!news.ecn.bgu.edu!psuvax1!news.pop.psu.edu!news.cac.psu.edu!newsserver.jvnc.net!nntpserver.pppl.gov!princeton!elan!ah From: ah@elan.Princeton.EDU (Alejo Hausner) Subject: Fast algorithm for CUBE roots Message-ID: <1994Apr20.034540.7985@Princeton.EDU> Originator: news@nimaster Sender: news@Princeton.EDU (USENET News System) Nntp-Posting-Host: elan.princeton.edu Organization: Princeton University Date: Wed, 20 Apr 1994 03:45:40 GMT Lines: 64 A couple of people expressed interest in extracting cube roots. Here's a description: Find the cube root of .5 to 4 places. w z 0 0 0+7=7 * 7--> 49 x r -- number root 49 .500,000,000,000 ( .7937 7+7=14 * 7--> 98 343 <- 7 * 49 14+7=21 --- --- 21*10=210 14700 157,000 210+9=219 * 9--> 1971 150,039 <- 9 * 16671 ----- ------- 16671 6,961,000 219+9=228 * 9--> 2052 5,638,257 <- 3 * 1879419 228+9=237 ----- --------- 237*10=2370 1872300 1,322,743,000 2370+3=2373 * 3--> 7119 1,321,748,953 <- 7 * 188821279 ------- ------------- 1879419 994,047 2373+3=2376 * 3--> 7128 2376+3=2379 ------- 2379*10=23790 188654700 23790+7=23797 * 7--> 166579 --------- 188821279 Given : x, the digits of the number whose cube root is needed, n, the desired precision in the answer, b, the base to use in computations (here, b is ten) Compute : r, the digits of the square root of x. Algorithm: Initialization: Starting at the decimal point, break up the digits of x into groups of 3 digits. 1. y = first three digits of x 2. t = floor(y^(1/3)) 3. z = 0 4. w = 0 Loop: 5. for i = 1 to n 6. r[i] = t 7. w = w + t 8. z = z + (w * t) 9. y = y - z * t 10. y = y * b * b * b + next three digits of x 11. w = w + t 12. z = (z + (w * t)) * b * b 13. w = (w + t) * b 14. t = int(t / z) 15. if (y < (z+t*(w+t))) then 16. t = t - 1 17. end if 18. end for