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?

do góry

Użytkownik <o...@g...com> napisał w wiadomości
news:b7426ee8-be56-48fc-9657-da5a18e0729b@googlegrou
ps.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 ...

do góry

Użytkownik "Radoslaw Szwed" <r...@p...fm> napisał w wiadomości
news:qs7uv5$col$1@gioia.aioe.org...
>
> Użytkownik <o...@g...com> napisał w wiadomości
news:b7426ee8-be56-48fc-9657-da5a18e0729b@googlegrou
ps.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 :)

do góry

> > 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 :)

Chyba tak. Kilka pierwszych wyrazów:

850705917302346158658436518579420528630

425352958651173079329218259289710264315

1063382396627932698323045648224275660790

531691198313966349161522824112137830395

1329227995784915872903807060280344575990

664613997892457936451903530140172287995

1661534994731144841129758825350430719990

830767497365572420564879412675215359995

2076918743413931051412198531688038399990

1038459371706965525706099265844019199995

do góry

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.

do góry

W dniu 2019-12-04 o 12:43, o...@g...com pisze:
>>> 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 :)
>
> Chyba tak. Kilka pierwszych wyrazów:
>
> 850705917302346158658436518579420528630
>
> 425352958651173079329218259289710264315
>
> 1063382396627932698323045648224275660790
>
> 531691198313966349161522824112137830395
>
> 1329227995784915872903807060280344575990
>
> 664613997892457936451903530140172287995
>
> 1661534994731144841129758825350430719990
>
> 830767497365572420564879412675215359995
>
> 2076918743413931051412198531688038399990
>
> 1038459371706965525706099265844019199995
>

Jeśli się gdzieś nie pomyliłem, to komplet wyników
pośrednich (po mnożeniu, dodawaniu i dzieleniu) to:

340282366920938463463374607431768211451
425352958651173079329218259289710264315
531691198313966349161522824112137830395
664613997892457936451903530140172287995
830767497365572420564879412675215359995
1038459371706965525706099265844019199995
1298074214633706907132624082305023999995
1622592768292133633915780102881279999995
2028240960365167042394725128601599999995
2535301200456458802993406410751999999995
3169126500570573503741758013439999999995
3961408125713216879677197516799999999995
4951760157141521099596496895999999999995
6189700196426901374495621119999999999995
7737125245533626718119526399999999999995
9671406556917033397649407999999999999995
12089258196146291747061759999999999999995
15111572745182864683827199999999999999995
18889465931478580854783999999999999999995
23611832414348226068479999999999999999995
29514790517935282585599999999999999999995
36893488147419103231999999999999999999995
46116860184273879039999999999999999999995
57646075230342348799999999999999999999995
72057594037927935999999999999999999999995
90071992547409919999999999999999999999995
112589990684262399999999999999999999999995
140737488355327999999999999999999999999995
175921860444159999999999999999999999999995
219902325555199999999999999999999999999995
274877906943999999999999999999999999999995
343597383679999999999999999999999999999995
429496729599999999999999999999999999999995
536870911999999999999999999999999999999995
671088639999999999999999999999999999999995
838860799999999999999999999999999999999995
1048575999999999999999999999999999999999995
1310719999999999999999999999999999999999995
1638399999999999999999999999999999999999995
2047999999999999999999999999999999999999995
2559999999999999999999999999999999999999995
3199999999999999999999999999999999999999995
3999999999999999999999999999999999999999995
4999999999999999999999999999999999999999995
6249999999999999999999999999999999999999995
7812499999999999999999999999999999999999995
9765624999999999999999999999999999999999995
12207031249999999999999999999999999999999995
15258789062499999999999999999999999999999995
19073486328124999999999999999999999999999995
23841857910156249999999999999999999999999995
29802322387695312499999999999999999999999995
37252902984619140624999999999999999999999995
46566128730773925781249999999999999999999995
58207660913467407226562499999999999999999995
72759576141834259033203124999999999999999995
90949470177292823791503906249999999999999995
113686837721616029739379882812499999999999995
142108547152020037174224853515624999999999995
177635683940025046467781066894531249999999995
222044604925031308084726333618164062499999995
277555756156289135105907917022705078124999995
346944695195361418882384896278381347656249995
433680868994201773602981120347976684570312495
542101086242752217003726400434970855712890620

ale dalsze iteracje już są ułamkowe.

dla 2^64 całkowite są tylko do 32 iteracji:

18446744073709551611
23058430092136939515
28823037615171174395
36028797018963967995
45035996273704959995
56294995342131199995
70368744177663999995
87960930222079999995
109951162777599999995
137438953471999999995
171798691839999999995
214748364799999999995
268435455999999999995
335544319999999999995
419430399999999999995
524287999999999999995
655359999999999999995
819199999999999999995
1023999999999999999995
1279999999999999999995
1599999999999999999995
1999999999999999999995
2499999999999999999995
3124999999999999999995
3906249999999999999995
4882812499999999999995
6103515624999999999995
7629394531249999999995
9536743164062499999995
11920928955078124999995
14901161193847656249995
18626451492309570312495
23283064365386962890620
116415321826934814453105/4
582076609134674072265545/16
2910383045673370361327805/64
14551915228366851806639345/256
72759576141834259033198005/1024
363797880709171295165995145/4096
1818989403545856475829996205/16384
9094947017729282379150062945/65536
45474735088646411895750642405/262144
227373675443232059478754522745/1048576
1136868377216160297393777856605/4194304
5684341886080801486968910254545/16777216
28421709430404007434844635158805/67108864
142108547152020037174223511338345/268435456
710542735760100185871118898869005/1073741824
3552713678800500929355599863054145/4294967296
17763568394002504646778020790107205/17179869184
88817841970012523233890189849881945/68719476736
444089209850062616169451292846793405/274877906944
2220446049250313080847257838623501745/1099511627776
11102230246251565404236294690675647605/4398046511104
55511151231257827021181495443610793545/1759218604441
6
277555756156289135105907565178984189805/703687441776
64
1387778780781445675529538177738641837345/28147497671
0656
6938893903907228377647692296068092740005/11258999068
42624
34694469519536141888238467109839997913145/4503599627
370496
173472347597680709441192358067198126418205/180143985
09481984
867361737988403547205961880407983179500945/720575940
37927936
4336808689942017736029809762327886087144405/28823037
6151711744
21684043449710088680149050252791311194280745/1152921
504606846976
108420217248550443400745257028564079005638605/461168
6018427387904
542101086242752217003726308201250487165132545/184467
44073709551616

