Re: rapidly converging rational sqrt

From: David Loeffler (loefflerdavid_at_hotmail.com)
Date: 10/28/04

  • Next message: Diego: "weighted tree generation" 
    Date: Thu, 28 Oct 2004 20:30:08 +0000 (UTC)

    TheBean wrote:

    > Below is a description of an algorithm which, with
    > each iteration, will double the number of significant
    > digits in the computation of a rational square root
    > approximation.

    [snip]
     
    > Here is an example run computing the sqrt of 1973 for 1 to 10
    > iterations of the algorithm. Note that after iteration 6 we have
    > more than 100 significant digits.
    >
    > 1 : 44.4184 | 552114124148567022233646060917619843207813905667651972754144711476673949363834982650044981364863
    > 2 : 44.41846462 | 88146721950566598272783899534327268025085249602382778806857857085449370627285274658896791048
    > 3 : 44.418464629025618764 | 2752431232557204024098591484297090342230548605659661647016608600579504981095676558
    > 4 : 44.4184646290256187643810796574090605395 | 683327294135496111246850857337544379108155113103260155775597834
    > 5 : 44.41846462902561876438107965740906053959497442704659903610246205761940066180 | 26805283703947239542091268
    > 6 : 44.4184646290256187643810796574090605395949744270465990361024620576194006618043686917147360058911830087
    > 7 : 44.4184646290256187643810796574090605395949744270465990361024620576194006618043686917147360058911830087
    > 8 : 44.4184646290256187643810796574090605395949744270465990361024620576194006618043686917147360058911830087
    > 9 : 44.4184646290256187643810796574090605395949744270465990361024620576194006618043686917147360058911830087
    > 10 : 44.4184646290256187643810796574090605395949744270465990361024620576194006618043686917147360058911830087

    I don't wish to denigrate your algorithm unduly, but square root algorithms
    with this rate of convergence have been known for millennia. The iteration
    x_{n+1} = 1/2 (x_n + C/x_n), which is believed to have been known to the
    ancient Babylonians, yields the following output if we take C = 1973 and start
    it at 44 (since your algorithm presupposes we know isqrt(C) this seems a fair
    comparison.) I have added vertical bars to indicate the correct portion of
    each decimal expansion; I have done the same for the quoted output from your
    algorithm above.

    1 : 44.4 | 2045454545454545454545454545454545454545454545454545454545454545454545454545454545454545454545455
    2 : 44.4184646 | 7359706039675341287006674573827298309263006116421312123537756692016093397520872578432056559
    3 : 44.418464629025618786 | 74355237890368384233529296754366053971048032852669727540929455186628564646861810
    4 : 44.4184646290256187643810796574090605 | 4522416704318229439469928529242853981217111573442879409690525472
    5 : 44.41846462902561876438107965740906053959497442704659903610246205761940066 | 216106505407447827420345844
    6 : 44.41846462902561876438107965740906053959497442704659903610246205761940066180436869171473600589118301...

    So like your algorithm this also produces 100 digits in 6 iterations, and it is
    easy to prove (since this is a special case of Newton's method for a general
    function) that convergence is quadratic in general.

    In short, your algorithm is interesting but it doesn't outperform the standard
    algorithms for square roots.

    Yours,

    David Loeffler

    (student, Trinity College,
    University of Cambridge, UK)

  • Next message: Diego: "weighted tree generation"

    Relevant Pages

    • Re: Not Just the US With Education Problems
      ... to compute a square root decide that they will never ... The algorithm for the computation isn't important. ... wanted into pairs of digits, ... actually is a longhand method of completing the square. ...
      (talk.origins)
    • Re: Fast Cube Root Using C33
      ... That algorithm computes one bit per iteration. ... I just checked a simple N-R algorithm for both square root and cube root. ...
      (comp.dsp)
    • Re: New integer multiplication algorithm
      ... this algorithm could be used to test ... If a coded string square root can be ... found which has all even digits, then replacing the 2's by 1's in that ... string gives the binary representation for the square root. ...
      (sci.math)
    • Short koan-like code snippets (was: coerce for arbitrary types)
      ... (defun bfs6 (test children pending) ... The algorithm seems to be a tail-recursive expression of what ... I don't like using tail recursion to emulate iteration, ...
      (comp.lang.lisp)
    • Iterative subspace decomposition
      ... Subspace Tracking," IEEE Transactions on Signal Processing, vol. 43, ... the PASTd algorithm does not produce orthogonal ... it is not producing the eigendecomposition I ...
      (sci.math.num-analysis)