Generator liczb losowych
Generator liczb losowych zrealizowany na bazie mikroprocesora pochodzącego z „zamierzchłych” czasów. Niektóre z tych układów odcisnęły piętno na historii rozwoju techniki mikroprocesorowej. Takim przykładem był mikroprocesor z oferty Intel, o symbolu 8085.
Obecna oferta mikrokontrolerów jest bardzo szeroka. Ich różnorodne wyposażenie w układy peryferyjne zintegrowane w obrębie jednej struktury półprzewodnikowej, pozwala na realizację nawet złożonych projektów. Jednak zanim do tego doszło, konstruktorzy musieli wcześniej sami borykać się z problemami, o których obecnie wielu nawet nie wie, że istniały. Tytułowy mikroprocesor 8085 (fotografia 1) miał swoją premierę w 1976 roku i był znacząco ulepszoną wersją bardzo popularnego poprzednika 8080.
Fotografia 1
Potrzebowałem jakiegoś rozwiązania sprzętowego pozwalającego na diagnostykę i ocenę zachowania się układów cyfrowych w warunkach sterowania chaotycznego. Taką możliwość zapewni mi generator liczb losowych. Zagadnienie nie jest aż tak wymagające, by wykorzystać nowoczesne mikrokontrolery, mając w szufladzie układy, których świetność minęła już wiele lat temu. Z drugiej strony, zapotrzebowanie na zasoby (jako liczbę pinów dostępnych do użycia oraz wielkość pamięci operacyjnej) jest większe, niż możliwości wielu popularnych obecnych mikrokontrolerów. By sprostać tym potrzebom można uzupełnić podstawowy mikrokontroler o dodatkowe układy, jednak nie wszystkie mają możliwość prostej rozbudowy (szczególnie o dodatkową pamięć operacyjną). Nie bez znaczenia jest również możliwość wykorzystania układów, które od dawna zalegają na dnie szuflady – wykorzystania ich zamiast oddania do recyklingu złota. Dodatkowo jest to swoista podróż w głąb historii do pionierskich czasów, gdzie wszystko zależało od nas samych (wielkość pamięci, liczba portów oraz funkcjonalność dodatkowych kontrolerów do realizacji specyficznych operacji).
Algorytmiczne rozwiązanie generatora liczb losowych
Najbardziej znanym sposobem generowania liczb pseudolosowych jest metoda opracowana przez Lehmer’a, zwana LCG (ang. LCG – Linear Congruential Generator – liniowy generator kongruentny). Polega ona na obliczaniu kolejnych liczb pseudolosowych: zgodnie z prostą formułą, bazując na poprzedniej liczbie losowej (wynik obliczeń zawsze obcięty do 16-bitów):
Oczywiście algorytm wymaga pierwszej liczby losowej, określanej jako ziarno (ang. seed). Do celów testowych jako ziarno można wybrać dowolną liczbę 16-bitową, w rzeczywistej realizacji jest to wartość wygenerowana przez mikroprocesor w następujący sposób: mikroprocesor w każdym przerwaniu inkrementuje pewną 16-bitową zmienną. Użycie przycisku z klawiatury uruchamiającego generowanie liczb, bierze jako ziarno tę inkrementowaną liczbę (użytkownik uruchamiając przyciskiem generowanie liczb działa wystarczająco losowo, a mikroprocesor bierze od chwili włączenia zasilania ciągle inkrementowaną liczbę w obsłudze przerwania od upływu czasu). Zanim przystąpiłem do realizacji projektu sprawdziłem w komputerze działanie algorytmu. Napisałem prosty program (listing 1), który generował 65536 liczb (tyle jest różnych liczb 16-bitowych) i zliczał ich liczbę wystąpień:
#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;
}
Poprawnym wynikiem jest by każda liczba wygenerowała się jeden raz. Występujące w formule dwie wartości stałych mają istotny wpływ na generowane liczby. Okazuje się, że są kombinacje wartości stałych współczynników, w których formuła działa właściwie oraz takie, gdzie algorytm zapętla się, generując ciągle te same wartości. Przykładowo dla a=128 i b=9 gdy wygeneruje się liczba 17545, to jej następnikiem jest ta sama liczba (17545 * 128 + 9 = 2245769, która po obcięciu do 16 bitów daje 17545). Dobrym wariantem jest a = 129, b = 9 (wymagane operacje arytmetyczne dają się prosto realizować nawet w językach typu assembler) i ten wariant został wybrany.
(…)
——– ciach! ——–
To jest tylko fragment artykułu, którego pełna wersja ukazała się w majowym numerze czasopisma Zrozumieć Elektronikę (ZE 5/2026). Pełną wersję czasopisma znajdziesz pod tym linkiem. Natomiast niepełna, okrojona wersja, pozwalająca zapoznać się z zawartością numeru ZE 5/2026 znajduje się tutaj.
Andrzej Pawluczuk
apawluczuk@vp.pl
Uwaga! Wskazówki, jak nabyć pełne wersje dowolnych numerów ZE znajdują się na stronie:
https://piotr-gorecki.pl/n11.
