Karekök Alma Algoritması

Bir örnek ile cevabı gösterelim. sayısının karekökünü hesaplayalım. Önce sayısının basamaklarını sağdan sola 2'şer 2'şer grupluyoruz. ← ← 2 63 1 6 2 2 63 1 2 26*6= *2= 56 Önce sol baştan başlıyoruz. Karesi 2 den küçük en büyük sayıyı buluyoruz. Bu durumda 1. Sağ tarafa 1'i yazarız. Sonra 2'den 1'in karesi olarak 1'i çıkarırız. Kalan 1'in yanına 63'ü ineriz. olur. Sağa yazdığımız 1'in iki katını sağ alta ineriz. Bu durumda 2. Şimdi ikinin sağına birler samağı olarak öyle bir sayı yazarız ki,sonucu aynı sayı ile yapılan çarpma 'den küçük veya eşit, ama 'e en yakın sayı olsun. Örneğimizde, 2'nin yanına 7 yazarsak 27*7=; 6 yazarsak 26*6= buluruz. O halde, 6 yazmalıyız. 6'yı yukarıya, sağa yazdık. Demekk ki aradığımız sayı 16'dan büyük, 17'den küçük olacaktır. 'den 'yı çıkardık, 7 kaldı. 7'nin içinde 16 olmadığına göre, 16 dan sonraki ondalık sayıları bulalım. 7'nin yanına iki sıfır yazarız, olurken sağ tarafta 16'nın 2 katını sağ alta tekrar iner, 32'nin 1' ler basamağına öyle bir sayı yazarız ki, bu sayıyla yapılacak çarpım, 'e eşit veya küçük ama 'e mümkün olan en yakın sayı olsun. Örneğimizde 2 olur. Böylece 'ün karekökü, yaklaşık 16,2 olarak bulunur. İstenirse aynı şekilde devam ederek virgülden sonra istediğimiz kadar basamağa gidebiliriz. Ondalık kesirlerin karekökleri de aynı algoritma ile bulunabilir. Tek farklı yapacağımız, karekökü alınacak sayının virgülünden itibaren tam sayı kısmını sağdan sola, ondalık kısmını ise soldan sağa ikişer basamaklı guruplandırmak gerektiğidir. Bu algoritmanın, nasıl türetildiğini ve yakınsak olduğunu görmek isteyenler için aşağıda bu türetimi sunuyoruz. Biraz uzunca ve dikkat gerektiriyor. Karekök Alma Algoritması Türetimi Karekökünü aradığımız sayının tamsayı kısmı n, kesirli kısmı k basamaklı olsun: x = xn xn-1 xn-2 x1 x0 , x -1 x -2 x -3 xp Bu gösterimde, x’in virgülden önceki ve sonraki basamaklarının sayılarını; gerekirse en sola ve en sağa birer 0 ekleyip, çift hale getirmiş olalım. Yani, x’in virgülden önceki basamaklarının sayısı n+1 olduğuna göre, n sayısı tek sayı, virgülden sonraki basamak sayısı da k olduğuna göre, k sayısı çift sayı olsun. 10 tabanlı bu gösterim şu açılıma eşdeğerdir: x = (10nxn + 10n-1xn-1 + 10n-2 xn-2 + + x1 + x0) + x -1 +x + x ++k x -p) Dikkat edilecek olursa, burada xn sıfır olabilir. Fakat hem xn, hem de xn-1 sıfır olamaz. O halde, x’in tamsayı kısmının en solundaki ikili, yani xn xn-1, 0’dan büyük olmak zorundadır ve dolayısıyla, içinde en azından 1’in karesi vardır. Bunu akılda tutalım. Şimdi, aradığımız karekökünü y ile gösterelim: y = ym ym-1 ym-2 y1 y0 , y-1 y-2 y-3 y-q yani, 10 tabanına göre açılımıyla: y = (10mym + 10m-1ym-1 + 10m-2 ym-2 + + y1 + y0) + (y-1 +y + y ++qy-q) x ≈ y2 olduğuna göre, önce y2’yi yazalım: y2 = (10mym + 10m-1ym-1 + 10m-2 ym-2 + + y1 + y0 + y-1 +y + y ++qy-q)2 m m m m m 2m = ( ∑ 10i yi)2 = ( ∑ 10i yi). ( ∑ 10j yj) = ∑ ∑ 10i+j seafoodplus.info = ∑ 10s ( ∑ seafoodplus.info) i=-q i=-q j=-q i=-q, j=-q s=-2q i+j=s = (10nxn + 10n-1xn-1 + 10n-2 xn-2 + + x1 + x0) + x -1 +x + x ++p x -p) (1) Bu son eşitlik sağlanmak zorundadır. y2’nin açılımındaki en büyük terim; s=2m: ymm kuvveti şeklinde. Bu terim 10’un en yüksek kuvvetini içeriyor. Öte yandan, ym basamağı 0’dan büyük olmak zorunda. Yani, ym’nin değeri 1 ile 9, ym2’ninki de, 1 ile 81 arasındadır. O halde, ym2 bir veya iki basamaklı olabiliyor. Önce iki basamaklı olduğunu var sayalım. Bu durumda; y mm, 10’un en fazla (2m+1)’ci kuvvetini, yani m+1’i içeren bir sayı verebilir. Ki bu kuvvetin, x’in (1) denklemindeki açılımında en solda görülen 10n kuvvetine karşılık gelmesi gerekir. O halde, 2m+1=n olmalıdır. Ya da: 2m=n Yok eğer ym2 tek basamaklı ise, ymm en fazla m’i içeren bir sayı verebilir ve bu; x’in açılımındaki 10n’in kat sayısının, yani xn’in sıfır olmasını gerektirir. Çünkü 2m bir çift sayı, n ise tek sayıdır. Söz konusu sıfırın nereden geldiği malum. Çünkü biz başlangıçta yaptığımız düzenlemeyle, x sayısının virgülden önceki basamaklarının sayısını çift hale getirmiş ve bunun için gerektiyse eğer, sol başına bir sıfır koymuştuk. Bu sıfır, o sıfırdır. Ki bu durumda m kuvvetinin, x’in (1) denklemindeki açılımındaki 10n-1 kuvvetine karşılık gelmesi gerekir. O halde 2m=n-1 olmalıdır. Tıpkı bir önceki durumdaki gibi. Demek ki, her iki durumda da: 2m=n Şimdi y2’nin açılımındaki terimleri, baştan itibaren, çarpanlarındaki 10’un azalan kuvvetleri şeklinde sıralayalım: s=2m=n ymm s=2m-1=n seafoodplus.info-1 s=2m-2=n (ym + seafoodplus.info-2)m-2 s=2m-3=n (seafoodplus.info-3 + 2ymym-2)m-3 s=2m-4=n (ym + seafoodplus.info-4 + 2ymym-3)m-4 s=2m-5=n (2ymym-5 + 2ymym-4 + 2ymym-3)m-5 Bu dizilim, aradığımız ymym-1ym terimlerini bize sırasıyla verebilecek olan bir algoritma öneriyor. İlk bulabileceğimiz terim ym. Bunun için şuna dikkat etmek lazım: ymm terimi, x’in açılımındaki xnn ve xnn-1 terimlerine katkıda bulunabiliyordu. Yani, xnn + xnn-1 sayısının içinde olması lazım. Halbuki, xnn + xnn-1= (xn + xn-1)n-1 veya; xn, 10’lar, xn-1 de 1’ler basamağını oluşturmak üzere; (xnxn-1)n-1 şeklinde yazılabilir. (Dikkat: Eğer izleyen sayı ya da simgeler arasında bir nokta varsa, bu onların çarpımı, aksi halde birbirini izleyen basamaklar oldukları anlamına geliyor.) Buradaki n-1 üssü, 2m’ye eşittir. Bu durumda, y mm terimini, x’in açılımındaki en sol iki basamaktan oluşan (xnxn-1)m teriminin içinde aramamız gerekir. Yani, aradığımız ym2; xnxn-1 sayısının içindeki en büyük karedir. Bunu bulabilir ve böylelikle y m’yi elde ederiz. Bunu bir kenara yazmış olalım (ym). Bir de, xnxn-1’den ym2’yi çıkartıp, kalan sonucu b ile gösterelim. Bu kalanın anlamı şu: Eğer x’ sayısından ymm terimini çıkartırsak, geriye; bxn-2xn- n-3 3xn basamaklarından oluşan sayı kalmış olur. Yani: bxn-2xn + xnn-4 + Şimdi sırada ym-1 var. Bunun için, ym-1’i içeren ve başka da bilinmeyen içermeyen bir ilişki bulmamız lazım. Dikkat edilecek olursa, ym-1; bir önceki adımda belirlemiş olduğumuz ym ile birlikte veya yalnız olarak, sadece, kuvvetler listesindeki s=n-2 ve s=n-3 kuvvetlerinde görünüyor. Söz konusu terimler; s=n-2 kuvvetinden gelen seafoodplus.info-1 ile, s=n-3 kuvvetinden gelen ym- 2 2m-2 1 . Bunların toplamı seafoodplus.info-1+ ymm-2 = (ym + ym-1).ymm-2 şeklinde yazılabilir. Burada, ym ve ym-1, birer basamaklı olmak zorunda. Dolayısıyla, parantez içerisindeki ifade; seafoodplus.info onlar basamağını, ym-1 de birler basamağını oluşturmak üzere; (seafoodplus.info)ym-1 basamaklar dizisi şeklinde yazılabilir. Yani, ilgilendiğimiz iki terimin toplamı, [(seafoodplus.info)ym-1].ym- 2m-2 ’dir. Ya da, burada 2m-2=n-3 olduğuna göre; (seafoodplus.info)ymn Elimizde x’ten geriye bxn-2xn- n-3 + xnn-4 + kaldığına göre; 10’un karşılıklı üslerini kıyaslayınca görürüz ki; [(seafoodplus.info)ym- 1].ym-1 sayısını bxn-2xn-3 sayısının içinde aramamız gerekiyor. Buradaki bxn-2xn-3’ü ve ym’yi bildiğimize göre, ym-1 öyle bir sayıdır ki; (seafoodplus.info)’nin yanına yazılarak elde edilen sayıyla çarpıldığında bize bxn-2xn-3’den küçük olan en büyük sayıyı verir. Bu özelliğiyle, y m-1’i bulabiliriz. Dikkat edilecek olursa, [(seafoodplus.info)ym-1].ym-1 sayısı bxn-2xn-3’in içinde bulunmayabilir ve bu durum,ym-1’in sıfır olduğu anlamına gelir. Gerçi bunun için b kalanının sıfır olmuş olması gerekir, ama bu önemli değil) Diyelim, sıfır veya değil, ym-1’i bulduk ve daha önceki ym’nin yanına not ettik (ymym-1). Bir de, bxn-2xn-3’den [(seafoodplus.info)ym-1].ym-1 sayısını çıkartıp, kalan sonucu B ile gösterelim. Bu kalanın anlamı şu: Eğer bxn-2xn-3xn sayısından [(seafoodplus.info)ym-1].ymm-2 sayısını çıkartırsak, geriye; Bxn-4xn-5xn basamaklarından oluşan sayı kalmış olur. Yani: Bxn-4xnn-5 + xnn-6 + Her bulduğumuz yeni ‘kalan’a farklı bir isim vermek zorunda kalmamak için; b’nin daha önceki değerini unutup; burada B ile gösterdiğimiz ‘kalan’ı b ile gösterelim. Tabii, eğer ym-1 sıfır idiyse, bu son çıkartmayı yapmaya gerek yok. Doğrudan aşağıdaki adımla devam ederiz Şimdi sırada ym-2 var. Bunun için, ym ve ym-1’i içeren ve başka da bilinmeyen içermeyen bir ilişki bulmamız lazım. Dikkat edilecek olursa, ym-2; halen bildiğimiz ym ve ym-1 ile birlikte veya yalnız olarak sadece, kuvvetler listesindeki s=n-3, s=n-4 ve s=n-4 kuvvetlerinde görünüyor. Sözkonusu terimler; s=n-3 kuvvetinden gelen seafoodplus.info-2 ile, s=n-4 kuvvetinden gelen seafoodplus.info-3 ve s=n-5 kuvvetinden gelen ymm-4 terimleri. Bunların toplamı seafoodplus.info-2+ seafoodplus.info-3 + ym)m-4 = (ym + ym-1 + ym-2).ymm-4 = [(ym + ym-1) + ym-2].ymm-4 Burada, ym ve ym-1, birer basamaklı olmak zorunda. Dolayısıyla, iç parantezin içerisindeki ifade; ym onlar basamağını, ym-1 de birler basamağını oluşturmak üzere; ymym-1 şeklinde yazılabilir. Bu durumda, [(ymym-1) + ym-2].ymm-4 elde ederiz. Ki, buradaki parantez içindeki ifade de benzer şekilde, [2.(ymym-1)]ym-2 basamaklar dizisi olarak yazılabilir. Sonuçta, ([2.(ymym-1)]ym-2).ymm-4 elde ederiz. Yani, ilgilendiğimiz üç terimin toplamı, bu ([2.(ymym-1)]ym-2).ymm-4 ifadesidir. Ya da, burada 2m-4=n-5 olduğuna göre; ([2.(ymym-1)]ym-2).ymn Elimizde x’ten geriye bxn-4xn-5xn basamaklarından oluşan sayı, yani: bxn-4xnn-5 + xnn-6 + kalmıştı. O halde; 10’un karşılıklı üslerini kıyaslayınca görürüz ki; ([2.(ymym-1)]ym-2).ym-2 sayısını bxn-4xn-5 sayısının içinde aramamız gerekiyor. Buradaki bxn-4xn-5’ü ve ym ile ym-1’i bildiğimize göre, ym-2 öyle bir sayıdır ki; ([2.(ymym-1)]ym-2)’nin yanına yazılarak elde edilen sayıyla çarpıldığında bize bxn-4xn-5’den küçük olan en büyük sayıyı verir. Bu özelliğiyle, ym-2’yi bulabiliriz. Diyelim bulduk ve daha önceki ymym-1’in yanına not ettik (ymym-1ym-2). Bir de, bxn-4xn-5’den ([2.(ymym-1)]ym-2) sayısını çıkartıp, kalan sonucu B ile gösterelim. Bu kalanın anlamı şu: Eğer bxn-4xn-5xn sayısından ([2.(ymym-1)]ym-2)n-5 sayısını çıkartırsak, geriye; Bxn-6xn-7xn basamaklarından oluşan sayı kalmış olur. Yani: Bxn-6xnn-7 + xnn-8 + Her bulduğumuz yeni ‘kalan’a farklı bir isim vermek zorunda kalmamak için; b’nin daha önceki değerini unutup; burada B ile gösterdiğimiz ‘kalan’ı b ile gösterelim. Şimdi sırada ym-3 var. Ama artık kabak tadı vermeyelim. İzleyen terimleri, aynı adımları izleyerek bulmak mümkün. Dikkat edilecek olursa, algoritma x’in virgülden sonraki kısmı için de aynı şekilde devam ediyor. Sadece, x’in tamsayı kısmından son kalan bx1x0’la yaptığımız işlemle y0’ı da bulduktan sonra, bu aşamaya kadar elde etmiş olduğumuz ymym-1ym y0 dizisinin ardından bir virgül koyup, öyle devam etmemiz gerekiyor. Bir de algoritmanın nerede sona erdirileceği sorusu var. Bu sorunun yanıtı için, iki olasılık sözkonusu. Birincisi, “x’ten kalan” olarak nitelendirdiğimiz bxixi dizisinin sıfıra eşit çıkması. Bu durumda, karekök bulma işlemi kendiliğinden sona ermiş demektir ve x sayısının karekökünü ‘tam’ olarak bulmuş oluruz. Ancak, örneğin √2 gibi irrasyonel sonuç veren bir karekök için bu olasılıkla karşılaşmayacağımız açık. O zaman, ikinci olasılık devreye girer. Ki o da; virgülden sonra belli, diyelim 5’ci basamağa ulaştıktan sonra, bxixi kalanının hala sıfır olmamasına karşın, yeterli duyarlılık düzeyine ulaşılmış olduğu kanaatine varıp, algoritmayı durdurmaktır. Bu durumda, karekök bulma işlemini biz sona erdirmiş ve x sayısının karekökünü ‘yaklaşık’ olarak bulmuş oluruz. Algoritmamız böyle, örneğini vermiş olduğumuz karekök bulma sürecindeki işlemler dizisi bu yüzden öyle çalışıyor. 

