Article View: pl.comp.programming
Article #216583Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128
From: Piotr Chamera
Date: Fri, 13 Dec 2019 07:34
Date: Fri, 13 Dec 2019 07:34
19 lines
3142 bytes
3142 bytes
W dniu 2019-12-13 o 06:42, osobliwy nick pisze: > 166 mikrosekund wziąłem z wyliczeń Piotra Chamera. Z tego co Ty napisałeś wynika zaś, że można to zrobić 50 razy szybciej. 10 nanosekund dla 64-bitowych liczb na iterację, dla 128-bitowych - 3 razy wolniej, czyli 30 nanosekund. To daje 128*30=3840 nanosekund na 128 iteracji (czyli 3,84 mikrosekund). Wówczas wychodzi: > > 1000000/3,84*128/20*1/2^20 = 1,59 MB/s > > Nie rozumiem w takim razie tylko skąd taka rozbieżność pomiędzy tym co piszesz Ty, a tym co policzył Piotra Chamera. Muszę się odezwać, bo tu jakieś absurdy wychodzą. Napisałem na szybko zupełnie niezoptymalizowany program, który policzył przykładowy algorytm w 166 ms. O czym to świadczy? Tylko o tym, że bez wysiłku można taki czas uzyskać. Trzeba też wziąć pod uwagę, że jest to program zupełnie bez ograniczeń na to jak duże są liczby, czy są całkowite itp. Kolega fir oszacował, że ten sam algorytm można policzyć wielokrotnie szybciej i to też prawda. Szczególnie jeśli da się ustalić, że wszystko da się np. policzyć na 128 bitowych liczbach całkowitych bez znaku :) O ile to będzie szybciej okaże się kiedy ktoś to napisze w konkretnym języku, skompiluje i uruchomi na konkretnym procesorze (50 razy szybciej względem mojego przykładu jest jak najbardziej realne :).
Technical Details
Message-ID:
<qsveui$eop$1@dont-email.me>Path:
mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!news-1.dfn.de!news.dfn.de!feeder.erje.net!2.eu.feeder.erje.net!news.uzoreto.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mailReferences:
<b7426ee8-be56-48fc-9657-da5a18e0729b@googlegroups.com> <qs878c$luk$1@dont-email.me> <5b01b3a8-9042-4203-871a-13f166f671dd@googlegroups.com> <deb8cf44-96c2-4bfa-8b78-a1c4a28440ec@googlegroups.com> <862ac5c6-5ac5-4915-a8dc-77669b7b1cfd@googlegroups.com> <8db2ea36-8d5e-4eec-8fb2-819658614d57@googlegroups.com> <624af684-7168-4de7-a37b-fe77566845b0@googlegroups.com> <2833b474-3c9c-4562-8138-2812fd55a70a@googlegroups.com> <e4e5ba4b-11cd-4d3e-a7a9-84d858d96f9b@googlegroups.com> <0fc59400-31f6-4b9d-9253-da0a06bbe203@googlegroups.com> <a8322dc9-9879-4a6d-b0e8-1a47cdef5408@googlegroups.com>Show Full Headers
Complete Article Headers
Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!news-1.dfn.de!news.dfn.de!feeder.erje.net!2.eu.feeder.erje.net!news.uzoreto.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Piotr Chamera <piotr_chamera@poczta.onet.pl> Newsgroups: pl.comp.programming Subject: Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 Date: Fri, 13 Dec 2019 08:34:34 +0100 Organization: A noiseless patient Spider Lines: 19 Message-ID: <qsveui$eop$1@dont-email.me> References: <b7426ee8-be56-48fc-9657-da5a18e0729b@googlegroups.com> <qs878c$luk$1@dont-email.me> <5b01b3a8-9042-4203-871a-13f166f671dd@googlegroups.com> <deb8cf44-96c2-4bfa-8b78-a1c4a28440ec@googlegroups.com> <862ac5c6-5ac5-4915-a8dc-77669b7b1cfd@googlegroups.com> <8db2ea36-8d5e-4eec-8fb2-819658614d57@googlegroups.com> <624af684-7168-4de7-a37b-fe77566845b0@googlegroups.com> <2833b474-3c9c-4562-8138-2812fd55a70a@googlegroups.com> <e4e5ba4b-11cd-4d3e-a7a9-84d858d96f9b@googlegroups.com> <0fc59400-31f6-4b9d-9253-da0a06bbe203@googlegroups.com> <a8322dc9-9879-4a6d-b0e8-1a47cdef5408@googlegroups.com> Mime-Version: 1.0 Injection-Date: Fri, 13 Dec 2019 07:34:42 -0000 (UTC) Injection-Info: reader02.eternal-september.org; posting-host="82ef82f9b20f891106c6da5bffbd903e"; logging-data="15129"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/+Bm3i5jaS3m55siwnGuVV" User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.9.1 Cancel-Lock: sha1:KsAa6gXDaHjjexrVcPLOLtSks7k= In-Reply-To: <a8322dc9-9879-4a6d-b0e8-1a47cdef5408@googlegroups.com> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit