Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #33537

Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128

Show all headers | View raw

W dniu czwartek, 5 grudnia 2019 03:11:18 UTC+1 użytkownik osobli...@gmail.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)

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy.nick@gmail.com - 2019-12-03 15:19 -0800
  Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 "Radoslaw Szwed" <radekszwed@pochta.fm> - 2019-12-04 10:41 +0100
    Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 "Radoslaw Szwed" <radekszwed@pochta.fm> - 2019-12-04 11:55 +0100
      Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy.nick@gmail.com - 2019-12-04 03:43 -0800
        Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 Piotr Chamera <piotr_chamera@poczta.onet.pl> - 2019-12-04 13:25 +0100
          Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy.nick@gmail.com - 2019-12-04 04:46 -0800
  Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 Piotr Chamera <piotr_chamera@poczta.onet.pl> - 2019-12-04 13:02 +0100
    Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy.nick@gmail.com - 2019-12-04 04:55 -0800
      Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2019-12-04 16:19 -0800
        Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy.nick@gmail.com - 2019-12-04 18:11 -0800
          Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy.nick@gmail.com - 2019-12-04 18:12 -0800
          Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2019-12-05 01:17 -0800
            Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy.nick@gmail.com - 2019-12-05 12:18 -0800
              Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2019-12-07 13:17 -0800
                Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy nick <osobliwy.nick@gmail.com> - 2019-12-10 18:09 -0800
                Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2019-12-12 05:09 -0800
                Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2019-12-12 05:16 -0800
                Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy nick <osobliwy.nick@gmail.com> - 2019-12-12 21:42 -0800
                Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 Piotr Chamera <piotr_chamera@poczta.onet.pl> - 2019-12-13 08:34 +0100
                Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy nick <osobliwy.nick@gmail.com> - 2019-12-13 16:59 -0800
                Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2019-12-13 06:17 -0800
                Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy nick <osobliwy.nick@gmail.com> - 2019-12-13 16:56 -0800
                Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2019-12-14 03:14 -0800
              Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2019-12-07 13:22 -0800
  Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 "Radoslaw Szwed" <radekszwed@pochta.fm> - 2019-12-10 10:29 +0100
    Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy nick <osobliwy.nick@gmail.com> - 2019-12-10 18:24 -0800
  Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy nick <osobliwy.nick@gmail.com> - 2019-12-11 21:15 -0800
  Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy nick <osobliwy.nick@gmail.com> - 2020-05-25 12:55 -0700
    Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2020-05-26 01:35 -0700
      Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy nick <osobliwy.nick@gmail.com> - 2020-05-27 12:12 -0700
        Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2020-05-27 13:58 -0700
          Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2020-05-27 14:03 -0700

csiph-web