Skocz do zawartości


Zdjęcie

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


  • Zaloguj się, aby dodać odpowiedź
275 odpowiedzi w tym temacie

#41 ~Astro

~Astro
  • Goście

Napisano 17 marzec 2016 - 17:05

Cymbał kompilator liczy to za każdym razem. […] jestem prawie pewien, że powinien to zoptymalizować do stałej.

 

Ponieważ Twój namber jest zmienną (szczególnie, że ją zmieniasz ;)), to dostrzegam jednak w kompilatorze cechy mądrości. :)

 

A tu nie wiem o co chodzi

 

Wydaje mi się, że edycje napisanego już tekstu na poziomie "technicznym" (korekta językowa) jest ok., jednak dodawanie na początku posta nowego tekstu już niekoniecznie. Lepiej wygląda dodanie niżej po "Edit", "Edycja", "Oj, zapomniałek", "Oj, nie zauważyłek" itp.



Reklamy Google

#42 Jajcenty

Jajcenty

    padawan młody

  • Użytkownicy
  • PipPipPipPipPipPip
  • 3233 postów

Napisano 17 marzec 2016 - 17:21

Ponieważ Twój namber jest zmienną (szczególnie, że ją zmieniasz ), to dostrzegam jednak w kompilatorze cechy mądrości.
 

No nie wiem. Nie widzę jak zmienna Number miałaby się zmienić w ramach pętli for. Ale OK, nie pierwszy raz mamy kontrowersję z kompilatorem.

Lepiej wygląda dodanie niżej po "Edit"

Skoro tak uważasz - nie ma sprawy.Specjalnie dla Ciebie będę sufiksował, nigdy prefiksował. 


  • 0

#43 radar

radar

    Lis major

  • Użytkownicy
  • PipPipPipPipPip
  • 1290 postów

Napisano 17 marzec 2016 - 17:21

O kurcze, dopiero zobaczyłem, że tu się konkurs zrobił.D

Dla javowców, BigInteger nie posiada ograniczenia z góry, więc można i 2100 jak ktoś ma tyle pamięci ;)


  • 0

#44 ~Astro

~Astro
  • Goście

Napisano 17 marzec 2016 - 17:31

No nie wiem. Nie widzę jak zmienna Number miałaby się zmienić w ramach pętli for

 

No chyba już ustaliliśmy, że kompilator to żadna AI. Swoją drogą, przykładów konstrukcji bardzo prostej pętli wywołującej funkcję z Twoim namberem można mnożyć; funkcja może wywoływać pińcet innych i nawet Tobie tygodnia może braknąć by rozstrzygnąć, czy się w końcu zmienia, czy nie. Może być też zmienną globalną, ale trzymajmy się może jednego – kompilator jest głupi, a inteligencji oczekujmy od piszącego kod. ;)



#45 radar

radar

    Lis major

  • Użytkownicy
  • PipPipPipPipPip
  • 1290 postów

Napisano 17 marzec 2016 - 17:35

Ale piszmy wszyscy jednowątkowo, bo inaczej czasy będą nieporównywalne :)


  • 0

#46 Jajcenty

Jajcenty

    padawan młody

  • Użytkownicy
  • PipPipPipPipPipPip
  • 3233 postów

Napisano 17 marzec 2016 - 17:53

Ale piszmy wszyscy jednowątkowo, bo inaczej czasy będą nieporównywalne

I tak będą nieporównywalne bo mamy różne maszyny. A jednowątkowo  to się nawet nie zbliżymy do jakiś rozsądnych czasów.

 

Tak się zastanawiam. Skoro w publikacji chodzi o korelację między ostatnimi cyframi, to może nie trzeba pamiętać wszystkiego, a wystarczy tablica 10x10 do zapamiętania częstości par.

 

 

 

funkcja może wywoływać pińcet

Tak, zajarzyłem w końcu. Przyczyną jest funkcja. Kompilator słusznie nie chciał uronić ni jednego  efektu ubocznego. Dobry krzemiak.

 

EDYCJA: 

Po ostatnich zmianach 48 minut / 100 największych. Urwaliśmy 6 minut z 54. Astro urwał 4. Brawo Astro!


Użytkownik Jajcenty edytował ten post 17 marzec 2016 - 17:57

  • 0

#47 Afordancja

Afordancja

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 604 postów

Napisano 17 marzec 2016 - 19:49

to będzie około 2^63/log(2^63)*4B ~= 8.4486e+17 ~= 850 PB. Powodzenia 

 

Ja tego nie muszę nigdzie zapisać aby zrobić badanie, wystarczą mi dwie kolejne a potem je zapominamy :) 

 

Muszę zobaczyć cudzy gotowy kod używający tej własności. Wtedy będę wiedział. Na razie odsuwam to koniec listy.

 

Myślę, że mamy podobny koncept z radarem, i sprawdzałem (mimo, że w javie i parę rzeczy mam hm..delikatnie rzecz mówiąc, na szybciora (teraz to poprawię)) Twoje liczenie o tyłu (chociaż nie tak to sobie ułożyłem) i znalezienie 100 ostatnich zajmuje mi 20 minut. Przeczytam forum i zasiadam do poprawek, mam nawet mega koncepcję, która narodziła się w samochodzie, ale muszę to przemyśleć.

 

 

O kurcze, dopiero zobaczyłem, że tu się konkurs zrobił.D Dla javowców, BigInteger nie posiada ograniczenia z góry, więc można i 2100 jak ktoś ma tyle pamięci

Oj tam od razu konkurs, lepsza motywacja, do co BigInteger, to ja dziękuję już wole liczyć 2 razy mniej, wydajnością bym raczej padł.

 

Ale piszmy wszyscy jednowątkowo, bo inaczej czasy będą nieporównywalne

dobra koncepcja ale i tak nie będą, o kompy różne, ja będę na pewno pisał jednowątkowo (Aż tak serio do tego nie podchodzę)


  • 0

#48 pogo

pogo

    1010011010

  • Moderatorzy
  • 2868 postów

Napisano 17 marzec 2016 - 20:03

@Jajcenty

Jak pozbędziesz się dzielenia na 5 to urwiesz kolejne 20%. Wystarczy zrobić pętlę, która w środku będzie miała od razu 4 liczby do policzenia z 1, 3, 7 i 9 na końcu. Do tego redukujesz ilość obiegów pętli, co też poprawi wydajność.
Analogicznie można pomijać dzielenie liczb z 5 na końcu. Kod się robi długi i niezbyt ładny, ale bardziej optymalny.

Do zabawy będę mógł dołączyć dopiero w sobotę, więc pewnie będzie już wtedy po wszystkim.

Inna sprawa, że nie szczególnie podoba mi się koncepcja powtarzania cudzych badań, wolałbym poszukać innych zależności.


  • 0

#49 Afordancja

Afordancja

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 604 postów

Napisano 17 marzec 2016 - 20:10

Do zabawy będę mógł dołączyć dopiero w sobotę, więc pewnie będzie już wtedy po wszystkim.
 

Nie byłbym tego taki pewien ;)

 

 

Inna sprawa, że nie szczególnie podoba mi się koncepcja powtarzania cudzych badań, wolałbym poszukać innych zależności.

Ależ akurat ja chcę zbadać trochę inne zależności (patrz mój pierwszy post). Tzn. chcę ich badanie bardziej uogólnić, bo przecież ostatnia cyfra to nic innego jak -> liczba pierwsza % 10. A dlaczego ta 10 taka uprzywilejowana ? ;)


  • 0

#50 radar

radar

    Lis major

  • Użytkownicy
  • PipPipPipPipPip
  • 1290 postów

Napisano 17 marzec 2016 - 22:50

Wystarczy zrobić pętlę, która w środku będzie miała od razu 4 liczby do policzenia z 1, 3, 7 i 9 na końcu. Do tego redukujesz ilość obiegów pętli, co też poprawi wydajność.

No ja tak dokładnie robię. Zamieszczę potem timingi.


  • 0

#51 Afordancja

Afordancja

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 604 postów

Napisano 17 marzec 2016 - 22:57

Ja skolei, jeżlei nie popełniłem nigdzie błędu. (wyniki skonfrontuję z wami), 

W niecałe 6 minut, wygenerowałem(w zasadzie to policzyłem) ostatnie 49 188 859 liczb pierwszych, czyli ekstrapolując (ale idę spać), 100 milionów powinienem pyknąć, w 8 minut (bo 4 minuty to koszt stały).

 

Ale to już jutro.

Są jakieś stronki gdzie poznam ile jest liczb pierwszych z jakiegoś zakresu liczb? to bym zweryfikował.


  • 0

#52 radar

radar

    Lis major

  • Użytkownicy
  • PipPipPipPipPip
  • 1290 postów

Napisano 17 marzec 2016 - 23:29

https://en.wikipedia...unting_function

 

 

 

ostatnie 49 188 859 liczb pierwszych

 

Co masz na myśli pisząc "ostatnie"?

 

EDIT:

No dobra, podawajcie od razu typ procka i zegar.

Pentium G3258, 3.2GHz.


Użytkownik radar edytował ten post 17 marzec 2016 - 23:34

  • 0

#53 Afordancja

Afordancja

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 604 postów

Napisano 17 marzec 2016 - 23:58

Co masz na myśli pisząc "ostatnie"?

 

 

(JEdnak nie śpię i liczę liczby pierwsze z zakresu 3 do 100 mld ;) )

 

