ÜÇ TERİMLİ POLİNOMLAR İÇİN KARATSUBA BENZERİ ÇARPMA YÖNTEMLERİNİN ARAŞTIRILMASI
Öz
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.
Anahtar Kelimeler
Kaynakça
- [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).
Ayrıntılar
Birincil Dil
Türkçe
Konular
Mühendislik
Bölüm
Araştırma Makalesi
Yayımlanma Tarihi
31 Aralık 2017
Gönderilme Tarihi
31 Aralık 2017
Kabul Tarihi
31 Aralık 2017
Yayımlandığı Sayı
Yıl 2017 Cilt: 3 Sayı: 2