przebiegów losowych
Potrzebuję 16-bitowego generatora przebiegów losowych. Jego głównych przeznaczeniem jest diagnostyka elektronicznych układów w czasie pracy w warunkach losowych i niepewnych. Wymyśliłem sobie, że zbuduję odpowiednią aparaturę pozwalającą na generowanie owych przebiegów. Ujmując to w skrócie, jest procek, który będzie generował na porcie równoległym przebieg losowy. Pogrzebałem w swojej szufladzie i padło na 8085. Zagadnienie nie jest aż tak złożone jakby mogło się wydawać a jego moc obliczeniowa w zupełności wystarczy. A z drugiej strony, to będzie miał okazję się wykazać zamiast oddawać się nieróbstwu w szufladzie.
Zanim przejdę do etapu budowy, to zrobiłem sobie badania symulacyjne. Można zaproponować wiele algorytmów dających różne rozkłady generowanych liczb. Mnie interesuje rozkład równomierny, czyli ma zostać wygenerowanych 65536 liczb i żadna nie może się powtórzyć (czyli ma wystąpić każda możliwa kombinacja). Na taką okoliczność ludzkość dopracowała się wzoru:
Xnew = M * Xold + Aczyli każda nowa liczba jest otrzymywana z poprzedniej poprzez pomnożenie jest przez stałą (stała multiplikatywna) i dodaniu innej stałej (stała addytywna). Oczywiście wystąpi problem pierwszej liczby losowej, ale to daje się rozwiązać w miarę prosty sposób. Przykładowo w przerwaniach od czasu inkrementowana jest zmienna w pamięci i jak użytkownik wciśnie przycisk „Start”, to stanowi ona wystarczająco dobrą startową zmienną losową.
By wiedzieć co w trawie piszczy i dokąd to zmierza, napisałem sobie w C program na PC do podstawowych badań. Z eksperymentów wyłonił się istotny wniosek: nie każda wartość stałych M i A daje oczekiwany rozkład generowanych liczb. Programik jest następujący:
Kod: Zaznacz cały
/*
Test 16-bitowego generatora liczb losowych
napisał: gaweł
Białystok, 04.2023
Licencja: CC BY 3.0
*/
#include <stdio.h>
#include <stdlib.h>
#define TabSize 0x10000
#define MultConst 65
#define AddConst 17
FILE * OutFile ;
unsigned short Status [ TabSize ] ;
int main(int argc, char *argv[])
{
unsigned long Loop ;
unsigned short RandomV ;
/*----------------------------------------------------------------*/
OutFile = fopen ( "random.txt" , "w" ) ;
for ( Loop = 0 ; Loop < TabSize ; Loop ++ )
Status [ Loop ] = 0 ;
RandomV = 1234 ;
fprintf ( OutFile , "Badania losowosci: stala multiplikatywna=%d, stala addytywna=%d\n" , MultConst , AddConst ) ;
for ( Loop = 0 ; Loop < TabSize ; Loop ++ )
{
RandomV = ( ( MultConst * RandomV ) + AddConst ) ;
fprintf ( OutFile , "Liczba losowa numer %d=%d\n" , Loop , RandomV ) ;
Status [ RandomV ] ++ ;
} /* for */ ;
for ( Loop = 0 ; Loop < TabSize ; Loop ++ )
{
fprintf ( OutFile , "Krotnosc liczby %d=%d\n" , Loop , Status [ Loop ] ) ;
} /* for */ ;
fprintf ( OutFile , "Tropienie statystyki\n" ) ;
for ( Loop = 0 ; Loop < TabSize ; Loop ++ )
{
if ( Status [ Loop ] == 0 )
fprintf ( OutFile , "blad liczba %d nie wygenerowala\n" , Loop ) ;
if ( Status [ Loop ] > 1 )
fprintf ( OutFile , "blad dla liczby %d wygenerowala się %d razy\n" , Loop , Status [ Loop ] ) ;
} /* for */ ;
fprintf ( OutFile , "Koniec statystyki\n" ) ;
fclose ( OutFile ) ;
return 0;
}
Z badań wynika, że najlepiej jest jak obie stałe są liczbami nieparzystymi. Przykładowo dla M=128 i A=9 program wpadł w pętlę i nie mógł się z niej wyrwać. Generował w kółko liczbę 17545 (17545 * 128 + 9 = 2245769, co po obcięciu do 16 bitów daje 17545). Zmiana stałej na M=129, A=9 daje już bardzo dobre rezultaty (żadna liczba się nie powtórzyła, zatem wystąpiło 65536 różnych liczb).
Również dobrze wypadły następujące pary: M=1025 A=7, M=1025 A=9, M=129 A=9, M=257 A=31, M=257 A=33, M=65 A=17, M=65 A=7. Dobór stałej M ma fundamentalne znaczenie. Starłem się dobrać stała multiplikatywną jako 2 do potęgi 0 plus 2 do potęgi jakiejś. To daje bardzo prostą realizację operacji mnożenia w prockach, które nie mają wymaganych instrukcji. By wyliczyć przykładowo nową liczbę dla parametrów M=257 i A=33 [Xnew=257 * Xold + 33 = (256 +1 ) * Xold + 33 = Xold * 256 + Xold + 33], mamy tylko sumowanie i operacje przesunięcia (nadaje się nawet dla 8085, który nie wiem, czy nawet wyciąga jednego MIPS’a).
Jeżeli ktoś jest zainteresowany wynikami badań, to zapraszam do lektury: