Zot-Mk
Loading...
Date
2009
Authors
Jahani, Shahram
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Multiplication of big numbers is being used heavily in scientific computation.
However, there are only a few existing algorithms today that gain their efficiency
through the multiplication of the big integer characteristic. Since the multiplication
on integers is not native to the computer architecture numbering structure of bits and
bytes, such algorithms are bound to be a bit slower on the implementation.
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 5000 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 1Kbits) is about 35
percent of the Karatsuba algorithm. This average value will decrease for higher
range numbers (1Kbits 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
Master
Keywords
Computer Science , Zot-Mk , Algorithm , Integer multiplication