Ostatnie mam na myśli to o czym pisał Jajcenty.

Czyli biorę long_max (dla mnie to signed), i lecę w dół.

i otrzymuję 49 kk liczb pierwszych, które są ostatnie z zakresu.

 

Czyli nie szukam ich z zakresu 0..do N.. tylko  od N do long_max (i Jajcenty postawił próg 100 milionów)

Bo od dołu (od zera) to zraz będę wiedział czy dobrze liczę, bo spodziewam się ich znaleźć około 4 miliardy (Tzn. pierwsze 4 miliardy liczb pierwszych) 

 

 

Innymi słowy, większych już nie znajdę bo mi się nie mieszczą w longu


[edit]

Ok, wygląda na to, że działa dobrze.

 

Znalezienie pierwszych 4,1 mld liczb pierwszych (czyli zaczynając od liczby 2) zajęło mi 39 minut i 16 sekund)

Już nie mam tych 8 minut, ale jestem prawie pewien, że zmieszczę się w 8 minutach do znalezienia 100 mln. ostatnich (z przedziału N do long_max) liczb pierwszych.

 

Po podaniu przez was czasów (bo jednak domniemam, że w C możecie być szybsi) zdecyduję czy wprowadzę moją mega koncepcję która jak domniemam, dość znacznie przyspieszy proces., 


Użytkownik Afordancja edytował ten post 17 marzec 2016 - 23:35

  • 0

#54 Eco_PL

Eco_PL

    Górnik

  • Użytkownicy
  • Pip
  • 94 postów

Napisano 18 marzec 2016 - 00:11

Potwierdzam, liczby pierwsze nie są rozmieszczone losowo. Kilka miesięcy temu bawiłem się próbując "rozkminić" jakąś regułę rządzącą ich rozkładem i wydaje mi się że ją znalazłem. Wystarczy prosty zestaw funkcji okresowych i bazując na liczbie 2 jestem w stanie wygenerować kolejne liczby pierwsze. Inna kwestia to złożoność obliczeń potrzebnych do wygenerowania coraz większych liczb, ponieważ aby wygenerować liczby pierwsze mniejsze od k muszę znać wszystkie liczby pierwsze mniejsze od SQRT(k). Ta funkcja ma dość skomplikowany kształt, ale z pewnością nie ma nic wspólnego z losowością, choć na pierwszy rzut oka można takie wrażenie odnieść. Kształtem przypomina nieco zapis dźwięku, ciekawe jak by to brzmiało.
bez-nazwy.jpg


  • 0

#55 Jajcenty

Jajcenty

    padawan młody

  • Użytkownicy
  • PipPipPipPipPipPip
  • 3233 postów

Napisano 18 marzec 2016 - 00:36

Innymi słowy, większych już nie znajdę bo mi się nie mieszczą w longu

Podaj proszę jaką największą liczbę znalazłeś?  Czasy jakie podałeś u mnie osiągam dla ulong.MaxValue/10. Coś mi tu nie gra.


  • 0

#56 Jan

Jan

    Górnik

  • Użytkownicy
  • Pip
  • 6 postów

Napisano 18 marzec 2016 - 01:04

Mój algorytm wolny  :(

W 88 i pół minuty mam wszystkie pierwsze poniżej 5e9 (234954223 sztuki w 4.5 minuty) i dzięki nim 218 sztuk "od góry". Największa 18446744073709551557, najmniejsza 18446744073709541621.

Pociesza mnie jedynie fakt, że to czas na bardzo słabym i3-2375M @ 1.5GHz + 6GB RAM


  • 0

#57 ex nihilo

ex nihilo

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 936 postów

Napisano 18 marzec 2016 - 04:59

https://en.wikipedia...iki/Ulam_spiral

https://ru.wikipedia.../Скатерть_Улама


  • 0

#58 Afordancja

Afordancja

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 604 postów

Napisano 18 marzec 2016 - 08:37

Inna kwestia to złożoność obliczeń potrzebnych do wygenerowania coraz większych liczb, ponieważ aby wygenerować liczby pierwsze mniejsze od k muszę znać wszystkie liczby pierwsze mniejsze od SQRT(k).

 

To chyba dość oczywiste.

 

 

 

Wystarczy prosty zestaw funkcji okresowych i bazując na liczbie 2 jestem w stanie wygenerować kolejne liczby pierwsze.

A to już nie bardzo, bo skoro masz zestaw funkcji bazujących an liczbie 2 to po co Ci te poprzednie wyniki? Nie możesz ich wygenerować za pomocą tych funkcji?

 

Kształt funkcji może nie wygląda jak biały szum, ale nie wygląda na taki oczywisty.No ale wyglądanie to sobie mogę wsadzić ;)

 

 

 

