Alıntı (Salih Dinçer):
> "bir resim bin söze bedeldir" ... Gerçi yukarıdaki kod örneğinden bütün bu anlatacaklarımı çıkarabilirdiniz...:)
Diğer arkadaşları bilemem ama benim bunları anlamam imkansız! :)
Nasıl bir anlamazlık içinde olduğumu önce kod açıklamaları ile göstereyim:
/*
asalTara.d (v5-11.03.2012)
*/
import std.stdio;
/* [Ali] Sanırım x önekini "adet" anlamında kullanıyorsun. Yani burada 1001
* tane asal sayı bulacağız... Yo, hayır: xAsal "sonuncu asal" ve xDizi
* "eleman adedi" anlamına geliyormuş.
*/
const uint xAsal = 1001; //179424673; //982451653; (50 milyonuncu)
const uint xDizi = (xAsal/16) + 1;
/* [Ali] veri çok genel bir isim olmuş. Aslında bulunan asallar bu dizi içinde
* oluşacaklar, değil mi? Ek: Hayır, değilmiş. veri yalnızca bir karalama
* tahtası olarak kullanılıyor. Asal sayılar k döngüsündeki k değerleri
* olacaklar. */
ubyte[] veri;
/* [Ali] Çok genel bir isim daha. :( Sen bu işlevin ne yaptığını çok iyi
* anlıyorsun ama bizim gibi dışarıdan bakanlar hangi bitin test edildiğini ve
* k'nin ne anlama geldiğini anlayamıyoruz.
*
* Tamam şimdi anladım... mı acaba... Sayının alt bitlerindeki değerin üst
* bitlerindeki değeri bölüp bölemediğine mi bakıyoruz?
*/
bool bitTest(uint k) {
/* [Ali] Burada son dört bit dışındaki bitlerine bakıyoruz. Tamam.*/
ubyte bits = veri[k >> 4];
/* [Ali] Hmmm... :) Bir düşüneyim... 16'ya bölümünden kalanı ikiye
* bölüyorsun. (?) Peki... 16'ya bölüm en fazla 15 olacağına göre 15/2 = 7
* olur. Sonra 1'i o kadar bit sola öteliyorsun. Yani 7 indeksli bitin 1
* olduğu bir durumdayız.
*
* Ondan sonra bits'in 7 indeksli biti 1 ise false, 0 ise true
* döndürüyorsun.
*
* Tamam, bu kadarını anladım. Özetle: veri dizisinin k/16'ıncı elemanı
* şimdiye kadar özel bir desene sahipse false, değilse true.
*
* O özel desen de şunun gibi bir şey: Sondan bir önceki üç bitin değerine
* karşılık gelen bit 1 mi... Ona da anlamadan "peki"... :D
*/
if ((bits & (1 << ((k % 16) >> 1))) != 0) return false;
return true;
}
void main() {
/* [Ali] Tamam, xDizi adet elemanlı dizimiz var. Biraz sonra bunun
* değerlerinin bitlerini ayarlayacağız. */
veri = new ubyte[xDizi];
/* [Ali] Bunlar indeksler ama alışık olduğumun tersindeler. Genellikle i,
* j, k diye adlandırıldıklarında kodu okurken j'nin k'den daha dışarda
* olduğunu hemen biliriz. Bu kod tersi olmuş. Peki, olsun... */
uint l, k, j, n = xAsal, xSay = 1;
write ("2\t"); // Çift asal sayı düzeltmesi...
/* [Ali] Burası tamam: Tek sayılar üzerinde ilerliyoruz. Bunlardan
* bazılarının asal olduklarına karar vereceğiz. */
for (k = 3; k <= n; k += 2) {
if (bitTest(k)) {
/* [Ali] Tamam, bir asal bulduk. Şimdi karalama tahtamızdaki bazı
* bitleri 1 yaparak daha sonra kullanılmak üzeri bazı bilgiler
* bırakacağız. */
writefln("bitTest %s için tuttu (bu bir asal sayı)", k);
for (j = 3; j <= (n / k); j += 2) {
/* [Ali] Bu asal sayının bütün katları ile ilgili işlem
* yapacağız. */
l = k * j;
writefln(" katı: %s", l);
/* [Ali] Evet, bu da bitTest içindeki işlemle ilgili. veri'nin
* ilgili bitini 1 yapıyoruz. Daha sonra k döngüsünde l
* değerine rastladığımızda l'nin asal olmadığını bileceğiz
* çünkü l k'ye tam bölünür.
*
* Peki bunu niye bir BitVector ile yapmıyoruz? (Belki de öyle
* yapıyoruzdur; daha tam anlamadım.)
*/
veri[l >> 4] |= 1 << ((l % 16) >> 1);
writefln("veri[%s] |= %s", l >> 4, ((l % 16) >> 1));
}
xSay++;
writef ("%d\t", k);
}
}
writefln ("\n\nToplam %d adet asal bulundu...", xSay);
}
Yani sonuçta bu Eratosten kalburu... Zaten sen de başka bir şey demiyorsun. Konunun başlığı bile öyle. :)
Ama burada Eratosten kalburu algoritmalarında uygulanan dıştaki döngünün N'nin kare köküne kadar ilerletilmesi ve içteki döngünün dıştakinin karesinden başlatılması uygulamalarını görmüyorum. Asal desen uymaz diye mi öyle, yoksa o burada da uygulanabilir mi?
Benim kafamı karıştıran başka şeyler de var:
-
Gösterdiğin ikinci resim için teşekkürler ama doğrusu benim anlamama yardımı olmadı. Örneğin 17 ve 31, 203 değerli bayta işaret ediyorlar. Neden? Mavi ve kırmızı bitler ne anlama geliyor?
-
Deseni bu resimde mi görebiliyoruz? Örneğin 110 değerli baytın son üç bitinin 110 olduklarını görüyorum. (Tabii tesadüf olduğunu da anladım: Biri ikili, biri onlu.) Bir alttaki 203 değerli baytın da ilk üç biti 110... Desen o mu? Ama öyle olsa aynı ilişkiyi 203 ile 180 arasında göremiyorum. (?) Birisinin sonu diğerinin başı değil. (?)
-
Sonsuza giden sayıları bellek engeline takılmadan ifade edebilmek diyorsun ama algoritma xDizi adet elemanla başlıyor. O işi başaran başka bir algoritma mı var? Onu daha sonra mı göstereceksin?
Ali
--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]
Permalink
Reply
