\u0130lkokulda \u00f6\u011fretilen alt alta \u00e7arpma y\u00f6ntemi, y\u00fczy\u0131llar boyunca say\u0131lar\u0131 \u00e7arpman\u0131n en h\u0131zl\u0131 yolu say\u0131l\u0131yordu. Ancak 1960’ta 23 ya\u015f\u0131nda bir \u00f6\u011frencinin yapt\u0131\u011f\u0131 \u015fa\u015f\u0131rt\u0131c\u0131 ke\u015fif, bug\u00fcne kadar tam olarak \u00e7\u00f6z\u00fclememi\u015f bir matematik gizemini ba\u015flatt\u0131.<\/p>\n\n\n\n
Scientific American’a g\u00f6re<\/strong> bu gizem sadece akademik bir merak konusu de\u011fil: \u015eifreleme, robotik, yapay zeka, ses i\u015fleme ve bilgisayar \u00e7iplerinin \u00fcstlendi\u011fi hemen her i\u015flem, b\u00fcy\u00fck say\u0131lar\u0131n defalarca \u00e7arp\u0131lmas\u0131n\u0131 gerektiriyor. Bu \u00f6l\u00e7ekte en basit i\u015flem bile bir soruna d\u00f6n\u00fc\u015febiliyor ve k\u00fc\u00e7\u00fck bir verimlilik kazan\u0131m\u0131 bile k\u00fcresel ekonomik sonu\u00e7lar do\u011furabiliyor.<\/p>\n\n\n\n \u0130ki basamakl\u0131 iki say\u0131y\u0131 \u00e7arparken d\u00f6rt, \u00fc\u00e7 basamakl\u0131 say\u0131larda ise dokuz ayr\u0131 tek basamakl\u0131 \u00e7arpma i\u015flemi gerekiyor; yani i\u015f y\u00fck\u00fc basamak say\u0131s\u0131n\u0131n karesiyle b\u00fcy\u00fcyor. Bilgisayar bilimciler bu b\u00fcy\u00fcmeyi saniye yerine i\u015flem ad\u0131m\u0131 say\u0131s\u0131yla, “Big O” g\u00f6sterimiyle ifade ediyor: \u0130lkokul y\u00f6ntemi O(n\u00b2) ad\u0131m gerektiriyor. Bu da say\u0131lar iki kat\u0131na \u00e7\u0131kt\u0131\u011f\u0131nda i\u015fin d\u00f6rt kat, bin kat\u0131na \u00e7\u0131kt\u0131\u011f\u0131nda ise bir milyon kat artmas\u0131 anlam\u0131na geliyor.<\/p>\n\n\n\n Antik \u00e7a\u011flardan bu yana matematik\u00e7iler, O(n\u00b2)’nin \u00e7arpma i\u00e7in a\u015f\u0131lamaz bir h\u0131z s\u0131n\u0131r\u0131 oldu\u011funu d\u00fc\u015f\u00fcn\u00fcyordu. \u00dcnl\u00fc Sovyet matematik\u00e7i Andrey Kolmogorov, 1960’ta Moskova Devlet \u00dcniversitesi’nde verdi\u011fi bir seminerde bu s\u0131n\u0131r\u0131 resmi bir varsay\u0131m olarak ortaya att\u0131.<\/p>\n\n\n\n Seminerde dinleyiciler aras\u0131nda bulunan 23 ya\u015f\u0131ndaki \u00fcniversite \u00f6\u011frencisi Anatoly Karatsuba, yaln\u0131zca bir hafta sonra geri d\u00f6n\u00fcp Kolmogorov’un yan\u0131ld\u0131\u011f\u0131n\u0131 kan\u0131tlad\u0131.<\/p>\n\n\n\n Kolmogorov bu sonu\u00e7 kar\u015f\u0131s\u0131nda b\u00fcy\u00fck \u015fa\u015fk\u0131nl\u0131k ya\u015fad\u0131, ilgin\u00e7 bir \u015fekilde kan\u0131t\u0131n resmi metnini kendisi kaleme al\u0131p Karatsuba’y\u0131 ba\u015f yazar g\u00f6stererek yay\u0131mlatt\u0131. Karatsuba, \u00e7al\u0131\u015fmadan ancak makalenin bask\u0131lar\u0131n\u0131 postada ald\u0131\u011f\u0131nda haberdar oldu.<\/p>\n\n\n\n Karatsuba’n\u0131n dehas\u0131, zahmetli ve zaman alan \u00e7arpma i\u015flemlerinin bir k\u0131sm\u0131n\u0131 kolay ve h\u0131zl\u0131 toplama i\u015flemleriyle de\u011fi\u015ftirebilece\u011fini fark etmesinde yat\u0131yordu. \u0130ki n basamakl\u0131 say\u0131y\u0131 toplamak yaln\u0131zca O(n) zaman al\u0131yor, \u00e7\u00fcnk\u00fc rakamlar \u00fczerinde tek bir ge\u00e7i\u015f yeterli oluyor.<\/p>\n\n\n\n Say\u0131lar onlar ve birler basama\u011f\u0131na ayr\u0131l\u0131yor: 12 i\u00e7in a=1, b=2; 34 i\u00e7in c=3, d=4.<\/p>\n\n\n\n B\u00f6ylece 12 \u00d7 34 i\u015flemi (10a+b) \u00d7 (10c+d) olarak yaz\u0131l\u0131p a\u00e7\u0131ld\u0131\u011f\u0131nda 100(ac) + 10(ad+bc) + (bd) ifadesi ortaya \u00e7\u0131k\u0131yor.<\/p>\n\n\n\n Geleneksel y\u00f6ntemde bunun i\u00e7in d\u00f6rt ayr\u0131 \u00e7arpma gerekir: ac=3, ad=4, bc=6, bd=8. Karatsuba’n\u0131n hilesi ise ortadaki (ad+bc) terimini tek bir \u00e7arpmayla bulmay\u0131 sa\u011fl\u0131yor:<\/strong><\/p>\n\n\n\n (ad+bc) = ((a+b) \u00d7 (c+d)) \u2212 ac \u2212 bd<\/p>\n\n\n\n Say\u0131larla: ((1+2) \u00d7 (3+4)) \u2212 3 \u2212 8 = 21 \u2212 11 = 10.<\/p>\n\n\n\n Yani ac=3, bd=8 ve (ad+bc)=10 de\u011ferleri yerine kondu\u011funda sonu\u00e7 yine 408 \u00e7\u0131k\u0131yor ama bu kez d\u00f6rt de\u011fil, yaln\u0131zca \u00fc\u00e7 \u00e7arpma i\u015flemiyle. Say\u0131lar b\u00fcy\u00fcd\u00fck\u00e7e bu y\u00f6ntem \u00f6zyinelemeli olarak tekrar tekrar uygulanabiliyor ve kazan\u00e7 katlanarak art\u0131yor.<\/strong><\/p>\n\n\n\n Bu y\u00f6ntem bug\u00fcn bir\u00e7ok yaz\u0131l\u0131m\u0131n temelinde yer al\u0131yor, \u00f6rne\u011fin Python programlama dili, say\u0131lar belirli bir b\u00fcy\u00fckl\u00fc\u011f\u00fc (yakla\u015f\u0131k 630 ondal\u0131k basama\u011f\u0131) a\u015ft\u0131\u011f\u0131nda otomatik olarak Karatsuba’n\u0131n y\u00f6ntemine ge\u00e7iyor.<\/p>\n\n\n\n Karatsuba’n\u0131n bulu\u015fu, \u00e7arpman\u0131n nihai h\u0131z s\u0131n\u0131r\u0131n\u0131 bulmak i\u00e7in onlarca y\u0131l s\u00fcren bir yar\u0131\u015f\u0131 ba\u015flatt\u0131. Bu yar\u0131\u015f 2019’da matematik\u00e7iler David Harvey ve Joris van der Hoeven’in, \u00f6nceki t\u00fcm at\u0131l\u0131mlar\u0131 geride b\u0131rakan son derece sofistike bir algoritma tan\u0131mlamas\u0131yla bir d\u00f6n\u00fcm noktas\u0131na ula\u015ft\u0131. Yeni algoritma O(n\u00d7log n) s\u00fcrede \u00e7al\u0131\u015f\u0131yor, bu da iki devasa say\u0131n\u0131n \u00e7arp\u0131m\u0131n\u0131 hesaplaman\u0131n, onlar\u0131 toplamaktan ya da yaln\u0131zca okumaktan \u00e7ok da fazla zaman almad\u0131\u011f\u0131 anlam\u0131na geliyor.<\/p>\n\n\n\n Ancak bu zaferin bir k\u0131s\u0131t\u0131 var: Karatsuba’n\u0131n y\u00f6ntemi yaln\u0131zca yeterince b\u00fcy\u00fck say\u0131larda ilkokul y\u00f6ntemini geride b\u0131rak\u0131rken Harvey-van der Hoeven algoritmas\u0131 ancak ak\u0131l almaz b\u00fcy\u00fckl\u00fckteki say\u0131larda \u00f6ne ge\u00e7ebiliyor. Bilgisayar biliminde b\u00f6ylesi y\u00f6ntemlere, pratikte hi\u00e7bir zaman kullan\u0131lamayacak kadar dev say\u0131larda etkili olan “galaktik algoritma” deniyor.<\/p>\n\n\n\n Bununla birlikte bu, alan\u0131nda \u00e7\u0131\u011f\u0131r a\u00e7an bir ba\u015far\u0131 olarak kabul ediliyor. Bug\u00fcn teorik bilgisayar bilimcilerin \u00e7o\u011fu, O(n\u00d7log n)’nin \u00e7arpma i\u00e7in m\u00fcmk\u00fcn olan en h\u0131zl\u0131 s\u0131n\u0131r oldu\u011fundan \u015f\u00fcpheleniyor; bunu resmi olarak kan\u0131tlamak ise matematik alan\u0131n\u0131n kutsal problemi, haline geldi. Ne var ki tarih, geni\u015f bir uzla\u015f\u0131n\u0131n matematiksel bir kan\u0131t anlam\u0131na gelmedi\u011fini g\u00f6steriyor \u00e7arpman\u0131n h\u0131z s\u0131n\u0131r\u0131na dair varsay\u0131mlar daha \u00f6nce de \u00e7\u00fcr\u00fct\u00fclm\u00fc\u015ft\u00fc.<\/p>\n","protected":false},"excerpt":{"rendered":" \u0130lkokulda \u00f6\u011fretilen alt alta \u00e7arpma y\u00f6ntemi, y\u00fczy\u0131llar boyunca say\u0131lar\u0131 \u00e7arpman\u0131n en h\u0131zl\u0131 yolu say\u0131l\u0131yordu. <\/p>\n","protected":false},"author":1,"featured_media":2927,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[48],"tags":[1104],"class_list":["post-2926","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-bilim","tag-matematikciler-sayilari-carpmanin-en-hizli-yolu"],"acf":[],"_links":{"self":[{"href":"https:\/\/bimanset.com\/index.php?rest_route=\/wp\/v2\/posts\/2926","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/bimanset.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/bimanset.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/bimanset.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/bimanset.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2926"}],"version-history":[{"count":1,"href":"https:\/\/bimanset.com\/index.php?rest_route=\/wp\/v2\/posts\/2926\/revisions"}],"predecessor-version":[{"id":2928,"href":"https:\/\/bimanset.com\/index.php?rest_route=\/wp\/v2\/posts\/2926\/revisions\/2928"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/bimanset.com\/index.php?rest_route=\/wp\/v2\/media\/2927"}],"wp:attachment":[{"href":"https:\/\/bimanset.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2926"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/bimanset.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2926"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/bimanset.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2926"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\u0130lkokul y\u00f6nteminin gizli maliyeti<\/h2>\n\n\n\n
Kolmogorov’un iddias\u0131n\u0131 23 ya\u015f\u0131nda bir \u00f6\u011frenci \u00e7\u00fcr\u00fctt\u00fc<\/h2>\n\n\n\n
Pahal\u0131 \u00e7arpmay\u0131 ucuz toplamayla de\u011fi\u015ftirmek<\/h2>\n\n\n\n
\u00d6rnek: 12 \u00d7 34<\/h4>\n\n\n\n
2019’daki “galaktik” rekor<\/h2>\n\n\n\n