ÜÇ TERİMLİ POLİNOMLAR İÇİN KARATSUBA BENZERİ ÇARPMA YÖNTEMLERİNİN ARAŞTIRILMASI
Abstract
Bu çalışmada, katsayıları tamsayı olan iki polinomu aritmetik karmaşıklık açısından daha verimli çarpan yöntemlerin araştırılması hedeflenmektedir. Bu yüzden, Böl-ve-Fethet mantığını kullanan, Karatsuba-Ofman Algoritmasından yola çıkarak çarpma işlemlerini daha az maliyetli toplama/çıkarma işlemleriyle değiştiren denklemler bulan bir yazılım geliştirilmiştir. Geliştirilen uygulamada, üç terimli iki polinomun katsayılarının olası kombinasyonları kullanılarak çarpma işleminden sonra bütün çarpım katsayılarının bulunup bulmadığını test edilmektedir. Üç terimli polinomları çarpmak için 3 farklı yöntem olduğu ve bu yöntemlerin hepsinde 6 çarpma, 13 toplama/çıkarma işlemine ihtiyaç duyulduğu hesaplanmıştır. Bunlara ek olarak, daha fazla terimli polinomların çarpımı için ne tür uygulamalara ihtiyaç duyulduğu konusunda detaylara da yer verilmiştir.
Keywords
References
- [1] Von zur Gathen, J. ve J. Gerhard, Modern Computer Algebra, 3rd ed., Cambridge University Press, 2013.
- [2] Knuth, D. The Art of Computer Programming, 3rd ed., vol. 2. Seminumerical Algorithms, Addison-Wesley Longman, Amerika, 1997.
- [3] Karatsuba, A. ve Y. Ofman, “Multiplication of Many-Digital Numbers by Automatic Computers”, Physics-Doklady, 1963.
- [4] Cook, T. ve A. Stephen, On the Minimum Computation Time of Functions, Doktora Tezi, Harvard University, Department of Mathematics, 1966.
- [5] Heideman, M., D. Johnson ve C. Burrus, “Gauss and the history of the fast fourier transform”, IEEE ASSP Dergisi, Cilt 1, 14-21, 1984.
- [6] Fürer, M. “Faster Integer Multiplication”, Pennsylvania State University, Amerika, 2007.
- [7] Montgomery, P. L. “Five, Six, and Seven-Term Karatsuba-Like Formulae”, IEEE Transactions On Computers Dergisi, Cilt 54, Numara:3, 2005, syf. 362-369.
- [8] Paar, C. ve A. Weimerskirch, “Generalizations of the Karatsuba Algorithm for Efficient Implementations”, Ruhr-Universty Bochum, Almanya, 2006, http://eprint.iacr.org/2006/224.pdf (Son erişim tarihi: 15 Mart 2017).
Details
Primary Language
Turkish
Subjects
Engineering
Journal Section
Research Article
Publication Date
December 31, 2017
Submission Date
December 31, 2017
Acceptance Date
December 31, 2017
Published in Issue
Year 2017 Volume: 3 Number: 2