A Fast Multiplication Approach Using a Tree-Based Structure


  • Md. Solaiman Mia Green University of Bangladesh


Multiplication, Tree, Algorithmic Complexity


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.



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