Parallel algorithms for addition and multiplication on processor arrays with reconfigurable bus systems (Q1802064)

We design an \(O(1)\) time algorithm for computing the sum of two \(n\)-bit binary numbers and an \(O(\log n)\) time algorithm for computing the product of two given \(n\)-bit binary numbers. The first is designed to run on a linear PARBS in which each processor having an AND gate, NOT gate and an EXOR gate with five single bit registers and hence with gate complexity \(O(n)\). The other is designed to run on an \(n \times 2n\)- PARBS. Here the gate complexity is \(O(n^ 2)\).