🚀 go-pugleaf

W dniu 2019-12-04 o 00:19, osobliwy.nick@gmail.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.