Merhaba,

Yaklaşık 1 senedir, hobi maksatlı bir proje için kod yazıyorum. Ama bazen kendimden şüphe ediyorum...:)

Çünkü görebildiklerimi başka insanlar neden göremiyor, anlamıyorum! Elbette bakış açısından dolayı olmalı. Hatta konuyla alakalı olarak geçen gün Zekeriya'nın gördüğü şeyi ben de görememişim. Ancak, algoritma ile kanıtladığım için artık pek de şüphe etmiyorum. Peki ya siz aşağıda bir desen (tekrar eden, algoritması kolayca yazılabilen bir aritmetik) görebiliyor musunuz?

Alıntı ("bwstest.d çıktısı"):

Sanırım bu forumda işaretlerini ilk olarak şu başlıkta vermiştim: Eratosten Kalburu Algoritması (3.ileti) (http://ddili.org/forum/post/6962)

Şekiller çizmiştim ve öncesinde bir Google Projesi (https://code.google.com/p/bitwise-sieve/) açmış, e-posta yoluyla arkadaşlarımla gidebildiği yere kadar tartışmıştım. Aslında temeli basit, çünkü milattan önce 3. yüzyılda yaşamış Eratosten'nin kalburunu (-bknz. Sieve of Eratosthenes (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)) kullanıyorum. Ancak bilen bilir, önceki tüm asal kökleri kullanarak çıkarılan (katları elenen) bu yönteme ihtiyaç duymuyorum. Temelini ikilik sistemde kaydırma komutları (o yüzden Bitwise Sieve ismini verdim) oluşturuyor ve sonra modüler aritmetik kullanarak ileriki bir asal sayıyı çıkarabiliyorum. Gerçi şu var:

Belki Erastosten'nin geleneğini sürdürüyor olabilirim. Gerçekten de, asal olmayanları binary 1 sayısı ile işaretleyerek eliyorum. Ancak çift sayılarda işlem yapmıyor, 8 bitlik ubyte değişkenine verdiğim değerlerle (0-255) 16 tam sayı veya 8 tek sayı ifade edebiliyorum. Örneğin:

Alıntı:

Mutlaka dikkatinizi çekmiştir, neden DEC.18 değil de 72 sayısı. Çünkü verileri bir yığında (stack array) tutuyorum ve BIN'deki ilk bit (LSB tarafı) aslında 3'ü temsil ediyor. Peki, her bitin değer 1, 2, 4, 8... diye gittiğine göre; dördüncü bit 1 (DEC.8) asal olmayan sayıyı perdelesin. Tıpkı Eratosten'nin yaptığı gibi çizgi üzerine bir çizik atıyoruz. Sanırım henüz çok kafa karıştırmadım ve herkese basit gelmiş olmalı, değil mi?

Şimdilik bu kadar...

Dip Not: Zamanla, gelen sorular veya gelişmeler doğrultusunda bu tartışmayı devam ettireceğim inşaallah. Başlangıçta kod vermedim ama yukarıda naklettiğim 3. ileti ve devamına bakarak bazı kodlara erişebilirsiniz. Amacım olabildiğince basitten konuyu işleyerek herkesin anlamasını sağlamak.

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

Önceden (diğer başlığın 3. iletisi), "Ormandaki Okçu" hikayesini anlatacağım sözünü vermişim. Bakın şimdi size, bir tane de fazladan (hemen aşağıdaki) hikaye anlatarak bu sözümü tutayım...:)

Alıntı:

Bu hikayedeki mantığı bir an için doğru sayalım. Eğer mantığını geçersiz kılmaya çalışırsanız; bana, ilerlerden (örn. 1 trilyon sayısından itibaren) öyle bir ardışık 16 tek sayı getirmelisiniz ki içinde 8'den fazla asal sayı bulunsun! Matematiksel olarak ispat yapacak kadar kabiliyetli değilim ama bunun asal sayıların doğasına aykırı olduğunu ve böyle bir sayı dizisi getiremeyeceğinizi adım gibi biliyorum. Çünkü başlarda bunu yapmak kolay ama sonra asıl sayıların arası hikayedeki gibi açılmaktadır. Örneğin ilk 10 asal sayıya bakalım:

Alıntı:

Yukarıda tam 16 tek sayı var ve köşeli parantez içine alınmayan 10 sayı asal. Kural gereği 8'li gruplar haline aralarının açılması gerekiyordu. Öyleyse asal sayıların gittikçe seyrekleşmesi ve bazen bir anda sayılarının artmasının tek sebebi yukarıdaki hikayede anlatılan vagonların aralarının açılmasıdır. Gerçi herkes bilir, asal kökler arttığı için sayılar seyrekleşiyor ama bunun böyle bir düzeni olduğunu söyleyen oldu mu onu ben bilmiyorum...:)

Gelelim 2. hikayemize, bu kısa olacak çünkü daha önce e-posta yoluyla anlatmıştım...

Alıntı:

Dip Not: Hikayeyi bir ara Flash animasyonu ile görselleştirmeyi ve geliştirmeyi düşünüyorum. Çünkü anlaşılması için biraz hayal gücü istiyor ama bir kaç ayrıntı daha verebilirim. Alice'in koştuğu kuzey yönü +sonsuz ve 2 rakamından başlıyor. Başlangıçta 1 ağaç var ve gittikçe sıklaşıyorlar ama okçu ile Alice arasında sonsuza kadar mesafe var ve okçumuzun attığı oklar ışıktan bile hızlı...:)

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

Salih hocam çok kısaca göz attım ve bir şey dikkatimi çekti.

G, C harfi:
(1,3,5,7,9...). satırdan hareket : 3 ileri
(2,4,6,8,10...) satırdan hareket : 1 geri

A, E harfi:
(1,3,5,7,9...). satırdan hareket : 1 geri
(2,4,6,8,10...) satırdan hareket : 3 ileri

F, H harfi:
(1,3,5,7,9...). satırdan hareket : 1 ileri
(2,4,6,8,10...) satırdan hareket : 3 geri

B ve D harfi:
(1,3,5,7,9...). satırdan hareket : 5 ileri
(2,4,6,8,10...) satırdan hareket : 1 ileri

Zekeriya

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

Evet, kaydırma komutları bunları...:)

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

