Czy numpy przyspieszy działania na dużych liczbach w Pythonie?

[[e-mail]]

Potrzebuję wykonać w Pythonie tego typu operacje:

s1 = s0*k1 + k2

s2 = s1*k1 + k2

i tak dalej, powiedzmy kilkadziesiąt iteracji. Chodzi o duże liczby, głównie 128-bitowe. Czy numpy jakkolwiek może to przyspieszyć? Jeśli tak, to jak tego użyć?

[slawek]

Potrzebuję wykonać w Pythonie tego typu operacje:s1 = s0*k1 + k2s2 = s1*k1 + k2i tak dalej, powiedzmy kilkadziesiąt iteracji. Chodzi o duże liczby, głównie 128-bitowe. Czy numpy jakkolwiek może to przyspieszyć? Jeśli tak, to jak tego użyć?

1. Numpy jest proste aż do bólu, ale AFAIK liczy float pointy na
liczbach 64 bitowych IEEE 754, czyli na 80 bitowym FPU jeżeli to
zgodne z x86 (a właściwie x87). Chyba że jednak na SEE2 lub
AVX.

2. Python jest raczej mało wydajny, porównując z C lub Fortranem.
I oczywiście Asemblerem - w tym da się użyć SIMD co naprawdę daje
kopa.

3. CUDA itp. - jest do tego jakiś moduł w Pythonie (do wszystkiego
jest jakiś moduł) - patrz pypi. To powinno być prawie
to.

4. Ogólnie problem to brak 128 bitowych FPU - tzn. brak hardware.

0. Nie piszesz czy są to liczby float point. Nota bene, da się
liczyć nie tylko na int-ach, ale także na fixed-point, ułamkach
zwyczajnych...

-1. Jeżeli to kilkadziesiąt takich operacji liniowych... na cały
program... to wydajność nie ma znaczenia.

-2. Operacje jakie chcesz robić to mnożenie y = A x, gdzie y i x
są wektorami, A jest macierzą. Może być opłacalne
zdiagonalizowanie macierzy A (czyli transformacja U y = U A U^-1
U x), bo wtedy wielokrotne mnożenia się trywializują. Patrz też
wartości i wektory własne.

-3. No i kwestia - duże liczby (większe niż 10^310), czy liczby z
dużą liczbą cyfr znaczących, np. 0.123456789123
456789123456789123455667789 ?


----Android NewsGroup Reader----
http://usenet.sinaapp.com/

[[e-mail]]

Trochę się zmieniło. Okazało się, że mogę tu skrócić modulo, a w związku z tym zastosować "&", zaś dzielenia przez 2 zastąpić ">>".

a=333
b=555
c=777
d=999
x=12345

mask128 = 2**4-1

for i in range(128):
if x & 1:
x=((x * a + b) >> 1) & mask128
else:
x=(x * (c >> 1) + d) & mask128
s=10//2
print(x)

Tak to teraz wygląda. W tej chwili matematyki jest tu już mniej. Wciąż pozostają jednak mnożenia z dodawaniem (ale coraz mniej widzę tu pola do przyspieszeń). Takich pętli dla różnych a, b, c, d, x muszę mieć 20 w programie. Działamy tylko na liczbach całkowitych, a, b, c, d mogą być też ujemne.

Post by slawek
3. CUDA itp. - jest do tego jakiś moduł w Pythonie (do wszystkiego
jest jakiś moduł) - patrz pypi. To powinno być prawie
to.

Ok, poszukam.

Post by slawek
-2. Operacje jakie chcesz robić to mnożenie y = A x, gdzie y i x
są wektorami, A jest macierzą. Może być opłacalne
zdiagonalizowanie macierzy A (czyli transformacja U y = U A U^-1
U x), bo wtedy wielokrotne mnożenia się trywializują. Patrz też
wartości i wektory własne.

Zapomniałem dodać, że nie można założyć, że te operacje będą wykonywane pod rząd. Jak widzimy w pętli jest warunek, który jest spełniony dosyć chaotycznie i wtedy zmieniamy współczynniki. A zdaje się, że powyższa operacja miałaby sens tylko dla wielu mnożeń pod rząd?

[[e-mail]]

Oczywiście mask128 = 2**128-1, ma być równe 2**128-1. W kodzie jest błąd.

[slawek]

Post by ***@gmail.com
for i in range(128)

Pentium wyciągało około miliard operacji zmiennoprzecinkowych na
sekundę jakieś 20 lat temu... nie ma sensu bawić się w
przyspieszanie, optymalizacje itp. rękodzieło. Bo te 10 pętli po
128 i tak zajmie ułamki sekundy i to nawet na jakimś
ARM.

Zastanowić się można jedynie czy to ma być Python - lubię Pythona
za całokształt ale tu bardziej pasuje C. Tak czy siak dłużej
będzie trwało uruchamianie programu - niż same obliczenia. A
największym złodziejem czasu jest print wewnątrz pętli
for.

Na poziomie Pythona - 1000 razy wolniejszy niż C - nie ma różnicy
pomiędzy shift a mnożeniem. Zwłaszcza jak uruchamia się program
na współczesnym dużym CPU (z jednotaktowym mnożeniem). Rożnica
mogłaby być przy np. 8 bitowych mikrokontrolerach PIC (nie mają
hardwareowego mnożenia, za to kosztują grosze) - programowanych w
C ew. Asemblerze.


Co innego jeżeli to ma być np. liczone dla każdego pikselka w
transmisji 8K...


----Android NewsGroup Reader----
http://usenet.sinaapp.com/