// ************************************************************************** // // // // eses eses // // eses eses // // eses eseses esesese eses Embedded Systems Group // // ese ese ese ese ese // // ese eseseses eseseses ese Department of Computer Science // // eses eses ese eses // // eses eseses eseseses eses University of Kaiserslautern // // eses eses // // // // ************************************************************************** // // Exponentiation of a number can be reduced to the multiplication of smaller // // numbers by the equation exp(a,b+c) = exp(a,b) * exp(a,c). To make use of as// // few multiplications as possible, addition chains of minimal length have to // // be computed: Formally, an addition chain is a sequence of numbers c[i] so // // that c[0] = 1 and c[i+1] = c[j]+c[k] for j,k<=i. Often, one requires that // // even c[i+1] = c[j]+c[i] for j<=i holds (as below). It is obvious that the // // length of the addition chain ending in x is the number of multiplications // // required to compute exp(a,x). The module below computes the addition chain // // due to Brauer that is better than the addition chain obtained by the // // binary representation. Given numbers x and k, the Brauer sequence B(k,x) is// // defined as B(k,x) = B(k,q) * [2q,4q,8q,…,exp(2,k)q,x] if x>=exp(2,k) with // // q=n/exp(2,k) and B(k,x) = [1,2,3,…,exp(2,k)-1] if x<exp(2,k). The length is// // best for k around log(log(x)) - 2log(log(log(x))). // // ************************************************************************** // macro K = 16; macro ceillog(x) = (exp(2,log(x))==x ? log(x) : log(x)-1); module BrauerChain(nat{exp(2,K)} ?x,nat{K} ?k,[2*K]nat c,event !rdy) { nat{exp(2,K)} n,q; nat{2*K} i,j; j = 0; n = x; while(n>=exp(2,k)) { // determine subsequence [2q,4q,8q,…,exp(2,k)q,n] in c[j..j+k] in // reversed order; we also write c[j+k+1] = q, which may be overwritten q = n/exp(2,k); next(i) = j+k; next(c[j]) = n; next(c[j+k+1]) = q; pause; while(i>j) { next(c[i]) = 2*c[i+1]; next(i) = i-1; pause; } next(j) = j+k+1; next(n) = q; pause; } // add the final subsequence 1,2,3,…,exp(2,k)-1 in c[j..exp(2,k)] i = exp(2,k)-1; while(i>0) { next(c[j]) = i; next(j) = j+1; next(i) = i-1; pause; } emit(rdy); } drivenby { x = 31415; k = 3; await(rdy); } drivenby { x = 32767; k = 3; await(rdy); }