Name
Abstract | ||
|---|---|---|
We consider the problem of adding two n-bit numbers which are chosen independently anduniformly at random where the adder is a circuit of AND, OR, and NOT gates of fan-in two.The fastest currently known worst-case adder has running time log n +O(plog n) [Khr].We first present a circuit which adds at least 1 \Gamma ffl fraction of pairs of numbers correctly andhas running time log log (nffl ) +O(plog log (nffl )).We then prove that this running time is optimal.Next we present ... |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1016/0020-0190(94)90031-0 | Inf. Process. Lett. |
Keywords | Field | DocType |
tight bound,expected time,addition | Log-log plot,Binary logarithm,Discrete mathematics,Combinatorics,Adder,Uniform distribution (continuous),Mathematics,Speedup | Journal |
Volume | Issue | ISSN |
49 | 2 | 0020-0190 |
Citations | PageRank | References |
3 | 0.51 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Gemmell | 1 | 675 | 108.87 |
| Mor Harchol | 2 | 3 | 0.51 |