% !TEX TS-program = LuaLaTeX
% !TEX encoding = UTF-8 Unicode 
% !TEX root = ../../mal-core.tex

\gdef\mujnazevCS{Generování pseudonáhodných čísel po cifrách}
\gdef\mujnazevEN{Generating pseudorandom numbers by digits}
\gdef\mujnazevPR{\mujnazevCS}
\gdef\mujnazevDR{\mujnazevEN}
\gdef\mujauthor{Pavel Stříž}

%\bonushyper

\nazev{\mujnazevCS}

\nazev{\mujnazevEN}

\author{\mujauthor}

%\Adresa{}

\Email{pavel@striz.cz}

\Abstrakt{V~článku autor představuje jednoduchý algoritmus na generování pseudonáhodných čísel po cifrách. To je užitečné u~sekvencí, jako je tomu u~obřích Rubikových kostek. Aby se autor vyhnul podmíněné pravděpodobnosti, vyřazuje nevhodná čísla jak jen to je nejdřív možné.}
\smallskip
\KlicovaSlova{Pseudonáhodná čísla, Python, R, JavaScript}

\Abstract{This article presents a~simple algorithm generating pseudorandom numbers by digits. It's useful for very long sequences, e.g. in experiments with huge Rubik's cubes. To avoid conditional probability along the way, the author discards unsuitable numbers as soon as possible.}
\smallskip
\KeyWords{Pseudorandom Numbers, PRNG, Python, R, JavaScript}


\section{Motivace}

