Email list hosting service & mailing list manager

Proposed PFN for SRFI 27 John Cowan (14 Jul 2020 01:52 UTC)
Re: Proposed PFN for SRFI 27 Marc Nieper-Wißkirchen (14 Jul 2020 09:36 UTC)
Re: Proposed PFN for SRFI 27 John Cowan (14 Jul 2020 17:21 UTC)
Re: Proposed PFN for SRFI 27 Marc Nieper-Wißkirchen (14 Jul 2020 18:17 UTC)
Re: Proposed PFN for SRFI 27 John Cowan (14 Jul 2020 18:39 UTC)

Re: Proposed PFN for SRFI 27 Marc Nieper-Wißkirchen 14 Jul 2020 18:17 UTC

Am Di., 14. Juli 2020 um 19:21 Uhr schrieb John Cowan <xxxxxx@ccil.org>:
>
> By definition no pseudo-random generator can generate an unbounded number of integers without looping, as that would require keeping an infinite amount of state.  As the period is finite, the range of generated values is finite too.

The infinite amount of state is no problem. For an implementation, in
which exact integers were truly unbounded, this would certainly be no
problem. For implementations existing in the real world, there are
practical bounds to the exact integers. It is enough if
"random-source-pseudo-randomize!" works within these boundaries. So
the bound you give for the MWC1029 would make this an implementation
that is indistinguishable from an ideal implementation and thus fine.

> <https://en.wikipedia.org/wiki/Pseudorandom_number_generator#Mathematical_definition>.

Take the sequence of the digits of all the prime numbers in
succession: 2, 3, 5, 7, 1, 1, 1, 3, 1, 7, 1, 9, 2, 3, 2, 9, ... It has
no period and the digits are uniformly distributed (in the sense of
the pseudo-random number generator definition), see [1]. Thus, we get
a PRG with no period. Its state is encoded in a natural number, namely
the index of the last digit produced. As the size of the state is
O(log N) of the number N of generated values N, the principal
unboundedness of the state does not matter for all practical purposes.

..
[1] https://en.wikipedia.org/wiki/Copeland%E2%80%93Erd%C5%91s_constant