Podaj proszę jaką największą liczbę znalazłeś?  Czasy jakie podałeś u mnie osiągam dla ulong.MaxValue/10. Coś mi tu nie gra.

 

hm..jeśli dobrze spojrzałem to największa z moich to 9223372036854775783.

 

Ostateczny wynik (trochę nie trafiłem, bo stop mam nie wg. znalezionych liczb, ale wg. zakresów szukania, a że jadę zawsze z dołu do góry, to nawet jak szukam od N do long_max, to N muszę podać).

 

Znalezionych największych (w zakresie do long_max signed)liczb pierwszych 98 369 463 (@Jajcenty, będziesz się czepiał czy tyle może być? :) ) w czasie 6 minut i 32 sekundy. 

 

Koszt stały programu(niezależnie ile i które, liczby pierwsze będę liczył)  to mniej więcej 4:25 minuty, jest dość nieoptymalny, ale olać. 

Nie stosowałem, żadnych bibliotek matematycznych oprócz sqr oczywiście ;)

Pozbyłem się praktycznie modulo (jest słabe).

 

Obstawiam, że mogę jeszcze podkręcić dokonując małych optymalizacji, dużo pokręcić (ale to już przeczucie), dość mocno zmieniając koncepcję (a trochę mi się nie chce).

Ostatecznie jeszcze widzę trzecią możliwość "optymalizacji" widzę możliwość przepisania tego na kartę graficzną :D (ale to było by już małe oszustwo).

 

[edit]

(Aby mieć wyniki w jednym miejscu)

 

Znalezienie pierwszych(czyli najmniejszych)  4,1 mld liczb pierwszych (czyli zaczynając od liczby 2 a kończąc  w granicach 100 mld-> dlatego około bo używam liczby 1024 w celach optymalizacyjnych ) zajęło mi 39 minut i 16 sekund)

 

Jeszcze testowo spróbuje znaleźć ostatnie (największe) nie wiem wyjdzie ale szacuję, że powyżej 2 miliardów (no chyba, że są w wyższych liczbach jakoś mocno rzadziej) i zobaczę ile mi wyjdzie, w każdym razie jadę taki sam zakres jak od dołu

N do max_long gdzie N = max_long - 100 * 1024*1024*1024.


Użytkownik Afordancja edytował ten post 18 marzec 2016 - 08:45

  • 0

#59 Jajcenty

Jajcenty

    padawan młody

  • Użytkownicy
  • PipPipPipPipPipPip
  • 3233 postów

Napisano 18 marzec 2016 - 09:14

Znalezionych największych (w zakresie do long_max signed)liczb pierwszych 98 369 463 (@Jajcenty, będziesz się czepiał czy tyle może być? ) w czasie 6 minut i 32 sekundy.   

Dla mnie bomba. Widać że nie ma większych trudności z uzyskaniem 10e8 liczb pierwszych  rzędu 10e18. A oni zatrzymali się na 1oe7 liczb rzędu 10e12.

Teraz powinieneś im je posłać. :D

Ja ciągle płacę 47 sekund za prime'a, ale się nie poddaję :D Prze weekend coś wymyślę.

ttps://en.wikipedia...iki/Ulam_spiral

Tak, spirala Ulama miała być naocznym dowodem na nielosowości pierszych, ale tłumaczono mi że to tylko przypadek. Dla mnie wskazówką podejrzanego zachowania pierwszych jest twierdzenie Gaussa o liczbie dc417289d89a2bd2ac86e4179a3dcf35.png

Podejrzana sprawa :) 


  • 0

#60 Afordancja

Afordancja

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 604 postów

Napisano 18 marzec 2016 - 10:12

Ostatenie "podsumowanie" z pierwszych testów.

 

Dwa zakresy sprawdzone

od 2 do około 100 miliardów ->4,1 mld liczb pierwszych czas 39 minut i 16 sekund.

od (long_max - około 100 miliardów)  do long_max -> 2,4 mld liczb pierwszych czas 78 minut i 59 sekund.

 

Na razie dalsze optymalizowanie czasowe odkładam na później (chyba, że się pojawi jakiś super czas :) ) .

 

A co zrobię:

1. Przeczytam z grubsza co zrobili

2. wezmę 5 zakresów. (każdy zakres 100 miliardów liczb,  a w każdym zakresie jak do mniemam, liczb pierwszych od 2,4 mld do 4,1 mld.)

zakresy będą w miarę równo rozłożone w zakresie od 2 do long_max. czyli na początku, ćwiartka, połówka, trzy czwarte i końcówka (tak to sobie wymyśliłem).

3. Przeprowadzę takie same statystyki ostatnich cyfr, ale też ostatnich cyfr dla X systemów zapisu (nie wiem jeszcze ile ich wezmę).

4. Nie wiem co z tym zrobię :D 


  • 0