[EMAIL PROTECTED] 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 [EMAIL PROTECTED] _______________________________________________ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig