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

[thikim 117]

Główne obciążenie idzie w pętli gdzie sprawdzam daną liczbę czy jest podzielna, linia 14-21.
A pierwiastkowanie robię poza tą pętlą.

Ale Twój pomysł wykorzystam, tylko w innym przypadku

W przypadku o którym pisałem że będę cedził tylko przez pierwsze 100, potem 1000 potem 10 000 liczb pierwszych.

Tam sobie wygeneruję tablicę kwadratów kolejno pierwszych 100, 1000, 10 000 liczb pierwszych i będę miał sprawdzenie warunku bez pierwiastkowania.

Znam trzy możliwości przyspieszenia ale jako że tylko czasem koduje to na każdą jestem za słaby: (chwilowo oczywiście)

- kilka wątków, muszę sobie przypomnieć co można by tu zrobić

- GPU, próbuję

- assembler, http://ipij.aei.polsl.pl/articles/bezbolesne-programowanie-z-wykorzystaniem-c-i-asemblera/

Jakby się udało o to przerobić na assemblera:

                for ( int licznik = 0; pierwiastekliczby > tablicaliczbpierwszych[licznik]; licznik++) //sprawdza podzielność przez liczby pierwsze już wygenerowane
                {
                    if (liczba % tablicaliczbpierwszych[licznik] == 0)
                    {
                        czypodzielna = true;
                        break;
                    }
                }

Ciekawa sprawa:

zmieniłem bool czypodzielna = false;

na bool czypierwsza=true;

dzięki czemu niżej wyeliminowywałem negację w if w liniii 22.

Po wyeliminowaniu negacji czas wzrósł o 3 sekundy

Pozostaje mi tylko napisać to co kiedyś napisała intrygująca dziewczyna:

"Proszę mi uwierzyć. Ja też byłam w szoku"

Edytowane 28 lipca 2016 przez thikim

[Afordancja 57]

 

 

GPU, próbuję

 

Tego wyniku jestem bardzo ciekaw, ja już nie miałem motywacji, (Brak rywalizacji ) 

[thikim 117]

Póki co mam trochę nauki przed sobą. Właśnie spojrzałem na użycie procesora podczas uruchomienia programu. Tylko 15 % Procesor na wakacjach

Edytowane 28 lipca 2016 przez thikim

[tomak 1]

 

 

Na moje oko w tym białym szumie coś dudni

Jak się przyjrzeć spirali Ulama lub Sacks'a to "dudnienie" widać gołym okiem.

Panowie macie ciekawe pomysły a mi to "dudnienie" nasunęło taki zwariowany trochę - jakby tak właśnie z tej spirali Ulama (lub z wersji Sacks'a) zrobić... płytę winylową i wrzucić to na gramofon?

Może usłyszymy szyderczy śmiech Stwórcy ?

Jest tu na Forum kilku zdolnych programistów - można by ten winyl zasymulować. Zakładam, że będą potrzebne jakieś filtry, żeby z tych kropek (pików?) zrobić coś bardziej łagodnego dla ucha, ale powinniśmy usłyszeć wyraźne "dudnienie" a nie biały szum...

[Stanley 15]

thikim -  era asemblera mineła, od czasu kompilatorów x86-64 https://msdn.microsoft.com/en-us/library/26td21ds.aspx

Dla C# zamiast szarpać sie z OpenCL,CUDA, Microsoft zrobił AMP

https://msdn.microsoft.com/pl-pl/library/hh265136.aspx

Nie znam ale polecam, podobno najlepsze w swoim rodzaju

Edytowane 28 lipca 2016 przez Stanley

[Afordancja 57]

jakby tak właśnie z tej spirali Ulama (lub z wersji Sacks'a) zrobić... płytę winylową i wrzucić to na gramofon? Może usłyszymy szyderczy śmiech Stwórcy ? Jest tu na Forum kilku zdolnych programistów - można by ten winyl zasymulować. Zakładam, że będą potrzebne jakieś filtry, żeby z tych kropek (pików?) zrobić coś bardziej łagodnego dla ucha, ale powinniśmy usłyszeć wyraźne "dudnienie" a nie biały szum...

 

hm... jaki to ma sens? Jak sobie wyobrażasz zrobienie z tego płyty analogowej? Nawet jak by była to byś usłyszał "piski" i tyle, nie da się tego zinterpretować w żaden sposób.

TAm nie ma nic ukryte, liczby pierwsze nie są ułozone w jakiś specjalny sposób, tzn. celowy, liczby są ułożone jak są ułożone i tyle, a że nie umiemy znaleźć prawdwidłowości..hm..to inna historia.

 

W sumie jak by pomyśleć to nie wiemy czy musi być jakaś prawidłowość. No bo mamy sobie po kolei liczby..nieskończone..usówamy jedną prawidłowość, wszystkie podzielne przez 2,, potem usówamy kolejny wzorek, podzielne przez 3, potem 5,7,11 ,13, itd... usówamy kolejne wzorki... i pytanie jest czy w z pozostałych liczb da się ułożyć jakiś wzorek, może tak może nie.  "wzorek" to taki skrót myslowy

Edytowane 29 lipca 2016 przez Afordancja

[thikim 117]

thikim - era asemblera mineła, od czasu kompilatorów x86-64

Bez wątpienia. Ale tu mam problem nie ery tylko wydajności.

Zachowanie kompilatora o którym pisałem wcześniej, pozbycie się negacji w if zwiększyło czas wykonywania operacji o 3 sekundy. Jakieś 5 % nie licząc zbyt dokładnie.

W assemblerze nie do pomyślenia. Jak to wyjaśnić? Moim zdaniem kompilator daje d... i to mocno

Assembler przeminął bo programiści są ekonomiczni i liczy się jakiś efekt w jakimś czasie a nie najlepszy efekt w sporo dłuższym czasie.

Przy miliardy razy powtarzanych obliczeniach (jeżeli chcemy skrócić czas wykonywania) opłaca się nadal korzystać z assemblera.

 

 

Microsoft zrobił AMP

Spróbuję jak znajdę czas bo ostatnio to malowanie i malowanie ścian

PS. https://commons.wikimedia.org/wiki/File:Sacks_Spiral_Divisors_100000.png

To rzeczywiście robi wrażenie ale to bardziej matematyka niż radosne kodowanie

Edytowane 29 lipca 2016 przez thikim

[Jajcenty 314]

 

 

Panowie macie ciekawe pomysły a mi to "dudnienie" nasunęło taki zwariowany trochę - jakby tak właśnie z tej spirali Ulama (lub z wersji Sacks'a) zrobić... płytę winylową i wrzucić to na gramofon?

Wydaje się, że przypisanie ostatniej cyfrze liczby pierwszej nuty (wysokość, czas trwania) i podanie na wejście do programu muzycznego powinno ujawnić muzykę matematyki. Podobnie można zrobić z e,pi. Do nudnych utworów zaliczyłbym np 1/3.

[Gość Astro]

Musiałem tego utworu wysłuchać kilkukrotnie. Robi wrażenie

 

 

 

Chłopaki, jak ktoś z Was napisze nieco dłuższą etiudę, to chętnie posłucham, bo ten kawałek jakiś taki niedokończony…

[thikim 117]

Odpowiedni zakres żeby było w miarę przyjemne

Ale tu przecież można zakodować to na 100 sposobów.

Dobra, przyjmuję wyzwanie

[Gość Astro]

Czekam zatem Thikim na Twoją kompozycję. Można to zapewne zakodować na tyle sposobów, ile jest liczb pierwszych.

[thikim 117]

Już mi gra na kompie ale to nie to muszę przemyśleć algorytm robienia z tego utworu.

Może od razu wpiszę random? I tak się nie kapniesz

Edit: Po przeróbkach da się tego posłuchać nawet chwilę

Siądę później nad jakimś minimum grafiki, albo puszczę to do wave i połączę z jakimś wygaszaczem zależnym od dźwięku

Edytowane 29 lipca 2016 przez thikim

[Stanley 15]

Tomak, Thikim ->

#include <iostream>
#include <windows.h>
#include <mmsystem.h>
#include <stdio.h>

#pragma comment(lib, "C:\\Borland\\BCC55\\Lib\\PSDK\\winmm.lib")

int main(int argc, char** argv)
{
    HWAVEOUT hWaveOut = 0;
    WAVEFORMATEX wfx = { WAVE_FORMAT_PCM, 1, 8000, 8000, 1, 8, 0 };
    waveOutOpen(&hWaveOut, WAVE_MAPPER, &wfx, 0, 0, CALLBACK_NULL);
    char buffer[8000 * 60];

    for (DWORD t = 0; t < sizeof(buffer); ++t)
        buffer[t] = static_cast<char>((((t * (t >> 8 | t >> 9) & 46 & t >> 8)) ^ (t & t >> 13 | t >> 6)) & 0xFF);

    WAVEHDR header = { buffer, sizeof(buffer), 0, 0, 0, 0, 0, 0 };
    waveOutPrepareHeader(hWaveOut, &header, sizeof(WAVEHDR));
    waveOutWrite(hWaveOut, &header, sizeof(WAVEHDR));
    waveOutUnprepareHeader(hWaveOut, &header, sizeof(WAVEHDR));
    waveOutClose(hWaveOut);
    std::cout << "Koniec :)";
    Sleep(60 * 1000);
	return 0;
}

W miejsce for (...) { buffer[t] = .. } możesz wstawić co chcesz. np. pierwsze albo rand(255);  

Odgrzebałem fragment z programu "WIFI-HIFI" (socket audio sender - funkcjonalność PulseAudio) ale nie mogłem wczoraj skompilować, dziś sprawdzone -  muza ala gierka z lat 80. Wymaga tuningu bo troche za szybko.

Link do http://goo.gl/hQdTi skąd pobrałem wzór oraz próbka audio.

Skompilowane exe(32bit) można pobrać z https://github.com/stasinek/WIFI-HIFI/blob/master/WIFI-HIFI.exe

 

thikim - __buildin to jest asembler, ale troche inaczej, jestem fanem asemblera ale jako wstawki asm {}  LLVM do asemblera jest cudne prawie takie jak dawne asm {}, GCC to zabugowana parodia, Borland C++ to jest coś.. co sie nie wróci no bo działa raptem SSE i 32 bit. Uznaje po czasie że asembler to po prostu strata czasu skoro im sie nie chciało aktualizować kompilatorów do nowszego CPU to trzeba sie poddać. Jest opcja Lazarus tam wstawki można nadal stosować ale to Pascal. Microsoft i Embarcadero olało wstawki asemblera bo zrobili po nowemu własnie w postaci instrictów. Zobacz apex_memmove na codeproject(kod, pomiń blablanie autora). Dla mnie już za późno na nauke

 

Stricte asembler nadal można stosować (FASM np. Fresh IDE, NASM, YASM), albo wspomniana przec Ciebie opcja do C#, ale zmusza do tworzenia pełnego ciała funkcji, nauki makr i w sumie to sie nie opłaca. Obecnie kompilator potrafi robić to lepiej w dodatku lepiej wdrażać CUDA niż asemblera. Moge zrobić to co chcesz w asemblerze ale raczej spróbuje to w swojej wersji skompilować i conieco poprzestawiać tak że kompilator skompiluje lepiej. Podam przykład Borland lubi jak mu się tworzy zmienną w ciele funkcji do której przypisujesz parametr w wywołaniu funkcji wówczas nawet bez słówka register(obsolete w C++) przypisuje rejestr do zmiennej. Troche daje odpowiednie stosowanie prefetch, movntq.. itd. Ale w sumie to takie detale że szkoda mi czasu. Podejrzewam że w C# też tak jest z rejestrami mimo iż to JIT i możliwe że dlatego 3s dłużej niż krócej bo z jakiegoś powodu po zmianie operuje na ram zmiast rejestru. Może dlatego 15% CPU a nie 100%? W C# można dodać volatile ale to zadziała odwrotnie - zmusza do pozostawienia zmiennej jako adres ram. Tobie polecam weź sie za GPU rozbij to jakoś na mniejsze.. to jest zadanie bo podstawowy problem multithread to: mądre blokowanie dostepu, synchronizacja watków. Tak na marginesie https://github.com/stasinek/ssthreads

#define ATOMIC(num)\
__int64 __unique##num;\
volatile static __int64 __shared##num = 0;

#define ATOMIC_LOCK(num)\
    while (__shared##num !=0) { ts::time::wait_us(0); }\
    __unique##num = ts::cpu::rdtsc(); __shared##num = __unique##num;\
    asm("mfence");\
    while(__shared##num !=0 ? __shared##num != __unique##num : false) { ts::time::wait_us(0); }\
    printf("ATOMIC_LOCK: %lld\n",__unique##num);

#define ATOMIC_UNLOCK(num)\
    printf("ATOMIC_UNLOCK: %lld\n",__unique##num);\
    __shared##num = 0;

Edytowane 29 lipca 2016 przez Stanley

[thikim 117]

 

 

Może dlatego 15% CPU a nie 100%?

Ależ 15 % z powodu jednego rdzenia

I tu jedna dobra uwaga:

 

 

skoro im sie nie chciało aktualizować kompilatorów do nowszego CPU to trzeba sie poddać

Dokładnie. Ale inne powody. Po co to mieli robić jak mało kto tego używał? Do kliknięcia dwóch buttonów nie potrzeba asma.

Ale gdy w grę wchodzi naprawdę krytyczne wykonanie czasowe to jednak asm.

Inna sprawa że asm pewnie nie pójdzie na GPU tak sobie zgaduję. Więc trzeba wybrać i GPU będzie lepsze.

[thikim 117]

Program już niby mam grający ale wychodzi na to że dźwięki powodują zamrożenie GUI i nie wiem jak to pokonać.

[Jajcenty 314]

 

 

dźwięki powodują zamrożenie GUI i nie wiem jak to pokonać.

Wątkami? 

[thikim 117]

Robiłem. Nie dało za wiele.
Możliwe że źle robiłem bo doświadczenia brak a procedura generowania dźwięku prosta nie jest.

Zresztą nie jestem pewien co tak naprawdę mrozi wątek.

Bo mogą dźwięki, mogą obliczenia. Ale dźwięki blokują obliczenia bo wszystko czeka na koniec dźwięku.

Edytowane 10 sierpnia 2016 przez thikim

[ojciec detecktor 4]

Dźwięki są wypadkową kumulacji energii, a jak by tak dźwiękiem skumulować enegię?

 

w długości liczb pierwszych okaże się,że jedne będą występowały częściej od drugich a później na odwrót i to się ograniczy do fali korpuskularno-falowej.za 20 lat ogólny trend myślowy będize taki;,że jako cywilizacja gówno wiemy i będziemy musieli powtarzać dodawanie z podstawówki!

 

Pragnienia w żaden sposób nie są realizowane do wymogów! szukanie statystyk występowania liczb pierwszych co do wieczności będzie wynosiło 3,14 a dokładniej 3,3,33333333333333333333333.zawsze do udowodnienia absolutu będzie brakowało o,oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo1 i jeszcze dalej. czy sensem jest szukanie nieskończoności? czy  sensem jest zauważenie własnej granicy pojmowania?

[Matcher 2]

Dodam jeszcze taką ciekawostkę:

 

Przy szukaniu liczb pierwszych można posiłkować się sumą wszystkich cyfr danej liczby. Liczba pierwsza posiada sumę cyfr zawsze równą 1,2,4,5,7,8. więc wystarczy szukać właśnie takich liczb. W dodatku każdą liczbę pierwszą można opisać w sposób (x * 30) +y ,gdzie y to jedna z liczb pierwszych (11,13,17,19,23,29,31,37). 

Np.   liczba 43 = ( 1 * 30 )+ 13 a liczba 2469757 = ( 82324 * 30 )+ 37.

 

Jeśli takie liczby wpisze się w tablicę dwu-wymiarową to liczba x będzie obrazować numer wiersza w tablicy , a liczba y numer kolumny. Dziwnie to wygląda,ale i tak jest bardzo ciekawe. Można pomyśleć,że liczby pierwsze są jakoś uporządkowane i mają swoje miejsce,które można szybko odszukać.. hmn

[thikim 117]

Ale Matcher rozbijanie liczby dajmy na to: "2354354254354" na sumę cyfr jest dość kosztowne obliczeniowo.

No i zauważ:

Ile liczb ma sumę cyfr równą 1,2,4,5,7,8 (rozumiem że modulo 10)  - około  60 %

Ile liczb jest podzielnych przez 2 - około 50 %

ile liczb jest podzielnych przez 3 - około 33 %

i przez 5 - około 20 %.

 

 

W dodatku każdą liczbę pierwszą można opisać w sposób (x * 30) +y ,gdzie y to jedna z liczb pierwszych (11,13,17,19,23,29,31,37).

A tego nie znam.

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229

no to jedziemy:

60+19=79 +

60+13=73 +

90+11=101+

90+29=119 -

Edytowane 24 października 2016 przez thikim

[Matcher 2]

90+29=119 -  

 

Nie tędy droga.. To działa odwrotnie. Jak masz pewność,że liczba jest pierwsza to wtedy tak możesz rozłożyć. Ale mając za X liczby losowe masz tylko pewne prawdopodobieństwo ,że trafisz w liczbę pierwszą. w przedziale 100-200 takich liczb może być max 24-28% ,więc dużo szukać nie trzeba.

[thikim 117]

Oki. Tak napisałeś.

Ponieważ jednak rozwiązujemy tu problem odwrotny to spróbuję to zastosować do niego.

Czyli jeśli rozumiem:

biorę:

0,1,2,3,4,5,6,7,8,9... mnożę przez 30

dodaję do każdej z tych liczb: kolejno 11,13,17,19,23,29,31,37.

Dla każdej 30-stki liczb mam 8 liczb do sprawdzenia.

Normalnie eliminowaliśmy parzyste czyli co drugą, czyli 50 %.

Teraz zostanie nam: 8/30 = 26,7 % czyli niemal dwa razy mniej liczb do sprawdzenia.

To byłby rzeczywiście zysk obliczeniowy

Pytanie pierwsze skąd ten sposób znasz?

[Matcher 2]

Dokładnie stało się to 2 lata temu.. Teraz musiałbym przebić się przez stertę gratów i znaleźć zeszyt, gdzie wzór powstał z killu pobazgranych kartek. Pamiętam ,że chodziło dokładnie o liczbę 6. Potem powstał ciąg 11,13,15,17,19,23,25,27,29,31,35,37 itd.. Następnie wykasowałem wszystkie liczby z końcówką 5 i tak to powstało.

 

TAK To jest zysk obliczeniowy   Bo liczby spełniają warunki: Suma cyfr(1,2,4,5,7,8) oraz Ostatnia cyfra(1,3,7,9)

[thikim 117]

A może i inaczej, jak tak sobie myślę. Dodaję 2 mam 3, dodaję 4 mam 7, dodaję 2 mam 9, dodaję 2, mam 11 itd.

czyli dodaję ciąg 2,4,2,2,4,2,2,4...Czyli co trzecią liczbę dodaję 4. Też zysk.

Muszę się kiedyś zmobilizować i przejrzeć te programy co pisałem

[Matcher 2]

Zaczynasz od 11.. czyli jedziesz:| 2,4,2,4,6,2,6,4 |.  Tak można liczyć od samego początku, ale jakbyś chciał liczyć od pewnej liczy np. 211 543 873 453 to będziesz mieć problem co do niej dodać?? masz wtedy 8 kombinacji do sprawdzenia.. Żeby nie sprawdzać każdej możliwości z osobna dzielisz liczbę przez 30. W tym przypadku wynik wynosi 7051462448 i 13/30.  13 to liczba,która została dodana do X*30 --> (X*30)+13 Czyli dalej generując liczby dodajesz kolejno 17,19,23.. itd

 

Inne rozwiązanie to sprawdzenie,która to liczba z kolei. Pierwsza liczba to zawsze 11, druga 13, trzecia 17, Setna 379  A liczba 211 543 873 453 jest na miejscu o numerze :   56 411 699 586.