pragma options "--bnd-inline-amnt 5 --bnd-inbits 2 --bnd-cbits 3 "; int BASE = 4; int[2*N] mult(int N, int[N] x, int[N] y){ int[2*N] out = 0; for(int i=0; i<N; ++i){ for(int j=0; j<N; ++j){ int tmp = y[i] * x[j]; tmp = out[j + i] + tmp; out[j + i] = tmp % BASE; out[j + i + 1] = out[j + i + 1] + (tmp / BASE); } } return out; } int[2*N] karatsuba(int N, int[N] x, int[N] y) implements mult { if(N % 2 != 0){ return mult(N, x, y); } int No2 = N/2; int[No2] x1, x2, y1, y2; int[N] a=0, b=0, c=0; int[2*N] out = 0; x1=x[0::No2]; x2=x[No2::No2]; y1=y[0::No2]; y2=y[No2::No2]; a = karatsuba(No2, x1, y1); b = karatsuba(No2, x2, y2); c = karatsuba(No2, poly1(No2, x1,x2,y1,y2), poly1(No2, x1,x2,y1,y2)); out = a; out = plus(2*N, out, shiftVect(2*N, b, N)); repeat(??){ int[N] t = {| a | b | c |}; out = plus(2*N, out, shiftVect(2*N, {| t | minus(N, t) |} , {|N | No2 | 0|} ) ); } out = normalize(2*N, out); return out; } int[N] plus(int N, int[N] x, int[N] y){ int[N] out = 0; for(int i = 0; i<N; ++i){ int tmp = x[i] + y[i] + out[i]; out[i] = tmp % BASE; if(i < N-1){ out[i+1] = tmp / BASE; } } return out; } int[N] shiftVect(int N, int[N] in, int s){ int[N] out = 0; for(int i=0; i<N; ++i){ if(i ≥ s){ out[i] = in[i-s]; } } return out; } int[N] minus(int N, int[N] t){ int[N] out = 0; for(int i=0; i<N; ++i){ out[i] = -t[i]; } return out; } generator int[N] poly1(int N, int[N] a, int[N] b, int[N] c, int [N] d){ int[N] out = 0; if(??){ out = plus(N, out, {| a | minus(N,a) |}); } if(??){ out = plus(N, out, {| b | minus(N,b) |}); } if(??){ out = plus(N, out, {| c | minus(N,c) |}); } if(??){ out = plus(N, out, {| d | minus(N,d) |}); } return out; } void print(int x){ if(x==0){ x = 5; } } int sgn(int i){ return i ≥ 0 ? 1 : -1; } int[N] normalize(int N, int[N] in){ int end = N-1; int[N] out = in; int s = 0; bit found = 0; for(int i = 0; i<N; ++i){ if(!found && out[end-i]!=0){ s = sgn(out[end-i]); found = 1; } } for(int i = 0; i<N-1; ++i){ if(sgn(out[i]) != s){ int t = BASE * s + out[i]; out[i] = t; out[i+1] = out[i+1] - s; } } return out; }