Konu çok ilgimi çekiyor.Bu arada algoritma Eratosten Kalburu değil, değil mi? Dün Eratosten Kalburu'nun bir gerçeklemesini yazarak kütüphaneme ekledim, fakat bu çalışmanın hızını görünce gözlerime inanamadım.
Bu arada sanırım isteğin asal sayıları bulmaktan ziyade asal sayılar arasında desen olup olmadığını kontrol etmek, değil mi?
Eğer kodlamada faydam olacaksa yardım etmek isterim.

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Aslında bir desen var ve geliştirdiğim algoritma bu desenin varlığı üzerine iş görmekte. Yılbaşında olduğunu görüyor ama kanıtlayamıyordum. Sonra içinde Ali Çehreli'nin de bulunduğu bir kaç arkadaşım ile e-posta yazışması yaptığımda bunun test sonuçlarını yayınladım. Toplamda 2 test yapmıştım ve 3.'sünde listeletmeyi başardım. Şimdi sıra ışınlanmakta ki işte orada zorlanıyorum.

Hoş, olayı kavramak da zor. O yüzden kodlamaya yardımcı olacak arkadaşların önce konuyu anlamış olması gerekiyor. Bir de elektronik bilgisi olması faydalı olabilir çünkü kodlama bitwise operator'leri ağırlıklı kullanılmakta. En iyisi mi katkı sağlamak isteyen herkesle işin doğasını özet olarak anlatan ilk hazırladığım belgeyi paylaşayım, bakalım 53 numaralı satırı (yMask = 16) bulabilecek misiniz?

Alıntı ("Asal Düzen - özet-"):

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (acehreli):

import std.stdio;

 struct Mask {
   uint ara;   // iki desene ara'sı
   char bit;   // desenleri bit'ler ile ifade edilmesi (byte karşılığı)
 };

void main() {
 auto maske = [ Mask(0, 32), Mask(0, 64), Mask(0,128), Mask(1,  1),
                Mask(0,  2), Mask(0,  4), Mask(0,  8), Mask(0, 16) ];

 for(int i; i < 10; i++) {
   foreach(ref s; maske) {
     writef ("%d + %d\t", s.bit, s.ara);
   }
   writefln(" = %d", maskÖtele(maske));
 }
}

 uint maskÖtele (ref Mask[] desen)
 {
     if(desen[0].bit > 16) {
       if(desen[0].bit != 64) desen[0].ara++;// İstisna hariç MSB ise arttır!
       final switch (desen[0].bit) {
         case 128: desen[0].bit = 4; break;
         case  64: desen[0].bit = 2; break;
         case  32: desen[0].bit = 1; break;
       }
     } else desen[0].bit <<= 3;
//----------------------------------------------------1.desen biter!
     if(desen[1].bit == 128) desen[1].ara++;// Tanımsız istisna için FIX 1a
     if(desen[1].bit < 8) {
       if(desen[1].bit != 2) desen[2].ara++; // Sonraki bit, (2)'yi arttır!
       final switch (desen[1].bit) {
         case 1: desen[1].bit =  32; break;
         case 2: desen[1].bit =  64; break;
         case 4: desen[1].bit = 128; break;
       }
     } else desen[1].bit >>= 3;
     if(desen[1].bit == 1) desen[1].ara++;    // Tanımsız istisna için FIX 1b
//----------------------------------------------------2.desen biter!
     if(desen[2].bit == 1) {
       desen[3].ara++;                        // Sonraki bit, (3)'ü arttır!
       desen[2].bit = 128;
     } else desen[2].bit >>= 1;
//----------------------------------------------------3.desen biter!
     if(desen[3].bit == 128) {
       desen[3].ara++;                        // İçe dönükse kendini arttır...
       desen[3].bit = 1;
     } else desen[3].bit <<=1;
//----------------------------------------------------4.desen biter!
     if(desen[4].bit > 16) {
       if(desen[4].bit != 64) desen[4].ara++; // İstisna hariç MSB ise arttır!
       final switch (desen[4].bit) {
         case 128: desen[4].bit = 4; break;
         case  64: desen[4].bit = 2; break;
         case  32: desen[4].bit = 1; break;
       }
     } else desen[4].bit <<= 3;
//----------------------------------------------------5.desen biter!
     if(desen[5].bit == 128) desen[5].ara++;  // Tanımsız istisna için FIX 2a
     if(desen[5].bit < 8) {
       if(desen[5].bit != 2 ) desen[6].ara++; // Sonraki bit, (6)'yı arttır!
       final switch (desen[5].bit) {
         case 1: desen[5].bit =  32; break;
         case 2: desen[5].bit =  64; break;
         case 4: desen[5].bit = 128; break;
       }
     } else desen[5].bit >>= 3;
     if(desen[5].bit == 1) desen[5].ara++;    // Tanımsız istisna için FIX 2b
//----------------------------------------------------6.desen biter!
     if(desen[6].bit == 1) {
       desen[7].ara++;                        // Sonraki bit, (7)'yi arttır!
       desen[6].bit = 128;
     } else desen[6].bit >>=1;
//----------------------------------------------------7.desen biter!
     if(desen[7].bit == 128) {
       desen[7].ara++;                        // İçe dönükse kendini arttır...
       desen[7].bit = 1;
     } else desen[7].bit <<=1;
//----------------------------------------------------8.desen biter!
     uint yMask = 0;
     for(short i; i < 8; i++) yMask += desen[i].ara;
     return 8 + yMask;    // Veri demetinin toplam genişiliğini döndür...
   }

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Sütunlardaki büyük yazılmış olan 8'er bitin bir alt satıra nasıl geçtiğini anlıyorum: 8 biti sütunun başında belirtilen biçimde kaydırıyoruz.