do góry

> ale dalsze iteracje już są ułamkowe.

Zgadza się. Traktujesz mnożenie z dzieleniem jako jedną operację. Natomiast są to
dwie operacje.

> dla 2^64 całkowite są tylko do 32 iteracji:

To też się zgadza. Zrobiłeś tak naprawdę 64 iteracje, wypisałeś tylko nieparzyste.
Ogólnie nie można tego w żaden sposób skrócić. Trzeba liczyć tak jak jest. Czyli
a*2,5+2,5=b. A dopiero później dzielimy przez 2.

To wynika z definicji funkcji, którą rozważam:

f(x) = 2,5*x+2,5 - gdy x jest nieparzyste

f(x) = x/2 - gdy x jest parzyste

Dla liczb 2^n-5 jest ją łatwo liczyć. Ale gdy spróbujemy 2^n-19, to nie ma dróg na
skróty. Kolejne wyrazy raz są nieparzyste, raz parzyste - brak wyraźnego wzorca. Stąd
w każdym trzeba sprawdzać ich parzystość i albo dzielić przez 2 albo mnożyć z
dodawaniem. Dlatego nie chciałem, żebyście stosowali jakieś skróty, czy uproszczenia
wynikające z matematyki, bo w większości przypadków nie da się ich zastosować.

do góry

> 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.

Dzięki za pomoc. Niestety to dużo za dużo. Spodziewałem się wielkości o dwa rzędy
mniejszej. Nawet optymalizacja nie sprawi chyba, że mogłoby to być 0,5 mikrosekundy,
nie?

Generalnie chciałbym, aby było to dokładnie 0,1 lub okolice tych czasów. Jest pewien
algorytm, który na procesorze klasy Pentium M o szybkości 1.7 GHz ma właśnie taką
wydajność szyfrowania, bo o szyfrowanie cały czas chodzi. Oczywiście działa on
zupełnie inaczej od mojego, ale muszę w takim razie tak dobrać parametry, aby zbliżyć
się do tej prędkości.

Czy byłbyś w stanie sprawdzić mniejsze przypadki, np. liczbę 2^100-5 dla 100
iteracji? Ogólnie znaleźć takie n, że dla n iteracji na liczbie 2^n-5 ten czas będzie
wynosił ok. 0,1 mikrosekundy?

do góry

W dniu środa, 4 grudnia 2019 13:55:15 UTC+1 użytkownik o...@g...com napisał:
> > 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.
>
> Dzięki za pomoc. Niestety to dużo za dużo. Spodziewałem się wielkości o dwa rzędy
mniejszej. Nawet optymalizacja nie sprawi chyba, że mogłoby to być 0,5 mikrosekundy,
nie?
>
> Generalnie chciałbym, aby było to dokładnie 0,1 lub okolice tych czasów. Jest
pewien algorytm, który na procesorze klasy Pentium M o szybkości 1.7 GHz ma właśnie
taką wydajność szyfrowania, bo o szyfrowanie cały czas chodzi. Oczywiście działa on
zupełnie inaczej od mojego, ale muszę w takim razie tak dobrać parametry, aby zbliżyć
się do tej prędkości.
>
> Czy byłbyś w stanie sprawdzić mniejsze przypadki, np. liczbę 2^100-5 dla 100
iteracji? Ogólnie znaleźć takie n, że dla n iteracji na liczbie 2^n-5 ten czas będzie
wynosił ok. 0,1 mikrosekundy?

troche nudne to pytanie, ale mozesz zalozyc ze proste operacje (dodawanie, mnozenei ,
shift) na 64 bitowym incie zajmuje w granicach 1-5 cykli (powiedzmy)

czyli w temacie zgrubnego ogarniecia mozesz zalozyc ze jedna operacje zajmuje okolo 1
nanosekunde

z tym ze taki mnozenie przez 2.5 to raczej jest mnozenie x przez dwa i dodanie polowy
x czyli

((x<<1) + (x>>1)) + 2.5

4 operacje, zalozmy ze to zajmuje 4 ns (mozliwe ze w praktyce zajmie ciut mniej, moze
ze 2 ns)

wiec sto iteracji tego zajmie 400 ns (200 ns?)

to przy zalozeniu ze mowimy o obliczeniach ktore sie da zrobi na 64 bitowych
integerach, jak robi sie to na 128 bitowych integereach mysle ze zjamie to minimum 2
razy tyle (zief)

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))

do góry

> 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.

do góry