<XML><RECORDS><RECORD><REFERENCE_TYPE>0</REFERENCE_TYPE><REFNUM>7526</REFNUM><AUTHORS><AUTHOR>O'Donnell,J.T.</AUTHOR><AUTHOR>Ruenger,G.</AUTHOR></AUTHORS><YEAR>2004</YEAR><TITLE>Derivation of a Logarithmic Time Carry Lookahead Addition Circuit</TITLE><PLACE_PUBLISHED>Journal of Functional Programming, Volume 14, Number 6.</PLACE_PUBLISHED><PUBLISHER>Cambridge University Press</PUBLISHER><PAGES>697-713</PAGES><LABEL>O'Donnell:2004:7526</LABEL><KEYWORDS><KEYWORD>Digital circuit design</KEYWORD></KEYWORDS<ABSTRACT>Using Haskell as a digital circuit description language, we transform a ripple carry adder that requres O(n) time to add two n-bit words into a parallel carry lookahead adder that requires O(log n) time. The ripple carry adder uses a scan function to calculate carry bits, but this scan cannot be parallelized directly since it is applied to a non-associative function. Several techniques are applied in order to introduce parallelism, including partial evalutation and symbolic function representation. The derivation given here constitutes a semi-formal correctness proof, and it also brings out explicitly each of the ideas underlying the algorithm.</ABSTRACT></RECORD></RECORDS></XML>