eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingIle zajmie komputerowi mnożenie liczb rzędu 2^128Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128
  • 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)

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: