Forum: D Programlama Dili RSS
Eratosten Kalburu Algoritması
Sieve of Eratosthenes Algorithm
Sayfa:  1  2  sonraki 
Avatar
Salih Dinçer #1
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Konu adı: Eratosten Kalburu Algoritması
Merhaba,

Yılbaşında asal sayılar üzerine küçük bir zihin çalışması yapmıştık; bunun son halini aşağıda paylaşmak istiyorum. Başlangıcı Ali Eskici getirmiş, her hafta küçük eklemeler ile ne hikmetse en iyileştirmesi bitirememiştim! Şimdi bile...:)

Dün de Zafer Çelenk sayesinde küçük bir ekleme daha yaptım ve sanırım bu böyle sonsuza kadar gider... Gerçi hafızayı çok daha iyi kullanan hızlı algoritmalar (-bknz. primeSieve) var ama bu basitliği (her bayta 16 tek sayı alması) ve anlaşılmasının kolay olması açısından öğrencilere faydalı olacağını düşünüyorum. Tamam, başlangıçta zor gelebilir ama sayısal elektronik dersini almış herkesin bileceği şeyler bunlar:
/*
 asalTara.d (v5-11.03.2012)
*/
    import std.stdio;
                                 
    const uint xAsal =  1001; //179424673; //982451653; (50 milyonuncu)
    const uint xDizi = (xAsal/16) + 1;
    ubyte[] veri;
 
    bool bitTest(uint k) {
        ubyte bits = veri[k >> 4];
        if ((bits & (1 << ((k % 16) >> 1))) != 0) return false;
        return true;
    }
void main() {
    veri = new ubyte[xDizi];
    uint l, k, j, n = xAsal, xSay = 1;
 
    write ("2\t"); // Çift asal sayı düzeltmesi...
 
    for (k = 3; k <= n; k += 2) {
        if (bitTest(k)) {
            for (j = 3; j <= (n / k); j += 2) {
                l = k * j;
                veri[l >> 4] |= 1 << ((l % 16) >> 1);
            }
            xSay++;
            writef ("%d\t", k);
        }
    }
 
    writefln ("\n\nToplam %d adet asal bulundu...", xSay);
}
Başarılar...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #2
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Biraz bandı başa sarmak istiyorum!

Çok değil canım, Eratosten'nin yaşadığı devire gitmeyeceğiz bu sefer. Bu daha yakın, milattan öncesiyle de işimiz yok...:)

Turing Machine'nı bilmeyenimiz yoktur herhalde? Bir manyetik şeritli bant (veri kaynağı) ve bunu okuyan bir kafa (bilgisayar) var; tıpkı aşağıdaki çizim gibi. Sonra ileri geri hareketler ile var olan veriyi işliyoruz ve ortaya çok güzel basitlikte olaylar karşımıza çıkıyor. Konu hakkında daha çok bilgi için: (-bknz. Kral'ın Yeni Usu - TÜBİTAK, Cilt-1)


Peki bu bant üzerine asal sayıları yerleştirsek n'olur? Pek güzel olur ki yukarıdaki algoritmada ubyte[] veri ismindeki sınırsız (tabi bilgisayarın izin verdiği yasal değere kadar) olan işte bu şerit. Zaten kuramsal olarak bu makine sınırsız veri işleme kabiliyetine sahip. Eee asal sayılar da sonsuz olduğuna göre pekala biz bunu yapabiliriz...:)

Ancak dikkat çift sayılar ile işimiz yok, dolayısıyla algoritmanın ilk döngüsünden anlayacağınız üzere bu şerite sadece tek sayıları dahil ettik ve asal olanlara True, olmayanlar False dedik. (ya da tam tersi miydi, ben de unuttum şimdi...:))

Neyse bunların hiç bir önemi yok, hatta yukarıdaki algoritmayı anlamanız da gereksiz. Sizi, şimdi mucize bir algoritmaya doğru (ismi kısaca Asal Desen!!!) yola çıkaracağım! Şu fikre ne dersiniz:

