// ----------------------------------------------------------------- // numbers.txt: big number arithmetic // Concrete Abstractions: Big Number and Polynomial Arithmetic // (c) 2020, Wolfgang Schreiner, RISC, JKU Linz, Austria // ----------------------------------------------------------------- val N:ℕ; // number of digits val D:ℕ; // digit base axiom notZero ⇔ D ≥ 2; // core types type digit = ℕ[D-1]; type num = Array[N,digit]; type index = ℤ[-1,N]; // interpretation of digit sequences as natural numbers val M = D^N-1; type nat = ℕ[M]; fun nat(a:num,n:index):nat = ∑i:index with 0 ≤ i ∧ i < n. a[i]⋅D^i; fun nat(a:num):nat = nat(a,N); // sequences of digits val zero = Array[N,digit](0); theorem zeroVal ⇔ nat(zero) = 0; fun num(i:index,d:digit):num requires 0 ≤ i ∧ i < N; ensures nat(result) = d⋅D^i; = zero with [i] = d; // an "infinity value" val infinity:num = Array[N,digit](D-1); theorem infinityVal ⇔ nat(infinity) = M; // conversion of possibly larger computational results to natural numbers type res = ℕ[M⋅M]; fun cut(r:res):nat = if r ≤ M then r else M; // implicit definition of addition for analysis fun add1(a:num,b:num):num ensures nat(result) = nat(a)+nat(b); = choose c:num with nat(c) = nat(a)+nat(b); fun add2(a:num,b:num):num ensures nat(result) = cut(nat(a)+nat(b)); = choose c:num with nat(c) = cut(nat(a)+nat(b)); proc shiftLeft(a:num,n:index):num requires 0 ≤ n ∧ n < N; ensures nat(result) = cut(nat(a)⋅D^n); /* ensures if ∃i:index with N-n ≤ i ∧ i < N. a[i] > 0 then result = infinity else ∀i:index with 0 ≤ i ∧ i < N. if i < n then result[i] = 0 else result[i] = a[i-n]; */ { var c:num ≔ zero; if ∃i:index with N-n ≤ i ∧ i < N. a[i] > 0 then c ≔ infinity; else { for var i:index ≔ 0; i < N-n; i ≔ i+1 do invariant 0 ≤ i ∧ i ≤ N-n; invariant nat(c,i+n) = cut(nat(a,i)⋅D^n); decreases N-n-i; { c[i+n] ≔ a[i]; } } return c; } proc shiftRight(a:num,n:index):num requires 0 ≤ n ∧ n ≤ N; ensures nat(result) = nat(a)/(D^n); // ensures ∀k:index with 0 ≤ k ∧ k < N. // result[k] = if k < N-n then a[k+n] else 0; { var c:num ≔ zero; for var i:index ≔ 0; i < N-n; i ≔ i+1 do invariant 0 ≤ i ∧ i ≤ N-n; invariant ∀k:index with 0 ≤ k ∧ k < N. c[k] = if k < i then a[k+n] else 0; decreases N-i; { c[i] := a[i+n]; } return c; } proc add(a:num,b:num):num ensures nat(result) = cut(nat(a)+nat(b)); { var c:num ≔ zero; var carry:digit ≔ 0; for var i:index ≔ 0; i < N; i ≔ i+1 do invariant 0 ≤ i ∧ i ≤ N; invariant 0 ≤ carry ∧ carry ≤ 1; invariant nat(c,i)+carry⋅D^i = nat(a,i)+nat(b,i); decreases N-i; { val r = a[i]+b[i]+carry; c[i] ≔ r%D; carry ≔ r/D; } if carry > 0 then c ≔ infinity; return c; } proc subtract(a:num,b:num):num requires nat(a) ≥ nat(b); ensures nat(result) = nat(a)-nat(b); { var c:num ≔ zero; var carry:digit ≔ 0; for var i:index ≔ 0; i < N; i ≔ i+1 do invariant 0 ≤ i ∧ i ≤ N; invariant 0 ≤ carry ∧ carry ≤ 1; invariant nat(c,i)-carry⋅D^i = nat(a,i)-nat(b,i); decreases N-i; { val r = a[i]-b[i]-carry; if r ≥ 0 then { c[i] ≔ r; carry ≔ 0; } else { c[i] ≔ r+D; carry ≔ 1; } } return c; } proc multiply(a:num,b:digit):num ensures nat(result) = cut(nat(a)⋅b); { var c:num ≔ zero; var carry:digit = 0; for var i:index = 0; i < N; i ≔ i+1 do invariant 0 ≤ i ∧ i ≤ N; invariant nat(c,i)+carry⋅D^i = nat(a,i)⋅b; decreases N-i; { val r = a[i]⋅b+carry; c[i] = r%D; carry = r/D; } if carry > 0 then c ≔ infinity; return c; } proc multiply(a:num,b:num):num ensures nat(result) = cut(nat(a)⋅nat(b)); { var c:num ≔ zero; for var i:index = N-1; i ≥ 0; i ≔ i-1 do invariant -1 ≤ i ∧ i ≤ N-1; invariant nat(c) = cut(∑k:index with i+1 ≤ k ∧ k < N. nat(a)⋅b[k]⋅D^(k-i-1)); decreases i+1; { val r = multiply(a,b[i]); c ≔ add(shiftLeft(c,1),r); } return c; } proc divide(a:num,b:num):Tuple[num,num] requires nat(b) ≠ 0; ensures nat(a) = nat(b)⋅nat(result.1)+nat(result.2); ensures nat(result.2) < nat(b); { var q:num ≔ zero; var r:num ≔ a; if nat(a) ≥ nat(b) then { val m = max i:index with 0 ≤ i ∧ i ≤ N ∧ nat(shiftRight(a,i)) ≥ nat(b). i; for var i:index ≔ m; i ≥ 0; i ≔ i-1 do invariant -1 ≤ i ∧ i ≤ m; invariant ∀k:index with 0 ≤ k ∧ k ≤ i. q[k] = 0; invariant nat(a) = nat(b)⋅nat(q)+nat(r); invariant nat(shiftRight(r,i+1)) < nat(b); decreases i+1; { q[i] ≔ nat(shiftRight(r,i))/nat(b); r ≔ subtract(r, multiply(b,num(i,q[i]))); } } return ⟨q,r⟩; } // ----------------------------------------------------------------- // Karatsuba algorithm // ----------------------------------------------------------------- proc split(a:num,n:index):Tuple[num,num] requires 0 ≤ n ∧ 2⋅n ≤ N; ensures ∀k:index with 0 ≤ k ∧ k < N. (result.1[k] = if k < n then a[k+n] else 0); ensures ∀k:index with 0 ≤ k ∧ k < N. (result.2[k] = if k < n then a[k] else 0); { var c:num ≔ zero; for var i:index ≔ 0; i < n; i ≔ i+1 do invariant 0 ≤ i ∧ i ≤ n; invariant ∀k:index with 0 ≤ k ∧ k < N. (c[k] = if k < i then a[k+n] else 0); decreases n-i; { c[i] ≔ a[i+n]; } var d:num = zero; for var i:index ≔ 0; i < n; i ≔ i+1 do invariant 0 ≤ i ∧ i ≤ n ∧ c = old_c; invariant ∀k:index with 0 ≤ k ∧ k < N. (d[k] = if k < i then a[k] else 0); decreases n-i; { d[i] ≔ a[i]; } return ⟨c,d⟩; } proc multTwoDigits(a:num,i:index,b:num,j:index):num requires 0 ≤ i ∧ i < N ∧ 0 ≤ j ∧ j < N; ensures nat(result) = cut(a[i]⋅b[j]); { var c:num ≔ zero; val r = a[i]⋅b[j]; c[0] = r%D; if r/D > 0 then { if N = 1 then c ≔ infinity; else c[1] = r/D; } return c; } proc multNumPartDigit(a:num,n:index,b:digit):num requires 0 ≤ n ∧ n ≤ N; ensures nat(result) = cut(nat(a,n)⋅b); { var c:num ≔ zero; var carry:digit = 0; for var i:index = 0; i < n; i ≔ i+1 do invariant 0 ≤ i ∧ i ≤ n; invariant ∀k:index with i ≤ k ∧ k < N. c[i] = 0; invariant cut(nat(c)+carry⋅D^i) = cut(nat(a,i)⋅b); decreases n-i; { val r = a[i]⋅b+carry; c[i] = r%D; carry = r/D; } if carry > 0 then { if n < N then c[n] := carry; else c := infinity; } return c; } fun karatsuba(a:num,b:num,m:index):num requires 0 ≤ m ∧ 2^(m+1)+1 ≤ N; requires ∀i:index with 2^m ≤ i ∧ i < N. a[i] = 0 ∧ b[i] = 0; ensures nat(result) = nat(a,2^m)⋅nat(b,2^m); decreases m; = if m = 0 then multTwoDigits(a,0,b,0) else let n = 2^m, a0 = split(a,n/2), b0 = split(b,n/2), p1 = karatsuba(a0.1,b0.1,m-1), p2 = karatsuba(a0.2,b0.2,m-1), q1 = add(a0.1,a0.2), q2 = add(b0.1,b0.2), r1 = multTwoDigits(q1,n/2,q2,n/2), r2 = multNumPartDigit(q1,n/2,q2[n/2]), r3 = multNumPartDigit(q2,n/2,q1[n/2]), r4 = karatsuba(q1 with [2^(m-1)] = 0,q2 with [2^(m-1)] = 0,m-1), p3 = add(shiftLeft(r1,n),add(shiftLeft(add(r2,r3),n/2), r4)), s = add(shiftLeft(p1,n),add(shiftLeft(p3,n/2), p2)), c = subtract(subtract(s,shiftLeft(p1,n/2)),shiftLeft(p2,n/2)) in c ; // ----------------------------------------------------------------- // end of file // -----------------------------------------------------------------