-
Data: 2019-12-05 03:11:16
Temat: Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128
Od: o...@g...com szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]> 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.
Następne wpisy z tego wątku
- 05.12.19 03:12 o...@g...com
- 05.12.19 10:17 fir
- 05.12.19 21:18 o...@g...com
- 07.12.19 22:17 fir
- 07.12.19 22:22 fir
- 10.12.19 10:29 Radoslaw Szwed
- 11.12.19 03:09 osobliwy nick
- 11.12.19 03:24 osobliwy nick
- 12.12.19 06:15 osobliwy nick
- 12.12.19 14:09 fir
- 12.12.19 14:16 fir
- 13.12.19 06:42 osobliwy nick
- 13.12.19 08:34 Piotr Chamera
- 13.12.19 15:17 fir
- 14.12.19 01:56 osobliwy nick
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-05-17 ZŁOMNIK o pracy w TVN TURBO, nowych przepisach i współczesnej motoryzacji. Turbo Taryfa!
- 2024-05-17 Białystok => DevOps Engineer Conexa First (Contractor) <=
- 2024-05-17 Warszawa => Starszy inżynier oprogramowania (Rust) <=
- 2024-05-17 Zabrze => Junior HelpDesk <=
- 2024-05-17 Bieruń => Administrator i wdrożeniowiec Lotus Notes/Domino <=
- 2024-05-17 Warszawa => Senior Software Engineer PHP (BillPro) Contractor <=
- 2024-05-17 Warszawa => International freight forwarder <=
- 2024-05-17 Warszawa => Fullastack (Java) Developer <=
- 2024-05-17 Lublin => Business Development Manager - obszar bezpieczeństwa IT <=
- 2024-05-17 Warszawa => Mid PHP Developer (Laravel) <=
- 2024-05-17 Warszawa => Mid PHP Developer (Laravel) <=
- 2024-05-17 Warszawa => Senior PHP Developer (Symfony) <=
- 2024-05-18 wojna wojno a kredyt trzeba spłacać
- 2024-05-16 Samo rozładowywanie baterii trakcyjnej w elektryku.
- 2024-05-16 Warszawa => Senior PHP Developer (Symfony) <=