Mike Reid>>gfee>From the book titled "Seminumerical Algorithms" second edition, > by D. Knuth, page 363, exercice 4.5.3 number 39. says: > > 39. [M25] (R. W. Gosper) If a baseball player's battling average > is .334, what is the fewest possible number of times he has been at bat? MR >!!! >well how's about that! i'll make a guess that my pal from little league >didn't know about that (nor did i). A much older reference: www.tweedledum.com/rwg/cfup.htm . Excerpt: Here is an example which illustrates the tricky points. A sportscaster remarks that Joe diMolisho batted over .312 last year. Unfortunately, the sportscaster is notoriously pro diMolisho, so you can bet that if Joe batted as much as .3125, his friend in the booth would have said "Joe batted .313 last year". At least we know Joe saw a fair amount of action, by determining the simplest rational in the open interval (.312, .3125) (both endpoints excluded): .3120 +.0005 1.000 .0000 0 .3120 +.0005 3 .0640 -.0015 4 .0560 +.0065 1 .0625 .0080 -.0080 7 .0000 oo .0000 +.0625 thus establishing that .312 = 0 3 4 1 7 and .3125 = 0 3 4 1 oo = 0 3 5 . Notice that our streamlined algorithm conveniently produced the continued fraction for .3125 in just the (nonstandard) form we needed for the recipe. We have only to find the simplest rational in (7, oo), which is 8 because the oo is not in the interval. So, diMolisho's simplest possible performance ratio is 0 3 4 1 8 = 44/141 = .312051... MR >analysis is quite easy using the c.f. method i sketched. left as an >exercise for math-funsters. was the c.f. method the intended approach? At the time, yes. (It is, after all, the c.f. section of AoCP). However, for hand computation, an iterated mediant method (http://gosper.org/rectarith11.rtf (14MB!)) is usually easier. E.g., suppose the target is .239. On opposite sides of the page write 0/1 and 1/1 . The mediant, 1/2, is too big, so write it on the right: 1/2 Now take mediant(0/1,1/2) = 1/3. Still too big. 1/3 And again. 1/4 But the next one, 1/5 is too small, and goes on the left: 1/5 Continuing, 2/9 3/13 4/17 5/21 6/25 and finally 11/46 ~ .23913 . This is roughly equivalent to Euclid's cf method using subtraction instead of divison, and suffers from the problem of infinite worst-case "running time" due to the infinite expected value of c.f. terms, despite 2-lg 3 ~ 41.5% of them being 1. This is why I used .239 instead of .499.

rwg> (d75) 138

...

at bats. Serves me right for not using continued fractions.

MR >ok, that looks better. but how do you get the form (2n + 1) / (5n + 3) ?

is there some way without continued fractions?

When the target is close to a rational, the c.f. will have a large term, and the mediant process will bog down. But two glad tidings: you can skip the iterated subtraction by solving a little equation, and for small problems like batting averages, this large term will probably finish the spinach. We expect that the .399 case will end in a long march toward 2/5, and it can only have started from 1/3, hence the numerator 1+2n and denominator 3+5n. MR >btw, the c.f. method i described before can be cleaned up slightly.

to find the "simplest" rational number in the closed interval [a, b] , compute the convergents for the cf's of a and b . suppose p/q and P/Q are the last two they have in common. then the next convergent for each will be of the form (p + Pn) / (q + Qn) for some positive integer n .

Unless one terminated. if the simpler of these two is in the target interval,

then that's the one. otherwise, replace n by n+1 in its expression as above, and that gives the simplest fraction in the interval.

(this may require a and b to be positive, but it's easy to reduce to that case.)

A trickier problem, for which the mediant algorithm seems better suited: What is the nearest fraction to x with numerator <= a and denominator <= b? E.g., (farint pi 999) 355 113 (farint pi 999 112) 333 106 But notice I said "for hand computation" For some reason (personal stupidity?), the iterated mediant is ugly to code. The following was maybe my sixth try: (defun farint (x &optional (nhi 400) (dhi nhi) (ln 0) (ld 1) (hn 1) (hd 0)) (if (> (+ ln hn) (* (+ ld hd) x)) (let* ((m (min (if (= 0 ln) nhi (floor(- nhi hn) ln)) (floor (- dhi hd) ld))) (d (- (* x ld) ln)) (k (if (= 0 d) m (ceiling (- hn (* x hd)) d)))) (if (< k m) (farint x nhi dhi (setf hn (+ (* k ln) hn)) (setf hd (+ (* k ld) hd)) (- hn ln) (- hd ld)) (let* ((n (+ (* m ln) hn)) (d (+ (* m ld) hd))) (if (< (* 2 d ld x) (+ (* ld n) (* ln d))) (values ln ld) (values n d))))) (let* ((m (min (floor (- nhi ln) hn) (if (= 0 hd) dhi (floor (- dhi ld) hd)))) (d (- hn (* x hd))) (k (if (= 0 d) m (ceiling (- (* x ld) ln) d)))) (if (< k m) (farint x nhi dhi (- (setf ln (+ (* k hn) ln)) hn) (- (setf ld (+ (* k hd) ld)) hd) ln ld) (let* ((n (+ (* m hn) ln)) (d (+ (* m hd) ld))) (if (< (* 2 d hd x) (+ (* hd n) (* hn d))) (values n d) (values hn hd))))))) Presumably the two outer branches can be obnubilated into something half as long and twice as turbid. --rwg PS, http://gosper.org/rectarith11.rtf is my contribution to M. Gardner's 90th birthday Festschrift. http://gosper.org/rectarith12.rtf has a couple more pictures, but was insanely inflated another factor of 3+ by WordPad! PPS: Did Cooley and Tukey get a Festschrifft?