1 # Generate test cases for a bignum implementation.
6 def findprod(target, dir = +1, ratio=(1,1)):
7 # Return two numbers whose product is as close as we can get to
8 # 'target', with any deviation having the sign of 'dir', and in
9 # the same approximate ratio as 'ratio'.
11 r = mathlib.sqrt(target * ratio[0] * ratio[1])
14 if a*b * dir < target * dir:
17 assert a*b * dir >= target * dir
25 terms = mathlib.confracr(a, b, output=None)
26 coeffs = [(1,0),(0,1)]
28 coeffs.append((coeffs[-2][0]-t*coeffs[-1][0],
29 coeffs[-2][1]-t*coeffs[-1][1]))
31 # a*c[0]+b*c[1] is as close as we can get it to zero. So
32 # if we replace a and b with a+c[1] and b+c[0], then that
33 # will be added to our product, along with c[0]*c[1].
36 # Flip signs as appropriate.
37 if (a+da) * (b+db) * dir < target * dir:
40 # Multiply up. We want to get as close as we can to a
41 # solution of the quadratic equation in n
43 # (a + n da) (b + n db) = target
44 # => n^2 da db + n (b da + a db) + (a b - target) = 0
45 A,B,C = da*db, b*da+a*db, a*b-target
47 if discrim > 0 and A != 0:
48 root = mathlib.sqrt(discrim)
50 vals.append((-B + root) / (2*A))
51 vals.append((-B - root) / (2*A))
52 if root * root != discrim:
54 vals.append((-B + root) / (2*A))
55 vals.append((-B - root) / (2*A))
61 if pp * dir >= target * dir and pp * dir < best[2]*dir:
72 if s[:2] == "0x": s = s[2:]
73 if s[-1:] == "L": s = s[:-1]
76 # Tests of multiplication which exercise the propagation of the last
77 # carry to the very top of the number.
78 for i in range(1,4200):
79 a, b, p = findprod((1<<i)+1, +1, (i, i*i+1))
80 print hexstr(a), hexstr(b), hexstr(p)
81 a, b, p = findprod((1<<i)+1, +1, (i, i+1))
82 print hexstr(a), hexstr(b), hexstr(p)