Carry propagation is the nightmare of school pupils and the headache of computer engineers: not only can the addition of two digits give rise to a carry, but this carry itself, when added to the next digits to the left1 may give rise to another carry, and so on, and so forth, and this may happen for an arbitrarily long time. Since the beginnings of computer science, the evaluation of the carry propagation length has been the subject of many works and it is known that the average carry propagation length (or complexity) for addition of two uniformly distributed n-digits binary numbers is log_2(n)+O(1) (see [5, 7, 10]).
展开▼