bir onceki derste, ikili arama algoritmasini gorduk, okumadiysaniz geri donun sonra buraya atlayin :p

soru su; verilen 32bitlik pozitif bir integer sayinin karekokonun alt tabandaki degerini 32bit integer sonuc donecek sekilde bul. hayda bu ne simdi demeyin, arama ve ozellikle binary search &#; ikili arama , (kim cevirdiyse bunu hosuma gitmedi, bundan sonra bolerek arama diyecegim, ikili arama bir anlam ifade etmiyor bana) ile iliskilendirerek bir cozume ulasmaya calisalim. cok duyarli bir cozum aramamiz istenseydi bisection veya newton yontemlerini kullanmak durumunda kalacaktik. fakat soruda yuksek duyarlilik istenmedigi icin biz bolerek arama yontemini nasil kullanacagimizi dusunelim.

bolerek arama yapacagimizi dusununce, bolmemiz gereken bir elemen listesi olmasi lazim oyle degil mi, evet aynen oyle. hatirlayalim, pozitif integer en fazla kac bit olabiliyordu, 32 bit degilmi. dolayisiyla karakoku en fazla kac bit olabilir; 16 bitle ifade edilebilecek onluk tabandaki en buyuk deger ne?

evet yavas yavas biyere geliyoruz. eger ki dersek, bir liste hazirlayalim, bu listede 1 den baslayarak ya kadar olan sayilarin kareleri olsun. dolayisiyla bana verilen sayiyi bu listeden arayarak bulursam, sayinin listedeki sirasi bana aradigim sayinin karekokunu verir. yani karekokunu aradigimiz sayi ise, biz karekok listemizde sirada sayisini muhafaza ettigimizden dolayi, listede &#;i buldugumuz anda sayinin karekokunu de bulmus olacagiz. cok asiri zeki bir cozum degil, bir cok optimizasyon yapilabilir fakat bolerek arama yontemini kullanarak cozume ulasacagimiz bir yaklasim boyle olabilir, baska yaklasimlariniz varsa lutfen belirtin

