Abstract

A new cellular algorithm architecture for multiplication of two long binary integers in arrays of restricted size is presented. The new algorithm is based on “divide and conquer” technique and performed in terms of a model of fine-grained parallelism – Parallel Substitution Algorithm. Time complexity of the new algorithm for multiplication of *n*-bit binary integers complexity of calculation of product is (1.25*n* + log2*n* + 14) steps, which is less to that of the parallel version of the Karatzuba algorithm constructed on the same techniques.

File

markova.pdf4.18 MB

Pages

45-57