This paper presents an algorithm for fast addition on the fat pyramid. The fat pyramid is a pyramid in which the storage space and the processing power allocated to a single node increase as the root of the structure is approached. The addition algorithm is based on a carry-lookahead technique. The computation time of the algorithm is proportional to logp+q for operands of size p*q bits, when p processors are used to deal with the numbers. The addition algorithm was simulated on the Connection Machine supercomputer; some performance results are presented in this paper.
Return to the "selected publications" page