Re: finding n-limit ratios

Hi there,

I've been working recently on section of FTS that finds close
approximations to n-limit ratios

You can find it in current beta preview, but it is very slow
for large quotients. It does it just by testing all quotients,
and working out what the denominator would be for that quotient,
then if denom / denum is within the desired tolerance,
checks if they are both n-limit. If denom is n-limit, and denum isn't,
does an increment / decrement of denum until it finds one that is okay,
or until it goes outside the desired tolerance.

However, even that fairly crude technique is useful for this
work, where small values of denom. and denum. are interesting to find.
It's not too bad for max quotient of 1000.

I'm interested to extend the range.

I've been trying a very simple technique:

suppose r = ratio, and suppose you want it 5 limit,
then write

r~= 2^a*3^b*5^c

as
log r ~= a log 2 + b log 3 + c log 5

Now set a max quotient to find and tolerance in cents
in advance.

From that, one can calculate a max possible power for each
of the exponents. E.g. b < log(N)/log 3 where N is the max quotient.

Now just loop over all the possible values for b and c.
Leave a free, since as a power of 2, it will be the largest.

For each value of b, c, you can then work out a value for a
as
a = (log r - b log 3 - c log 5)/ log 2

and since you want an integer, use the floor and ceil of a
i.e. nearest integers above and below.

This is very fast for 5 limit ratios.

E.g. for max quotient of 1000000, you have
integer part of log(1000000)/log(5)= 10
and of log(1000000)/log(3)= 12

So, taking negative numbers into account you have
24*16 = 384 loops to do for each ratio. That's tiny,
even if you are testing maybe 20 numbers or more,
and doing a fair bit of processing in each loop.

Even up to max quotient of 1000000000000 works fine.

Doubling the number of digits will only double the
range for each of the powers, and since there are
two involved, that quadruples the time.

Add in fourth factor though
2 3 5 7
and you begin to get into seriously large numbers.
Each time you double the number of digits you
multiply the time needed by 8. That's a siginificant
difference.

Add a couple more factors and it is getting on for as
slow as the method of checking all the quotients in
succession, for small quotients (of course
it will always be faster for large quotients
if you are willing to wait for the answer).

I can refine this a little by just doing things
more efficiently.

However, I wondered if there is any way to go more
directly to the solution rather than search all
the points of the lattice. I've been puzzling it
over but haven't come up with anything yet.

I've heard of the LLL and PLSQ algorithms.
However, seems to me if you look for an integer
relation between (r, log 2, log 3, log 5, log 7)
then you are as likely to find a relation with 0
coeff. for r as one involving r and the remaining
ones. Also if you find a relation involving r,
then the coeff. for r could be greater than 1,
and that would be no good either. Am I missing
something?

I've had a look for free source code
for PLSQ but only found gpld code which I can't
use in FTS. However, if it is likely to solve this
I'll be interested to look more thoroughly, or
if nec, try and see if I can code it myself,
which should be poss, if I can find a good
clear description somewhere of how it works.

Any thoughts? Or hints of an idea even that might
lead to something?

Robert

Hi there,

> However, seems to me if you look for an integer
> relation between (r, log 2, log 3, log 5, log 7)
that of course should be

> relation between (log r, log 2, log 3, log 5, log 7)

so if coeff of log r > 1 you end up with a nice expression
of, say, r^3 as an n-limit ratio.

Robert