Ferguson-Forcade

Hello all,

I would like to start a discussion of the Ferguson-Forcade algorithm,
and related integer relation algorithms, and their application in
finding a generalized mediant function, applicable to chords of more
than two tones.

First, can anybody show how the Euclidean algorithm is related to our
familar "freshman sums" mediants?

-Carl

Carl wrote:
> I would like to start a discussion of the Ferguson-Forcade algorithm,
> and related integer relation algorithms, and their application in
> finding a generalized mediant function, applicable to chords of more
> than two tones.
>
> First, can anybody show how the Euclidean algorithm is related to our
> familar "freshman sums" mediants?
>
> -Carl

I can't find any relation yet.
But maybe this can give us idea's:

This is a kind of Euclidean algorithm to convert a ratio to its cf.
-----------------------------------------------------------------------
ratio -> cf

given ratio: 60/53

60/53 = 1.13207... TRUNC(1.13207...) = 1 60 - 53*1 = 7
53/7 = 7.57142... TRUNC(7.57142...) = 7 53 - 7*7 = 4
7/4 = 1.75 TRUNC(1.75) = 1 7 - 4*1 = 3
4/3 = 1.33333... TRUNC(1.33333...) = 1 4 - 3*1 = 1
3/1 = 3 TRUNC(3) = 3 3 - 1*3 = 0

60/53 = cf(1,7,1,1,3)
-----------------------------------------------------------------------

This is a way to find the mediant out of two cf's.
-----------------------------------------------------------------------
2 cf's -> mediant

given cf's: cf(1,2)
cf(1,3)

rewrite te given cf's in a way they can be seen as the limits of a
common cf-layer.

cf(1,2) = cf(1,2,1,0) (= 3/2 )
cf(1,3) = cf(1,2,1,%) (= 4/7 )

This cf-layer cuts the mediant in "1".

mediant = cf(1,2,1,1) = cf(1,2,2) (= 7/5 )
-----------------------------------------------------------------------
given cf's: cf(1,2)
cf(1,1,1,2)

rewrite te given cf's in a way they can be seen as the limits of a
common cf-layer.

cf(1,2) = cf(1,1,1,2,0) (= 3/2 )
cf(1,1,1,2) = cf(1,1,1,2,%) (= 8/5 )

This cf-layer cuts the mediant in "1".

mediant = cf(1,1,1,2,1) = cf(1,1,1,3) (= 11/7 )
-----------------------------------------------------------------------
-----------------------------------------------------------------------

Ever noticed the sum of the cf elements equals the level in the
Stern-Brocot tree. Is there an explanation?
-----------------------------------------------------------------------
1/1 = cf(1) = 1
2/1 = cf(2) = 2
3/2 = cf(1,2) = 1+2 = 3
4/3 = cf(1,3) = 1+3 = 4
5/3 = cf(1,1,2) = 1+1+2 = 4
5/4 = cf(1,4) = 1+4 = 5
7/5 = cf(1,2,2) = 1+2+2 = 5
8/5 = cf(1,1,1,2) = 1+1+1+2 = 5
7/4 = cf(1,1,3) = 1+1+3 = 5
6/5 = cf(1,5) = 1+5 = 6
9/7 = cf(1,3,2) = 1+3+2 = 6
11/8 = cf(1,2,1,2) = 1+2+1+2 = 6
10/7 = cf(1,2,3) = 1+2+3 = 6
11/7 = cf(1,1,1,3) = 1+1+1+3 = 6
13/8 = cf(1,1,1,1,2) = 1+1+1+1+2 = 6
12/7 = cf(1,1,2,2) = 1+1+2+2 = 6
9/5 = cf(1,1,4) = 1+1+4 = 6
-----------------------------------------------------------------------

Peter

>Ever noticed the sum of the cf elements equals the level in the
>Stern-Brocot tree. Is there an explanation?

It's trivial, isn't it? Each move up in the S-B tree either adds 1 to the
last term of the CF or adds a term to the CF, right?

Peter (me):
>> Ever noticed the sum of the cf elements equals the level in the
>> Stern-Brocot tree. Is there an explanation?

Paul
> It's trivial, isn't it? Each move up in the S-B tree either adds
> 1 to the last term of the CF or adds a term to the CF, right?

Right, but that's a second more specific fenomen.
I was just looking at the levels in general, not climbing up by
the branches like you did.

Peter

P.Mulkers@...
Belgium

Peter:
>>> Ever noticed the sum of the cf elements equals the level in the
>>> Stern-Brocot tree. Is there an explanation?

Paul
>> It's trivial, isn't it? Each move up in the S-B tree either adds
>> 1 to the last term of the CF or adds a term to the CF, right?

Peter:
>Right, but that's a second more specific fenomen.
>I was just looking at the levels in general, not climbing up by
>the branches like you did.

Right, so the inductive proof of your observation would consist of my
observation plus the observation that the first level consists only of the
fractions 1/0 and 0/1.