W dniu czwartek, 5 grudnia 2019 03:11:18 UTC+1 użytkownik o...@g...com
napisał:
> > swoje droga esli to jest iteracja na stalej 2^128 - 5 to wynik konkretnej liczby
iteracji na tym (np 100) jest znany i nie trzeba tego liczyc wiec wyliczenie tego
wynosi 0 czasu (i dlatego tez niekonkretne pytaia sa nie tylko niecialawe ale i
denerwujace (ziew))
>
> To jest tylko część bardziej złożonego problemu nad którym się głowię. Może on wyda
Ci się ciekawszy. Rozważmy funkcje rekurencyjne o następującej definicji:
>
> f(x) = a/2*x+b/2 - gdy x jest nieparzyste
> f(x) = x2 - gdy x jest parzyste
>
> a i b to jakieś liczby nieparzyste, a x może być dowolną liczbą naturalną.
Określając a i b dostajemy jakiś ciąg zdefiniowany za pomocą funkcji rekurencyjnej.
Najsłynniejszym z nich jest ciąg Collatza, którego dotyczy nierozwiązania do dziś
hipoteza. Ciąg Collatza dostaniemy dla a=3 i b=1. Weźmy pary a, b z przedziału
(-7,-5, ..., 5, 7). Będzie ich tyle co wariacji z powtórzeniami, 2-wyrazowych, w
zbiorze 8-elementowym, czyli 64. Dla każdej z takich 64 par a i b mamy zdefiniowaną
jakąś funkcję rekurencyjną. To co chcę oszacować, to ile zajmie policzenie w każdej z
tych 64 funkcji n iteracji dla kolejnych liczb naturalnych z przedziału od 1 do 2^n.
Np. dla a=5 i b=3 oraz n=3 mamy do policzenia iteracje dla liczb 1,2,3,...,8:
>
> 1,4,2,1
> 2,1,4,2
> 3,9,24,12
> 4,2,1,4
> 5,14,7,19
> 6,3,9,24
> 7,19,49,124
> 8,4,2,1
>
> Rzecz w tym, że interesują mnie duże n, rzędu minimum 50, a najlepiej rzędu 100.
Nie wiem, czy to jest bardziej interesujące? Na pewno żaden komputer tego nie policzy
w żadnym czasie np. dla n=128. Łatwo policzyć, że, jeśli średnio taki ciąg jest
liczony np. przez 100 mikrosekund, to obliczenia dla 64 par a i b zajmą
64*100*1/1000000*2^128 sekund, czyli może jeszcze nastąpi to przed śmiercią cieplną
Wszechświata, a może nie. Dlatego trzeba policzyć średni przypadek i ten, który
podałem jest średnim przypadkiem, można bowiem udowodnić, że średnio w tych ciągach w
przedziale liczb od 1 do 2^n wystąpi tyle samo mnożeń z dodawaniem, co dzieleń.
Natomiast potrzebuję to oszacować, bo zamierzam stworzyć algorytm, który będzie się
wymagał obliczenia losowego x z przedziału od 1 do 2^n dla losowej pary a i b. I chcę
wiedzieć ile średnio zajmie to czasu. W szczególności jakie maksymalne n mogę
przyjąć, aby taki pojedynczy ciąg był liczony około 0,1 mikrosekundy.

dla mnie to wogole nie jest interesujace, a jesli chcesz odpowiedz to raczej staraj
sie zadac pytanie w jakis zachecajacy sposob (bez glupot i dziur logicznych oraz w
miare krotki i nie mulace - bo ludzie sa leniwi, zwlaszcza na starosc ;c)


jak oszacowac czas obliczen napisalem
takie proste obliczenie jak dodawanie, mnozenie, i dzilenie przez dwa dla liczb
calkowitych mozesz optymistycznie zalozyc zajmuja minimum jeden cykl procesora na
dzialanie, ale oprocz arytmetyki moga byc tez tam movy (nalezaloby to napisac przy
pomoy komend w asemblerze by to sobie zwizualizowac), dlatego jabym to pomnozyl przez
2 lub 3, do tego jesli mowa o ifie to ten juz sie robi duzo drozszy (powiedzmy z
15-20 cykli)

takie cos
> f(x) = a/2*x + b/2 - gdy x jest nieparzyste
> f(x) = x2 - gdy x jest parzyste

(w zaleznosci od tego czym to naprawde jest, np czy to dzielenie przed dwa ma obcinac
bit..oraz czy przypadkiem nie da sie jakos usunac tego if) mozna zgrubnie oszacowac
na okolo 10 nanosekund (20-30 cykli) na iteracje (mowiac srednio optymistycznie)
(jesli mowimy o 64 bitowych intach, dla 128 bit bedzie chyab ze 2-3 razy wolniej)

napisz kod w c i sprawdz czy dziala (tj czy daje wogole poprawne wyniki - podejrzewam
ze zanim go napiszesz to przejdziesz przez 15 wersji w ktorych bedzie dawal
nipoprawne ;c i jak juz bedziesz to miec to nie ma problemu ze zmierzeniem tego - ale
jesli chesz zgrubne oszacowanie to z ogory ci mowie takie rzeczy zajmuja w okolicach
kilkudziesieciu cykli na iteracje (w zaleznosci od szczegolow)czyli w granicach
5,10,20, 30 nanosekund na iteracje (w zaleznosci od szczegolow)

oczywiste jest ze nie w czasie tego kawalka jest problem tylko w tej kombinatoryce a
ja trzeba jakos optymalizowac w inny sposob (matematycznie, hackerskom itd..nie che
mis ie w to wnikac bo to za nudne dla mnie)