OFFSET
1,2
COMMENTS
The addition is carried out by a parallel adder as described by J. von Neumann. Pippenger describes E(n) as the expected number of times that a "carry-save" adder must be used to clear all carries.
LINKS
Volker Claus, Die mittlere Additionsdauer eines Paralleladdierwerks, Acta Informat. 2 (1973), 283-291.
D. E. Knuth, The average time for carry propagation, Nederl. Akad. Wetensch. Indag. Math., 81 (2) (1978), 238-242.
Nicholas Pippenger, Analysis of carry propagation in addition: an elementary approach, J. Algorithms 42 (2002), 317-333.
FORMULA
The formulas used in the Maple program are due to Claus. Knuth gives an asymptotic expansion for E(n).
EXAMPLE
Values of E(n), n>=1: 1/2, 1, 23/16, 117/64, 555/256, 2525/1024, 11167/4096, 48437/16384, ...
MAPLE
q := proc(n, i)
option remember ;
if i > n then
0 ;
elif i = 0 then
1;
elif i = 1 then
if n >= 2 then
(procname(n-1, 1)+1)/2 ;
else
1/2 ;
end if;
elif i >=2 then
procname(n-1, i)+(1-procname(n-i+1, i))/2^i ;
end if;
end proc:
E := proc(n)
add( q(n, i), i=1..n) ;
end proc:
[seq(2^(2*n-1)*E(n), n=1..30)];
MATHEMATICA
q[n_, i_] := q[n, i] = Which[i > n, 0, i == 0, 1, i == 1, If[n >= 2, (q[n-1, 1]+1)/2, 1/2], i >= 2, q[n-1, i] + (1-q[n-i+1, i])/2^i];
En[n_] := Sum[ q[n, i], {i, 1, n}];
Table[2^(2*n-1)*En[n], { n, 1, 30}] (* Jean-François Alcover, Aug 30 2024, after Maple program *)
CROSSREFS
KEYWORD
nonn,frac
AUTHOR
R. J. Mathar and N. J. A. Sloane, May 22 2011
STATUS
approved