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