A Fast Multiplication Approach Using a Tree-Based Structure
DOI:
https://doi.org/10.3329/gubjse.v6i1.52046Keywords:
Multiplication, Tree, Algorithmic ComplexityAbstract
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
Downloads
31
25
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish in the GUB Journal of Science and Engineering agree to the following terms that:
- Authors retain copyright and grant the GUB Journal of Science and Engineering the right of first publication of the work.
Articles in GUB Journal of Science and Engineering are licensed under a Creative Commons CC BY-NC-ND License Attribution-NonCommercial-NoDerivatives 4.0 International License. This license permits Share — copy and redistribute the material in any medium or format.
Copyright and Reprint Permissions
- Individual contributions contained in it are protected by the copyright of Green University of Bangladesh.
- Photocopies of this journal in full or parts for personal or classroom usage may be allowed provided that copies are not made or distributed for profit or commercial advantage and the copies bear this notice and the full citation.
- Copyright for components of this work owned by others must be honored. Abstracting with credit is permitted.
- Specific permission of the publisher and payment of a fee are required for multiple or systemic copying, advertising or promotional purposes, resale, republishing, posting on servers, redistributing to lists and all forms of document delivery.
- Subscribers may reproduce a table of contents or prepare lists of articles including abstracts for internal circulation within their institutions.
- Permission of the Publisher is required for resale and distribution outside the institution. Permission of the publisher is required for all other derivative works, including compilations and translations.
- Except as outlined above, no part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, such as electronic, mechanical, photocopying, magnetic recording or otherwise, without prior written permission of the publisher.
- Permissions may be sought directly from the office of the executive editor of GUB Journal of Science and Engineering through E-mail at gubjse@fse.green.edu.bd.
Notice
- Responsibility for the contents of an article rests upon the author(s) and not upon the editor or the publisher. Therefore, on responsibility is assumed by the publisher for any injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or operation of any methods, product instructions or ideas contained in the material herein.
