Wondering about Domingo's Rational Mean book
Author Message
Wondering about Domingo's Rational Mean book

Have folks on sci.math already discussed
http://www.*-*-*.com/
to anyone's recollection?  I'd be interested in
comments and/or pointers to previous postings.

I don't have the necessary background to evaluate the
significance of this work, but the algorithms made
interesting programming exercises.  Using them, I
was able to get:

3rd root of 2 is about:

65379522
---------
51891761

3rd root of 10 is about:

91969780593702397138462508494860
---------------------------------
42688590663356403236303435376201

You can push these things further.  E.g.

10^(1/3) ~=  2196555918195778106276024585870817879185576760
----------------------------------------------
1019550942230358826790302872023722041913882251

I also liked his concise presentation of Halley's method, which
gives me the floating point nth rooth of an integer.  Here's
a recursive version:

def halley(P,n,d=10,x=1):
# Source: http://www.*-*-*.com/
# P -- find nth root of this number
# n -- whole number root
# d -- level of depth for recursion (default 10)
# x -- initial value of x (default 1)
if d>1:
newx = ((n+1.0)*P*x + (n-1)*(x**(n+1)))/((n-1)*P + (n+1)*x**n)
return halley(P,n,d-1,newx)
else:
return x

Usage:

>>> halley(10,3)            # 3rd root of 10 to depth 10
2.1544346900318838
>>> halley(2,3)             # 3rd root of 10 to depth 10
1.2599210498948732
>>> halley(12931021,7)      # 7th root of 12931021 to depth 10
10.336898680701067
>>> halley(12931021,7,40)   # same to depth 40 (more accurate)
10.374031092075427

Sorry if this is old hat on sci.math -- thought it was pretty
cool myself.

Kirby

Domingo's work):

=============

Quote:

>Subject: fluidiom: math stuff
>Date: Tue, 9 May 2000 16:55:14 -0400

>Anybody out there follow what this guy (Domingo Gomez  Morin) is up to...?
>Kirby? Allen?
>Would this be useful in fluidiom ... *IS*  this "New and Improved"?
>He doesn't seem bashful even as he bashes cartesian thought...
>so he oughta fit in OK around here.

> http://www.*-*-*.com/

>Core9

Sat, 16 Nov 2002 03:00:00 GMT
Wondering about Domingo's Rational Mean book

> >>> halley(2,3)             # 3rd root of 10 to depth 10
^^
2
Sorry, typo.

If anyone on comp.lang.python wants me to post source
code for the giant root fractions, let me know.

Don't worry, I won't clutter sci.math with such stuff.

Kirby

Sat, 16 Nov 2002 03:00:00 GMT
Wondering about Domingo's Rational Mean book

Quote:

> Have folks on sci.math already discussed
> http://www.etheron.net/usuarios/dgomez/Roots.htm
> to anyone's recollection?  I'd be interested in
> comments and/or pointers to previous postings.

The advantage of standard CFs is that they produce all
best approximations. The mean method for cbrt(2)-1 misses
131/ 504, for example.

Sun, 17 Nov 2002 03:00:00 GMT
Wondering about Domingo's Rational Mean book

Quote:

>> Have folks on sci.math already discussed
>> http://www.etheron.net/usuarios/dgomez/Roots.htm
>> to anyone's recollection?  I'd be interested in
>> comments and/or pointers to previous postings.

>The advantage of standard CFs is that they produce all
>best approximations. The mean method for cbrt(2)-1 misses
>131/ 504, for example.

I presume by "best" you mean most accuracy for the least
digits.  Like, the mean method gets me closer to cbrt(2)-1
than 131/504 with fractions like 4159/16001 or 236845/911219
or 168286661033/647452990441 -- but you're saying standard
CFs will converge more quickly, yes?

In other words the standard CFs will give a better approximation
when pushed to the same total number of digits -- something
along those lines?

Forgive my ignorance, but this is not my field of expertise.

Do you know of an URL where the standard algorithms for
approximating the nth root of k as p/q are spelled out,
something suitable for computerizing?

I'd like to code an algorithm that _does_ hit 131/504, and
compare it with the mean method for other values -- just
for kicks (plus I'm seeing applications in early math ed,
when ideas about fractions and roots are first being defined).

Kirby

Sun, 17 Nov 2002 03:00:00 GMT
Wondering about Domingo's Rational Mean book

[...]

Quote:
> Do you know of an URL where the standard algorithms for
> approximating the nth root of k as p/q are spelled out,
> something suitable for computerizing?

