-
Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!3.eu.feeder.erj
e.net!feeder.erje.net!eternal-september.org!feeder.eternal-september.org!reader
01.eternal-september.org!.POSTED!not-for-mail
From: Piotr Chamera <p...@p...onet.pl>
Newsgroups: pl.comp.programming
Subject: Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128
Date: Wed, 4 Dec 2019 13:02:20 +0100
Organization: A noiseless patient Spider
Lines: 57
Message-ID: <qs878c$luk$1@dont-email.me>
References: <b...@g...com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 4 Dec 2019 12:02:20 -0000 (UTC)
Injection-Info: reader02.eternal-september.org;
posting-host="a89c5efaffd842868cfaa8fd3da806ce";
logging-data="22484";
mail-complaints-to="a...@e...org";
posting-account="U2FsdGVkX1/WZZcNRwX+eNS4iuKPS/vG"
User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:60.0) Gecko/20100101
Thunderbird/60.9.1
Cancel-Lock: sha1:H1jDUhuC/6dATFRYUXmpMOlFS2E=
In-Reply-To: <b...@g...com>
Content-Language: pl
Xref: news-archive.icm.edu.pl pl.comp.programming:214500
[ ukryj nagłówki ]W dniu 2019-12-04 o 00:19, o...@g...com pisze:
> 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. Ale nie chodzi mi o wynik, tylko o sprawdzenie ile
komputerowi zajmie policzenie czegoś takiego.
>
> Zaznaczę, że dla tak dużych liczb szybko tracona jest precyzja. Jestem laikiem, ale
z tego co wiem trzeba do tego albo specjalnych bibliotek albo jakichś własnych
rozwiązań do wykonywania obliczeń na tak dużych liczbach (które pewnie będą znacznie
wolniejsze, niż dedykowane, specjalne biblioteki, które stworzyli np. naukowcy do
różnych zaawansowanych obliczeń).
>
> Czy ktoś jest w stanie wykonać takie obliczenia i zmierzyć czas? A może możecie
podsunąć jakiś sensowny sposób oszacowania tego?
>
Rzeczywiście wychodzi liczba całkowita, ale dla pojedynczej takiej pętli
czas jest niemierzalny w tej implementacji lispu
CL-USER> (time
(let ((x (- (expt 2 128) 5)))
(dotimes (i 64)
(setf x (/ (+ (* x 5/2)
5/2)
2)))
x))
wynik:
542101086242752217003726400434970855712890620
(LET ((X (- (EXPT 2 128) 5))) (DOTIMES (I 64) (SETF X (/ (+ (* X 5/2)
5/2) 2))) X)
took 0 microseconds (0.000000 seconds) to run.
During that period, and with 6 available CPU cores,
0 microseconds (0.000000 seconds) were spent in user mode
0 microseconds (0.000000 seconds) were spent in system mode
22,592 bytes of memory allocated.
Dla 1000 powtórzeń pętli mamy
(DOTIMES (N 1000) (LET ((X (- (EXPT 2 128) 5))) (DOTIMES (I 64) (SETF X
(/ (+ (* X 5/2) 5/2) 2))) X))
took 166,000 microseconds (0.166000 seconds) to run.
9,762 microseconds (0.009762 seconds, 5.88%) of which was spent
in GC.
During that period, and with 6 available CPU cores,
156,250 microseconds (0.156250 seconds) were spent in user mode
0 microseconds (0.000000 seconds) were spent in system mode
22,528,064 bytes of memory allocated.
czyli wychodziłoby 166 mikrosekund na takie obliczenie.
Ale trzeba pamiętać, że to jest nieoptymalizowany program w lispie,
na pewno można napisać program, który policzy to szybciej.
Następne wpisy z tego wątku
- 04.12.19 13:25 Piotr Chamera
- 04.12.19 13:46 o...@g...com
- 04.12.19 13:55 o...@g...com
- 05.12.19 01:19 fir
- 05.12.19 03:11 o...@g...com
- 05.12.19 03:12 o...@g...com
- 05.12.19 10:17 fir
- 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
Najnowsze wątki z tej grupy
- 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
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
- Ideologia Polskiego Programisty wer.3
Najnowsze wątki
- 2024-05-04 Jaką kamerkę samochodową polecacie?
- 2024-05-04 Warszawa => Spedytor międzynarodowy <=
- 2024-05-04 Warszawa => Mid PHP Developer (Laravel) <=
- 2024-05-04 Warszawa => Inżynier DevOps (projekt JP) <=
- 2024-05-04 Gdańsk => Specjalista ds. Sprzedaży <=
- 2024-05-04 Łódź => Business Development Manager - obszar bezpieczeństwa IT <=
- 2024-05-04 Warszawa => Interactive/Experience Designer <=
- 2024-05-04 Berlin => IT Systems Administrator and Customer Support Engineer <=
- 2024-05-04 Warszawa => Mid IT Recruiter <=
- 2024-05-04 Odpowiedzialność PORTALU za reklamy
- 2024-05-04 Lunar Rover był elektrykiem. Ważył 35 kg Zasięg 80 km Na Księżycu w 1971 r.
- 2024-05-04 Marki => ERP Implementer <=
- 2024-05-04 Gdańsk => Head of International Freight Forwarding Department <=
- 2024-05-04 Marki => Wdrożeniowiec ERP <=
- 2024-05-03 Warszawa => Sprzedawca usług rekrutacyjnych <=