Test szybkości wyznaczania Liczby 1sze regułą Chaldejską

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
diskbit
Użytkownik
Użytkownik
Posty: 17
Rejestracja: 6 mar 2018, o 14:18
Płeć: Mężczyzna
Lokalizacja: Starogard Gdański
Podziękował: 1 raz

Test szybkości wyznaczania Liczby 1sze regułą Chaldejską

Post autor: diskbit »

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ę
Brombal
Użytkownik
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ą

Post autor: Brombal »

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 ;))
diskbit
Użytkownik
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ą

Post autor: diskbit »

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.
Brombal
Użytkownik
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ą

Post autor: Brombal »

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)
diskbit
Użytkownik
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ą

Post autor: diskbit »

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

Kod: Zaznacz cały

https://www.youtube.com/watch?v=7VHFr0GCSyw
. Tutaj mam związek między 60 okresem a ciągiem Fibonacciego . Właśnie tutaj widać tą zależność z liczbami 1-szymi
Ostatnio zmieniony 14 lut 2021, o 12:51 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Więcej szacunku dla Fibonacciego.
Brombal
Użytkownik
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ą

Post autor: Brombal »

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
diskbit
Użytkownik
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ą

Post autor: diskbit »

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
ODPOWIEDZ