There was a long thread right here on comp.lang.python
(let's see, is that where I am, I think so...) on continued
fractions recently. A deja search for "continued fraction"
works.

DU

Sent via Deja.com http://www.deja.com/

Sun, 17 Nov 2002 03:00:00 GMT
Wondering about Domingo's Rational Mean book

Quote:

>     There was a long thread right here on comp.lang.python
>(let's see, is that where I am, I think so...) on continued
>fractions recently. A deja search for "continued fraction"
>works.

>DU

Thanks David!

I did the search and indeed retrieved the source code I
was looking for, generously provided by Michael Hudson

http://www.deja.com/getdoc.xp?AN=624458140&fmt=text

========================================================

epsilon = 2.2204460492503131e-16

def cfrac(x,err=0.0):
result = []
err = err + epsilon
while 1:
a,b = divmod(x, 1.0)
result.append( int(a) )
if not b:
return result
err = err / (b * (b + err))
if err > b:
return result
x = 1 / b

def converge(partials):
p_1, q_1, p, q = 0, 1, 1, 0
result = []
for a in partials:
p_1, q_1, p, q = p,q, a*p+p_1, a*q+q_1
result.append( (p,q) )
return result

========================================================

Usage:

>>> from roots import cfrac,converge
>>> val = 2.**(1./3.)-1
>>> val
0.25992104989487319
>>> converge(cfrac(val))
[(0, 1), (1, 3), (1, 4), (6, 23), (7, 27), (13, 50), (59, 227),
(72, 277),   (131, 504), (1120, 4309), (1251, 4813), (18634, 71691),
(19885, 76504), (217484, 836731), (454853, 1749966),
(672337, 2586697),(3144201, 12096754)]

My python code for a different method, called RP2 at Domingo's
website, gets me the following (numerator, denominator) pairs
(Note: I've stripped off the long integer Ls for readability):

[(1, 5), (5, 19), (19, 73), (73, 281), (281, 1081), (1081, 4159),
(4159, 16001), (16001, 61561), (61561, 236845), (236845, 911219),
(911219, 3505753), (3505753, 13487761), (13487761, 51891761),
(51891761, 199644319), (199644319, 768096001),
(768096001, 2955112721), (2955112721, 11369270485)]

Note how the latter series uses the denominator of the previous
for the numerator of the next.  I'll do a quick comparison of
the error (absolute difference from the floating point target
value of 2**(1./3.)-1 in the form of a table:

METHOD 1 (standard CF)  METHOD 2 (rational mean)
0.259921049895          0.0599210498949
0.0734122834385         0.00323684484197
0.00992104989487        0.000352922707867
0.000948515322518       0.000134573026546
0.000661790635614       2.34459423146e-005
7.89501051268e-005      2.80031564742e-006
9.15562174542e-006      2.05026694233e-007
6.7479390618e-006       4.01913080594e-009
4.1497423825e-007       4.48542819553e-009
4.54868859245e-008      9.17280640333e-010
2.73094219461e-009      1.23254961792e-010
1.67198754841e-010      1.10377817997e-011
1.51283430228e-011      2.66620059364e-013
4.93438623295e-013      1.35114142097e-013
1.89515070304e-013      3.44169137634e-014
3.14193115969e-014      5.21804821574e-015
5.55111512313e-016      4.99600361081e-016

Note that METHOD 2 (Domingo's RP2) is actually converging
more quickly, right from the start.  However, it's also
true that "standard CF" is reaching its target with fewer
digits (shorter numerators and denominators).  Let's
compare "total number of digits" for the two methods:

Number of total digits in numerator,denominator:

METHOD1  METHOD2
2        2
2        3
2        4
3        5
3        7
4        8
5        9
5       10
6       11
8       12
8       13
10       15
10       16
12       17
13       18
13       19
15       21

So it's something of a trade off.  You'll get more accurate
fractions with fewer iterations using Method2, but you'll
need fewer digits for comparable accuracy using Method1.

Note that my code for Method2 (so far I haven't shared it,
mostly because it's kinda messy) isn't so general in that
it doesn't accept floating point values (like math.pi)
and aim at them.  Rather, my RP2 code finds the nth root
of k, with n and k both whole numbers.  So at this point
I can't easily give a converging series of fractions for
math.pi, as Michael does in his post.

Kirby

Sun, 17 Nov 2002 03:00:00 GMT
Wondering about Domingo's Rational Mean book

Quote:

>The advantage of standard CFs is that they produce all
>best approximations. The mean method for cbrt(2)-1 misses
>131/ 504, for example.

Domingo presents several algorithms based on the
rational mean.  His Rational Process ARP-2b, for
example, _does_ pick up the fraction you mention
i.e. 635/504 for cbrt(2) or 131/504 for cbrt(2)-1.

There's more source code in another branch of this
thread over at comp.lang.python, for those of you
interested in computerizing continued fractions etc.

Kirby

Sun, 17 Nov 2002 03:00:00 GMT
Wondering about Domingo's Rational Mean book

Quote:

> >The advantage of standard CFs is that they produce all
> >best approximations. The mean method for cbrt(2)-1 misses
> >131/ 504, for example.

> I presume by "best" you mean most accuracy for the least
> digits.  Like, the mean method gets me closer to cbrt(2)-1
> than 131/504 with fractions like 4159/16001 or 236845/911219
> or 168286661033/647452990441 -- but you're saying standard
> CFs will converge more quickly, yes?

> In other words the standard CFs will give a better approximation
> when pushed to the same total number of digits -- something
> along those lines?

You can always find better and better approximations
to say, cbrt(2)-1 , but there is no fraction with a smaller denominator
than 504 which will be closer. So in this sense 131/504 is optimal.

Quote:
> Do you know of an URL where the standard algorithms for
> approximating the nth root of k as p/q are spelled out,
> something suitable for computerizing?

Do you mean an algorithm that finds convergents directly
from x^n -k or just from a decimal approximation of the nth root ?

Cohen's book "A Course in Computational Algebraic Number
Theory" covers the latter I think.

Sun, 17 Nov 2002 03:00:00 GMT

 Page 1 of 1 [ 8 post ]

Relevant Pages