Open AccessA Fast Multiplication Approach Using a Tree-Based Structure
Author(s) -
Md. Solaiman Mia
Publication year - 2020
Publication title -
gub journal of science and engineering
Language(s) - English
Resource type - Journals
ISSN - 2409-0476
DOI - 10.3329/gubjse.v6i1.52046
Subject(s) - multiplication (music) , multiplication algorithm , diagonal , tree (set theory) , multiplier (economics) , arithmetic , mathematics , product (mathematics) , tree structure , computer science , discrete mathematics , binary tree , combinatorics , binary number , geometry , economics , macroeconomics
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 , 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 multiplication algorithm outperforms the existing techniques; e.g., the proposed 4 × 4 multiplication algorithm improves 50% on the worst case running time complexity over the best known existing ones.
GUB JOURNAL OF SCIENCE AND ENGINEERING, Vol 6(1), Dec 2019 P 20-26