[Edu-sig] Brute force solutions

[Scott David Daniels]

urnerk at 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 at Acm.Org