RE: Puzzler's Edge
03-06-2017, 04:32 PM
When you use Python (or any other respectable programming language), there are two iterative ways that you can use to approximate any real to a decently close fraction with low-ish denominators, terminating the process once you have sufficiently good approximations. (Once again if you're going to graph things on the real line and you want fractions, this is a necessary tradeoff.)
1) Continued fractions
Given N, keep taking the fractional part, then taking the reciprocal, etc. constructing a continued fraction expansion. You can choose to stop after some number of terms and then reconstruct your desired fraction. This converges pretty rapidly, I think. On the other hand, you're going to have to divide floats and thus you may encounter rounding errors.
2) Farey sequences
It's also iterative, in the following algorithm:
I'll assume your real number is between 0 and 1. Consider 0/1 and 1/1. Next, we "binary search" - however, instead of taking the midpoint of the two bound fractions, we instead take the mediant. That is to say, given a/b and c/d, your divider is (a+c)/(b+d).
That this process will eventually stumble upon every single exact rational is an exercise left to the reader. You can also terminate when the bounds are say within some epsilon apart.
Plus side: you only have to worry about float comparisons, so errors will not propagate in this algorithm.
Minus side: well... let's see
An example. So suppose we want to approximate pi-3=0.1415926535...
0/1 1/1
divider 1/2>x, so take left half
0/1 1/2
divider 1/3>x, so take left half
0/1 1/3
divider 1/4>x, so take left half
0/1 1/4
divider 1/5>x, so take left half
0/1 1/5
divider 1/6>x, so take left half
0/1 1/6
divider 1/7>x, so take left half
0/1 1/7
divider 1/8<x, so take right half
1/8 1/7
divider 2/15<x, so take right half
2/15 1/7
divider 3/22<x, so take right half
3/22 1/7
divider 4/29<x, so take right half
4/29 1/7
divider 5/36<x
5/36 1/7
6/43 1/7
7/50 1/7
8/57 1/7
9/64 1/7
10/71 1/7
11/78 1/7
12/85 1/7
13/92 1/7
14/99 1/7
15/106 1/7
15/106 16/113
...
So incidentally this touches both the approximations 22/7 and 355/113. That's not a coincidence.
On the other hand yeah this converges pretty slowly. You're basically doing Euclidean algorithm by individually subtracting each term, in some sense. Continued fractions shortcuts this.
1) Continued fractions
Given N, keep taking the fractional part, then taking the reciprocal, etc. constructing a continued fraction expansion. You can choose to stop after some number of terms and then reconstruct your desired fraction. This converges pretty rapidly, I think. On the other hand, you're going to have to divide floats and thus you may encounter rounding errors.
2) Farey sequences
It's also iterative, in the following algorithm:
I'll assume your real number is between 0 and 1. Consider 0/1 and 1/1. Next, we "binary search" - however, instead of taking the midpoint of the two bound fractions, we instead take the mediant. That is to say, given a/b and c/d, your divider is (a+c)/(b+d).
That this process will eventually stumble upon every single exact rational is an exercise left to the reader. You can also terminate when the bounds are say within some epsilon apart.
Plus side: you only have to worry about float comparisons, so errors will not propagate in this algorithm.
Minus side: well... let's see
An example. So suppose we want to approximate pi-3=0.1415926535...
0/1 1/1
divider 1/2>x, so take left half
0/1 1/2
divider 1/3>x, so take left half
0/1 1/3
divider 1/4>x, so take left half
0/1 1/4
divider 1/5>x, so take left half
0/1 1/5
divider 1/6>x, so take left half
0/1 1/6
divider 1/7>x, so take left half
0/1 1/7
divider 1/8<x, so take right half
1/8 1/7
divider 2/15<x, so take right half
2/15 1/7
divider 3/22<x, so take right half
3/22 1/7
divider 4/29<x, so take right half
4/29 1/7
divider 5/36<x
5/36 1/7
6/43 1/7
7/50 1/7
8/57 1/7
9/64 1/7
10/71 1/7
11/78 1/7
12/85 1/7
13/92 1/7
14/99 1/7
15/106 1/7
15/106 16/113
...
So incidentally this touches both the approximations 22/7 and 355/113. That's not a coincidence.
On the other hand yeah this converges pretty slowly. You're basically doing Euclidean algorithm by individually subtracting each term, in some sense. Continued fractions shortcuts this.