urnerk@qwest.net wrote:
The fun part here is we can use numerator/denominator syntax with
open-ended
precision integers, to like express sqrt of 19 as some humongous fraction (as many digits as memory will allow). This lets us far surpass the floating point barrier.
OK, here we go: def test_sqrt(numerator, denominator, trial): '''True iff trial (a num,den pair) over-estimates the sqrt(n/d)''' root_n, root_d = trial # return numerator / denominator >= root_n ** 2 / root_d ** 2 return root_d ** 2 * numerator >= root_n ** 2 * denominator # since we don't have 2.5 yet, here's a version of partial: def partial(function, *args): '''Simple no-kwargs version of partial''' def andthen(*final_args): return function(*(args + final_args)) return andthen def farey_trials(tester): '''Binary search for fraction. value must be between 0 and +Inf tester((num, den)) returns True if fract is high, False if Low ''' low_n, low_d = low = 0, 1 # 0/1 = 0 .. high_n, high_d = high = 1, 0 # 1/0 = Infinity while True: mediant_n = low_n + high_n mediant_d = low_d + high_d mediant = mediant_n, mediant_d yield mediant if tester(mediant): low_n, low_d = low = mediant else: high_n, high_d = high = mediant # Now here is a cute reporter that relies on another trick: # n & -n == n only if n is either 0 or a power of 2. for n, fraction in enumerate(farey_trials(partial(test_sqrt, 19, 1))): if n & -n == n: # report increasingly rarely print n, fraction if n > 4096: break -- Scott David Daniels Scott.Daniels@Acm.Org