Asallar

[BrainDamage 0]

İşte ben sadece karekök yöntemini kullanalım diyorum 2. program ile 3. program birleşirse her biri öbürünü bekler

[QQyL 0]

Buyrun biraz değişiklik yaptım sınırı kendiniz belirliyorsunuz ve program hangi dizinde çalışıyorsa orada liste.txt adında bir dosya açıp içine asal sayıları alt alta yazıyor. Bu da kaynak kodu:

#include <iostream>
#include <math.h>
#include <stdio.h>
#include <cstdlib>
using namespace std;
int main()
{
FILE* dosya = fopen("liste.txt","w");
char buffer[10] = {0};
if(dosya==NULL){
exit(1);
}
int kok,sinir;
cout<<"Asal sayilarin bulunacagi araligi seciniz: ";
cin>>sinir;
bool bolunme = false;
for(unsigned int d=2 ; d<=sinir ; d++){
bolunme = false;
kok=(int)sqrt(d);
for(unsigned int i=2 ; i<=kok ; i++){
if(d%i == 0){
bolunme=true;
}
if(bolunme) break;
}
if(!bolunme){
cout<<d<<endl;
fwrite(itoa(d,buffer,10),1,sizeof(buffer),dosya);
fwrite("\n",1,1,dosya);
}
}
system("PAUSE");
return 0;
}

Bu da Python versiyonu, öylesine içimden geldi yazayım dedim;

#-*- coding: utf-8 -*-

with open("liste.txt","w") as dosya:
  sinir = int(raw_input("Asal sayilarin bulunacagi araligi seciniz: "))
  for i in range(3,sinir):
     for j in range(2,i):
        if j % 2 == 0:
           dosya.write(j)

Mart 20, 2013 tarihinde QQyL tarafından düzenlendi

[QQyL 0]

Ben git uykulu kafayla kodu yanlış yaz tabi =)

with open("liste.txt","w") as dosya:
   sinir = int(raw_input("Asal sayilarin bulunacagi araligi seciniz: "))
   for i in range(3,sinir):
    bolunme = False
    for j in range(2,i):
	    if i % 2 == 0:
		    bolunme = True
    if bolunme == False:
	    dosya.write("%s\n"%i)

Ama her ne kadar kodum kısa olsa da senin ki her zaman daha hızlı olacaktır

[DreiMalAli 0]

İşte ben sadece karekök yöntemini kullanalım diyorum 2. program ile 3. program birleşirse her biri öbürünü bekler

Yok yok! Biz anlaşamayacağız.

En hızlı yöntem de zaten o iki metodun birleşmesi ile ortaya çıkıyor. Buna 4. metod diyelim.

Senin metot ile 4. metodu süre yönünden karşılaştırmak ister misin?

Mesela 1 000 000 000'a kadar asal sayı listesi yapmak isek... Bilgisayarlar birbirine eşdeğer olsunlar.

4. metod tek bilgisayar ile bu listeyi hazırlasın. Bu bilgisayarın asal sayı listesi hazırlaması için geçen süre T1 olsun.

Senin metod ile, kaç bilgisayar T1 süresinden daha kısa zamanda bu listeyi hazırlayabilir?

Ben; 10 tane bilgisayar yetmez. diye tahmin etsem...

İnanır mısın?

Sevgiler

[BrainDamage 0]

4. yöntem birden çok bilgisayarda kullanmak için uygun değil. Normalde tek bilgisayarda yapabileceğimiz süreden daha fazla sürer. Zaman kaybı olur.

[DreiMalAli 0]

4. yöntem birden çok bilgisayarda kullanmak için uygun değil. Normalde tek bilgisayarda yapabileceğimiz süreden daha fazla sürer. Zaman kaybı olur.

4. yöntem birden çok bilgisayarda kullanmak için uygun değil.

Doğru ve...

4. metodun güzel tarafı da o ya!

Tek bir bilgisayar 10 bilgisayarın yaptığını tek başına ve daha kısa bir sürede yapıyor.

Normalde tek bilgisayarda yapabileceğimiz süreden daha fazla sürer. Zaman kaybı olur.

Hayır!

