Thread: March 2019
View Single Post
Old 2019-04-04, 16:32   #7
Jan 2017

79 Posts

Originally Posted by Dieter View Post
my "quadruple-precision floating point format" codes were not exact enough to compute BAT((sqrt(ni),N1) or BAT((sqrt(ni),N2
You don't need floating point. In the case of square roots, the usual rational approximation algorithm works out so that all the intermediate values can be represented by small integers (you only get numbers of the form (sqrt(n) + a)/b, where a and b are below 2*sqrt(n)).

The code below demonstrates this. Note that it prints all optimal lower and upper bounds, not just optimal approximations.


n = 53
limit = 1e19

k = int(n**.5)
assert k**2 != n
e = 0
a, d, p = 0, 1, n
lb, ub = [0, 1], [1, 0]
while lb[1] < limit:
    print(('lower' if e == 0 else 'upper') + ' bounds:')
    i = (a+k)//d
    for _ in range(i):
        lb[0] += ub[0]
        lb[1] += ub[1]
        if lb[1] >= limit:
        print(lb[0], '/', lb[1])
    a, d, p = i*d - a, p - i*(i*d -2*a), d
    assert a < (k+1) and d < 2*(k+1)
    lb, ub, e = ub, lb, 1-e

Last fiddled with by uau on 2019-04-04 at 17:06 Reason: simplify code
uau is offline   Reply With Quote