simdi bu mantigin uygulamasini nasil yapariz ona bakalim

Projelerimizde hazır matematik fonksiyonlarını kullanırız genelde. Örneğin 19 sayısının karekökünü almak için &#;double sayi = seafoodplus.info(19);&#; kodunu yazdığımız an sonucu bize  şeklinde double olarak döndürür. Burada bir sıkıntı yok. Peki neden hazır &#;seafoodplus.info()&#; metodunu kullanmak yerine bir algoritma geliştirmek isteyelim. Hazır fonksiyon ile elde ettiğimiz double sayı virgülden sonra 15 hane. Daha hassas sonuçlar elde etmek istediğimiz projelerimiz olabilir. Mesela virgülden sonra 28 haneye kadar basamak görmek isteyebiliriz. Özellikle kripto algoritmalarında (MD5,SHA vb&#; gibi) ve uzay biliminde ölçümler ve hesaplamalar virgülden sonra çok daha fazla basamak sayıları ile çalışmakta. Bu durumda kendi karekök algoritmamızı kurmamız gerekebilir. Aşağıda ki kodları inceleyin derim.

Kodu incelediğimiz de matematik ile haşır neşir olanlarımızın hemen farkına varacağı babil yöntemi göze çarpmaktadır. Babil yöntemi aslında basit bir iterasyon yöntemidir. Tahmin edilen değer işlem sonucu çıkan değere yaklaşana ve nihayetinde eşit olana kadar bir döngüye sokulur. Olay bu kadar basit.

x=0,5*(x+y/x) şeklinde matematize edilmiş bir denklem var karşımızda. Denklemi bir başka şekilde şöyle yazabiliriz. x=1/2*((x²+y)/x)  &#;->  2x²=x²+y &#;&#;>  x²=y

Zaten bizim de çözmek istediğimiz öyle bir x bulalım ki x²=y  şartını sağlasın. Bu denklemlerde y sayısı karekökünü bulmak istediğimiz sayı, x sayısı ise ilk tahmin değerini ifade etmektedir.