Během kombinatorického zkoumání u~Rubikovy kostky jsem narazil na celou plejádu nových typů, více viz \href{https://www.youtube.com/watch?v=8cevWKDXPGY}{\tt www.youtube.com/watch?v=8cevWKDXPGY}. Co mě však zaujalo víc bylo, jak obrovské množství kombinací dostávám u~obřích virtuálních kostek. Např. u~kostky $150\times150\times150$ se dostávám na více jak 86~tisíc cifer. Začal jsem zkoumat, jaká omezení mají generátory pseudonáhodných čísel, ponevadž bych si rád takovou kostku zamíchal. Brzy lze zjistit, že nemůžu generovat sekvenci pohybů [FBLRUD], abych získal kostky rovnoměrně rozložené.


\section{Generování po cifrách}

Pokud bych generoval číslo od nuly po $10^D-1$, kde $D$ je počet cifer, nemám problém. Vygeneruji si sérii $D$ čísel v~intervalu 0--9 a~ty spojím. Problém nastává tehdy, pokud chci vygenerovat číslo 0 až $N$, kdy $N$ netvoří hranici $10^D-1$. Intuitivní řešení je, vygenerovat si sérii $D$ čísel a~na závěr srovnat číslo s~$N$. Pokud je větší, vyřadíme jej a~generování zopakujeme. U~čísel s~desítkami tisíc cifer to už stojí čas. Můj drobný nápad bylo zkusit vyřadit čísla dřív, než se vygeneruje celá $D$ várka.

Zvolil jsem si desítkovou soustavu, dobře se nad tím přemýšlí, ale každá cifra je reprezentována 8 bity. To by se dalo dál zefektivnit přejitím do binární soustavy, ale principu vyřazení se nevyhnu, pokud zrovna není horní hranice mocnina dvojky mínus jedna.


\section{Podmíněná pravděpodobnost}

Kdybych čísla nevyřazoval, dostal bych se do oblasti podmíněné pravděpodobnosti, uvedu příklad. Volím hodnotu v~intervalu 00--12: nemůžeme u~první cifry předpokládat 50\,\% na 50\,\%, ale 10/13 (0--9) versus 3/13 (10--12). Takový problém nemáme u~mocniny dvojky, např. 0--3.

\begin{tikzpicture}[nodes={draw, circle}, -Stealth, thick, minimum width=1cm, level distance=25mm]
\node{$<2?$} 
  child{node[label=above:{Ano}]{$<1?$}
    child{node[label=above:{Ano}]{0}}
    child{node[label=above:{Ne}]{1}}
    }
  child[missing]
  child{node[label=above:{Ne}]{$<3?$}
    child{node[label=above:{Ano}]{2}}
    child{node[label=above:{Ne}]{3}}
  };
\end{tikzpicture}
%
\hfill
\begin{tikzpicture}[nodes={draw, circle}, -Stealth, thick, minimum size=20mm, level distance=35mm, sibling distance=24mm]
\node{$0?$} 
  child{node[label=above:{Ano}]{00--09}}
  child{node[label=above:{Ne}]{10,11,12}
  };
\end{tikzpicture}

Zde je tato past při simulaci 100000 hodnot, interval 0--12.

Ukázka chybně generovaného postupu bez vyřazení čísel.
Má být $100000/13\doteq7692$. Je to $50000/10=5000$ (0--9) a~$50000/3\doteq16667$ (10--12).

\begin{verbatim}
Generuji hodnoty od nuly po 12 ...
Čítač 100000
Kolikrát se hodnoty opakují [5038, 5004, 
4998, 5048, 4942, 4956, 5015, 4998, 
4913, 5191, 16576, 16866, 16455]
Kontrolní počet 100000
Úspěch u generování 1.0
\end{verbatim}

Ukázka správného užití s~vyřazováním čísel. Má být a~je to $100000/13\doteq7692$. Vyřazené hodnoty se mi pohybovaly do 55\,\%.

\begin{verbatim}
Generuji hodnoty od nuly po 12 ...
Čítač 153543
Kolikrát se hodnoty opakují [7743, 7630, 
7621, 7796, 7610, 7645, 7695, 7787, 
7596, 7888, 7575, 7688, 7726]
Kontrolní počet 100000
Úspěch u generování 0.651283353848759
\end{verbatim}

Shrnu-li poznatky pro čtyřciferné číslo. Nevyřadím žádnou hodnotu, pokud jsem v~intervalu 0000--9999; vyřadím 90\,\% hodnot, pokud jsem v~intervalu 0000--1000. V~průměru vyřadím 45\,\% generovaných hodnot.


\section{Algoritmus}

Algoritmus je následující. U~každé cifry zkoumám, jestli je menší, rovna či větší než cifra u~horní hranice (spodní hranice je vždy nula). Pokud je menší, tento test nemusím u~dalších cifer provádět, složené číslo bude vždy menší než chtěné. Pokud je cifra rovna, musím test dál provádět. Pokud je cifra vyšší, složené číslo bude vyšší, generované číslo vyřadím a~začínám od začátku.

Zde je ukázka u~intervalu 0--4382. Pokud je například první cifra 2, všechny ostatní cifry mohou být libovolné v~intervalu 0--9, dostáváme například číslo 2155. Kdyby první cifra byla 4, musím testovat další cifry (mohu dostat 4122, ale třeba 4956), pokud by byla cifra 5--9, skládaná hodnota bude vždy vyšší než 4382 (např. 5407, 5328 ap.), a~hodnotu vyřadím.

\noindent\hfil
\begin{tikzpicture}[scale=0.8]
\draw[fill=red] (0,0) rectangle (4,10);
\pgfmathparse{-1}
\let\x=\pgfmathresult
\foreach \y in {0,...,9} {
\node at (-0.5,\y+0.5) {\y};
}
\foreach \y in {4,3,8,2} {
\pgfmathparse{\x+1}
\global\let\x=\pgfmathresult
\node at (\x+0.5,-0.5) {\y};
\draw[fill=green] (\x,0) rectangle +(1,\y+1);
\draw[fill=yellow] (\x,\y) rectangle +(1,1);
}
%\draw[fill=blue] (3,2) rectangle +(1,1);
\draw[thick] (0,0) grid +(4,10);
\end{tikzpicture}
%
\hspace{1cm}%
\begin{tikzpicture}[scale=0.8]
%\draw[fill=red] (0,0) rectangle (4,10);
\pgfmathparse{-1}
\let\x=\pgfmathresult
\foreach \y in {0,...,9} {
\node at (-0.5,\y+0.5) {\y};
}
\foreach \y in {2,1,5,5} {
\pgfmathparse{\x+1}
\global\let\x=\pgfmathresult
\node at (\x+0.5,-0.5) {\y};
}
\pgfmathparse{-1}
\let\x=\pgfmathresult
\foreach \y in {4,9,9,9} {
\pgfmathparse{\x+1}
\global\let\x=\pgfmathresult
\draw[fill=green] (\x,0) rectangle +(1,\y+1);
}
\draw[fill=yellow] (0,4) rectangle +(1,1);
\draw[thick] (0,0) grid +(4,10);
\end{tikzpicture}


\section{Softwarová implementace}

Na konci roku 2023 mohu říci, že svět vizualizace a~analýzy dat je bohatý. Nejčastěji se setkávám s~Pythonem, R a~D3js (JavaScript). Program je krátký, využil jsem toho, abych si zkusil všechny tři. Program jsem napsal v~Pythonu, za pomoci \url{https://www.javainuse.com/py2r} jsem převedl do R (jen jsem upravil \texttt{return} na \texttt{return()}), a~za pomocí \url{https://extendsclass.com/python-to-javascript.html} jsem převedl do JavaScriptu a~místo funkce \texttt{random.randint} jsem užil \texttt{Math.random()} a~knihovnu \texttt{random} jsem zakomentoval.

V~pozadí uvažuji tak, že volím číslo 0--4382, indexování od nuly. Indexování od jedné by bylo přičtení jedničky. Generuji na ukázku 4 čísla. Záporná čísla, čísla s~desetinnou čárkou získáme transformací. Pro názornost vypisuji i~úvodní nuly. Výstupem je textový řetězec, nikoliv číslo.

\subsection{Python}

\lstinputlisting[language=python,tabsize=2]{zdrojaky/striz-nahodna-cisla/po-cifrach-minimum.py}

Po spuštění dostávám:

\begin{lstlisting}
>python3 "po-cifrach-minimum.py"
Generuji 4 hodnot(y) od nuly po 4382 ...
0680
1961
1567
1665
\end{lstlisting}

\newpage
\subsection{R}

\lstinputlisting[language=r,tabsize=2]{zdrojaky/striz-nahodna-cisla/po-cifrach-minimum.R}

Po spuštění dostávám:

\begin{lstlisting}
>Rscript "po-cifrach-minimum.R"
[1] "Generuji 4 hodnot(y) od nuly po 4382 ..."
[1] "4257"
[1] "2710"
[1] "0809"
[1] "0611"
\end{lstlisting}

\subsection{JavaScript}

\lstinputlisting[language=,tabsize=2]{zdrojaky/striz-nahodna-cisla/po-cifrach-minimum.js}

Po instalaci NodeJS, \texttt{sudo apt install nodejs} mohu spustit \texttt{node po-cifrach-minimum.js.} 
%
Případně si vytvořím pomocný soubor a~otevřu si jej v~prohlížeči, např. \texttt{firefox po-cifrach-minimum.html}. Po zobrazení konzole, kombinace kláves Ctrl+Shift+I, dostanu žádané výstupy.

\lstinputlisting[language=html,tabsize=2]{zdrojaky/striz-nahodna-cisla/po-cifrach-minimum.html}



\subsection{Úvaha s~otazníkem}

Přemýšlel jsem interval rozdělit na několik částí, např. 0--9 na dvě (0--4 a~5--9). A~z~každé volit jedno číslo. Zajistil bych si rovnoměrné rozdělení dvou čísel bez opakujících se hodnot, ale přišel bych o~situace 1 a~2; 2 a~2; 8 a~9 apod. Asi je to špatný nápad, byť u~struktur s~tisíci ciframi by to nemuselo vadit. Nejspíš to chce jiný přístup.

\section{Otevřený problém}

Předchozí světový rekord u~řešení Rubikovy kostky má hranu délky $2^{15}$, viz \url{https://www.youtube.com/watch?v=xOJtLb_rPVg}, nový světový rekord dokonce $2^{16}$, viz \url{https://www.youtube.com/watch?v=y7J3sNR8aC4}. Je otázka, zda-li mohu na současných počítačích spočítat počet kombinací, s~přesností na jednotky, ze které bych pak jednu zvolil a~kostku vygeneroval, jak to vyžadují nová pravidla u~soutěží. Startovní bod nechť je pro zájemce \url{https://hlavolam.maweb.eu/number-of-combinations-for-rubiks-cube}.

\enlargethispage{\baselineskip}%
Autor se přiznává, že to nezkouší a~ani se raději nepouští do odhadu počtu cifer, což by byla přece jenom numericky přijatelnější úloha. Autor videa pro $2^{16}$ uvádí $1{,}379\cdot 10^{16655043947}$ kombinací. Cca 17GB soubor, s~tím se dá pracovat\ldots


\section{Zkušenost závěrem}

Používám editor SciTE. Instaluji si jej přes \texttt{sudo apt install scite}, spuštění je přes \texttt{scite}. Nebo jej instaluji přes příkaz \texttt{flatpak install} \texttt{flathub org.scintilla.SciTE}, spuštění přes \texttt{flatpak run org.scintilla.SciTE}. V~základní nabídce však není jazyk R. Je nutno smazat jazyk R v~souboru \texttt{/usr/share/scite/SciTEGlobal.properties}, je za \texttt{purebasic} před \texttt{rebol} v~bloku \texttt{imports.exclude}. Či odkomentovat a~zapsat \texttt{imports.include=r}.

Pro spuštění, klávesa F5, jsem si v~\texttt{$\sim$/.SciTEUser.properties} přidal \texttt{command.go.\$(file.patterns.r)=Rscript "\$(FileNameExt)"}. 

Byla to příjemná tečka u~mých bádání: spustit si R v~mém oblíbeném editoru rovnou.

% python3
% N=3
% math.factorial(7) * 3**6 * ( (24*(2**10)*math.factorial(12))**(N%2) ) * (math.factorial(24)**(math.floor((N-2)/2)) ) * ( (math.factorial(24)/math.factorial(4)**6)**( math.floor((N-2)/2)**2) )
% u N=30 kolaps

% Mathematica
% n=150; factorial(7) * 3**6 * ( (24*(2**10)*factorial(12))**(mod(n,2)) ) * (factorial(24)**(floor((n-2)/2)) ) * ( (factorial(24)/factorial(4)**6)**( floor((n-2)/2)**2) )

