Liczby pierwsze nie są rozłożone losowo?

[Jajcenty 314]

Mój naiwny algorytm w wersji czterowątkowej zszedł do 7 sekund na liczbę pierwszą. Słabo, ale zdecydowanie lepiej od początkowych 54 sekund. Postanowiłem sprawdzić jak daje radę sobie sito użyte przez Autorów. Wersja okienkowa pod windowsem bardzo słabo. W lini komend nie próbowałem, ale pod linuksem rewelacja,  ze 100 razy szybciej:

~/tmp/primesieve-5.6.0$ time ./primesieve 18446744020759878656 18446744030759878656 --print > primes.txt

real    1m19.901s
user    1m4.672s
sys     0m4.512s
~/tmp/primesieve-5.6.0$ cat primes.txt | wc -l
225429480

 

Windows I5-5300U, Linuks: AMD Phenom II 1090T

 

 

potrzebowałem użyć kompa a pamieć mi prawie całą z żarło.

Proponuję wynająć. U MSa maszyna A11 16 rdzeni 112 GB RAM kosztuje $2,5 na godzinę. To chyba niedużo biorąc pod uwagę spodziewany przychód. Największa dostępna to chyba 32 rdzenie +448 GB RAM za $11/godzinę. Ceny bez VAT jak sądzę. Taniej będzie zestawić własną farmę GPU

Edytowane 25 marca 2016 przez Jajcenty

[Afordancja 57]

 

 

Mój naiwny algorytm w wersji czterowątkowej zszedł do 7 sekund na liczbę pierwszą. Słabo, ale zdecydowanie lepiej od początkowych 54 sekund.

 

Patrząc na progres to i tak nieźle. Bez zwiększenia zapotrzebowania raczej już nic nie wydolisz (ja w mojej aktualnej wersji jakoś potrzebuję 2-3 GB a i tak zapisuje to w bitach, a tej którą mam nadzieję dziś skończę już 3-4 GB), no chyba, ze jeszcze "magicznymi" matematycznymi sztuczkami, ale dla mnie to już naprawdę bliżej magii

 

 

 

Postanowiłem sprawdzić jak daje radę sobie sito użyte przez Autorów.

 

A dałbyś radę streścić jak to działa? (wiem, wiem, jestem leniem ) (jak masz kod to bym tez zerknął)

 

 

 

W lini komend nie próbowałem, ale pod linuksem rewelacja,  ze 100 razy szybciej

hm..dalej mi się wydaje to jakieś słabe. Z chęcią  sprawdził bym ile by na moim kompie działalo (windows).

 

 

 

Proponuję wynająć. U MSa maszyna A11 16 rdzeni 112 GB RAM kosztuje $2,5 na godzinę. To chyba niedużo biorąc pod uwagę spodziewany przychód. Największa dostępna to chyba 32 rdzenie +448 GB RAM za $11/godzinę. Ceny bez VAT jak sądzę. Taniej będzie zestawić własną farmę GPU

 

haha, coi to spodziewanego przychodu to jest on z pewnym prawdopodobieństwem, i obawiam się, ze mniejszym niż 2,5 na 100 tys.  

