Thread: March 2019 View Single Post
2019-04-04, 16:32   #7
uau

Jan 2017

79 Posts

Quote:
 Originally Posted by Dieter 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.

Code:
#!/usr/bin/python3

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:
break
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