Durum tersine.

Vaktin olduğunda süreleri hesaplamayı/tahmin etmeyi bir deneyiver.

Sevgiler

[QQyL 0]

İşte ben sadece karekök yöntemini kullanalım diyorum 2. program ile 3. program birleşirse her biri öbürünü bekler

Threadinglere geçmedin sanırım,, Threadingler aynı anda birden fazla iş yapmanı sağlarlar, bu derdi atlatmak için birebir bir modüldür.

Şimdilik multithreading işini görecektir, al bakalım C++ dersi[EN]; http://www.tutorialspoint.com/cplusplus/cpp_multithreading.htm

[DreiMalAli 0]

Threadinglere geçmedin sanırım,, Threadingler aynı anda birden fazla iş yapmanı sağlarlar, bu derdi atlatmak için birebir bir modüldür.

Şimdilik multithreading işini görecektir, al bakalım C++ dersi[EN]; http://www.tutorials...tithreading.htm

Sevgili QQyL.

Threadinlere ben de geçmedim.

Ama benim söylediğimin threadin ile ilgisi yok.

Sadece algoritma ile ilgili.

Algoritmanın birisinde D sayısının kareköküne kadar her tam sayı ile deneme bölmesi yapılıyor. Bu arada tabi fuzuli yere bol bol bölme denemeleri yapılıyor.

Diğer algoritma ise sadece ve sadece D sayısının kareköküne kadar asal saylılarla deneme bölmesi yapıyor. Yani fuzuli bölme denemesi yapılmıyor.

Sevgiler

[BrainDamage 0]

Threadinglere geçmedin sanırım,, Threadingler aynı anda birden fazla iş yapmanı sağlarlar, bu derdi atlatmak için birebir bir modüldür.

Şimdilik multithreading işini görecektir, al bakalım C++ dersi[EN]; http://www.tutorialspoint.com/cplusplus/cpp_multithreading.htm

Threadingleri biliyorum ama bu programda kullanmadım.

[mazdaist 0]

Yok yok! Biz anlaşamayacağız.

En hızlı yöntem de zaten o iki metodun birleşmesi ile ortaya çıkıyor. Buna 4. metod diyelim.

Senin metot ile 4. metodu süre yönünden karşılaştırmak ister misin?

Mesela 1 000 000 000'a kadar asal sayı listesi yapmak isek... Bilgisayarlar birbirine eşdeğer olsunlar.

4. metod tek bilgisayar ile bu listeyi hazırlasın. Bu bilgisayarın asal sayı listesi hazırlaması için geçen süre T1 olsun.

Senin metod ile, kaç bilgisayar T1 süresinden daha kısa zamanda bu listeyi hazırlayabilir?

Ben; 10 tane bilgisayar yetmez. diye tahmin etsem...

İnanır mısın?

Sevgiler

arkadaş neden anlaşamadınız anlayamadım

for(int d=2 ; d<=10000 ; d++){
	 bolunme = false;
	 kok=(int)sqrt(d);
	 for(int i=2 ; i<=kok ; i++){
			 if(d%i == 0){
					 bolunme=true;
			 }
			 if(bolunme) break;
	 }
	 if(!bolunme){
			 cout<<d<<endl;
	 }
}

arkadaş bu kodta bir bilgisayarda bilgisayarda d=2 alırım d<=30000 diyeceğime (burda pc 30000-1 sayı inceleyecek)

1. bilgisayarda d=2 alırım d<=10000 derim (bu pc 10000-1 sayı inceleyecek)

2. bilgisayarda d=10001 alır d<=20000 derim (bu pc 10000-1 sayı inceleyecek)

3.bilgisayarda d=20001 alır d<=30000 der ve işlemi bitiririm diyor (bu pc 10000-1 sayı inceleyecek)

burda işi parçalara ayırıyo ve paylaştırıyoruz kimse kimseyi beklemek zorunda değil herkes işini bitirip yeni bir iş parçası alacak.

ve bir sayıyı sadece bir pc kontrol edecek bir sayı asla iki pc tarafından incelenmeyecek örneğin 13 sayısı sadece 1. pc tarafından incelenir.

