[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