Ve ayrıca burada da kayarak birbirini tekrar etme var. Hatta ve hatta
1.satır ile 9.satır ile 17.satır ile 25.satır aynı. Hatta aynı şekilde
2.satır ile 10.satır ile 18.satır ...

Yani tekrarlama bulunmaktadır.

Bu arada Salih hocam hikaye okumayla pek aram iyi değil :) Bunun videolusu yok mu? :D

Zekeriya

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

Bahsettiğini kodda şu şekilde dönüştürüp ekrana yansıtıyorum:

 with(i2c) ubyte[][] bits = [ [ A, D, G, B, E, H, C, F ],
                              [ D, A, F, C, H, E, B, G ],
                              [ G, F, E, D, C, B, A, H ],
                              [ B, C, D, E, F, G, H, A ],
                              [ E, H, C, F, A, D, G, B ],
                              [ H, E, B, G, D, A, F, C ],
                              [ C, B, A, H, G, F, E, D ],
                              [ F, G, H, A, B, C, D, E ]
                            ];

Bu en bariz desen ama desenin sadece bir bölümü. Yani asal sayılar gibi asil (karmaşık) görünen bir yapı basit ama o kadar da değil...:)

Temelini boşluklar (byte), ağaçlar (bits) olmak üzere 2 desen oluşturuyor. Ayrıca binary olarak ifade edilemeyen 3, 5, 7 kökleri var. Çünkü 3 sağa, 3 sola, 1 sola, 1 sağa, 3 sağa, 3 sola kaydırma algoritması 0'a yaklaştıkça daralıyor ve 1/0 ile ifade edilemeyecek nibble bitler meydana geliyor.

Özetle bir tesadüf mü bilmiyorum ama 1 byte (8 bit) ile çok sıkı bir ilişkisi var! Ama bu ilişki yukarıda belirttiğim gibi 3, 5, 7 köklerinde (derinlik) bozuluyor. O yüzden modüler aritmetik kullanıyorum:

 struct CycleArray(T) {
   T[] data;
   size_t offset;

   T opIndex(size_t index) {
     // Modular Arithmetic------------v
     return data[(offset + index - 1) % $];
   }
 }

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

Devam edelim...

Şimdi, bizim referansımız Eratosten Algoritmamız olacak! Hani forumda ve dışında bir çok kişinin katkı verdiği o algoritmada bir dizi (xData) var ya işte o bizim referansımız. Aslında yakında 7. sürümü çıkabilir ama biz Eratosten(T) sınıfı içine aldığımız sürümü kullanacağız. Çünkü onun üzerinde cirit atmak daha kolay...:)

