> Nawiasem pisząc, mi się spodobał generator whyhash. Dostałem do niego link
> tutaj na grupie. Jest ekstremalnie prosty, a zatem i ekstremalnie szybki:
>
> https://github.com/mmarszik/MRndCPP/blob/master/rnd_
wyhash64.h
>
> U mnie przeszedł test na ponad 11.5 terabajta danych:
> [
> rng=RNG_stdin, seed=0x4175954b
> length= 11.544 terabytes (2^43.529 bytes), time= 345602 seconds no anomalies in 327
test result(s)
> real 5760m3.249s
> user 5636m4.175s
> sys 121m47.242s
> ]
>
> https://github.com/mmarszik/MRndCPP/blob/master/use_
rnd_wyhash64_0.h

Przyjrzałem się dzisiaj temu wyhash64 i działa bardzo podobnie do moich generatorów,
a także generatorów PCG (Melissy O'Neil), tyle, że ja wprowadzam jeszcze rotacje poza
xorowaniem niskich i wysokich bitów (podobnie jak w PCG XSL-RR-RR). Prędkości moich
generatorów są porównywalne z wyhash64. Tyle, że tak jak pisałem według moich
wstępnych ustaleń (nie wiem, czy wszystkie klucze są tak samo dobre) moje generatory
(128-bitowe) można parametryzować za pomocą 2^256 różnych kluczy, czyli można uzyskać
2^256 różnych generatorów (a w każdym generatorze wciąż możemy oczywiście użyć
różnych seedów).

wyhash64 wydaje się być jednym z najszybszych generatorów obecnie na rynku, które
zdają testy (nie licząc prostego lehmer64):

https://github.com/lemire/testingRNG

Jedną z szybkich, świeżych propozycji jest generator ROMU:

https://www.romu-random.org/romupaper.pdf

ale ze względu na rotacje, to chyba nie będzie szybsze niż wyhash.

do góry

Bardzo szybki powinien też być ulepszony przeze mnie PCG Melissy O'Neil o nazwie
XSL-RR-RR (128-bitowy, choć można stworzyć też wersje 64-bitowe i 32-bitowe):

https://en.wikipedia.org/wiki/Permuted_congruential_
generator

Normalnie oblewa on dosyć szybko testy PractRand (kod w Pythonie, sam mixer pewnie
można napisać lepiej w C, może jako jakieś macro):

import struct
import sys

x = 83866140117348733064738400095399246193
#seed

def PCGmixer(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 * 47026247687942121848144207491837523525 +
83866140218348733064834828227924511723) & 340282366920938463463374607431768211455
return x

while 1 == 1:

x=LCG(x)
w=PCGmixer(x)

split = [(w >> x) & 0xFFFFFFFF for x in reversed(range(0, 128, 32))]
binary = struct.pack('IIII', split[0], split[1], split[2], split[3])
sys.stdout.buffer.write(binary)

Ale wystarczy dodać xorowanie kolejnych wyników:

import struct
import sys

x = 83866140117348733064738400095399246193

def PCGmixer(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 * 47026247687942121848144207491837523525 +
83866140218348733064834828227924511723) & 340282366920938463463374607431768211455
return x

w=0

while 1 == 1:

w_1 = w

x=LCG(x)
w=PCGmixer(x)

w_2 = w_1 ^ w

#split = [(w_2 >> x) & 0xFFFFFFFF for x in reversed(range(0, 128, 32))]
#binary = struct.pack('IIII', split[0], split[1], split[2], split[3])
#sys.stdout.buffer.write(binary)

Żeby zdawał on testy. Oczywiście sam PCGmixer wydłuża czas pracy istotnie (względem
bazowego LCG), ale pewnie można go wykonywać szybciej.

do góry

wtorek, 31 sierpnia 2021 o 02:36:05 UTC+2 M.M. napisał(a):
> On Tuesday, August 31, 2021 at 12:57:36 AM UTC+2, o...@g...com wrote:
> > poniedziałek, 30 sierpnia 2021 o 21:38:50 UTC+2 M.M. napisał(a):
> > > On Sunday, August 29, 2021 at 4:29:12 PM UTC+2, o...@g...com wrote:
> > > > Mogę otwierać szampana, a nawet dwa. Zaktualizowałem wersję do 0.94 - nie
pomogło, ale aktualizacja do 0.95 pomogła. Była to w takim razie prawdopodobnie
wyłącznie wina testów, nie moja, nie konsoli, nie Pythona.
> > > >
> > > > Mój generator zdaje testy:
> > > >
> > > > RNG_test using PractRand version 0.95
> > > > RNG = RNG_stdin, seed = unknown
> > > > test set = core, folding = standard(unknown format)
> > > >
> > > > rng=RNG_stdin, seed=unknown
> > > > length= 16 megabytes (2^24 bytes), time= 2.5 seconds
> > > > no anomalies in 153 test result(s)
> > > >
> > > > rng=RNG_stdin, seed=unknown
> > > > length= 32 megabytes (2^25 bytes), time= 6.5 seconds
> > > > no anomalies in 169 test result(s)
> > > >
> > > > rng=RNG_stdin, seed=unknown
> > > > length= 64 megabytes (2^26 bytes), time= 12.9 seconds
> > > > no anomalies in 182 test result(s)
> > > >
> > > > rng=RNG_stdin, seed=unknown
> > > > length= 128 megabytes (2^27 bytes), time= 24.3 seconds
> > > > no anomalies in 199 test result(s)
> > > >
> > > > rng=RNG_stdin, seed=unknown
> > > > length= 256 megabytes (2^28 bytes), time= 45.5 seconds
> > > > no anomalies in 217 test result(s)
> > > >
> > > > rng=RNG_stdin, seed=unknown
> > > > length= 512 megabytes (2^29 bytes), time= 86.5 seconds
> > > > no anomalies in 232 test result(s)
> > > > rng=RNG_stdin, seed=unknown
> > > > length= 1 gigabyte (2^30 bytes), time= 167 seconds
> > > > no anomalies in 251 test result(s)
> > > >
> > > > rng=RNG_stdin, seed=unknown
> > > > length= 2 gigabytes (2^31 bytes), time= 327 seconds
> > > > no anomalies in 269 test result(s)
> > > >
> > > > rng=RNG_stdin, seed=unknown
> > > > length= 4 gigabytes (2^32 bytes), time= 645 seconds
> > > > no anomalies in 283 test result(s)
> > > >
> > > > rng=RNG_stdin, seed=unknown
> > > > length= 8 gigabytes (2^33 bytes), time= 1283 seconds
> > > > no anomalies in 300 test result(s)
> > > >
> > > > rng=RNG_stdin, seed=unknown
> > > > length= 16 gigabytes (2^34 bytes), time= 2557 seconds
> > > > no anomalies in 315 test result(s)
> > > >
> > > > rng=RNG_stdin, seed=unknown
> > > > length= 32 gigabytes (2^35 bytes), time= 5096 seconds
> > > > no anomalies in 328 test result(s)
> > > >
> > > > rng=RNG_stdin, seed=unknown
> > > > length= 64 gigabytes (2^36 bytes), time= 10170 seconds
> > > > no anomalies in 344 test result(s)
> > > >
> > > > rng=RNG_stdin, seed=unknown
> > > > length= 128 gigabytes (2^37 bytes), time= 20316 seconds
> > > > no anomalies in 359 test result(s)
> > > >
> > > > Aczkolwiek trzeba ich pewnie zrobić przynajmniej 2^40 bajtów. Jestem pewien,
że gdzieś powyżej 128 GB konsola mi się wyłączyła, pomimo, że zostawiłem ją na noc
włączoną, razem z laptopem. Mam nadzieję, że sytuacja się nie powtórzy i był to
przypadek.
> > > Gratulacje.
> > >
> > > Kilka pytań:
> > >
> > > Czy możesz gdzieś zamieścić zrozumiały kod samego (wyizolowanego) generatora w
> > > celu przeczytania kodu?
> > >
> > > Jakimi generatorami i generalnie jakim algorytmami wzorowałeś się podczas
pisania tego generatora?
> > >
> > > Czy mogę Twój generator dorzucić do mojej biblioteki i zrobić testy takie jak
innych generatorów? - ale to
> > > kiedyś w przyszłości, pod warunkiem że znajdę czas i będę miał jakiś serwer do
testów.
> > >
> > > Pozdrawiam
> > Mam pewne plany co do tych generatorów i właściwie aktualnie szukam możliwości
ich publikacji lub komercjalizacji, dlatego z publikacją wolałbym zaczekać. Te
generatory są dosyć interesującym wynalazkiem z kilku powodów:
> > - inspiracją były ciągi Collatza i pewne generalizacje tego rodzaju funkcji,
teoria stojąca za tymi generatorami jest moim zdaniem naprawdę ciekawa,
> > - generatory mają klucze, ale są łatwo odwracalne i same w sobie nie są
kryptograficznie bezpieczne, jakkolwiek można ich użyć jako budulców algorytmu
szyfrującego (stworzyłem taki algorytm),
> > - wciąż są słabo poznane, poza tym, że dla kilku przetestowanych kluczy
generowały dobre wyniki, nie ma teorii, która określałaby ich okres (dla prawdziwie
losowej n-elementowej permutacji spodziewamy się okresu (n+1)/2, ale to założenie
będzie prawdziwe, jeśli generator daje bardzo dobrej jakości liczby pseudolosowe),
> > - potrafią generować bloki dowolnej wielkości, przy użyciu odpowiednio dużych
kluczy,
> > - są szybkie (okolice prędkości uzyskiwanych przez generatory PCG).
> Jeszcze jedno, w sieci coś jest o generatorach na bazie ciągu collatza:
> https://link.springer.com/article/10.1007/s41870-019
-00307-9

Cześć. Minęły 2 lata, a ja opatentowałem te generatory PRNG z autorem wspomnianej
publikacji - profesorem Danem Tamirem. W międzyczasie wielokrotnie zmieniałem schemat
i właściwie to opatentowaliśmy całą klasę generatorów, tak szeroką, że nie do końca
zbadałem wszystkie możliwe warianty - taka strategia ma na celu głównie ochronę
właściwego generatora przed ominięciem patentu. Ale sprawa jest wciąż delikatna, bo
mamy tzw. provisional patent, ważny tylko na rok i zapewniający niepełną ochronę. Po
roku podejmiemy decyzję co dalej (czy porzucamy wniosek, czy przekształcamy go w
pełen patent).

Schemat może posłużyć do zastosowań kryptograficznych, stąd w ogóle zacząłem myśleć o
patencie, w przeciwnym razie raczej nie patentowałbym prostego generatora PRNG. Z
uwagi na mój brak doświadczenia w kryptografii, zdecydowałem się zacząć od próby
komercjalizacji prostych generatorów PRNG (a następnie sfinansować w ten sposób
badania nad zastosowaniami kryptograficznymi, jeżeli nie znajdą się chętni do
współpracy). I nad tym obecnie zaczynamy pracować (celujemy m.in. w instytucje
badawcze wykorzystujące symulacje Monte Carlo, branżę AI, gry, przetwarzanie obrazów,
głównie za pomocą metody Monte Carlo path tracing). Jednocześnie będę szukał kontaktu
z naukowcami, którzy chcieliby podjąć z nami współpracę w celu opracowania schematów,
analizy i publikacji naukowej dotyczącej zastosowań kryptograficznych (głównie myślę
o funkcji hashującej i szyfrze strumieniowym, które stworzyłem, ale nie mam
odpowiedniej wiedzy, by ocenić i ich bezpieczeństwo, tzn. przeanalizować pod kątem
wszelkich znanych współcześnie ataków kryptograficznych).

Gdybyś nadal chciał przetestować mój generator, to tu jest wersja 128-bitowa:

https://pastebin.com/mJiU8Dsk

Tu jest wersja 64-bitowa:

https://pastebin.com/qMrqmiue

Oraz najszybsza w przeliczeniu na cykle na bajt wersja 128/64-bitowa (zwraca
128-bitów, ale działa głównie na arytmetyce 64-bitowej):

https://pastebin.com/AHz88Ldj

Wszystkie wersje zdają testy PractRand powyżej gwarantowanego okresu minimalnego (co
widać w pomniejszonych wersjach 16-bitowej oraz 32-bitowej). Oznacza to, że wersji
128 bitowej można używać bez ryzyka statystycznych anomalii aż do 2^128
wygenerowanych liczb, a wersji 64-bitowych aż do 2^64 wygenerowanych liczb. Nie
trzeba się też martwić problemem urodzinowym i nie przekraczać użycia pierwiastka z
okresu generatora, bowiem są to generatory chaotyczne i nie mają struktury
pojedynczego cyklu. Inicjalizacja może być dowolna, pod warunkiem liczby c[0], która
musi być nieparzysta. Generatorowi może zająć kilka iteracji zanim wypełni swój stan
bitami równomiernie, jeżeli zainicjujemy go niewielką liczbą. Do tego celu można użyć
inicjalizatora lub po prostu zainicjować generator losową liczbą. Ponadto można
uzyskać 2^64 (w wersji 64-bitowej) lub 2^128 (w wersji 128-bitowej) niezależnych
strumieni liczb, dla każdej unikalnej inicjalizacji unikalną liczbą nieparzystą. Przy
inicjalizacji kolejno następującymi po sobie liczbami nieparzystymi niektóre bity
niskiego rzędu mogą być skorelowane, choć PractRand nie umie tego wykryć. Aby uniknąć
korelacji, należy pominąć odpowiednio 48 lub 32 pierwsze wyniki, do czego może
posłużyć inicjalizator lub inicjować kolejne strumienie losowymi liczbami. Z uwagi na
fakt, że każdy unikalnie zainicjowany generator tworzy unikalny strumień liczb - nie
ma ryzyka tzw. overlapping - nachodzenia na siebie dwóch sekwencji (nie poruszamy się
po jednym i tym samym cyklu, każda inicjalizacja generuje swoją ścieżkę do cyklu o
gwarantowanej minimalnej długości i swój unikalny cykl).

do góry

W wersji 128/64-bitowej wkradł się błąd. Poprawione:

https://pastebin.com/pFq4ATy0

do góry

W wersji 128/64-bitowej wkradł się błąd. Poprawione:

https://pastebin.com/SFzE0wv1

do góry

W wersji 128/64-bitowej wkradł się błąd. Poprawione:

https://pastebin.com/NKcKveDT

do góry

Wyniki testów prędkości za pomocą repozytorium prof. Lemire, do którego dołączyłem
całkiem sporo generatorów, w tym moje CG:

https://github.com/lemire/testingRNG

mersennetwister32 : 0.68 cycles per byte
pcg32 : 0.73 cycles per byte
widynski32 : 0.81 cycles per byte
trivium32 : 1.99 cycles per byte
xorshift_k5 : 0.68 cycles per byte
xorshift_k4 : 0.72 cycles per byte
mitchellmoore : 0.83 cycles per byte
xorshift32 : 0.80 cycles per byte
rand : 1.29 cycles per byte

aesdragontamer : 0.23 cycles per byte
aesctr : 0.21 cycles per byte
lehmer64 : 0.36 cycles per byte
trivium64 : 0.88 cycles per byte
xorshift1024star : 0.52 cycles per byte
xorshift1024plus : 0.40 cycles per byte
xorshift128plus : 0.34 cycles per byte
wyhash64 : 0.29 cycles per byte
wyrand : 0.27 cycles per byte
xoroshiro512plus : 0.40 cycles per byte
xoroshiro128plus : 0.37 cycles per byte
xoroshiro256plus : 0.37 cycles per byte
GMWC256 : 0.53 cycles per byte
MWC256 : 0.31 cycles per byte
SFC64 : 0.57 cycles per byte
splitmix64 : 0.28 cycles per byte
pcg64 : 0.42 cycles per byte
PCG-DXSM : 0.42 cycles per byte
xoroshiro128plusplus : 0.34 cycles per byte
xoroshiro256plusplus : 0.38 cycles per byte

CG64 : 0.43 cycles per byte
CG128-64 : 0.23 cycles per byte
CG128 : 0.30 cycles per byte

do góry