ZOT-Mk : A New Algorithm For Big Integer Multiplication
Loading...
Date
2009-06
Authors
Shahram Jahani
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This research focuses on big number multiplication algorithm that is based on the
symbols extracted from the binary numbering system. We named the new
numbering structure as "ZOT". The new algorithm for big numbers multiplication,
ZOT-MK, is constructed from the combination of Karatsuba algorithm and the ZOT
structure.
For evaluation purposes, we simulate an environment capable of handling big
numbers to compare the performance of the propose algorithm against the well
known Karatsuba algorithm. Over the range of 25 to SOOO bits numbers, results
show that the compression rate of those numbers represented by the ZOT structure
against the normal binary representation is 41 percent. Therefore, theoretically, in
average the execution speed of ZOT-MK should be about double of the Karatsuba
algorithm. However because of efficient memory utilization of ZOT-MK that
eliminates extensive memory paging, the experimental result shows the average
execution time of ZOT-MK in lower range numbers (25 bits to lKbits) is about 35
percent of the Karatsuba algorithm. This average value will decrease for higher
range numbers (lKbits to 5Kbits) to 25 percent.
In conclusion, the available results validate the efficiency of the ZOT -MK
multiplication algorithm against Karatsuba algorithm, which is currently the defacto
standard for big number multiplication algorithm.
Description
Keywords
ZOT-MK, is constructed from the combination of , Karatsuba algorithm and the ZOT structure.