|
|
A158618
|
|
Number of gates in Ladner-Fisher prefix circuit.
|
|
1
|
|
|
0, 1, 2, 4, 5, 7, 9, 12, 13, 15, 17, 20, 22, 25, 27, 31, 32, 34, 36, 39, 41, 44, 46, 50, 52, 55, 57, 61, 64, 67, 69, 74, 75, 77, 79, 82, 84, 87, 89, 93, 95, 98, 100, 104, 107, 110, 112, 117, 119, 122, 124, 128, 131, 134, 136, 141, 143, 147, 149, 153
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
REFERENCES
|
D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 0. See exercise 7.1.2.36 and solution.
R. E. Ladner and M. J. Fischer, Parallel Prefix Computation, JACM 27 (1980) 831-838.
|
|
LINKS
|
|
|
FORMULA
|
With s = floor(n/2), r = ceiling(n/2) and a(1) = b(1) = 0,
recurrence relation is a(n) = s + b(r) + a(s), b(n) = 2s-1 + a(r).
If n = 2^m then a(n) = 4n+1 - Fibonacci(m+5).
|
|
PROG
|
(PARI)
b(n)={if(n<=1, 0, 2*(n\2) - 1 + a((n+1)\2))}
a(n)={if(n<=1, 0, n\2 + b((n+1)\2) + a(n\2))} \\ Andrew Howroyd, Mar 28 2020
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|