\\ --------------- GP code --------------------------------------- \\ \\ Description: Routines for counting DBCs \\ \\ Original author: Christophe Doche \\ christophe.doche@mq.edu.au \\ Department of Computing \\ Macquarie University \\ \\ Created: 15 Sept 2014 \\This file requires data contained in precomp100.gp and possibly precomp101-150.gp \\alternate implementation of Lagrange's method; faster than polinterpolate in our situation {lagrange(u, v) = local(d, w, wp); d = length(u); w = prod(i = 1, d, x - u[i]); wp = deriv(w, x); return(w*sum(i = 1, d, v[i]/(subst(wp,x,u[i])*(x - u[i]))))} \\returns S_k(n, m), i.e. the number of signed DBCs with leading factor equal to 2^n*3^m \\also prints the number of unsigned DBCs, i.e. 2^(k-1)*S_k(n,m) {Sk(n, m, k) = local(M, list, line, p, q); if(k > limit, print("Not enough precomputations"), M = eval(Str("S"""k)); p = min(n,m); q = max(n,m); if(p > 0 && q > 0 && q <= k, res = M[p+1,q+1], if(p > 0 && p <= k, list = vector(k+1,i,if(p+1 <= i, M[p+1,i], M[i,p+1])),list = vector(k+1,i,0); for(line=1,k+1,list[line] = lagrange(vector(k+1,i,i - 1), vector(k+1,i,if(line <= i, M[line,i], M[i,line])))); list = subst(list,x,p)); res = subst(lagrange(vector(k+1,i,i-1), vector(k+1,i,list[i])),x,q)); print("Number of DBCs of length ", k, " with leading factor = 2^", n, "x3^", m); print("Unsigned: ", res, " (", length(binary(res)), " bits)"); print("Signed : ", 2^(k-1)*res, " (", k-1 + length(binary(res)), " bits)"); return(res))} \\returns T_k(n, m), i.e. the number of signed DBCs with leading factor <= to 2^n*3^m \\also prints the number of unsigned DBCs, i.e. 2^(k-1)*T_k(n,m) {Tk(n, m, k) = local(M, list, line, p, q); if(k > limit, print("Not enough precomputations"), M = eval(Str("T"""k)); p = min(n,m); q = max(n,m); if(p >= 0 && q >= 0 && q <= k, res = M[p+1,q+1], if(p >= 0 && p <= k, list = vector(k+1,i,if(p+1 <= i, M[p+1,i],M[i,p+1])),list = vector(k+1,i,0); for(line=1,k+1,list[line] = lagrange(vector(k+1,i,i-1), vector(k+1,i,if(line <= i, M[line,i], M[i,line])))); list = subst(list,x,p)); res = subst(lagrange(vector(k+1,i,i-1), vector(k+1,i,list[i])),x,q)); print("Number of DBCs of length ", k, " with leading factor <= 2^", n, "x3^", m); print("Unsigned: ", res, " (", length(binary(res)), " bits)"); print("Signed : ", 2^(k-1)*res, " (", k-1 + length(binary(res)), " bits)"); return(res))}