Genişlemenin nasıl olduğunu ise göremiyorum. İlk sütuna baktığımda tahmin ettiğim şu: 1 değerli bit her soldan taşıp tekrar sağdan girdiğinde küçük olarak yazılmış olan sayı bir artıyor. Ama bu kuralı bütün sütunlara uygulayamıyorum.

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Eratosten Kalburu'nu kullanmadan ışınlanarak bulduğum ilk asal:

4294967279 (2^32 -17)

Hayırlı ve uğurlu olsun...

Dip Not: Ancak teknik olarak biraz uzun sürüyor! Çünkü hafızada (4294967287/16)+1 boyutluk bir dizi açıyorum. Bunu kurulumu bile çok zaman alıyor. Oysa 1-2 byte'lık (4294967287 - 4294967279 = 8) açmam yeter. Sanırım Bir Garip Yığıt (http://ddili.org/forum/thread/891) yapısında index'ler ile ilgili bir sıkıntı var ve bunu gidermek gerekiyor.

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

2. bulduklarım ise şunlar:
   'Counting, please wait...
   2147483629 2147483647
   Generating MD5 Hash...'

Sınır olarak Euler'in 1772'de bulduğu 10 basamaklı 8. Mersenne sayısını (2147483647) kullandım. Düşünsenize adam kağıt kalemle bulduğu şeyi ben zorlanarak henüz yeni buluyorum. Dolayısıyla daha yolun başındayım ve çok hata olabilir. Hatta yukarıda verdiğim iki sayıdan ilki asal değilse bu bulduklarım bir tesadüf oluyor...:)

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (Salih Dinçer):