biz iç döngüyü yani

for(int i=2 ; i<=kok ; i++){
			 if(d%i == 0){
					 bolunme=true;
			 }
			 if(bolunme) break;
	 }

bunu değiştirmiyoruz.sayılar yine 2 bölünmeye başlanarak test edilecek.

Süreyi test edebiliriz aslında önce bir pcde ilk 30.000 asalın listesinin oluşturma süresi alınacak t1.

ikinci işlem olarak

sonra 1. bilgisayarda ilk 15.000 asalın bulunması (t2)

2. bilgisayarda 15.001 ile 30.000 arasındaki asalların bulunmasının süresi(t3).olarak hesaplanacak

ikinci işlemin toplam süresi t2+t3 değildir. t2 ve t3 ten büyük olanıdır.örneğin 1. bilgisayar 10 saniyede hesaplamış 2. pc 15 saniyede hesaplamışsa ikinci işlemin toplam süresi 15 tir.yani ikinci işlemin süresi max(t2,t3) dir.

şimdi t1<max(t2,t3) ise programımız işe yaramadı zaman tasarrufu sağlamadı demektir.

t1>max(t2,t3) ise programımız zamandan tasarruf sağladır

t1=max(t2,t3) ne kar ne zarar.

ama burda test için önemli olan kullanılan bilgisayarların aynı özelliklerde olmasıdır yoksa test hatalı olur

bende böyle düşünüyorum ama yanlış olabilir.

[DreiMalAli 0]

1. bigisayarın 2 ile 100 (= karekök(10 000)) arası bütün sayılarla döngüyü tekrarlayacak.

2. bigisayarın 2 ile 141 (= karekök(20 000)) arası bütün sayılarla döngüyü tekrarlayacak. Tabi bu arada 1. bilgisayarın zaten yapmış olduğu işlemleri (2 ile 100 sayısı arasındaki sayıları kontrol) fuzuli yere tekrar yapmış olacak.

3. bigisayarın 2 ile 173 (= karekök(30 000)) arası bütün sayılarla döngüyü tekrarlayacak.Tabi bu arada 1. bilgisayarın zaten yapmış olduğu işlemleri (2 ile 100 sayısı arasındaki sayıları kontrol) fuzuli yere tekrar yapmış olacak. Ve yine 2. bilgisayarın zaten yapmış olduğu işlemi (101 ile 141 arası sayıları kontrol) tekrar yapmış olacak.

vs.

Bu örnekler sadece son sayılar içindi. Bu tekrar işlemleri her sayı için tekrar tekrar yapılıyor.

Yukarda bahsettiğim 4. algoritma fuzuli işlem yapmıyor. Kontrol/bölme işlemnini bütün sayılarla değil, sadece ve sadece asal sayılarla yapıyor. Fuzuli işlem yapmıyor. Bu yüzden çok daha hızlı. Özellikle büyük sayılarda yüzlerce bilgisayarın yapacağı asal sayı listesini, tek bilgisayarla ve daha hızlı yapabiliyor.

Kötü tarafı: Algoritmeyı sadece tek bir bilgisayarda uygulayabiliriz. Birden fazla bilgisayara görev dağıtımı yapamayız.

Yok yok!

Biz anlaşamayacağız.

Sevgiler

[BrainDamage 0]

1. bigisayarın 2 ile 100 (= karekök(10 000)) arası bütün sayılarla döngüyü tekrarlayacak.

2. bigisayarın 2 ile 141 (= karekök(20 000)) arası bütün sayılarla döngüyü tekrarlayacak. Tabi bu arada 1. bilgisayarın zaten yapmış olduğu işlemleri (2 ile 100 sayısı arasındaki sayıları kontrol) fuzuli yere tekrar yapmış olacak.

3. bigisayarın 2 ile 173 (= karekök(30 000)) arası bütün sayılarla döngüyü tekrarlayacak.Tabi bu arada 1. bilgisayarın zaten yapmış olduğu işlemleri (2 ile 100 sayısı arasındaki sayıları kontrol) fuzuli yere tekrar yapmış olacak. Ve yine 2. bilgisayarın zaten yapmış olduğu işlemi (101 ile 141 arası sayıları kontrol) tekrar yapmış olacak.

