A Fast Multiplication Approach Using a Tree-Based Structure
Keywords: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
Copyright (c) 2020 Md. Solaiman Mia
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
- Copyright on any open access article in a journal published by JAET is retained by the author(s).
- Authors grant JAET a license to publish the article and identify itself as the original publisher.
- Authors also grant any third party the right to use the article freely as long as its integrity is maintained and its original authors, citation details and publisher are identified.
- The Creative Commons Attribution License 4.0 formalizes these and other terms and conditions of publishing articles.
- The publisher will apply the Creative Commons Attribution-Noncommercial-ShareAlike Works 4.0 International License
(CC BY-NC-SA) to the Article where it publishes the Article in the journal on its online platforms on an Open Access basis.
The CC BY-NC-SA license allows users to copy, to create extracts, abstracts and new works from the Article, to alter and revise
the Article, provided this is not done for commercial purposes, and that the user gives appropriate credit (with a link to the
formal publication through the relevant DOI), provides a link to the license, indicates if changes were made and the licensor
is not represented as endorsing the use made of the work. Further, any new works must be made available on the same conditions. The full details of the license are available at http://creativecommons.org/licenses/by-nc-sa/4.0.