🚀 go-pugleaf

> 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.