"Biz, bu asal sayıların işaretlendiği şerit (tek sayılar kümesi) üzerinde bir desen olduğunu farkettiysek (insanları çoğunluğu yok diyormuş ama belkide var!) ve bandı bu sefer ileri sararsak pat diye bulması uzun sürecek çok büyük bir asal sayıya erişemez miyiz?"

Az sonra...:)
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #3
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Az sonra dedim ama çok sonra oldu. Aslında böyle olacağını biliyordum ve sadece espri yapmak istemiştim. Neyse ki sonunda doğru bir karar verebildim. Çünkü durumu en iyi nasıl anlatırım diye düşünüyordum. Ben de atalarımızın sözüyle, yani "bir resim bin söze bedeldir" düsturuyla hareket edeyim dedim. İşte ilk yansımız:

[Resim: http://img688.imageshack.us/img688/3773/asaldzenyansi1.png]

Ancak yine de anlatıma ihtiyaç duyuyor! Gerçi yukarıdaki kod örneğinden bütün bu anlatacaklarımı çıkarabilirdiniz...:)

Öncelikle tek sayılar kümesinde işlem yapıyoruz. Elbette 2 sayısı bir asal sayı ama bunu sonradan dahil edeceğiz yoksa Asal Desen (Düzen) bozulabilir. Gerçi ilk sayı olduğu için hiç önemi yok ama işin temeli tek sayılar ya; bu gerekli! Ancak bize bir şey daha gerekli! O da sonsuza giden sayıları bellek engeline takılmadan ifade edebilme yeteneği. Cevabı yukarıdaki resimde...

Dikkat ederseniz başlangıçta fikir olarak bool türünü kullandım ama ifade etmedim. Yine de bunu denediğimi itiraf etmeliyim. Sonra her sayıyı bir ubyte ile ifade edebileceğimi düşündüm ve bir kaç bitwise trick'leri ile bunu hallettim. Dediğim gibi bunları kod içinde görmeniz mümkün o yüzden ayrıntısına girmiyorum. Zaten işin büyüsü bitwise ve 1/0'larda...:)

Bir de işin iki püf noktası var ki tersliği de diyebiliriz. Verileri her byte'a ters yerleştiriyorum. Yani aslında soldaki MSB bir LSB'dir ve sağdaki de tam tersi tabi. Diğer terslik ise resimde ifade edilmemiştir. O da, bundan sonra 1'leri 0, 0'ları ise 1 ile ifade etme gerekliliğimizdir. Çünkü OR ile maskeleyerek bir kesişim kümesi oluşturacağız. Bunun bir hikayesi de var ama sonra nakledeyim: Ormandaki Okçu (oklarımız 1 rakamı!)

Dip Not: İşin sırrını beklemeden incelemek isteyenler şu adrese bakabilir: http://code.google.com/p/bitwise-sieve/
(Windows kullanıcıları için hoş bir demo var ve ana sayfadaki ekran görüntüsü o programa ait...
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-07-19, 21:07.
acehreli (Moderatör) #4
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ı
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:

1) 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?

2) 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. (?)

