Dzisiaj w cpp napisałem program do wyznaczania liczb 1-szych tą metodą
Łącznie ze sprawdzeniem czy dana liczba jest pierwsza
Maksymalna liczba pierwsza to 1 091 344 141, w sumie tych liczb od 7-ki było 3 852 080 pozycji
dlaczego taka mała bo zakres zmiennej "int" mi się skończył
na zwykłym, laptopie z i5 zajęło mi to 11 minut
Nie wiem czy to dużo czy mało
Proszę o opinię
Test szybkości wyznaczania Liczby 1sze regułą Chaldejską
-
- Użytkownik
- Posty: 465
- Rejestracja: 1 gru 2015, o 21:49
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 6 razy
- Pomógł: 20 razy
Re: Test szybkości wyznaczania Liczby 1sze regułą Chaldejską
Dla wersji 64 bit będzie to dwa razy większy int.
Proces sprawdzania pierwszości liczby zabija ten algorytm.
Zwykły Eratostenes robi to 50 razy szybciej. (mój algorytm 200 razy )
Proces sprawdzania pierwszości liczby zabija ten algorytm.
Zwykły Eratostenes robi to 50 razy szybciej. (mój algorytm 200 razy )
-
- Użytkownik
- Posty: 17
- Rejestracja: 6 mar 2018, o 14:18
- Płeć: Mężczyzna
- Lokalizacja: Starogard Gdański
- Podziękował: 1 raz
Re: Test szybkości wyznaczania Liczby 1sze regułą Chaldejską
Ok , sprawdziłem , ten długi czas 11 minut wynikał z nieprzemyślanego wydajnościowo algorytmu
Aktualnie mam taki sam czas wykonywania programu jak metodą sito eratostenesa.
Metoda Chaldejska ma jedną przewagę, nie musi pamiętać wszystkich wyników w tablicy. Wyznacza po prostu
zgodnie ze wzorem n-ty element zbioru liczb 1-szych.
teraz pracuję nad napisaniem klasy wykonującej operacje arytmetyczne nie za pomocą procesora
tylko traktuje wartości liczbowe jako tekst i wykonuje coś na wzór np sumowania pisemnego.
Może wybiorę Japoński system sumowania.
Dzięki temu będę mógł przeskoczyć ograniczenia wielkości typów zmiennych i wykonywać np na liczbach o wartościach (1*10^(1*10^100)) operacje
arytmetyczne.
Aktualnie mam taki sam czas wykonywania programu jak metodą sito eratostenesa.
Metoda Chaldejska ma jedną przewagę, nie musi pamiętać wszystkich wyników w tablicy. Wyznacza po prostu
zgodnie ze wzorem n-ty element zbioru liczb 1-szych.
teraz pracuję nad napisaniem klasy wykonującej operacje arytmetyczne nie za pomocą procesora
tylko traktuje wartości liczbowe jako tekst i wykonuje coś na wzór np sumowania pisemnego.
Może wybiorę Japoński system sumowania.
Dzięki temu będę mógł przeskoczyć ograniczenia wielkości typów zmiennych i wykonywać np na liczbach o wartościach (1*10^(1*10^100)) operacje
arytmetyczne.
-
- Użytkownik
- Posty: 465
- Rejestracja: 1 gru 2015, o 21:49
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 6 razy
- Pomógł: 20 razy
Re: Test szybkości wyznaczania Liczby 1sze regułą Chaldejską
Konieczność sprawdzania pierwszości liczby jest bardzo niekorzystne dla tego algorytmu.
Wyobraź sobie wygenerowanie jednej liczby \(\displaystyle{ 10^{24}}\) wymaga wygenerowania wszystkich liczb pierwszych (chyba że lecisz po nieparzystych +2) do \(\displaystyle{ 10^{12}}\).
(W Javie jest klasa BigInteger)
Wyobraź sobie wygenerowanie jednej liczby \(\displaystyle{ 10^{24}}\) wymaga wygenerowania wszystkich liczb pierwszych (chyba że lecisz po nieparzystych +2) do \(\displaystyle{ 10^{12}}\).
(W Javie jest klasa BigInteger)
-
- Użytkownik
- Posty: 17
- Rejestracja: 6 mar 2018, o 14:18
- Płeć: Mężczyzna
- Lokalizacja: Starogard Gdański
- Podziękował: 1 raz
Re: Test szybkości wyznaczania Liczby 1sze regułą Chaldejską
Ta okresowość 60-ciu nie jest moim zdaniem przypadkiem. W ciągu Fibonacciego nie wiadomo dlaczego ale występuje okresowość 60 elementów ciągu dla ostatnich cyfr. Odsyłam do . Tutaj mam związek między 60 okresem a ciągiem Fibonacciego . Właśnie tutaj widać tą zależność z liczbami 1-szymi
Kod: Zaznacz cały
https://www.youtube.com/watch?v=7VHFr0GCSyw
Ostatnio zmieniony 14 lut 2021, o 12:51 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Więcej szacunku dla Fibonacciego.
Powód: Więcej szacunku dla Fibonacciego.
-
- Użytkownik
- Posty: 465
- Rejestracja: 1 gru 2015, o 21:49
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 6 razy
- Pomógł: 20 razy
Re: Test szybkości wyznaczania Liczby 1sze regułą Chaldejską
Zakładam, że w algorytmie przesuwasz się po liczbach co określoną liczbę 2, 4, 6. Tak otrzymaną liczbę sprawdzasz pod kątem podzielności przez inne liczby pierwsze.
Być może zauważyłeś, że jeżeli z którejś kolumny liczb odrzuciłeś liczbę (np. ze względu na podzielność przez 7) to sprawdzanie w tej kolumnie następnych 6-ciu liczb (ich podzielności przez siedem) jest wykonaniem sześciu niepotrzebnych operacji (właściwie już nie ma potrzeby wykonywania takich operacji sprawdzających wcale do "końca" kolumny) ?
Tak jest dla każdej liczby pierwszej \(\displaystyle{ p}\). W kolumnie jeżeli natrafiasz na liczbę podzielną przez \(\displaystyle{ p}\) to następna podzielna przez \(\displaystyle{ p}\) w tej kolumnie będzie o \(\displaystyle{ p}\) niżej
Być może zauważyłeś, że jeżeli z którejś kolumny liczb odrzuciłeś liczbę (np. ze względu na podzielność przez 7) to sprawdzanie w tej kolumnie następnych 6-ciu liczb (ich podzielności przez siedem) jest wykonaniem sześciu niepotrzebnych operacji (właściwie już nie ma potrzeby wykonywania takich operacji sprawdzających wcale do "końca" kolumny) ?
Tak jest dla każdej liczby pierwszej \(\displaystyle{ p}\). W kolumnie jeżeli natrafiasz na liczbę podzielną przez \(\displaystyle{ p}\) to następna podzielna przez \(\displaystyle{ p}\) w tej kolumnie będzie o \(\displaystyle{ p}\) niżej
-
- Użytkownik
- Posty: 17
- Rejestracja: 6 mar 2018, o 14:18
- Płeć: Mężczyzna
- Lokalizacja: Starogard Gdański
- Podziękował: 1 raz
Re: Test szybkości wyznaczania Liczby 1sze regułą Chaldejską
Dzisiaj trafiłem na opis dwóch osób
Yitang Zhang z University of New Hampshire
oraz
Harald Helfgott z Ecole Normale Superieure
metoda polega na wyznaczaniu licz 1-szych poprzez sumowanie
Oto Przykład , kolumny Poz1,2,3 oznaczają kolejną pozycję w zbiorze liczb
\(\displaystyle{ \begin{array}{|rc|c}
\hline
& & Poz1 & Poz2 &Poz3\\ \hline
19 = 3 +5 +&11 & 2 & 3 &5\\ \hline
23 = 5 +7 +&11 &3 &4 &5\\ \hline
29 = 5 +7 +&17 &3 &4 &7\\ \hline
31 = 7 +11 +&13 &4 &5 &6\\ \hline
37 = 7 +11 +&19 &4 &5 &8\\ \hline
41 = 7 +11 +&23 &4 &5 &9\\ \hline
43 = 11 +13 +&19 &5 &6 &8\\ \hline
47 = 11 +17 +&19 &5 &7 &8\\ \hline
53 = 13 +17 +&23 &6 &7 &9\\ \hline
\end{array}}\)
Widać że między Poz1,2,3 zachodzi fraktal , tylko jaki ?
Jak ktoś ma pomysł to byłbym wdzięczny
Yitang Zhang z University of New Hampshire
oraz
Harald Helfgott z Ecole Normale Superieure
metoda polega na wyznaczaniu licz 1-szych poprzez sumowanie
Oto Przykład , kolumny Poz1,2,3 oznaczają kolejną pozycję w zbiorze liczb
\(\displaystyle{ \begin{array}{|rc|c}
\hline
& & Poz1 & Poz2 &Poz3\\ \hline
19 = 3 +5 +&11 & 2 & 3 &5\\ \hline
23 = 5 +7 +&11 &3 &4 &5\\ \hline
29 = 5 +7 +&17 &3 &4 &7\\ \hline
31 = 7 +11 +&13 &4 &5 &6\\ \hline
37 = 7 +11 +&19 &4 &5 &8\\ \hline
41 = 7 +11 +&23 &4 &5 &9\\ \hline
43 = 11 +13 +&19 &5 &6 &8\\ \hline
47 = 11 +17 +&19 &5 &7 &8\\ \hline
53 = 13 +17 +&23 &6 &7 &9\\ \hline
\end{array}}\)
Widać że między Poz1,2,3 zachodzi fraktal , tylko jaki ?
Jak ktoś ma pomysł to byłbym wdzięczny