Forum: D Programlama Dili RSS
Eratosten Kalburu Algoritması
Sieve of Eratosthenes Algorithm
Sayfa:  önceki  1  2 
Avatar
Salih Dinçer #16
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj ID 7020
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...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #17
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
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]
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Bu mesaj Salih Dinçer tarafından değiştirildi; zaman: 2012-10-11, 13:38.
acehreli (Moderatör) #18
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #16
Minik notlar:

1) k ve j'yi for döngüleri içinde tanımlamanı öneririm.

2) delegate içinde bulunduğu kapsamı gösteren gösterge de barındırdığından normalde function'dan daha ağır bir olanak olarak kabul edilir.

Senin durumunda yalnızca birincisi function'a dönüştürülebiliyor çünkü diğer ikisi birinciyi kullanıyorlar. Dikkat edersen, bitMask bir işlev değil, bir temsilci nesnesi. Dolayısıyla diğer ikisi bu yerel nesneye eriştikleri için delegate olmak zorundalar:
    ubyte function (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); };
Sanırım normal işlev kullanırsan kod daha hafif hale gelir. (Her zaman olduğu gibi: Bunlar hep tahmin, ölçmeden emin olamayız.)
    ubyte bitMask (uint k) { return cast(ubyte)1 << ((k % 16) >> 1); }
    bool bitTest (uint k) { return (veri[k >> 4] & bitMask(k)) == 0; }
    void bitSet (uint k) { veri[k >> 4] |= bitMask(k); }
3) %d int içindir. Tam doğru olması için ya %u olmalı ya da en iyisi %s olarak bırakmalı.

Ali
Avatar
Salih Dinçer #19
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
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?) 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...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #20
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Bir şey daha:

for döngüsünün denetim bölümü her döngüde işletilmek zorundadır. Normald (xAsal / k) bölme işlemi yavaşlık katıyor olabilir. Tabii derleyici, ne xAsal'ın ne de k'nin döngü içinde veya çağrılan işlevler içinde değiştirilmediklerini kanıtlayabilirse o zaman hesabı tek kere yapar. O sonucu yerleştirecek bir yazmaç da bulabilirse kod hızlı da olur.

O yüzden hiç olmazsa o hesabı for'dan önce senin bir kere hesaplatmanı öneririm.

Bu durumda başka bir seçenek iota'dır çünkü hesap ona bir parametre olarak gittiği için tek kere işletilir. Ama sınır değer olarak ne kullanacağımdan emin olamıyorum:
import std.range;
// ...
    // k ve j artık açıkça tanımlanmıyorlar:
    uint xSay = 1;
// ...
    foreach (k; iota!ubyte(3, xAsal + 1, 2)) {
// ...
            foreach (j; iota!ubyte(3, (xAsal / k) + 1, 2)) bitSet(k * j);
Emin olamamamın nedeni, sen <= işleci kullandığın halde iota < işlecini kullanır. Yani onda sınır değerin ikincisi aralığa dahil değildir. Senin aldığın sonuçları elde edebilmek için ben 'xAsal + 1' ve '(xAsal / k) + 1' yazdım. Öyle yaptığım zaman sonuçları değiştirmiyorum, değil mi?

Ali
Avatar
Salih Dinçer #21
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Teşekkürler hocam, aralıkları da katıp algoritmayı daha lezzetli hale getirebilseydik çok iyi olurdu. Ancak ben de denediğimde kaçırdığı asal olmayan tek sayılar çıkıyor. Aslında ikinci döngüde parantezin dışında +1 yapmak yerine içinde yani şöyle (xAsal+2) / k yapmak veya daha fazla arttırmak netice veriyor. Sorunun kaynağı ise küsüratlı işlemlerin aşağıya yuvarlanmasından kaynaklanıyor. Ne hikmetse olayı tek bir eşittir ile çözebiliyoruz...:)

Bu arada bahsettiğiniz geliştirmeyi ben daha önce, oranı döngü dışında hesaplatarak denemiştim. Aradaki fark o kadar küçük ki 50 milyon asal sayı için 1 saniyenin altında diyebilirim. Belki çok çok büyük sayılarda (öyle ya sayı büyüdükçe artmalı!) daha büyük gecikmeler olacaktır. Ancak oraya kadar hafıza yetmediği için ulong sınırlarına henüz gelemiyorum...:(

Şimdi bir düşüncemi sizlerle paylaşmak isterim. Belki bunu yapabilirsek ulong sınırına kadar asal sayıları üretebiliriz...

Nasıl olsa biz ikinci döngünün hemen altında xSay ve k.write("\t") ile asal sayıları sayıp ekrana yazabiliyoruz. Öyleyse geride kalan bitleri data = data[1..$] diliminde yaptığımız gibi silebiliriz. Tabi bunu öyle bir zamanda yapmalıyız ki (çünkü her byte 16 tek sayıyı üzerinde barındırıyor!) yanlışlıkla işler karışmasın...:)

Sanırım bunu henüz denemesem de Eratosten sınıfındaki bitSet() işlevinde yapabiliriz; 16 sayısını gözardı etmeden...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #22
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Hayırlı cumalar...:)

Cumanın bereketine yeni sürüm! Hep diyorum ya, son nokta bu artık ama yine olmadı; alın size sürüm 6:
/*
 * asalTara.d (v6 - 12.10.2012)
 */
    import core.stdc.stdio : printf;
    
    immutable n = 982451000;            // Alt Sınır
    immutable x = 982451653;            // Üst Sınır       
    immutable s  = ((x - n) / 16) + 1// Dizi Boyutu
    
    ubyte[] data;
    
    auto bitMask (uint k) {
        return cast(ubyte)1 << ((k % 16) >> 1);
    }
    
    bool bitTest (uint k) {
        if(k >= n) {
            return (data[(k - n) >> 4] & bitMask(k - n)) == 0;
        }
        return 1;
    }
    
    void bitSet  (uint k) {
        if(k >= n) {
            data[(k - n) >> 4] |= bitMask(k - n);
        }
    }
 
void main() {
    data = new ubyte[s];
    uint xSay;
 
    if(n <= 2) {
        xSay++;
        printf("2\t");
    }
 
    for(uint k = 3; k <= x; k += 2) {
        if(bitTest(k)) {
            for(uint j = 3; j <= (x / k); j += 2) bitSet(k * j);
            if(k >= n) {
                xSay++;
                printf("%u\t", k);
            }
        }
    }
    printf("\n\nToplam %u adet asal bulundu...\n", xSay);
}/* Çıktısı:
982451023    982451081    982451087    982451111    982451123    982451159    982451161
982451179    982451191    982451219    982451227    982451231    982451243    982451321
982451333    982451359    982451383    982451419    982451429    982451443    982451467
982451479    982451497    982451501    982451549    982451567    982451579    982451581
982451609    982451629    982451653    
 
Toplam 31 adet asal bulundu...
*/
Meğer sadece bir offset değeri (n, belki x veya o olmalıydı) ile iki aralığı tarayabilirmişiz...:)

Başarılar...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Sayfa:  önceki  1  2 
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-11-19, 19:50:40 (UTC -08:00)