vs.

Bu örnekler sadece son sayılar içindi. Bu tekrar işlemleri her sayı için tekrar tekrar yapılıyor.

Yukarda bahsettiğim 4. algoritma fuzuli işlem yapmıyor. Kontrol/bölme işlemnini bütün sayılarla değil, sadece ve sadece asal sayılarla yapıyor. Fuzuli işlem yapmıyor. Bu yüzden çok daha hızlı. Özellikle büyük sayılarda yüzlerce bilgisayarın yapacağı asal sayı listesini, tek bilgisayarla ve daha hızlı yapabiliyor.

Kötü tarafı: Algoritmeyı sadece tek bir bilgisayarda uygulayabiliriz. Birden fazla bilgisayara görev dağıtımı yapamayız.

Yok yok!

Biz anlaşamayacağız.

Sevgiler

Sadece asalların denendiği algoritmayı denedik DreiMalAli. Test sonuçlarını da yazdım. Kareköküne kadar yapmak daha hızlı.

[BrainDamage 0]

Online çalışan programı bu haftasonu yazabilirim. Ama benim size ip adresimi vermem gerek ayrıca ben sizin ip adresinizi öğrenemem çünkü aktif olarak çalışan bir ADSL modem üzerinden port açarak bağlantı sağlıyorum. Programı boşuna yazmak istemem. Eğer katılmak isterseniz bana özel mesaj yoluyla ulaşabilirsiniz. Ayrıca ateist olmanız ön şartı var. Bu bilim forumunda din konuşmak olarak algılanmasın lütfen. Oluşan dosya benim bilgisayarımda olacağı için bir siteye dosyayı yükleyip buraya linkini atarım. Çok hoş bir çalışma olur. Tekrardan ekliyorum, sizin ip adresinizi öğrenemeyeceğim ama siz benimkini bileceksiniz. Bu yüzden size güvenmem gerek.

[BrainDamage 0]

Çok büyük bir ilerleme kaydettim dostlar. Ama önce boyut ve zaman kavramını açıklamam gerek. Veri için eklenen her bit bize 2 kat daha fazla alan sağlar. Bir bit sadece 1 veya 0'ı gösterebilir. 3 bit 2³'den 8 farklı şekilde durabilirken, 4 bit bunun 2 katı olan 16 farklı şekilde durabilir. Alanımız arttıkça bir bitin yaptığı katkı artar. Sayı tutmak için kullanabileceğimiz en büyük veri tipi unsigned long long int tipidir. Bu tür 8 bayttır. Baştaki unsigned önadı o bayttaki bir bitin sayı tutmak için kullanılmayacağını söyler. Yani normalde bir bitimizi + ve - işaretleri için kullanırız. Ama bizim negatif sayılarla işimiz olmayacağı için - işaretli olarak tutabildiğimiz sayılar yerine daha fazla pozitif sayı tutabiliyoruz. Unsigned long long int tipinin tutabileceği maksimum sayı 2⁶⁴-1'dir. Bu da maksimum 18.446.744.073.709.551.615 sayısını tutabileceğimiz anlamına gelir. Fazla büyük...

Ben programı biraz daha geliştirip yüzde gösterecek hale getirdim. Böylece işlemin ne kadarının bittiği gözüküyor. 1.000.000.000 (1 milyar) 'a kadar olan bütün asal sayıları bulup dosyaya yazdım. Ne yazık ki programı açık bırakıp dışarı çıktığımda bilgisayar kendini beklemeye almış. %32'de durmuş. Ama süre sayımını zaman farkından yararlanarak yaptığım için bu uyku süresi de süreye eklendi. Ama bu vakitlerde program hesaplamıyordu. 305 dakikada işlem bitti. Ama dediğim gibi beklemeseydi daha kısa sürede biterdi. Malesef bir kötü haberim daha var, çıktı 527 MB. Böyle bir dosyayı paylaşmak o kadar da kolay bir iş değil. Sıkıştırıp boyutunu 106 MB'a düşürsem de hala biraz büyük gibi duruyor. Bir şeyi daha saydım, 2 ile 1.000.000.000 arasında 50.847.533 tane asal sayı var.

