Ostatnio interesuję się działaniem różnych generatorów liczb pseudolosowych. Podstawowym typem takiego generatora jest generator LCG:
https://en.wikipedia.org/wiki/Linear_congruential_generator
Wszędzie czytam, że z uwagi na architekturę procesorów mnożenie liczb 128-bitowych jest wolne, nawet dwa razy wolniejsze niż 64-bitowych. Umiem programować trochę tylko w Pythonie i testuję sobie takich generator:
import time
x = 83345345
def LCG(x):
x = (x * 254195286038525845401606965623589319477 + 128946049852079881334078718521384768725) & 340282366920938463463374607431768211455
#x = (x * 16653299995733013301 + 9999278969724736725) & 18446744073709551615
return x
start=time.time()
for i in range(20000000):
x=LCG(x)
end=time.time()
a=end-start
print (a)
I nieważne, czy użyję 64-bitowych stałych, czy 128-bitowych, dostaję podobne czasy. Podejrzewam, że to przypadłość Pythona, bo wszyscy w publikacjach używają C i C++ i przy tak nisko poziomowych językach pewnie będzie to widoczne, że procesor wyraźnie gorzej radzi sobie z arytmetyką 128-bitową.
Testuję też taki mixer bitów:
import time
x = 83345345
def PCG(x):
count1 = x >> 122
x1 = (x ^ (x >> 64)) & 18446744073709551615
low64 = (x1 >> count1) | (x1 << (64 - count1)) & 18446744073709551615
x2 = (x >> 64) & 18446744073709551615
count2 = low64 & 63
high64 = (x2 >> count2) | (x2 << (64 - count2)) & 18446744073709551615
x = (high64 << 64) | low64
return x
def LCG(x):
x = (x * 254195286038525845401606965623589319477 + 128946049852079881334078718521384768725) & 340282366920938463463374607431768211455
return x
start=time.time()
for i in range(20000000):
x=PCG(LCG(x))
end=time.time()
a=end-start
print (a)
Autorce wyszło, że, pomimo, że cały generator jest 128-bitowy (jego pełna nazwa to PCG XSL RR RR 128 (LCG):
https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf
Działa on dwa razy szybciej niż to:
import time
x = 83345345
def XSLRR(x):
count = x >> 122
x64 = (x ^ (x >> 64)) & 18446744073709551615
x = (x64 >> count) | (x64 << (64 - count)) & 18446744073709551615
return x
def LCG(x):
x = (x * 254195286038525845401606965623589319477 + 128946049852079881334078718521384768725) & 340282366920938463463374607431768211455
return x
start=time.time()
for i in range(20000000):
x=XSLRR(LCG(x))
end=time.time()
a=end-start
print (a)
Bo wersja XSLRR ucina połowę bitów w tym mixerze. Ja widzę, że PCG produkuje tylko 40% więcej bitów w tym samym czasie. Czy powinienem założyć, że w C++ wersja PCG będzie jednak dwa razy szybsza?
