🌒 🎣 👉🏻 One-dimensional random real number generator 🧚🏿 ♥️ 🧑🏻‍🤝‍🧑🏻

The generation of a continuous uniform random variable turned out to be not an easy task, maybe because the very formulation of the problem is slightly absurd, because logically getting randomness means not finding a solution. However, leaving the simplest "how will it be in English - I don't know?", In articles devoted to algorithms, you will find works on creating only sequences of random numbers.

The "True Random" generator class uses physical phenomena and external constraints, so for example, to generate a decimal random number, you can find the recommendation to use an "atmospheric sensor". Naturally, as a lover of programming, this state of affairs seemed unfair to me, and for quite a long time "the problem was maturing." A variant of the solution, as expected from the formulation of the problem, appeared by chance, as an addition to the compression problem for packing hard spheres . The problem has not found an analytical solution, as there is no evidence of its absence yet, respectively, the source is quite suitable by external signs. However, I did not get more than infinite complexity in the reverse computation of the generator state.

The idea is not new, it was used, for example, in UNIX systems, but the reason why I cannot use the given algorithm as a function only came across a thorough study of its work. It is impossible to mathematically provide a finite fluctuation of an infinite number of parameters, therefore, if the generator is really continuous, then, in contrast to the arithmetic one, the number of its values is infinite. In practice, I have not encountered any failures in its work, but in total it is no more than months of work, although the "second law of thermodynamics" is also on my side, it does not provide strict logical reliability. Therefore, I do not pretend to use the algorithm as a function for systems with high reliability, but I admit that, together with additional modifications, the formal reliability can be significantly increased.

The source of a continuous uniformly distributed random variable is the interaction of an element with a boundary in a hard sphere model. The internal interaction of elements has a non-uniform distribution, this was verified on Diehard tests and therefore was excluded from the algorithm, but left in a simplified form for additional "mixing".

The uniform distribution on the surface of the sphere is a special distribution, and an additional transformation is required to go to the flat version. I discovered this transformation experimentally, I did not receive any help from mathematicians to form a hypothesis into a theorem, the answers ranged from "this is obvious" to "I am not involved in this area." This hypothesis sounds like this:

D - D-2 .

A two-dimensional projection of random points from the surface of a four-dimensional sphere. — .

. .

RandomSphere[Rn_: 2, Pn_: 1, Rb_: 1] := 
 Module[{i, j, m, p, r, s, S, X, Xi, Xj, Pm},
  X = Array[0 &, {Pn, Rn}]; Pm = Rn; s = 1/Sqrt[2];
  For[p = 1, p <= Pn, p++, i = RandomInteger[{1, Rn}]; S = 0; 
   For[r = 1, r <= Rn, r++,
    X[[p, r]] = 
     If[r != i, RandomReal[{-1, 1}], RandomChoice[{-1, 1}]]; 
    S += X[[p, r]]^2];
   X[[p]] *= Rb/Sqrt[S];
   For[m = 1, m <= Pm, m++,
    i = RandomInteger[{1, Rn}]; j = i; 
    While[i == j, j = RandomInteger[{1, Rn}]];
    Xi = X[[p, i]];
    Xj = X[[p, j]];
    X[[p, i]] = s (Xj - Xi);
    X[[p, j]] = s (Xj + Xi)]]; Return[X]]

, . , , , . , , .

Illustration of a two-dimensional projection of a "dusty surface in the light" for transparent 7,4,3 dimensional balls. — " " 7,4,3 .

, " " .

. , . , :

. : , . .

. , , N. O(N(N-N1)/2) O(N^2). , N^(1+1/D) , .

Diehard, Parking Test, "Numerous experiments prove" , , . , .

: , . , , , .

$r = {\ left ({\ frac {{Gamma \ left ({\ frac {M} {2} + 1} \ right)}} {{{\ pi ^ {\ frac {M} {2}}}} }} \ right) ^ {\ frac {1} {M}}}$

M - , Gamma- . R-r,

$R = {\ left ({V \ frac {{Gamma \ left ({\ frac {M} {2} + 1} \ right)}} {{{\ pi ^ {\ frac {M} {2}}} }}} \ right) ^ {\ frac {1} {M}}}$

V , . ,

$P \ left (x \ right) = \ begin {cases} {{{\ left ({\ frac {x} {{R - r}}} \ right)} ^ M}} & \ text {$ {0 \ le x \ le R - r} $} \\ 1 & \ text {$ {x> R - r} $} \ end {cases}$

X, r, .. 2r :

$X = \ frac {{{{\ left ({2r} \ right)} ^ M}}} {{{{\ left ({R - r} \ right)} ^ M}}} = \ frac {{{ 2 ^ M}}} {{{{\ left ({\ frac {R} {r} - 1} \ right)} ^ M}}}$

(T(T-1))/2- , , Y :

$Y = {\ left ({1 - X} \ right) ^ {\ frac {{T \ left ({T - 1} \ right)}} {2}}} = {\ left ({1 - \ frac { {{2 ^ M}}} {{{{\ left ({\ frac {R} {r} - 1} \ right)} ^ M}}}} \ right) ^ {\ frac {{T \ left ( {T - 1} \ right)}} {2}}} = {{\ rm {e}} ^ {- \ frac {{{2 ^ M}}} {{{{\ left ({\ frac {R } {r} - 1} \ right)} ^ M}}} \ frac {{T \ left ({T - 1} \ right)}} {2}}}$

, , . , , .

Comparison of analytics and received values in a mathematical package. Along the axes of the graph, the probability of overlap in percent and the fill factor in percent (100 * T / V). Calculation parameters M = 3, V = 8000 — . (100*T/V). M=3, V=8000

C# . , , Diehard .

- , "" . , , ParkingTest . . , . , , , .

, , . 10^8 , .

, , . , .

. , , , . , . " " - , , .

Initially, I was interested in the question of the existence of a source for practically direct receipt of just random floating point numbers. Therefore, the nature of this article is methodical, the algorithm does not pretend to compete in performance with hardware RNGs, and even more so with arithmetic PRNGs, because it contains, for example, calculating the root, but it can still be used as a duplicate or debug one.

Algorithm implementation in C #

One-dimensional random real number generator

More articles: