Zaman Mekan İlişkisi ve Bölerek Deneme Algoritması

4623
zaman mekan ilişkisi

Merhaba arkadaşlar bu yazımızda sizlere zaman mekan ilişkisi ve bölerek deneme algoritmasını anlatacağım. Öğrendim ki Nasa mühendisleri Mars gezegeninde kullanacakları bellek platformu curiosity ile aynı olacakmış. Curiosity iki bilgisayar ile donatılmıştı. Fakat aynı anda sadece 1 i aktif halde bulunabiliyordu.

Curiosity bilgisayarlarının özelikleri şöyle idi:

  • 2 gb flash bellek.
  • 256 mg rastgele erişimli bellek.
  • Temel sistem işlevlerinin barındıran 256 kb salt okunur bellek.curiosity Ramleri

Tüm bir programı RAM’e yerleştirebilmek istiyoruz. Ne var ki alanı diğer programlarla paylaşmak zorunda olduğumuz için RAM’in sadece yüzde 5’i bize ayrılmış. Yani en fazla yüzde 5 ini kullanabiliyoruz. Buda toplamda yaklaşık 12,8 mg eder.

Bu konuyu açtım çünkü size zaman mekan takası ( Zaman Mekan İlişkisi) kavramından bahsetmek istiyorum veya mekan zaman takası. Bilgisayar terimlerinde bu terim çok kullanılır.


Öncelikle Bölerek Deneme Algoritması örneği görelim. Aşağıda ki gif te görüldüğü gibi ilk olarak 2 den başlamak suretiyle sayıları bölmeye başlıyor. Ardından 3,5,7 diye ilerliyor. Bu sayılardan hiç birine bölünmeyen sayıları asal sayı olarak kabul ediyor.

IV 42 Prime

Bu yönteme Eratosthenes Kalburu yöntemi deniliyor. Sizler için bunun programını yazıp sitemize ekledik. Yalnız çok fazla ram tükettiğinden genişlik 600 den sonrası için hesaplayamıyor  tarayıcınız donabilir. Eratosthenes Kalburu Programı.


zaman mekan ilişkisi ve bölerek

IV 42 tarafından yazılan bi programa bakalım. Bir milyondan asaldan oluşan bir dizi kullanılmış olsun, böylece algoritması bölerek deneme asallık testini uygularken mümkün olduğu sürece yalnızca asallara bakarak ilerliyor. Şöyle de bir soru sormuş kendisi, o anda hesaplamaya çalışmak yerine belli bir sınıra kadar ihtiyacımız olan tüm asaları niçin bir dizide saklamıyoruz?

Aslında bunun cevabı bölerek denerek algoritması için en iyi yöntemdir. Bu algoritma çok fazla adım kullanmıyor olsa da daha adım limitine ulaşamadan çok fena şekilde yavaşlayıp ve sonunda gelmeden kitlenip kalacaktır. MAX=9007199254740992

Yani daha önce tanımladığımız bu boyut için problemi hızlı bir şekilde çözmeyi başarmadı.  Bu örnekte tekrar tekrar bölünebilirlik testi yapmadan zamandan tasarruf edecek karşılığında ise mekandan, yani dizinin yerleştiği bellekten taviz verecekti. Peki neden işe yaramadı ?

Şimdi öğrendiklerimizi kullanarak kaba bir hesap yapalım. Ve bellek sınırlarımız dahilinde bu yöntemi kullanabileceğimizin mümkün olup olmadığına bakalım.

Hatırlayalım; 9 kat trilyon biraz üstünde ki sayılara işlem yapabilmemiz gerekiyor. Bölerek deneme algoritmamız sadece sayının kareköküne kadar sayıları denemeli. O noktaya kadar hiç çarpan bulamadı ise sayının asal olup olmadığını kesin bir şekilde söyleyebilmeli, şimdi bu sayının kareköküne ulaşarak kaç asal sayı geçmemiz lazım?

√9007199254740992= 94. 9 milyon olduğunu belirteyim.

Şimdi 95 milyondan küçük kaç asal sayı var?
Neysekı bu soruya yaklaşık bir cevap verebilmemizi sağlayan matematiksel bir çözüm biliyoruz.

Asal Sayı Teoremi

O halde x den küçük kaç asal sayı vardır?  x bölu x in dogal logaritması kadar. x 94,9 milyondan biraz büyük sayı oldugunda asal sayıların sayısı yaklaşık 5.1 milyon olur. Şimdi bu asal sayıları saklayamayacağımıza gore en buyuk asalın yanı bu durumda yaklaşık 5166823. asal sayının boyutunu bilmek gerekir ki bu sayınınn 94.9 milyondan küçük olacağını biliyoruz

İşlemlerden sonra en büyük asal sayı 89078611 çıktı. Peki yalnız bu asal sayıyı saklamak için ne kadar belleğe ihtiyacımız var ? Bunu bulmak için sayıyı 2 lik sisteme dönüştürelim. Çünkü bilgisayarlar sayıyı bu şekilde saklar.

En büyük asal sayıyı bit şeklinde yazınca;

89078611=100001111110110001010101 Burada 24 bit var. Yani tek bir sayıyı saklamak için 3 byte gerekiyor.

Şimdi diyelim ki tüm sayıları bellekte saklamak istiyoruz. En buyuk sayı 24 bit gerektirdiğine göre her asal sayı için 24 er bitlik bloklardan oluşan uzun bir liste düşünebiliriz. Listenin tamamı için kaç bit gerekir ?

Gereken Bellek=Değer x Alan

5166822 x 24 = 124003728 Bit = 14,7 Megabayt

Nerede ise 15 mg. Demek ki sınırlarımız dahilinde bu sayılardan oluşan listeyi bile bellekte saklamamız mümkün değil. Bunu söylediğimize göre artık bunu biliyoruz. Nispeten küçük bu sayının kare köküne kadar olan sayıları saklamak bu bellek sınırları dahilinde mümkün değil. Bu şekilde yapamıyoruz. Peki ya ödediğimiz bedel bin kata hatta 10 bin kat düşerse. Modern kriptografik  sistemlerde 512 bit hatta daha büyük boyutlar kullanılır. Böylece arama ve sayma imkansız halde geliyor. Mesela biri sizden 200 basamağa kadar olan tüm asal sayıların listesini isterse bunu aklınızdan bile geçirmemelisiniz.

Çünkü bunu saklayabilecek sabit diskin kütlesi gözlemlenebilir evrenden daha büyüktür. Hesabı yapmayı size bırakıyorum. Ama şunu bilin ki gözlemlenebilir evrende 10 üzere 80 atom bulunuyor. Bu 80 haneli bir sayı. Şimdi erişimimizi olan alan veya belleğin temel bir sınır var.  Problemlerimizi çözerken mekan ve zaman kullanımları arasında daima bir çekişme vardır. O halde bu asallık problemi testini küçük bir alan ve az bir zaman kullanarak hızla çözmek için ona bambaşka bir açıdan yaklaşmamız gerek.

