From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: fractional representations of decimals Date: 14 Jan 1999 17:39:36 GMT Keywords: Measures of quality of approximations by rationals Michael Hamm wrote: >The number 0.43 can be represented by several fractions: 43/100 is perfect >in accuracy, but is unwieldy in that the denominator has three digits; 1/2 >is very wieldy (that's not a word, but you get my point), but is not very >accurate; and 3/7 is a good compromise. > >If there is some way of measuring unwieldiness (say, proportional to the >value of the denominator, or proportional to the number of its digits, or >something of the sort), and some way of measuring accuracy (say, percent >difference from actual value or something), then the two values could be >combined to form some sort of criterium for which is the best fractional >representation of a decimal. You want fractions p/q so that |x - p/q| is small relative to p and q. You can ask for having |x - p/q| smaller than |x - p'/q'| for every fraction with q' < q ; those are the Farey approximants of x. Note that you can certainly have |x - p/q| be less than 1/q simply by choosing the right p, so perhaps what's more remarkable is when the ratio E(p/q) = ( |x - p/q| ) / ( 1/q ) is small. The fractions having E(p/q) less than E(p'/q') for every fraction with q' < q are the continued fraction approximants of x. Farey approximants include continued-fraction approximants. One can show that |x - p/q| < 1/q^2 for all continued-fraction approximants p/q of a number x. Indeed, the difference is approximately (1/N)*(1/q^2), where N is the next term in the continued-fractions expansion of x, so you can set your level of attention to, say, occurences of term greater than 10 in the continued-fractions expansion of x. Examples: Pi = 3.14159... has the Farey sequence 3/1 4/1 7/2 10/3 13/4 16/5 19/6 22/7 25/8 47/15 69/22 ... If you recognize "freshman addition", you might be able to discern the algorithm (Hint: which numbers are too big? Which too small?) The continued-fraction approximants abbreviate this sequence by jumping to the next change between too-big and too-small: 3/1 22/7 333/106 355/113 The terms following these in the continued-fraction exansion of Pi are 7, 15, 1, and 292 respectively, which is why people remember the "3", "22/7", and "355/113" but not the "333/106". log(3)/log(2) = 1.5849625... has Farey sequence 1/1 2/1 3/2 5/3 8/5 11/7 19/12 27/17 46/29 65/41 84/53 and continued-fraction sequence 1/1 2/1 3/2 8/5 19/12 65/41 84/53 485/306 1054/665 followed by 1 2 2 3 1 5 2 23 respectively, that is, none except the last is really remarkable, I guess. The denominators 5, 12, 41, ... suggest useful partitions of a musical octave into 5, 12, 41, ... equal tones, if you want transposable music which has a good approximation of a pure "fifth". Your number 0.43 has a Farey sequence 0/1 1/1 1/2 1/3 2/5 3/7 4/9 7/16 10/23 13/30 ... 43/100 among which we may select the continued-fraction approximants 0/1 1/2 3/7 43/100 Since the continued-fraction expansion is just [0,2,3,14], the penultimate term is rather good (and of course the last is perfect). Exercise: which real number in the interval [0,1] is the worst in terms of finding "remarkable" rational approximations? dave Continued fractions: index/11AXX.html Quality of rational approximations in general: index/11JXX.html ============================================================================== [Answer to exercise: 1/phi=[1,1,1,...]=0.618... --djr]