(prawdę mówiąc spodziewałem się, że że jak odpalę test na pierwszość "mojej liczby" to szybko stwierdzi, że nie jest pierwszą, a tu doba i nic (Ale nieświadomy dałem parametr 2->75% gwarancji, a mogę dać 1 z 50% prawdopodobieństwem, ale za to 2 razy szybciej).

 

Ale jak patrzę na ceny to całkiem nieźle. wiesz jak to wygląda, to jakiś linkuks jest tak? I mogę sobie na godzinkę nawet wynająć? 

(mam alternatywę, jak kolega skonfiguruje klaster z 48 kompów, i za prąd tylko, ale to niewiele taniej wychodzi, tylko rdzeni więcej )

 

 Kurczę, może i tak zrobię dla samej ciekawości, tylko najgorsze, że nie wiem ille godzin no bo ile razy to możę być szybsze niż mój komputerek. (Ta za 2,5 $ za h), 20?

[Jajcenty 314]

 

 

A dałbyś radę streścić jak to działa? (wiem, wiem, jestem leniem ) (jak masz kod to bym tez zerknął)

Jesteś zerkaj: http://primesieve.org/segmented_sieve.html

 

Segmented sieve of Eratosthenes

Further down is a simple C++ implementation of the segmented sieve of Eratosthenes that generates the primes below n using O(nloglogn)   operations and O(sqrt(n)) space. It runs significantly faster than a traditional sieve of Eratosthenes implementation due to its more efficient CPU cache usage i.e. it uses the CPU's L1 data cache size as its sieve array size. This ensures that less than 1 percent of the memory accesses will be cache misses. This implementation generates the primes below 10^9 in just 0.9 seconds (single-threaded) on an Intel Core i7-4770 3.4GHz CPU from 2013.

 

 

 

 

hm..dalej mi się wydaje to jakieś słabe.

Grzeszysz. O ile mi wiadomo nikt tu z nas nie zbliżył się do 2x10⁸ w 81 sekund. 225 milionów pierwszych ulongów w 81 sekund włączając w to zapis 4 GB na dysk

Ale jeśli myślisz o naprawdę dużych liczbach to chyba nie tędy droga.

 

 

Ale jak patrzę na ceny to całkiem nieźle. wiesz jak to wygląda, to jakiś linkuks jest tak? I mogę sobie na godzinkę nawet wynająć?

MS oferuje w ramach próby 150 euro na 30 dni do dowolnego rozdysponowania. Tylko brać i stawiać Vmy. Do dyspozycji jest cała kupa różnych Osów - windows server, ubuntu, W10, mnogość wyboru.

CO szybkości - rdzenie są wirtualne i nie są badzo szybkie. Nie wiem czy to aktualna wiedza ale chyba są standaryzowane jako 1.8 GHz. Dla maszyn wyższej klasy jest infomacja:

 

2.4 GHz Intel Xeon® E5-2673 v3 (Haswell) processor, and with Intel Turbo Boost Technology 2.0 can go to 3.2 GHz. 

Polecam, fajna zabawa a nie musisz zapłacić ani grosza. W moim przypadku się im opłaciło bo tak się podnieciłem, że zmolestowałem szefa i wydzielił trochę kasy na chmurę

[Afordancja 57]

 

 

Grzeszysz. O ile mi wiadomo nikt tu z nas nie zbliżył się do 2x108 w 81 sekund. 225 milionów pierwszych ulongów w 81 sekund włączając w to zapis 4 GB na dysk Ale jeśli myślisz o naprawdę dużych liczbach to chyba nie tędy droga.

 

właśnie odpaliłem zwykłe moje sito bez żadnych udziwnień (dla wyższych liczb liczy minimalnie inaczej, ale tak samo).

i pierwsze 234 954 223 liczb pierwszych (niestety bez zapisu) zajeło mi 92 sekundy (w javie), czyli dla 225 milionów wychodzi mi 88 sekund, dalej utrzymuję, że ich wynik D. nie urywa zwłaszcza, że niczego nie wiadomo czego nie zastosowałem, a do matematyków mi daleko,.

 

 

 

Polecam, fajna zabawa a nie musisz zapłacić ani grosza. W moim przypadku się im opłaciło bo tak się podnieciłem, że zmolestowałem szefa i wydzielił trochę kasy na chmurę

 

hm..a zerknę (wieczorem). Dzięki za te informacjie 

[Jajcenty 314]

i pierwsze 234 954 223 liczb pierwszych (niestety bez zapisu) zajeło mi 92 sekundy (w javie), czyli dla 225 milionów wychodzi mi 88 sekund,

No to się pochwal kodem? Bo moje zwykłe sito Eratostenesa bez większych  udziwnień potrzebuje na to 52 lata 

Czyli Twoje nie jest takie znowu zwykłe.

Edytowane 26 marca 2016 przez Jajcenty

[Afordancja 57]

ależ to naprawdę zwykłe sito (dla większych liczb niestety samego sita się nie da ze względu na pamięć).

package liczbypierwszev2;
 
/**
 *
 * @author Afordancja
 */
public class Sito {
 
    //public static final long maksLiczaP_table = Integer.MAX_VALUE;
    //public static final long maksLiczaP_table = 6469693230L;
    public final long maksLiczaP_table = 1000000000L * 5;
    
    MyBitSet bs;
 
    public Sito() {
        //       long ileBs = maksLiczaP_table / wielkoscPaczkiBitow + 1;
 
        System.out.println("SITO:inicjalizuje bity.....");
        this.bs = new MyBitSet(maksLiczaP_table);
 
        System.out.println("SITO:wypelnienie bitow...");
        this.bs.setAll();
        this.bs.setBit(0, false);
        this.bs.setBit(1, false);
        
        System.out.println("SITO start...");
        this.sito(2);
        int doilu = (int) Math.sqrt(maksLiczaP_table);
        int licznik = 0;
        for (long i = 3; i <= doilu; i += 2) {
            licznik++;
            if (licznik % 1000 == 0) {
                System.out.println("procent:" + (i * 1.0 / doilu * 100));
            }
            this.sito(i);
        }
        System.out.println("SITO ---->koniec");
        int liczbapierwszych = 0;
/**
        
        
        for (long i = 0; i < maksLiczaP_table; i++) {
            if (this.bs.getBit(i)) {
                liczbapierwszych++;
            }
        }
*/
//ulepszone szybsze liczenie
        liczbapierwszych = (int) this.bs.countSetBits();
        System.out.println("SITO liczba pierwszych:" + liczbapierwszych);
 
    }
 
    private void sito(long dzielnik) {
        if (!this.bs.getBit(dzielnik)) {
            return;//nie jest liczba pierwsza
        }
        long start = dzielnik + dzielnik;
        for (long i = start; i < maksLiczaP_table; i += dzielnik) {
            this.bs.setBit(i, false);
        }
    }
 
    private void status(){
        String wy = "";
        for(int i=0;i<100;i++){
            if (this.bs.getBit(i)){
                wy = wy +"1";
            }else{
                wy = wy + "0";
            }
        }
        System.out.println(wy);
    }
}
 

MyBitSet to ulepszona trochę przeze mnie (pod te zadanie) klasa BItSet (czyli trzymająca bity w longach).

 

Jak skończę szybszą wersję dla wielkich liczb to będzie co wrzucić

 

Z ulepszonym liczeniem bitów (ale to już tyllko do liczenia pierwszych liczy) to nawet 82 sekundy dla 225 mln liczb pierwszych 

Edytowane 26 marca 2016 przez Afordancja

[Afordancja 57]

No i zamiast ulepszać liczenie liczb pierwszych, wkręciłem się w zrobienie testu pierwszości mojej "wymyślonej" liczby, i rzeczywistość mnie zmiażdżyła.

 

1. Java ma swój test isPrime, który po dobie wyłączyłem

2. Napisałem (przepisałem) swój isPrime aby widzieć gdzie jest wolno...

3. kod satnąl na powMod (java ma wbudowany) muszę taki modPow wykonać tylko jeden, ale za to na olbrzymich liczbach.

4. Napisałem (przepisałem)  swoj modPow, był 3 razy szybszy na dość dużych liczbach od orginalnego.

5. Odpaliłem dla mojej "Wymyślonej" liczby. kod stanął na i teraz uwaga.... (x*x) mod m.

6. rozbiłem to na x= x*x  i x = x mod m. (nawet na x = (x mod m )^2  -> x = x mod m) i stanęło uwaga na...

x*x

a x*x już raczej nie zoptymalizuję

 

co ciekawe dla "trochę" mniejszych (czyli 90 milionów rzędów wielkości mniejszych), algorytm leci(chyba chodzi o pamięć, bo nic innego nie może być), ale prędkość wiele mówi.

aby policzyć ten  modPow, muszę wykonać 33 milionów cykli, a jeden cykl trwa...blisko minutę tzn. na pewno będą coraz szybsze, może nawet potem bardzo szybkie, ale jakoś wychodzi to raczej w latach, (no chyba, że potem naprawdę nagle liczby się zmniejszą w co wąpię, i już będzie wykonywało się szybko, ale sprawdzać nie będę)

 

Jako, że ten algorytm jest raczej jednym z najszybszych znanych, może jak by był taki który by zwracał isPrimary ze znacznie mniejszym prawdopodobieństwem (tutaj 50% na jeden przebieg) ale za to szybszy był, dało by się szybciej wykluczać liczby, ale takich nie widziałem.

Jako, zostaje technika którą stosował Jajcenty, ale ona jest zdecydowanie za wolna, a moja technika raczej się do tego nie nadaje, a swojego testu pierwszości  raczej nie stworzę bo za cienki jestem (chociaż chodzi mi coś po głowie, ale też słabe), temat testu na pierwszość mojej liczby uważam za zamknięty (100 tys. USD jest całkowicie po za zasięgiem zwykłego komputerka haha, a w GPU to nawet nie wiem jak bym to miał policzyć, ale i tak za wolne).

(jeszcze poszukam czy jest jakiś trik na policzenie, (2^dużo) mod m . No bo mówią losuj liczbę, z przedziału dużego, a może przecież mi się wylosować "2" .

[ex nihilo 214]

czyli 90 milionów rzędów wielkości mniejszych

 

Dla zabawy policzyłem sobie ilość "zdarzeń", czyli czterowymiarowych punktów czasoprzestrzeni obserwowalnego Wszechświata, od walnięcia do teraz. Liczyłem w jednostkach Plancka... wyszło ~10¹⁴⁴ sztuk.

Może gdzieś się walnąłem przy wklepywaniu danych do kalkulatora, ale jakie to ma znaczenie przy tych 90 milionach rzędów wielkości między trochę mniejszymi a trochę większymi liczbami Afordancji :D

A tak przy okazji jak już o trochę większych liczbach... - może ktoś by sprawdził, czy przypadkiem liczba Grahama +1 lub -1 jest liczbą pierwszą. Jest chętny? Bo mój kalkulator chyba się nie wyrobi

Albo... załóżmy, że każde zdarzenie z tych 10¹⁴⁴ sztuk może mieć n stanów (odpowiedników stanów pozycji w zapisie pozycyjnym) i potrafimy tak uporządkować zdarzenia, żeby wyszedł z tego n-kowy zapis pozycyjny liczby Grahama. Jakie by musiało być to "n"?

No i tak z rozpędu, jak ktoś sobie już z tym poradzi, to może jeszcze dla relaksu trochę kombinatoryki - mamy te 10¹⁴⁴ sztuk 4D punktów. Łączymy każdy z każdym. Ile takich wszechświatów by trzeba zużyć, coby ilość połączeń była większa od liczby Grahama.

To ostatnie może by nawet dało się jakoś policzyć.

Edytowane 28 marca 2016 przez ex nihilo

[glaude 40]

Ale tan Graham zdolny. I pieczywo zdrowe wymyślił, i liczbę

 

Wszystkie wpisy tego tematu uświadamiają mi, ze matematycznie jestem na poziomie szkoły podstawowej. I bynajmniej wcale nie świadczy to o wysokim poziomie podstawy programowej polskich podstawówek

[Afordancja 57]

ale jakie to ma znaczenie przy tych 90 milionach rzędów wielkości między trochę mniejszymi a trochę większymi liczbami Afordancji

haha, no deraz dopiero sobie uświadomiłem, że to dość duże liczby , no ale na szczęście nie trzeba tyle razy więcej obliczeń wykonać.

 

 

 

Bo mój kalkulator chyba się nie wyrobi

 

U mnie gorzej, mózg nie wyrobił.

 

 

 

No i tak z rozpędu, jak ktoś sobie już z tym poradzi, to może jeszcze dla relaksu trochę kombinatoryki - mamy te 10144 sztuk 4D punktów. Łączymy każdy z każdym. Ile takich wszechświatów by trzeba zużyć, coby ilość połączeń była większa od liczby Grahama.

 

Też wygląda na policzalne, ale mam już limit wyzwań na ten rok  (tzn. jak bym się podjął tego to bym wyczerpał cały limit wyzwań i to nie tylko na ten rok )

Edytowane 28 marca 2016 przez Afordancja

[Gość Astro]

 

 

tzn. jak bym się podjął tego to bym wyczerpał cały limit wyzwań

 

Z pokorą wyznaję, że myliłem się w przekonaniu, iż MacLeod to Jajcenty…

[Afordancja 57]

I w tym momencie kończy się moja przygoda w szybkim szukaniu liczb pierwszych.

 

 

 

Grzeszysz. O ile mi wiadomo nikt tu z nas nie zbliżył się do 2x108 w 81 sekund. 225 milionów pierwszych ulongów w 81 sekund włączając w to zapis 4 GB na dysk

 

 

Podsumowując.

Mój wynik prawie 1,9 mld liczb pierwszych. w czasie 8:55, w przeliczeniu na 225 milionów wychodzi 64 sekundy.

Dlatego tak dużo liczb pierwszych policzyłem, bo mam duży pewien narzut startowy, (a z drugiej strony im większe szukane liczby tym wolniej idzie), więc musiałem trochę bardziej korzystny dla mnie zakres wybrać (ale oni by zwolnili na takim zakresie).

 

Z sprawdzanie pierwszości się nie będę bawił, za cienkie uszy, komputer, wszechświat .

 

Wiemy już, że teoria z treści artykułu o 30% i jedynce, jest słaba i przy wysokich liczbach wychodzi po prostu klasycznie w granicach 25%, więc ten procent jest niczego dowodem.

 

Już straciłem wystarczającą ilość czasu na liczby pierwsze, (chociaż bawiłem się nieźle, ale życie to nie tylko zabawa), wiec na ich zapis w innych systemach zerknę tylko pobieżnie. 

[Jajcenty 314]

 

 

Już straciłem wystarczającą ilość czasu na liczby pierwsze, (chociaż bawiłem się nieźle, ale życie to nie tylko zabawa), wiec na ich zapis w innych systemach zerknę tylko pobieżnie.

Niestety, ze względu na rodzinny charakter świąt i wiele innych czynników, przełomowe odkrycia w numerologii liczb pierwszych będą musiały trochę poczekać.

Spróbuję uruchomić Twój algorytm z użyciem BitArray, ale będzie problem: w tej klasie wskaźnik jest Int32, więc pewnie skończy się na własnej implementacji.

W każdy razie na dysku leży i czeka na analizę dwieście milionów liczb pierwszych i mam kilka pomysłów żeby się nie zmarnowały. Myślę, że spróbuję się zaprzyjaźnić z R albo S. A może ktoś z tutejszych poleci dobry, warty poznania pakiet statystyczny open source?

 

 

 

Mój wynik prawie 1,9 mld liczb pierwszych. w czasie 8:55, w przeliczeniu na 225 milionów wychodzi 64 sekundy.

Jako facet mam duży problem z wyrażaniem emocji zatem pozostaje mi tylko powiedzieć: Szacun!

 

 

 

I bynajmniej wcale nie świadczy to o wysokim poziomie podstawy programowej polskich podstawówek

 

Pewnie się tu wszystkim narażę, ale sądzę że za wcześnie uczymy matematyki. Wydaje (mi) się jakby mózg dojrzewał do matematyki w okolicy 12-14 lat.

Wcześniej tylko niepotrzebnie męczymy i zniechęcamy dzieciaki.

[Afordancja 57]

 

 

Spróbuję uruchomić Twój algorytm z użyciem BitArray, ale będzie problem: w tej klasie wskaźnik jest Int32, więc pewnie skończy się na własnej implementacji.

Dlatego właśnie musiałem napisać swój, aż dziwi mnie, że nie napisali wersji dla longów.

 

 

 

Myślę, że spróbuję się zaprzyjaźnić z R albo S. A może ktoś z tutejszych poleci dobry, warty poznania pakiet statystyczny open source?

Przyłączam się do zapytania

Wiem, że wszyscy to R, ale jak patrzę na tę składnię tam to mam duży opór, no ale jak wyjdzie, że najlepszy to trzeba będzie się zaprzyjaźnić (kiedyś)

 

 

 

W każdy razie na dysku leży i czeka na analizę dwieście milionów liczb pierwszych i mam kilka pomysłów żeby się nie zmarnowały.

 

To proponuję jeszcze przyspieszenie które ja dodałem, mam BitArray o rozmiarze (2*3*5*7...*29), którą potem mam w zanadrzu, i nie muszę, już tych liczb "cedzić" przez sito., tylko ważne aby robocze "okienko" miało taki sam rozmiar i tym się przesówamy po kolejnych zakresach. 

[Afordancja 57]

ok,  wyszła D, usunąłem, napiszę jeszcze raz jutro)

Moja teoria V 0.3 .(która jest już pewnie wymyślona z ładną nazwą i dobrym opisem/dowodem).

 

Mamy dwie kolejne liczby pierwsze X, Y

 

Dla liczby X

Mamy

X mod 3 = a3

X mod 5 = a5

X mod 7 = a7

...

X mod n = an

dla kolejnych liczb pierwszych.

 

dla liczby Y mamy analogicznie

Y mod 3 = b3

Y mod 5 = b5

Y mod 7 = b7

...

Y mod n = bn

 

To prawdopodobieństwo, że ac = bc (Gdzie c = 3,5,7..n), jest znacznie mniejsze niż, że będą to inne kombinacje(dla 3..7 jakoś 30-krotnie niższe) .

przy czym, ac (gdzie c= 3,5,7,n), ma równy rozkład dla dowolnej liczby pierwszej X.

 

hm..nie wygląda to za dobrze, muszę to jakoś "skompresować" i zmieścić w 2,3 linijkach. 

 

Inaczej to można zapisać

(Y - X ) mod Z = 0 (Gdzie Z = 3*5*7*...n) jest znacznie mniej prawdopodobne niż.. (nie wiem co bo nie wiem jak zapisać pozostałe przypadki )

Na razie niech tak zostanie.

 

 

[edit]

Humanistycznie.

Jeżeli dowolną liczbę pierwsza X zapiszemy w systemach trójkowym, piątkowym, siódemkowym itd.

To jeżeli weźmiemy ostatnia cyfrę tej liczby w dowolnym systemie,  i zrobimy to samo dla liczby Y (kolejnej pierwszej) to te liczby będą częściej różne niż wynikało by to z prawdopodobieństwa.

Edytowane 31 marca 2016 przez Afordancja

[ex nihilo 214]

Tak do łba mi przyszło, że może warto by było, cobyś te swoje wyniki z "Napisano 20 marzec 2016 - 00:25" jakoś ładnie spakował i wysłał tam, gdzie "oni". Zaszkodzić nie zaszkodzi, a radocha może być, kto wie

[Jajcenty 314]

aktualizacja. Przyglądałem się ostatnim cyfrom liczb pierwszych (zbiór 2,25e8 liczb). Na pierwszy rzut oka jest doskonały:

średnia: 4,9999269217, oczekiwana 5( (1+3+7+9)/4)

 

Poszczególne cyfry też są rozłożone gładko, częstość:

[1] = 0.25000020405494439

[3] = 0.25002591941391161

[7] = 0.24995796468146048

[9] = 0.25001591184968353

 

Ale potem się robi ciekawie. Pary kolejnych cyfr nie są już tak gładkie. 

Oczekiwana częstość 0,0625. Widać że pary 11, 33, 77, 99 zdarzają się rzadziej.

11 : 0,053540508543958 

13 : 0,0621859660945853

17 : 0,0631844867849582

19 : 0,0710892426314429

31 : 0,0685747223477604

33 : 0,0532431117704747

37 : 0,064996929416685

39 : 0,0632111558789915

71 : 0,0681128484171635

73 : 0,0664837535889272

77 : 0,0531879326519318

79 : 0,0621734300234379

91 : 0,0597721247460625

93 : 0,0681130879599243

97 : 0,0685886113919085

99 : 0,0535420833158112

 

Podobne regularne nieregularności widać w zbiorze trójek. Na moje oko w tym białym szumie coś dudni. Może jeszcze kiedyś znajdę czas by formalnie przetestować hipotezy o średniej. Ale już teraz wydaje się że potraktowanie liczb pierwszych jak szeregu czasowego z autokorelacją może dać ciekawe wyniki. Fourier też pewnie mógłby pokazać jakieś tętno Wszechświata

[thikim 117]

Jajcenty - sprawdź losowość dla trzech ostatnich cyfr

A jak chcesz jeszcze większe nieregularności to w zbiorze czterech cyfr - i nie pytaj mnie czemu są większe

Każda kolejna cyfra zmniejsza losowość pi razy drzwi 10-krotnie.

Edytowane 17 kwietnia 2016 przez thikim

[thikim 117]

2016.07.28

dziś dopiero znalazłem czas i chęci

napisałem sobie algorytm z głowy na zasadzie sita. Ale w wersji okienkowej na laptopie.

Wyszło mi 10 mln liczb pierwszych w 90 s.

No to szybko przerobiłem na wersję konsolową. Tyle samo liczb ale w 91 s

Szału nie ma. Ale ja nie programuje tylko czasem hobbistycznie koduje

No i wielki ból bo dla 1 mln to były 3 s. A więc nakład czasu wzrósł 3 razy bardziej niż wzrasta ilość liczb.

Przy takim założeniu to przy 100 mln miałbym 2700 s a więc 45 minut

Po zastosowaniu pierwiastkowania zjechało z 90 s do 80 s

Wywaliłem deklarację inta poza główną petlę. Czas bez zmian. 80 s.

Wywaliłem konwersję double to int z pętli na zewnątrz. Czas wzrósł do 86 sekund

Przerzucenie warunku wyjścia w postaci if + break do warunków fora poprawiło wynik o 0.5 s Czyli w granicach błędu.

Zmiana typu głównych zmiennych z int na uint dała czas 100 s a więc zmianę cofamy.

Wersja Release - 67 sekund

Edytowane 28 lipca 2016 przez thikim

[Stanley 15]

Odkryłem na kartce coś ciekawego? 

Jeśli zamiast sitowania w BitArray oznaczając kolejne wielokrotności kolejnych liczb jako nie pierwsze = 1, wypiszesz w tabeli kolejno wartość pierwiastka bez części ułamkowej floor(sqrt(liczba)) to w jednym przebiegu powstanie:

 

01 1

02 1

03 1

04 2

05 2

06 2

07 2

08 2

09 3

10 3

11 3

12 3

13 3

14 3

15 3

16 4

17 4

18 4

19 4

20 4

21 4

22 4

23 4

24 4

25 5

26 5

27 5

28 5

29 5

30 5

31 5

32 5

33 5

34 5

35 5

36 6

37 6

38 6

39 6

40 6

41 6

42 6

43 6

44 6

45 6

46 6

47 6

48 6

49 7... itd.

 

Zliczając wystąpienia kolejnych powtarzających się wartości tj. 1,2,3,4,5,6, liczba wystąpień będzię kolejną liczbą pierwszą tj. 3,5,7,9*,11,13 itd. z wyjątkiem wystąpień 4. Przypomniało mi się po Twoim poście thikim co te kilka miesięcy temu proponowałem  - aby jako usprawnienie funkcję obliczającą pierwiastek zastąpić tabelą lookup.. Problem pierwiastka w sumie nadal istnieje, ale chyba wyszła metoda na wydrukowanie listy pierwszych z użyciem tylko i wyłącznie pierwiastka i pominięcia części ułamkowej? Podejrzewam że podobnie będzie dla pierwiastka = 9 tak że ilość wystąpień nie będzie liczbą pierwszą bo liczba 9 ma pierwiastek bez części ułamkowej tak jak dla 4... Idę o zakład że podobnie będzie dla 16,25,36 itd. ale zliczając wystąpienia pozostałych, te ilości będą liczbą pierwszą?

Edytowane 28 lipca 2016 przez Stanley

[pogo 102]

A ja stawiam, że jak pójdziesz dalej to będziesz miał wystąpienia: 15, 17, 19, 21, 23, 25... Zwyczajnie liczby nieparzyste.

Nie chce mi się sprawdzać, ale chyba tak to wychodziło.
To raczej może być uproszczenie by nie liczyć pierwiastków za każdym razem.

[thikim 117]

To raczej może być uproszczenie by nie liczyć pierwiastków za każdym razem.

Pierwiastka używam żeby nie sprawdzać w sicie całego zakresu. Wcześniej podnosiłem do kwadratu liczbę pierwszą z tablicy. Ale pierwiastek okazał się wydajniejszy niż dwukrotne sięgnięcie do tablicy.

Chociaż pewnie to już rozczailiście wcześniej

To był laptop wieczorem uruchamiam na prawdziwym kompie

Ogólnie zrobię jeszcze co innego.

Zrobię tablicę tylko z liczbami pierwszymi do 100. I porównam jak się ma gęstość przy różnego rodzaju tablicach, ergo uzyskam jaka jest zależność jakości liczb pierwszych w zależności od sita.

Być może daje to wielką oszczędność obliczeniową przy dużej szansie na liczbę pierwszą

Ale to później.

Edytowane 28 lipca 2016 przez thikim

[Gość Astro]

Tu chyba jakiejś fortecy nie zdobywamy. Wystarczy ołówek i bibułka na skręta.

(n+1)² - n² = 2n + 1

czyli 3, 5, 7, 9, 11, 13, …

[thikim 117]

Hmm, pewnie masz rację ale na razie podążę tropem pierwszym. A potem sprawdzę wydajnościowo i Twój sposób, jak się czymś innym nie zajmę

W domu zszedłem z 67 do 43 sekund dla wersji Release.

 

 

Przypomniało mi się po Twoim poście thikim co te kilka miesięcy temu proponowałem - aby jako usprawnienie funkcję obliczającą pierwiastek zastąpić tabelą lookup.. Problem pierwiastka w sumie nadal istnieje

Przegapiłem a pomysł ciekawy.

           
            DateTime startTime = DateTime.Now;
            int iloscliczbpierwszych = 10000000;
            int[] tablicaliczbpierwszych = new int[iloscliczbpierwszych];

            tablicaliczbpierwszych[0] = 3;
            int licznikliczb = 1;
            int pierwiastekliczby;

            for ( int liczba = 3; licznikliczb < iloscliczbpierwszych; liczba =liczba+2)//generuje liczby do sprawdzenia
            {
                bool czypodzielna = false;
                pierwiastekliczby = (int) Math.Sqrt(liczba);
                for ( int licznik = 0; pierwiastekliczby > tablicaliczbpierwszych[licznik]; licznik++) //sprawdza podzielność przez liczby pierwsze już wygenerowane
                {
                    if (liczba % tablicaliczbpierwszych[licznik] == 0)
                    {
                        czypodzielna = true;
                        break;
                    }
                }
                if (!czypodzielna)
                {
                    tablicaliczbpierwszych[licznikliczb] = liczba;
                    licznikliczb++;
                }
            }
            textBox1.AppendText(licznikliczb.ToString() + "  -  " +tablicaliczbpierwszych[licznikliczb-1].ToString() + "\n");
            DateTime stopTime = DateTime.Now;
            TimeSpan roznica = stopTime - startTime;
            textBox1.AppendText("\nCzas pracy:" + roznica.TotalSeconds);

W tej chwili robię to w ten sposób. Kod można wrzucić jako obsługę jakiegoś Buttona i dodać trzeba textBoxa na GUI.

Wersja Debug to ok. 64 sek., wersja Release to ok. 43 sek.

Szczerze mówiąc to teraz po przemyśleniu nie wiem jak mógłbym tu wykorzystać Twój pomysł Stanley

Widzę mały błąd z "int liczba=3" ale to jest pomijalne. U siebie poprawiłem na "5" już.

Edytowane 28 lipca 2016 przez thikim

[Stanley 15]

Szczerze mówiąc to teraz po przemyśleniu nie wiem jak mógłbym tu wykorzystać Twój pomysł Stanley

 

Dziwnie to zabrzmi: ale ja tym bardziej, bo jak coś wymyślam to rzadko świadomie. Niepotrzebnie o tym napisałem. Wychodziłem z założenia że sqrt jest skomplikowane, a okazuje sie że FSQRT zajmuje raptem od 6 do 21 cykli czyli raptem 2x gorsze od modulo (ok 12 cykli)

 

Zrobiłem baze dla swojej wersji ©, tablica pierwiastkowa + sito pokombinuje.

Faakycznie pogo ma racje. Szkoda