9. Sınıf Matematik (2. Kitap) Ders Kitabı Sayfa 145 Cevapları (MEB Yayınları)

5. Tema/Ölçme ve Değerlendirme

5. Anatoly Alexeevitch Karatsuba (Anatoli Alek­ siyeviç Karatsuba) tarafından 1960 yılında keşfedilen Karatsuba yöntemi, iki büyük sayıyı çarpmak için kullanılır. Bu yöntemde gelenek­ sel çarpma yöntemlerine göre daha az çarp­ ma işlemi yapılarak büyük sayılar daha verimli şekilde çarpılır. Bu durum özellikle kriptografi (şifreleme) gibi alanlarda verimliliği artırır. Geleneksel yaklaşımla 87 ve 91’in çarpımının çözümlemesi aşağıda verilmiştir. a ve b 87 91 = = için a p q 10 = + ve b r s 10 = + olmak üzere , , p q r ve s 8 7 9 1 = = = = elde edilir. a b p q r s pr ps qr qs 10 10 100 10 $ $ = + + = + + + _ _ _ i i i olduğundan . olur 87 91 100 8 9 10 8 1 7 9 7 1 7200 710 7 7917 $ $ $ $ $ $ = + + + = + + = _ i Karatsuba, geleneksel yaklaşımdaki çarpma işlemlerinin sayısını v değişkenini türeterek azaltmıştır. u p r v q p s r y q s $ $ $ = = - - = _ _ i i olmak üzere a b u u y v y 10 10 2 $ $ $ = + + - + _ i olur. Buradan . u v y bulunur 8 9 72 7 8 1 9 8 7 1 7 $ $ $ = = = - - = = = _ _ i i Bu durumda . elde edilir 87 91 72 10 72 7 8 10 7 7917 2 $ $ $ = + + - + = _ i Buna göre aşağıdaki soruları cevaplayınız.

a) 96 78 $ ifadesinin eşitini Karatsuba yön­ temiyle bulunuz.

b) Karatsuba yöntemiyle iki basamaklı iki doğal sayının çarpımını bulan algoritma­ nın işleyişini akış şemasıyla ifade ediniz. Akış Şeması