Evet, şimdi ne yapabiliriz? Öneriniz var mı?

[DreiMalAli 0]

Evet, şimdi ne yapabiliriz? Öneriniz var mı?

Öneri mi?

Var!

Mesela bana bir asal sayı listesi dosyası gönderebilirsin.

Dosyanın büyüklüğü hiç önemli değil. Dosya ne kadar büykse, o kadar makbule geçer.

Atalarımızda kalan bir huy olsa gerek... İşime yaramasa da, ilginç bulduğum şeyleri toplamayı severim.

Sevgili BrainDamage.

Forumda böyle somut işlerle ilgilenen az olur.

Gerçi yaptığın/yaptığımız listeler ne senin bir işine yarar ne de benim. Ama bu önemli değil. Burada önemli olan ve zevk veren bir düşüncenin somut bir olguya döşmesi, elle tutulur, denenir hale gelmesi. Güzel olan tarafı da bu zaten.

Aklıma dosya büyüklüğünü yarıya indirmek için bir öneri geliyor. Ama sonuç pratik olmayacak. Txt dosyaları ASCII kodu kullanıyor. Yani her rakam için bir byte alan harcıyorlar. Bizim işimizde ama 4 bitlik bir alan 0 ile 9 sayıları arasında bütün sayıları kodlamak için yeterli. Listemizdeki sayıları 4 bit ile kodlayıp peşpeşe yazarsak, dosya büyüklüğü yarıya iner.

Bu önerinin kötü tarafı, dosyayı normal bir editor ile açamamamız. Ancak dosyanın sistematiğini anlayan bir yazılım ile listeyi okunur hale getirebiliriz.

Tabi kodlama işlemi de zaman harcayacağından, asal sayı listesi hazırmak biraz daha uzun sürecektir.

Sevgiler

[BrainDamage 0]

DreiMalAli, o halde bir kodlayıcı bir de çözücü program yazıyorum. Listeyi baştan hazırlamamıza gerek yok. Varolan listeyi kodlayacağım. 1 haftaya bitiririm sanırım. Ama bunun ne kadar fayda sağlayacağını bilmiyorum. Çünkü normal ascii kodlamalı dosyayı sıkıştırarak zaten 1/5'e indirdik. Bir sorun daha var. Dosya o kadar büyük ki metin düzenleyici dosyayı açamıyor Kodlama programının içine biraz daha özellik ekleyerek ana dosyayı birden çok parçaya böleceğim. O zaman açılacağından eminim. Çünkü eski denemelerimde dosya boyutu pek de büyük değildi. 100-200 mb civarındalardı, biraz zaman gerekse de açıyorlardı. Hem böyle bir bölüm yaptığımız zaman 4 bit şifreleme daha da avantajlı olur. Çünkü bütün dosyaları aynı anda kodlayabilirim.

Sevgiler.

Haziran 18, 2013 tarihinde BrainDamage tarafından düzenlendi

[DreiMalAli 0]

Sevgili BrainDamage.

txt-dosyası açmak, dosya üzerinde değişiklikler yapmak için Microsoftun editoru uygun değil. DAha doğrusu büyük dosyalar için çok çok kötü bir editor. İnternette daha uygun editorlar bulunur mutlaka.

Tek bir dosya hazırlamak yerine, listeyi küçük dosyalara ayrıştırmak gayet güzel bir fiir.

Bence dosyayı açıp göstermeye de gerek yok. Çözücü programı menü halinde yaparsan daha kullanılışlı olmaz mı?

Kullanım menüsünde kaçıncı asal sayıyı görmek istediğimi belirtebilsem yeter. Tabi bir sonraki asal sayı-bir önceki asal sayı tuşu gibi özelliği de olursa daha pratik olur.

Kodlama konusunda bir önerim daha var.

Asal sayıları kayıt etmek yerine, asal sayılar arasındanki farkı kaydedersek de dosyanın büyüklüğünü azaltmış oluruz.

Söylemek istediğim şu.

1. asal sayıyı (=2) kaydediyoruz.

