Article View: pl.comp.programming
Article #216564Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128
From: Radoslaw Szwed
Date: Wed, 04 Dec 2019 10:55
Date: Wed, 04 Dec 2019 10:55
19 lines
2255 bytes
2255 bytes
Użytkownik "Radoslaw Szwed" <radekszwed@pochta.fm> napisał w wiadomości news:qs7uv5$col$1@gioia.aioe.org... > > Użytkownik <osobliwy.nick@gmail.com> napisał w wiadomości news:b7426ee8-be56-48fc-9657-da5a18e0729b@googlegroups.com... > >> Cześć. Badam pewne funkcje pod kątem zastosowań kryptograficznych. I mam następujący problem. Muszę oszacować ile czasu zajmie >> mnożenie liczby 2^128-5, z dodawaniem. Konkretnie - w pierwszym kroku obliczamy (2^128-5)*2,5+2,5, następnie dzielimy całość >> przez 2. A potem znów wynik mnożymy razy 2,5 i dodajemy 2,5. I znów dzielimy wynik przez 2. Musimy w sumie wykonać 128 takich >> operacji, to jest 64 mnożenia z dodawaniem i 64 dzielenia przez 2. > >> Dosyć łatwo wykazać, że liczba końcowa będzie całkowita i każda liczba uzyskana po drodze też będzie całkowita. ... > > Naprawdę będzie całkowita? Tak z ciekawości sprawdziłem dla 2^64 > > 2^64 -5= 18446744073709551611 * 2,5= 46116860184273879027,5 +2,5= 46116860184273879030 /2 > =23058430092136939515 * 2,5 =57646075230342348787,5 +2,5 = 57646075230342348790 /2 = > 28823037615171174395 *2,5= 72057594037927935993,75 + 2,5 ... Coś mi się źle wymnożyło :)
Technical Details
Message-ID:
<qs83b4$11jl$2@gioia.aioe.org>Path:
mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!3.eu.feeder.erje.net!feeder.erje.net!weretis.net!feeder7.news.weretis.net!news.mixmin.net!aioe.org!.POSTED.MOzQkSx0KhOHYjsyuRHqSg.user.gioia.aioe.org!not-for-mailReferences:
<b7426ee8-be56-48fc-9657-da5a18e0729b@googlegroups.com> <qs7uv5$col$1@gioia.aioe.org>Show Full Headers
Complete Article Headers
Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!3.eu.feeder.erje.net!feeder.erje.net!weretis.net!feeder7.news.weretis.net!news.mixmin.net!aioe.org!.POSTED.MOzQkSx0KhOHYjsyuRHqSg.user.gioia.aioe.org!not-for-mail From: "Radoslaw Szwed" <radekszwed@pochta.fm> Newsgroups: pl.comp.programming Subject: Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 Date: Wed, 4 Dec 2019 11:55:47 +0100 Organization: Aioe.org NNTP Server Lines: 20 Message-ID: <qs83b4$11jl$2@gioia.aioe.org> References: <b7426ee8-be56-48fc-9657-da5a18e0729b@googlegroups.com> <qs7uv5$col$1@gioia.aioe.org> NNTP-Posting-Host: MOzQkSx0KhOHYjsyuRHqSg.user.gioia.aioe.org Mime-Version: 1.0 X-Complaints-To: abuse@aioe.org X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.5512 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2900.5512 X-Notice: Filtered by postfilter v. 0.9.2 X-Priority: 3 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit