back to list

Re: Semi convergents

🔗Robert Walker <robert_walker@rcwalker.freeserve.co.uk>

3/3/2001 9:35:27 PM

Hi Dave,

Thanks for the suggestion.

I notice that Manuel has a command to find the semi-convergents
in SCALA

ratio/stern 250.0

and indeed, my one is leaving quite a few out - definitely a bug.

Thanks for noticing this.

There were two things going on.

First, my series begins 1/1, so when you are approximating to
250 cents, it will leave out the semi-convergents 2/1 and 3/2.

Secondly, there was a bug in the code.

I introduced it while optimising the javascript to be a little faster.

Code read:

...
// here approx >= x
// so 1- x/approx < approx/x - 1
// check for x/approx-1 < diff, and if this fails
// the new approx must be at least as far away as the previous one
//
if(x*denom/denum-1<diff)// no need for Math.abs(..) as it should be the right way round
...

Should have been:

// Note that if x >1, then x/approx -1 < x-approx < 1-approx/x,
//
if(1-x*denom/denum<diff)// no need for Math.abs(..) as it should be the right way round
....

Fixed now.

Plus also fixed the confusing comment in the code, and made sure x is
always >1 by inverting it (and then inverting the ratios again on output)
if you use program to find a ratio for a negative number of cents.

I'll have to look into semi-convergents and see how they work.

Checking it again with Scala, I find that it still misses out some
of the semi-convergents.

However, looking at the paper, the semi-convergents
[t0,t1,....,1],[t0,t1,....,2],...,[t0,t1,....,tkm1-1]
(using tkm1 for t subscript k-1)
are the best approximants to x from below, for k even,
and from above, for k odd.

This means that one can still expect to miss some out if one
looks only for the closest possible approximants, as a ratio
that is the best from above may be further away than the
most recent one that was best from below.

Indeed, looking at the Scala results, one finds, for 250 cents:

R 22/19 253.8049 cents 2.11.19^-1 [1;6,3]
Distance: 3.805 cents
L 37/32 251.3440 cents 2^-5.37 [1;6,2,2]
Distance: 1.344 cents
L 52/45 250.3039 cents 2^2.3^-2.5^-1.13 [1;6,2,3]
Distance: 0.304 cents
L 67/58 249.7298 cents 2^-1.29^-1.67 [1;6,2,4]
Distance: -0.270 cents
R 119/103 249.9807 cents 7.17.103^-1 [1;6,2,3,2]
Distance: -0.019 cents
R 171/148 250.0790 cents 2^-2.3^2.19.37^-1 [1;6,2,3,3]
Distance: 0.079 cents
L 290/251 250.0386 cents 2.5.29.251^-1 [1;6,2,3,2,2]
Distance: 0.039 cents
L 409/354 250.0218 cents 2^-1.3^-1.59^-1.409 [1;6,2,3,2,3]
Distance: 0.022 cents
L 528/457 250.0125 cents 2^4.3.11.457^-1 [1;6,2,3,2,4]
Distance: 0.013 cents
L 647/560 250.0067 cents 2^-4.5^-1.7^-1.647 [1;6,2,3,2,5]
Distance: 0.007 cents
L 766/663 250.0026 cents 2.3^-1.13^-1.17^-1.383 [1;6,2,3,2,6]
Distance: 0.003 cents
L 885/766 249.9997 cents 2^-1.3.5.59.383^-1 [1;6,2,3,2,7]

Notice that after 171/148, at -0.019 cents the next distance
is 0.079 cents, which indeed is closer than the previous closest
ratio from above at 0.304 cents, but further away than 171/148.

So my program is going to miss that one out.

Also it will miss the next two, and the next one you can expect
it to find is 528/457, which indeed it does (now anyway, after
fixing the bug)/

The semi-convergents look useful.

I wonder if one can prove that there are no other better
approximants between them - seems fairly likely somehow, but
would need to check up.

Also wonder if there is any way of forming a continued fraction
like approximation that only produces ratios that are n-limit,
or that involve a particular set of primes, or if there is
any way to extend these useful continued fraction type results
to n-limit ratios.

Robert