3) 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
Avatar
Salih Dinçer #5
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
acehreli:
/* [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ş.
 
    /* [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. 
Açıklamalar için çok teşekkürler, bu tür ifadelerine bayılıyorum. Bunları derslerde de görmek mümkün. İşte kod içine açıklama gömmeyi ben çok beceremiyorum...:)

acehreli:
1) 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?
Oklar o bölümün karşılığı (başı/sonu) olduğunu ifade ediyor. Maviler true, kırmızılar false ve bu henüz ilk yansı (slide). Aslında burada iki şekil var ve planlamada dört idi. Ama 1'den 4'e hızlıca atlamayı yeğledim. Yoksa ikinci şekilde bool ifadeleri gösterecektim. O yüzden oklar ve renkler ile zenginleştirdim.

acehreli:
2) 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. (?)
Hayır, burada deseni göstermedim. Bu sadece yukarıdaki kodun görselleşmiş hali. Yani 16'ya bölümden kalanı alarak iki bayt ile ifade edilebilecek sayıların konumunu alıyoruz. Tek sayılar olduğu için de ikiye bölüyoruz (sağa kaydırıyırıyoruz). Aslında 7 bit yok 8 bit var, belki 0. biti saymamış olabilirsin.

acehreli:
3) 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?
Evet, onu daha sonra göreceğiz. Hatırlarsan başka bir algoritmayı bir kaç ay evvel e-posta tartışmalarında herkese göndermiştim. Şu ana kadarlar ki olay çıkış noktası. Temeli olduğu için önemli ve devam bu mantık üzerine işleyecek inşaallah.

Acele etmeyin, acele işe şeytan karışırmış...:)
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #6
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Salih Dinçer:
Acele etmeyin, acele işe şeytan karışırmış...:)
Hoş, şeytanın (bu inancınıza göre içimizdeki herhangi bir kötülük de olabilir!) karışmadığı iş yok ya...:)

Şu mübarek Ramazan günü manevi hesaplar yapacağıma asal sayılar ile ilgileniyorum. Neyse ki kendimce bir sınır getirmeye gayret ediyorum. Çünkü tarih boyu kimi insanlar tarafından yaşam şeklini değiştirecek derecede kafayı bozmuş insanlar gelmiş geçmiş. Katkıları olan ünlü matematikçiler müstesna. Neyse, şimdi biraz heyecanlanalım...

Amacım deseni ilk gördüğüm ki heyecanı size hissettirmek, işte asal desenin asimetrik gösterimi:
[Resim: http://img32.imageshack.us/img32/9738/asalolmayanlar.th.png] [Resim: http://img835.imageshack.us/img835/3927/asalolmayanlartam.th.png]
Sağdaki de zannedersem aynı bölgeydi (1359844) içeriğinde asal sayılarda yer alıyordu. Yazdığım ve ileride başka başlıkta paylaşacağım algoritma ile yukarıdaki algoritmanın karşılaştırma sonucu ise şu şekildedir:

"Intel® Core™ i3 CPU 540 @ 3.07GHz × 4 Test:
ASAL DÜZEN v1.0 (Code Name: bwTren)
===================================
Bellek tahsisi yapılıyor.........
4294967287'a kadar olan sayılar taranıyor...

KÖKLER:
2    3    5    7    -bitti-

MD5 kodu üretiliyor...
MD5=4d85a7aa6ba96727f073fb7f22a289b9 (refID: bwSieve)

203280220 adet asal sayı, 37581,4 ms.'de bulundu...
İşlemden geçen toplam kök (Y) = 6545

Test ediliyor...
203280220 adet asal sayı, 163317,8 ms.'de bulundu...
(Eratosten Kalburu'nun algoritma sonucudur!)

MD5=4d85a7aa6ba96727f073fb7f22a289b9 (refID: Eratosthenes)
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #7
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Sahurda bir ekleme (tespit) yapmayı unutmuşum, affola...

Geliştirdiğim algoritma çok büyük aralıklarda Eratosten Kalburu'na göre 4-5 kat fark atıyor. Bunu zaten yukarıda görmektesiniz. Ha keza çok daha hızlı algoritmalar da (-bknz. primeSieve 3.6 ) mevcut ki şimdi deneyemiyorum ama herhalde bir kaç saniye içinde sayacaktır!

Beraberinde aşağıdaki dramatik sonucu da paylaşayım da öyle devam edeyim...:)
ASAL DÜZEN v1.0 (Code Name: bwTren)
===================================
Bellek tahsisi yapılıyor......1000'a kadar olan sayılar taranıyor...

KÖKLER:
2    3    5    7    11    13    17    19    23    29    31    37    -bitti-

MD5 kodu üretiliyor...
MD5=13535aadca2ac84fdec721c3361b7300 (refID: bwSieve)

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

168 adet asal sayı, 7 ms.'de bulundu...
İşlemden geçen toplam kök (yMask) = 12

Test ediliyor...
168 adet asal sayı, 0,1 ms.'de bulundu...
(Eratosten Kalburu'nun algoritma sonucudur!)

MD5=13535aadca2ac84fdec721c3361b7300 (refID: Eratosthenes)
Gördüğünüz gibi 1000'e kadar olan 168 asalı tespit etmesi 7 kat daha yavaş oluyor. Üstelik 12 kök (sqrt 1000 ~= 31) ile zaten 1000'e kadar olan sayılar yoklamak mümkün ve çok basit bir şey. Ama bu yeni geliştirilen algoritmada pek bir matematiksel işlem yapmamaktayız. En azından doğrudan asal sayıları filitre eden maskeleme sisteminde sayma (toplama) dışında bir şey kullanılmıyor. O yüzden yavaş gibi görünmekte. Ancak buradaki güç/imkan çok farklı. Kaydırma yöntemiyle ve başka bitwise operator'leri kullanılarak yapılan işlemler sayesinde ileri bir aralığa amiyane tabirle ışınlanmak mümkün!

Dip Not: Son olarak belirtmeliyim; kök'den kasıt yMask'dır. Bunu yukarıdaki alıntıda belirttim. Yakında algoritmayı gördüğünüzde ne demek istediğimi daha iyi anlayacaksınız. Ama kısaca; yukarıdaki örneğe göre 12 defa dikey doğrultuda (Y) yapılan maskeleme işlemi demek. Gerçi bunu, zannedersem 7 ya da taş çatlasa 8 defa yapıyorum çünkü başlangıçta maskInitialize() işlevi var. İşte bu vakit alıyor çünkü kökler küçük ve etkilediği desen büyük.

Şimdi soruyorum, kodlama katkı sağlamak isteyen var mı?
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Kadir Can #8
Üye Haz 2010 tarihinden beri · 413 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
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.
Avatar
Salih Dinçer #9
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
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?

"Asal Düzen - özet-":
ASAL DÜZEN: Asal sayılar, 2 dahil tek sayılardan oluşurken; sadece 1'e ve kendine bölünür. Asal düzen ise 1 rakamından başlar ve ikilik sistemde (Binary~BNS) sol ve sağa kaydırmalar ile aşağıdaki gibi ifade edilir. Buradaki küçük rakamlar, dörtlük sistem (Quaternary~QNS) olarak yazılmıştır ve boşlukları sayı değeri (x) byte kadar ifade eder. Örneğin hiç boşluk yoksa ºº = 0 byte, 8 sıfır varsa º¹ = 1 byte veya 4 byte ise ¹º şeklinde ifade edilir. Son olarak her satır tek başına anlamsızdır. Anlamlı olması için VEYA Kapıları (OR Logics) ile kesiştirilmelidir. Böylece tüm asal sayılar pat diye çıkar...:)
                                «³                    »³                    »¹                    «¹                    «³                    »³                    »¹                    «¹
11-upORcode    º²00000001    ºº00001000    ºº01000000    ºº00000010    ºº00010000    ºº10000000    ºº00000100    ºº00100000
13-upORcode    º²00001000    ºº00000001    ºº00100000    ºº00000100    ºº10000000    ºº00010000    ºº00000010    ºº01000000
17-upORcode    º²01000000    º¹00100000    º¹00010000    º¹00001000    º¹00000100    º¹00000010    º¹00000001    ºº10000000
19-upORcode    º³00000010    º¹00000100    º¹00001000    º¹00010000    º¹00100000    º¹01000000    º¹10000000    º²00000001
23-upORcode    º³00010000    º¹10000000    º²00000100    º¹00100000    º²00000001    º¹00001000    º¹01000000    º²00000010
29-upORcode    º³10000000    º²00010000    º²00000010    º¹01000000    º²00001000    º²00000001    º¹00100000    º²00000100
31-upORcode    ¹º00000100    º²00000010    º²00000001    º¹10000000    º²01000000    º²00100000    º²00010000    º²00001000
37-upORcode    ¹º00100000    º²01000000    º²10000000    º³00000001    º²00000010    º²00000100    º²00001000    º²00010000
41-upORcode    ¹¹00000001    º²00001000    º²01000000    º³00000010    º²00010000    º²10000000    º³00000100    º²00100000
43-upORcode    ¹¹00001000    º³00000001    º²00100000    º³00000100    º²10000000    º³00010000    º³00000010    º²01000000
47-upORcode    ¹¹01000000    º³00100000    º³00010000    º³00001000    º³00000100    º³00000010    º³00000001    º²10000000
53-upORcode¹²

Siz de kolayca 53. satırı (asalı) kolayca yazabiliyorsanız, genleşme (sayıların boşlukları artması) ve temel asal düzeni anlamışsınız demektir. İkilik düzendeki bu uyum, çok anlamlı görünse de aslında, işin içerisine rakamlar ve algoritma girdiğinde gerçekten karmaşıktır. Yani şu gördüğümüzü görebilmek için uzaktan bakmak gerekiyor ki buradaki veriler en sadesi ve basitidir...

NOTLAR

BNS : Binary Number System
QNS : Quaternary Number System
pat : Seri bir şekilde...:)
SHL : Sola kaydırma « (shift logical left)
SHR : Sağa kaydırma » (shift logical right)
ORL : VEYA kapısı (or gate)
      0-0 => 0
      0-1 => 1
      1-0 => 1
      1-1 => 1


ÖRNEKLER

SHL : q <<= 3;
SHR : q >>= 1;
ORL : q = a | b;


KAYNAKLAR

- http://en.wikibooks.org/wiki/Algorithm_Implementation/Math…
- http://bcu.copsewood.net/dsalg/bitwise/bitwise.html
- http://en.wikipedia.org/wiki/Binary_numeral_system
- http://en.wikipedia.org/wiki/Quaternary_numeral_system
- http://en.wikipedia.org/wiki/Number_theory
- http://en.wikipedia.org/wiki/Sieve_theory
- http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #10
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ı
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
Kadir Can #11
Üye Haz 2010 tarihinden beri · 413 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Ben de genişleme sayılarında sıkıntı çekiyorum. Şimdilik gördüğüm şöyle bir şey var, ikilik sistemdeki sayı aynı satırda hareket ederken genişleme sayısına uygun hareket ediyor. Mesela ilk satırda 1 hep iki bit atlayarak gitmiş. İftardan sonra bir daha bakacağım.
Her mesajda ayrı bir heyecan... :)
Bu mesaj Kadir Can tarafından değiştirildi; zaman: 2012-07-21, 10:03.
Avatar
Salih Dinçer #12
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #10
acehreli:
Ama bu kuralı bütün sütunlara uygulayamıyorum.
Haklısınız, çünkü iki istisna durumu o zaman keşfetmemiştim. Bunu kodlardan görebilirsiniz:

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(11),
                 Mask(02), Mask(04), Mask(08), 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].bit32; break;
          case 2: desen[1].bit64; 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].bit32; break;
          case 2: desen[5].bit64; 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...
    }
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #13
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
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 yapısında index'ler ile ilgili bir sıkıntı var ve bunu gidermek gerekiyor.
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #14
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
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...:)
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #15
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #13
Salih Dinçer:
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 yapısında index'ler ile ilgili bir sıkıntı var ve bunu gidermek gerekiyor.
Üçü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ç...
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:  1  2  sonraki 
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-18, 22:40:09 (UTC -08:00)