rationalize

This has probably been discussed here before... I'm looking
for a method to find the rational with the lowest Tenney height
within n cents of an irrational target. My recollection is
that Brun's algorithm does this, but that Gene said there
are better ways...

-Carl

I wrote...

>This has probably been discussed here before... I'm looking
>for a method to find the rational with the lowest Tenney height
>within n cents of an irrational target. My recollection is
>that Brun's algorithm does this, but that Gene said there
>are better ways...

Here's some scheme that attempts this by interating mediants.
I think this is the same as traversing the Stern-Brocott tree.
Is this the same as Brun's algorithm? Does it give correct answers?

-Carl

;; Returns the mediant of two fractions.

(define middle
(lambda (left right)
(if (not (and (exact? left) (exact? right)))
'inputerror
(/ (+ (numerator left) (numerator right))
(+ (denominator left) (denominator right))))))

;; Returns the simplest rational within a given factor (range) of
;; target, where complexity is defined as numerator*denominator
;; and 1 < range < target.

(define gear
(lambda (target range)
(letrec
((loop (lambda (left right target range)
(let ((mediant (middle left right)))
(if (<= (/ (max mediant target)
(min mediant target)) range)
mediant
(loop
(if (< mediant target) mediant left)
(if (> mediant target) mediant right)
target
range))))))
(if (or (<= range 1) (>= range target))
'inpur
(loop
(inexact->exact (floor (/ target range)))
(inexact->exact (ceiling (* target range)))
target
range)))))

--- In tuning-math@yahoogroups.com, Carl Lumma <ekin@l...> wrote:

> This has probably been discussed here before... I'm looking
> for a method to find the rational with the lowest Tenney height
> within n cents of an irrational target. My recollection is
> that Brun's algorithm does this, but that Gene said there
> are better ways...
>
> -Carl

Euclid's algorithm should get you there, because lowest Tenney height
is the same as lowest denominator as long as you're focusing on a small
enough neighborhood . . . I don't think there's a Brun algorithm for
two-term ratios which is distinct from Euclid's algorithm.

At 01:10 PM 8/26/2005, you wrote:
>--- In tuning-math@yahoogroups.com, Carl Lumma <ekin@l...> wrote:
>> This has probably been discussed here before... I'm looking
>> for a method to find the rational with the lowest Tenney height
>> within n cents of an irrational target. My recollection is
>> that Brun's algorithm does this, but that Gene said there
>> are better ways...
>>
>> -Carl
>
>Euclid's algorithm should get you there,

I know of this as a method for finding the gcd of two terms.
How can it be used to do the above?

>because lowest Tenney height is the same as lowest denominator
>as long as you're focusing on a small enough neighborhood . . .

How small would that have to be?

-Carl

--- In tuning-math@yahoogroups.com, Carl Lumma <ekin@l...> wrote:
> At 01:10 PM 8/26/2005, you wrote:

> >Euclid's algorithm should get you there,
>
> I know of this as a method for finding the gcd of two terms.
> How can it be used to do the above?

Euclid's method is closely connected to continued fractions, and hence
to convergents and semiconvergents.