A Fast Multiplication Approach Using a Tree-Based Structure

Authors

  • Md. Solaiman Mia Green University of Bangladesh

Keywords:

Multiplication, Tree, Algorithmic Complexity

Abstract

This paper presents a technique for integer number multiplication using a tree-based structure. In the proposed method, both the generation of the partial products and the addition of partial products are completed in the tree structure. The proposed multiplication approach has been designed in two steps: Firstly, the partial products are generated in a tree-based structure using the fewest numbers of gates. Secondly, diagonal partial products additions have been done by the partial products residing in the diagonal partial product nodes to get a faster multiplication result, where two partial product nodes Pi,j and  Pk,l are diagonal only if |i - k| = |j - l| where i and k are the multiplicand bits; and j and l are the multiplier bits. The comparative study shows that the proposed 4x4 multiplication algorithm outperforms the existing techniques; e.g., the proposed  multiplication algorithm improves 50% on the worst case running time complexity over the best known existing ones.

Published

2020-07-01

How to Cite

Mia, M. S. . (2020). A Fast Multiplication Approach Using a Tree-Based Structure. Journal of Applied Engineering & Technology (JAET), 4(1), 1-10. Retrieved from http://jae-tech.com/index.php/jaet/article/view/18