2. asal sayı olan 3'ü kaydetmiyoruz ikisi arasındaki farkı, yani 1'i (=3 - 2) kaydediyoruz.

3. asal sayı olan 5'i kaydetmiyoruz ikisi arasındaki farkı, yani 2'yi (=5 - 3) kaydediyoruz.

4. asal sayı olan 7'yi kaydetmiyoruz ikisi arasındaki farkı, yani 2'yi (=7 - 5) kaydediyoruz.

vs.

Bu algoritma da epeyce bellek tasarrufu yapar.

Çözücü program ise bu fark kayıtlarından istediğimiz asall sayıyı hesaplayıp gösterir.

Tabi bu fark sayılarının rakamlarını da 4 bit ile kodlayabiliriz.

Sevgiler

[garlic 0]

1 den 100 e kadar olan tamsayıların OKEK(Ortak Katların En Küçüğü) ini nasıl bulabiliriz?

[BrainDamage 0]

Sevgili BrainDamage.

txt-dosyası açmak, dosya üzerinde değişiklikler yapmak için Microsoftun editoru uygun değil. DAha doğrusu büyük dosyalar için çok çok kötü bir editor. İnternette daha uygun editorlar bulunur mutlaka.

Tek bir dosya hazırlamak yerine, listeyi küçük dosyalara ayrıştırmak gayet güzel bir fiir.

Bence dosyayı açıp göstermeye de gerek yok. Çözücü programı menü halinde yaparsan daha kullanılışlı olmaz mı?

Kullanım menüsünde kaçıncı asal sayıyı görmek istediğimi belirtebilsem yeter. Tabi bir sonraki asal sayı-bir önceki asal sayı tuşu gibi özelliği de olursa daha pratik olur.

Kodlama konusunda bir önerim daha var.

Asal sayıları kayıt etmek yerine, asal sayılar arasındanki farkı kaydedersek de dosyanın büyüklüğünü azaltmış oluruz.

Söylemek istediğim şu.

1. asal sayıyı (=2) kaydediyoruz.

2. asal sayı olan 3'ü kaydetmiyoruz ikisi arasındaki farkı, yani 1'i (=3 - 2) kaydediyoruz.

3. asal sayı olan 5'i kaydetmiyoruz ikisi arasındaki farkı, yani 2'yi (=5 - 3) kaydediyoruz.

4. asal sayı olan 7'yi kaydetmiyoruz ikisi arasındaki farkı, yani 2'yi (=7 - 5) kaydediyoruz.

vs.

Bu algoritma da epeyce bellek tasarrufu yapar.

Çözücü program ise bu fark kayıtlarından istediğimiz asall sayıyı hesaplayıp gösterir.

Tabi bu fark sayılarının rakamlarını da 4 bit ile kodlayabiliriz.

Sevgiler

Çok güzel bir fikir. Hesabıma göre 50 MB'dan aşağı olur liste. Bir deneyeyim bunu da. Ben de 4 bitten farklı bir çözüm bulmuştum. Hem asal sayı hesaplarken de zaman tasarrufu sağlıyordu. Integer 4 milyara kadar olan asal sayıları tutabiliyor. Sanırım bu konuda önceki mesajlarımdan birinde yanlış bir ifade söyledim. Integer 4 bayttır. Yani bütün asal sayılarımızı tutabilir. Biz ise dosyaya yazarken bunu karakter dizilerine çeviririz. Yani 1.000.000.000 sayısını dosyaya yazarken 11 bayt kullanırız(10 basamaklı ve eklediğimiz satır sonu bilgisi yani 10 numaralı karakter. Bunu koymazsak bir liste halinde değil iç içe geçmiş aralıksız sayılar halinde bir dosyamız olur.) Ama bu sayıyı integer olarak yazarsak sadece 4 bayt kullanırız. Yani 7 bayt kazanç. Ama sizin yönteminiz daha iyi. Onu bir deneyeyim. Hem dosyayı da bölerim.

[BrainDamage 0]

Programlar hazır, malesef üyeliğimi sildiriyorum. Sizlere bir şekilde ulaşıp göndereceğim.