Üçüncü deneme gerçekten ışık hızında (pat diye) bir sonuç ama yanlış tabi! Hala bir yerlerde hata var, çünkü tek sayılar çıkıyor...(

'Counting, please wait...
2147483631 2147483633 2147483635 2147483637 2147483639 2147483641 2147483643 2147483645 2147483647
Generating MD5 Hash...
MD5=C4103F122D27677C9DB144CAE1394A66 (refID: bwSieve)
'
arrLength = 2;
xOffset = 2147483647; iken alınmış bir sonuç...

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Merhaba,

Tam 7 ay önce yayınladığım (11.03.2012) Eratosten Kalburu algoritmasını gözden geçirdim ama v5'i geliştirmek kolay değil. Çünkü o kadar çok geliştirme yapıldı ki belki de son nokta bu! Bende azıcık düzenledim de şimdi çok daha şirin bir şey oldu...:)

/*
* asalTara.d (v5-11.10.2012)
*/
   import std.stdio;

   immutable xAsal = 1001; //179424673; //982451653;// (50 milyonuncu)
   immutable xDizi = (xAsal/16) + 1;

void main() {
   auto veri = new ubyte[xDizi];
   uint k, j, xSay = 1;

   ubyte delegate (uint) bitMask = (k) => cast(ubyte)1 << ((k % 16) >> 1);
   bool delegate (uint) bitTest = (k) => (veri[k >> 4] & bitMask(k)) == 0;
   void delegate (uint) bitSet = (k) { veri[k >> 4] |= bitMask(k); };

   write ("2\t"); // Çift asal sayı düzeltmesi...

   for(k = 3; k <= xAsal; k += 2) {
       if(bitTest(k)) {
           for(j = 3; j <= (xAsal / k); j += 2) bitSet(k * j);
           xSay++;
           writef("%d\t", k);
       }
   }
   writefln("\n\nToplam %d adet asal bulundu...", xSay);
}

Her şey, 'main()' işlevi hariç 1 'if()', iki 'for()', üç de işlev! Çok ama çok basit ve hızlı bir algoritma. Ders olarak okutulması lazım!

Başarılar...

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Belki geliştirme sayılmaz ama ders olarak okutulursa bit içeriğini incelemek için bu da güzel:

/*
* asalTara.d (v5c - 11.10.2012)
*/
   import std.stdio;

   immutable xAsal = 1000; //179424673; //982451653;// (50 milyonuncu)

class Eratosten(T) {
   private T[] data;

   public:
       immutable type_length = (T.sizeof * 16);

   this(size_t size)
   {
       size_t isOverload = size % type_length ? 1 : 0;
       data = new T[(size / type_length) + isOverload];
   }

   void bitSet(size_t index) @property
   {
       data[index / type_length] |= bitMask(index);
   }

   bool bitTest(size_t k) @property
   {
       return (data[k / type_length] & bitMask(k)) == 0;
   }

   auto bitMask(size_t k) @property
   {
       return cast(T)1 << ((k % type_length) >> 1);
   }

   string toString() {
       string sonuç = "[";
       size_t sınır = data.length * type_length;
       size_t farkı = data.length % type_length;
       for(size_t n = 3; n <= sınır - farkı; n += 2)
       {
           sonuç ~= bitTest(n) ? "1" : "0";
       }
       return sonuç ~ "]";
   }
}

void main() {
 with(new Eratosten!ulong(xAsal)) {/* eskiye dönmek için kapa

   auto data = new ubyte[(xAsal/16) + (xAsal/16?1:0)];

   auto bitMask (uint k) { return cast(ubyte)1 << ((k % 16) >> 1); }
   bool bitTest (uint k) { return (data[k >> 4] & bitMask(k)) == 0; }
   void bitSet  (uint k) { data[k >> 4] |= bitMask(k); }//*/

   write ("2\t"); // Çift asal sayı düzeltmesi...
   uint xSay = 1;

   for(uint k = 3; k <= xAsal; k += 2) {
       if(bitTest(k)) {
           for(uint j = 3; j <= (xAsal / k); j += 2) bitSet(k * j);
           xSay++;
           writef("%u\t", k);
       }
   }
   writefln("\n\nToplam %u adet asal bulundu...", xSay);
   toString.writeln; //data.writeln;
 } /* eskiye dönmek için kapamayı unutma */
}

Çıktısı:
' 2 3 5 7 11 13 17 19 23 29 31 37
41 43 47 53 59 61 67 71 73 79 83 89
97 101 103 107 109 113 127 131 137 139 149 151
157 163 167 173 179 181 191 193 197 199 211 223
227 229 233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349 353 359
367 373 379 383 389 397 401 409 419 421 431 433
439 443 449 457 461 463 467 479 487 491 499 503
509 521 523 541 547 557 563 569 571 577 587 593
599 601 607 613 617 619 631 641 643 647 653 659
661 673 677 683 691 701 709 719 727 733 739 743
751 757 761 769 773 787 797 809 811 821 823 827
829 839 853 857 859 863 877 881 883 887 907 911
919 929 937 941 947 953 967 971 977 983 991 997

Toplam 168 adet asal bulundu...
[1110110110100110010110100100110010110010100100010110
11010000001010011000011001001010010011000011011000001
00000101101001100001001001001100101100001000000101101
00000010010000110100100010010010100100010100010000110
00011001010010001011010000010001010001010010000011000
00000100100001001001100100001001001100100101100000100
00110100100110000010100100010000100010000100010010010
10001001010001010000001000010000011000011011000010000
00101101000000101101000000000101000100001000101001001
00000010100100100010]
'

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Teşekkürler Ali hocam, bahsettiklerini hemen düzeltiyorum...

Ayrıca toString() işlevinde artık bitleri (örn. yukarıdaki çıktıda 168 adetten fazlasını) gösterdiği için küçük bir düzeltme şarttı. Tabi hızlıca ezberden yazdığım için dikkatimden kaçmış. Ancak Ali hocamın ekledikleri ile beraber şimdi daha güzel oldu. Bu durumda sürüm 5c oluyor ve katkı sağlayanların sayısı da dörde çıkıyor...:)
'
/*

• asalTara.d (v5c - 11.10.2012)
• Katkı Sağlayanlar: Ali Çehreli

•                Ali Eskici
  

•                Salih Dinçer
  

•                Zafer Çelenk
  

*/
'
Ayrıca sınıflı sürümde farklı veri türlerini otomatik bir şekilde kullanabilmek büyük kolaylık. Buna universal tester'ı (-bknz. Değişken türleri performansa etkili mi? (http://ddili.org/forum/thread/992)) yaparken başlamıştım. Dolayısıyla asal sayıları bulurken test ettiğimde hiç bir şey fark etmediğini ispatladım. Ancak bir şey denedim de çok ilgimi çekti! Eğer verileri ulong veri türünde yazarsanız 172-1 adet asal sayıyı (3 .. 1021) sadece 8 sayıyla (onların bitsel karşılıklarıyla) ifade edebiliyorsunuz:

'[9120613216031552656, 16026479229352129485, 6590629788102937398, 13103079280978030267,
17855478254761000911, 16966668913282316724, 17635898192515022330, 11167650370772989791]'

Son olarak Ali hocanın temsilciden normal işleve çevirmesi arasında 1 sn. fark olduğunu belirteyim. Testi 1,66 MHz.'lik Atom işlemci ve 10 milyon asal sayı ile yaptım. Eskiden 28 saniyede buluyorken normal işlevler ile 27 sn. sürdü. Belki de sadece bir denk gelme hadisesi ve performansa etkili değil.

Sevgiler, saygılar...

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]