-
X-Received: by 2002:a37:9146:: with SMTP id t67mr6932660qkd.98.1575537422748; Thu, 05
Dec 2019 01:17:02 -0800 (PST)
X-Received: by 2002:a37:9146:: with SMTP id t67mr6932660qkd.98.1575537422748; Thu, 05
Dec 2019 01:17:02 -0800 (PST)
Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!goblin2!goblin.
stu.neva.ru!newsfeed.xs4all.nl!newsfeed7.news.xs4all.nl!185.151.15.255.MISMATCH
!tr1.eu1.usenetexpress.com!feeder.usenetexpress.com!tr1.iad1.usenetexpress.com!
border1.nntp.dca1.giganews.com!nntp.giganews.com!g89no7343427qtd.0!news-out.goo
gle.com!w29ni135qtc.0!nntp.google.com!g89no7343417qtd.0!postnews.google.com!gle
groupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Thu, 5 Dec 2019 01:17:02 -0800 (PST)
In-Reply-To: <8...@g...com>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=5.172.255.191;
posting-account=Sb6m8goAAABbWsBL7gouk3bfLsuxwMgN
NNTP-Posting-Host: 5.172.255.191
References: <b...@g...com>
<qs878c$luk$1@dont-email.me>
<5...@g...com>
<d...@g...com>
<8...@g...com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <8...@g...com>
Subject: Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128
From: fir <p...@g...com>
Injection-Date: Thu, 05 Dec 2019 09:17:03 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 90
Xref: news-archive.icm.edu.pl pl.comp.programming:214507
[ ukryj nagłówki ]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)
Następne wpisy z tego wątku
- 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
- 14.12.19 01:59 osobliwy nick
- 14.12.19 12:14 fir
Najnowsze wątki z tej grupy
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- 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
Najnowsze wątki
- 2024-12-01 Pijani kierowcy
- 2024-12-01 "Chciałem zamówić kurs tym"
- 2024-11-30 Windykatorzy ścigają spadkobierców z mandat nieboszczyka za przekroczenie prędkości???
- 2024-11-30 Łódź => Technical Artist <=
- 2024-11-30 Lublin => Inżynier Serwisu Sprzętu Medycznego <=
- 2024-11-30 Warszawa => Microsoft Dynamics 365 Business Central Developer <=
- 2024-11-30 Bieruń => Team Lead / Tribe Lead FrontEnd <=
- 2024-11-30 Zielona Góra => Senior PHP Symfony Developer <=
- 2024-11-30 Gdańsk => Specjalista ds. Sprzedaży <=
- 2024-11-30 Lublin => Spedytor międzynarodowy <=
- 2024-11-30 Warszawa => Mid IT Recruiter <=
- 2024-11-30 Warszawa => Fullstack Developer <=
- 2024-11-30 Żerniki => Dyspozytor Międzynarodowy <=
- 2024-11-30 Warszawa => System Architect (background deweloperski w Java) <=
- 2024-11-30 Katowice => Key Account Manager (ERP) <=