O kod şurada (http://ddili.org/forum/post/7943):
Alıntı:

> /*
>  * 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];
>     }
>   :  :  :
> ```

>

Ancak işleri kolaylaştırmak adına (çünkü tüm sayılar hakikaten doğru mu, asal mı diye tek tek bakamayız!) md5 işlevini ekleyelim. Tabi bunu kullanabilmek için "'''import' std.conv, std.md5''" satırını eklemeyi unutmayalım...

string md5() @property {
return getDigestString(to!string(this.data));
}

Artık referans noktamız sağlam temeller üzerine oturmuş ve hazır. Yani tüm büyü o malum dizi üzerinde. Her şeyi oradaki verileri inceleyerek çıkarabilirsiniz. Peki bundan sonra ne yapacağız?

Adım adım, kalburun ürettiği veriyi şekillendiren yeni algoritmamızı (Bitwise Sieve) inşaa edeceğiz. Ayrıca:
* **Modülün ismi:** bws
* **Sınıfın ismi:** bwsTren
* **Yapının ismi:** Tren
* **Üyenin ismi:** vagonlar

Olacak... Tıpkı hikayemizdeki gibi...:)

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

Alıntı (Salih Dinçer):

O benzetmeyi sevdim. Sanırım öyle daha kolay anlayacağız. :)

Ormandaki okçu bana açıklayıcı gelmemişti.

Ali

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

Belki herkese anlamsız gelecek ama, benim için önemli olan bir gelişmeyi (hatırayı) bildiriyorum...

( 'Gören de canlı yayında önemli bir gelişmeyi aktaran muhabir zannedecek...':) )

Çok değil, yaklaşık 8 saat önce (TSİ: 05:00) yazılımda sadece şu değişikliği uyguladım:

 union Veri {
   uint otuzikiBit;
   ubyte[4] sekizBit
 }

Son günlerde union kullanmada aşırı derece abarmış (Ankaralılar böyle dermiş) durumdayım! Buna rağmen daha önce neden aklıma gelmedi diye de ayıpladım kendimi. Gelişmenin önemine gelince; koşut (parallel) progralamadan daha iyi hız artışı sağladığımı söyleyebilirim. Teknik manada ayrıntıya girersek...

Her ne kadar aynı anda olmasa da bir çevrim zamanında (döngünün başa sardığı her aşamada) üretilen asal deseni 4 hücreye şu şekilde uyguluyorum:

 auto asal = new bwsTren(true);
 auto data = Veri(0);
 auto mLen = data.sekizBit.length;

   :    :    :

 xIndex = xDizi - xOffset - mLen;
 foreach(i, ref veri; data.sekizBit) {
   veri |= asal[ (xIndex + i) % asal.length() ];
 }

Örneğin, 1 trilyonunca asal olan (-bknz. OEIS A006988 Table (http://oeis.org/A006988/list)) 29996224275833 sayısından itibaren geriye doğru 64 adetlik aralığı 958 ms.'de üretiyor:

Alıntı:

Tabi, test tablosundaki (OEIS A006988) sayılar büyüdükçe doğal olarak işlem uzuyor. Ama bu başlığı açtığımdan bu yana, kaydettiğim bu gelişme gerçekten "pat" dedirtecek derecede iyileştirme sağladı. Alt döngüde 4 defa işlem yaptığına göre 4 x 2.738.441, yaklaşık 11 milyon işlem, Intel i3-540 CPU için mükemmel! Deseni oluşturan bwsTren sınıfındaki işlemleri hiç hesaba katmadım bile. Sizce de verimli değil mi?

Üstelik harcadığı bellek önemsenmeyecek derecede az. Tanrım, büyüksün...:)

Dip Not: Sonuçarı doğrulamak için şu sitedeki listelerden faydalanıyorum:
http://markknowsnothing.com/cgi-bin/primes.php

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

Aslını söylemek gerekirse o kadar iyi değil Ali hocam...

Neredeyse 1 seneyi aşkındır aynı çekirdek kod üzerinde çalışıyorum. Dolayısıyla hız da yukarıda söylediğimin dışında çok yol katedemedim. Çünkü sayılar ulong.max'a yaklaştıkça dakikaları bulan işlem süreleri ile boğuşuyorsunuz. Henüz std.bigint kütüphanesini de kullanmadım...:)

Ali hocam sen ve Zekeriya gibi akıllı arkadaşlarım şu çekirdek koda bir el atsa ne güzel olurdu:
https://code.google.com/p/bitwise-sieve/downloads/detail?name=bws_1_913.d

Orada next() ile her seferinde vagonların içeriği değişiyor. Tıpkı ilk iletimde naklettiğimin aynısı. Temeli çok basit bir mantık üzerine kurulu ama uzun bir yöntem ile "sequence" tutturabildim ancak. Sanırım daha hızlı bir algoritma geliştirilebilir.

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