8 Yorum

  1. Asal sayılar sonludur.
    Asal sayılar kalburu on lu değilde altılık kalburla elenir ise
    Bütün sayların tümü sonsuza kadar 1’in katlarından oluşur
    2 Asaldır ama sonsuza kadar sonu almayacak şekilde ikilik yani çift sayılar asal olmaktan çıkar yani bu kümede de asal sayı yoktur.
    3 tek sayıların üçte birini sonsuza kadar aslalıktan çıkarır
    4 ikin sozsuzluğu içinde asallıktan çıkan ilk sayıdır.
    5 yine 1 v 3 gibi kendi katlarının ilk ve son asal sayıdır.
    6 dört gibi ikilik (çit) kümedendir.
    Bütün asla sayıları en kolay altılık kalburdan eler isek. Her asal sayının kendi katlarından oluşan tüm sayılar içinden kendi asallıktan çıkan kümesini alıp artık asal olmayanlar arasına çekilir.
    1—–2—–3—4—5—–6
    7—–0—–0—0—11—12
    13—-0—-0—-17——-0
    Bu altılık kalburun 2– 3–4 ve 6 rakamlarının altını sonsuza kadar çizerek o kümelerde asal sayı olmayacağı için uğraşmak yerine sade bir ve beş in altında asal yayı kümelerinden sonraki küme başlarını aramaya devam ederiz, Çünkü her asal sayı sonsuz sayılar içinde birer küme başıdır ve artık o sayının katları o sayıya ait küme üyeleri olduğu için sonsuza kadar başka bir asal sayı çıkaramaz.Zaten asal sayıların giderek seyrelmesinin sebebi de budur. En son asal sayıyıya ulaşmak istiyor isek önce her asal sayının bir küma başı olduğunu kabul etmek için yeteri bilgi sahibi olmak gerektir. Bunu deneme yolu ile bulabilirsiniz. Ben matematikçi olmadığım için rakamlar arasında boğulmadan sonsuz sayıların sınırlı sayıda kümelerden oluştuğunu fark etmiş bulunuyorum.
    Nasıl ki sonsuza kadar sayılar sıfırdan on’a kadar sadece on rakamla yazılabiliyor ise, çok yüksek rakamlar ile yazılabilecek sınırlı sayıda asal sayı kümelerinden oluşmaktadır.
    Kutsal kitaplarda Allah kainatı altı günde (altı evrede)yarattı diye geçer. Muharref Tevratta yedinci gün ilave edilip yedinci gün dinlendi anlamında kelimeler geçer.
    Kuranda
    A’râf / 54 Şüphesiz ki Rabbiniz, gökleri ve yeri altı günde yaratan, sonra Arş’a istivâ eden, geceyi, durmadan kendisini kovalayan gündüze bürüyüp örten; güneşi, ayı ve yıldızları emrine boyun eğmiş durumda yaratan Allah’tır. Bilesiniz ki, yaratmak da emretmek de O’na mahsustur. Âlemlerin Rabbi Allah ne yücedir!
    Yûnus / 3 Ayet: Şüphesiz ki Rabbiniz, gökleri ve yeri altı günde yaratan, sonra da işleri yerli yerince idare ederek arşa istiva eden Allah’dır. Onun izni olmadan hiç kimse şefaatçı olamaz. İşte O Rabbiniz Allah’tır. O halde O’na kulluk edin. Hâla düşünmüyor musunuz!
    Kaf suresi 38. ayet: Andolsun biz, gökleri, yeri ve ikisi arasında bulunanları altı günde yarattık. Mumsema Andolsun biz, gökleri, yeri ve ikisi arasında bulunanları altı günde yarattık. Bize hiçbir yorgunluk çökmedi.
    Hadid suresi 4. ayet: O, gökleri ve yeri altı günde yaratan, sonra Arş’ın üzerine istivâ edendir. Mumsema O, gökleri ve yeri altı günde yaratan, sonra Arş’ın üzerine istivâ edendir. Yere gireni ve ondan çıkanı, gökten ineni ve oraya yükseleni bilir. Nerede olsanız, O sizinle beraberdir. Allah yaptıklarınızı görür.
    Furkan suresi 59. ayet: Gökleri, yeri ve ikisinin arasındakileri altı günde yaratan, sonra Arş’a istivâ eden (ona hükmed Mumsema Gökleri, yeri ve ikisinin arasındakileri altı günde yaratan, sonra Arş’a istivâ eden (ona hükmeden) Rahmân’dır. Bunu bir bilene sor.
    Secde suresi 4. ayet: Gökleri, yeri ve bunların arasındakileri altı günde (devirde) yaratan, sonra arşa istivâ eden Allah
    Zaman ve Mekân matematik ve Geometri de denilebilir. Altılık sistem ile genellikle ondalık sistemden daha geçerli oluşunun yaratılış kanunları ile ilgili olduğu düşünülebilir.
    Özet ile Asal sayılar da sınırlı sayıdaki rakamlar ile sonsuz sayıları yazma kabiliyetine sahip ama çok sayıda asal sayı kümelerinden oluşmaktadır.
    Cevap ve ya soru yazmak isteyenler bazı aksamalara uğramasın diye üç mail adresimi birlikte buraya ekliyorum.
    ahmetdogansimsek@hotmail.com,
    ahmetdogan.simsek@yahoo.com,
    ahmetdogan.simsek@gmail.com,
    Selam ve Saygılarımla

  2. Merhaba, bu güzel yazınız için teşekkür ederim.

    Yazınızda x sayısına kadar olan asal sayıların sayısı için “x bölu x in dogal logaritması kadar” yerine ‘x / (x in dogal logaritması)’ ifadesini kullansak acaba daha mı iyi anlaşılırdı. Gauss’un 200 yıllık asal sayılar yaklaşımı oldukça güvenilir sonuçlar veriyor büyük sayılarda ise yüzde 2,9 luk bir sapma olabiliyor bu noktada Reimann yüzde 1’in çok altınada bir sapmayla soruyu cevaplıyor.

    Öte yandan geçtiğimiz yıl 2^74207281 sayısının 1 eksiğinin asal sayı olduğu gösterilmiş bulunuyor. Bu sayı ne kadar büyük bir sayı sorusunun cevabına gelince, bu sayı evrendeki bütün atamların sayısından çok daha büyük bir sayı. Programlama dilleri gibi, programlama dili programlama programları da mevcut. Fonksiyonel programlama yapılıyor bu programlarda, mesela Lisp mesela Scheme.

    200 basamaklı bir sayı olarak mesela 10^199, evet haklısınız 10^199 sayısı evrendeki atom sayısı öngörümüz 4×10^80’den galaktik ölçekte büyüktür. Gauss yaklaşımıyla 200 basamaklı olan 10^199’a kadar olan bütün asal sayıların sayısı yaklaşık 2×10^196 kadardır. Evrendeki bütün atomları bir dizinin hücresi olarak kabul etsek ve hepsini 200 basamaklı olan 10^199 sayısına kadarki bütün asal sayılarımızı tek tek eşleştirmeye kalktığımızı varsayalım şimdi… Evet evrendeki atom sayısı kadar hücreden oluşturduğumuz sanal dizimiz 200 basamaklı ilk sayı olan 10^199 sayısına kadarki bütün asal sayıları almaya yetmedi. Peki şimdi şu soru akla geliyor, bir hücrede ortalama 100trilyon atom varsa ve insan beyni ortalama 90-100milyar hücreden oluşuyorsa, 10^25 atomdan oluşan ama evrendeki bütün atomların 10^(-64)’te birindeki bir dizgileme kapasitede 200 basamaklı sayıların içindeki asalları araştıran insan beyninin a) dizileme yani hafızalama tekniği nasıldır? En basit haliyle bire bir değildir, zaman ve mekan ilişkisini tiye alır şekilde zihnimiz evrenden daima daha büyüktür.

  3. “…200 basamağa kadar olan tüm asal sayıların listesini isterse bunu aklınızdan bile geçirmemelisiniz.” abartmayın o kadar fazla yer tutmuyor. En büyük mersenne sayısı bile kaç basamaklı. 200 basamağa kadar olana sayıları bulup yanyana koysanız bu mersenne asalı kadar basamağa erişemezsiniz. Alt tarafı 200 basamak? İnternetteki tüm verilerin sayısal karşılığı bu kadar etmez yani, öyle mi ? Dikkatli yazın yazıları.

    • 200 basamağa kadar olan tüm asal sayılardan kastı ne anladınız. 4*10^(97) adet sayı ediyor. Evrende 10^80 atom olduğunu düşünürsek gayet de makul bir hesap

  4. programa tıklayınca kaynak kodları gelecek diye bayağı sevinmiştim :) c ile mi yazıldı yoksa farklı bir dil mi kullandınız ? bir de programı siz mi yazdınız ? dönüt alırsam iyi olur… :) açıklama için teşekkürler bu arada yararlı bir yazı olmuş.

  5. Merhabalar, yazının amacı bence harika, bu siteye ve yazınıza rastladığım için gerçekten çok çok memnunum. Emeğiniz ve yazınız için çok teşekkürler. Tek bir konuda maruzatım olacak. Biz mühendisler okullarda dil ve anlatımı çok önemsemediğimizden genelde düşük cümleler kuruyor, anlatım problemleri çekiyoruz ama aslında bu çok büyük eksik. Üslubunda ve dil anlatımında problem olan metinleri okurken anlama güçlüğü çekiyoruz ama bizler pek dikkat edemiyoruz.

    Yazınız aslında sadece mühendislere yönelik olsa da bir takım karmaşık bilgiler içeriyor ve bence dil anlatımınıza biraz daha dikkat etmeniz bu yazıların okunabilirliğini artırır ve daha geniş bir kitleye ulaşır. Bu dostça ve naçizane bir öneriden fazlası değildir, lütfen yanlış algılamayın.

    Tekrar yazınız için çok müteşekkir olduğumu belirteyim, emeğinize sağlık.

  6. Oğuzhan abi bu yıl elektrik elektronik mühendisiligini kazandim ve sizin gibi biriyle meslektaş olduğum için çook gurur duyuyorum yaziniz çok güzel di ben böyle şeylere çook ilgi duyarım ve bunda dolayı bu bölümü seçtim umarım mesajımı okursunuz :)

Düşünceleriniz Nedir?

Lütfen yorumunuzu buraya yazınız.
Lütfen isminizi buraya yazını.