Abstract

In this paper, we introduce a novel method for multiplication of large integers called plum-blossom product method. This is not only an effective mental method of multiplication, but also can be used to computer science. Compared with the rapid multiplication method of Shi Fengshou and the Indian Vedic algorithm, the plum-blossom product method is more systematic, suitable for computing the multiplication of any multi-digit numbers in mind, and it has less formulae so that it is very simple and easy to learn. For the aspect of application to compute science, the corresponding multiplication algorithm with plum-blossom products is given for integers in the binary number system. Furthermore, an effective multiplier with the plum-blossom product method is designed, which can directly calculate the product of two 27-bit binary numbers. When associated with other methods such as Karatsuba algorithm, it may be able to compute product of any two large integers.

References

• MA D Z., He S. B., Sun K. H. 2021. A Modified Multivariable Complexity Measure Algorithm and Its Application for Identifying Mental Arithmetic Task. Entropy, 23 (8): 931.
• GOWERS W. T. 2007. Mathematics, memory, and mental arithmetic. Mathematical knowledge, 33--58, Oxford Univ. Press, Oxford.
• RAFFERTY C., O'Neill M., HANLEY N. 2017. Evaluation of large integer multiplication methods on hardware. IEEE Trans. Comput. 66(8): 1369--1382.
• SAN I., AT N. 2012. "On increasing the computational efficiency of long integer multiplication on FPGA". In Proc. 11th IEEE Int. Conf. Trust Secur. Privacy Comput. Commun., pp. 1149-1154.
• LIU W., NI J., LIU Z., et al. 2019. Optimized Modular Multiplication for Supersingular Isogeny Diffie-Hellman. IEEE Transactions on Computers, 68(8): 1249-1255. doi: 10.1109/TC.2019.2899847.
• GU Z., LI S. 2019. A Generalized RNS Mclaughlin Modular Multiplication with Non-Coprime Moduli Sets. IEEE Transactions on Computers, 68(11):1689-1696. doi: 10.1109/TC.2019.2917433.
• MATHUR M., AARNAV. 2017. Demystification of Vedic Multiplication Algorithm. American Journal of Computational Mathematics, 07(1):94-101.
• KAVITA U. G. 2013. Performance Analysis of Various Vedic Techniques for Multiplication. International Journal of Engineering Trends & Technology, 4(3): 231-234.
• RAMALATHA M., DAYALAN K D., DHARANI P., et al. 2009. "High speed energy efficient ALU design using Vedic multiplication techniques". In International Conference on Advances in Computational Tools for Engineering Applications, IEEE.
• PARAMASIVAM, SABEENIAN R. 2010. "An efficient bit reduction binary multiplication algorithm using Vedic methods". In Advance Computing Conference, IEEE.
• KAYAL D., MOSTAFA P., DANDAPAT A., et al. 2014. Design of High Performance 8 bit Multiplier using Vedic Multiplication Algorithm with McCMOS Technique. Journal of Signal Processing Systems, 76(1):1-9.
• GURUMRUTHY K. S., PRAHALAD M. S. 2010. "Fast and power efficient $16\times 16$ array of array multiplier using Vedic multiplication". In 2010 5th International Microsystems Packaging Assembly and Circuits Technology Conference, IEEE. doi:10.1109/IMPACT.2010.5699463.
• PRADHAN M., PANDA R., SAHU S. K. 2011. MAC Implementation using Vedic Multiplication Algorithm. International Journal of Computer Applications, 21(7): 26-28.
• BANSAL Y., MADHU C. 2016. A novel high-speed approach for 16×16 Vedic multiplication with compressor adders. Computers & Electrical Engineering, 49:39-49.
• SAHU S. R., BHOI B. K., PRADHAN M. 2020. Fast signed multiplier using Vedic Nikhilam algorithm. IET Circuits Devices & Systems,14(8):1160-1166.
• RASHNO M., HAGHPARAST M., MOSLEH M. 2020. A new design of a low-power reversible Vedic multiplier. International Journal of Quantum Information, 18(5):2050002.
• GARG A., HOSHI G. 2018. Gate Diffusion Input based 4-bit Vedic Multiplier Design. IET Circuits Devices & Systems, 12(6):764-770. doi: 10.1049/iet-cds.2017.0454.
• SHI F. S. 1989. The rapid calculation method of Shi Fengshou. Beijing: Science Press (in Chinese)
• ZHU Y. W. 2020. The theory of scissor products and applications[EB/OL]. Beijing: Sciencepaper Online [2020-11-25]. http://www.paper.edu.cn/releasepaper/content/202011-59.