Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #395879 > unrolled thread
| Started by | Michael Sanders <porkchop@invalid.foo> |
|---|---|
| First post | 2025-12-22 08:48 +0000 |
| Last post | 2026-01-08 02:57 +0000 |
| Articles | 20 on this page of 185 — 25 participants |
Back to article view | Back to comp.lang.c
srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-22 08:48 +0000
Re: srand(0) James Kuyper <jameskuyper@alumni.caltech.edu> - 2025-12-22 06:44 -0500
Re: srand(0) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-12-22 13:18 +0100
Re: srand(0) James Kuyper <jameskuyper@alumni.caltech.edu> - 2025-12-22 12:13 -0500
Re: srand(0) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-12-22 18:41 +0100
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2025-12-22 20:45 +0200
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2025-12-22 21:16 +0000
Re: srand(0) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-12-22 22:19 +0100
Re: srand(0) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-12-22 22:57 +0100
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2025-12-23 11:18 +0200
Re: srand(0) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-12-23 10:54 +0100
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2025-12-23 13:50 +0200
Re: srand(0) James Kuyper <jameskuyper@alumni.caltech.edu> - 2025-12-23 18:29 -0500
Re: srand(0) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-12-23 16:30 -0800
Re: srand(0) antispam@fricas.org (Waldek Hebisch) - 2025-12-23 17:54 +0000
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2025-12-24 00:08 +0200
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2025-12-24 02:02 +0000
Re: srand(0) James Kuyper <jameskuyper@alumni.caltech.edu> - 2025-12-23 23:43 -0500
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2025-12-24 05:34 +0000
Re: srand(0) antispam@fricas.org (Waldek Hebisch) - 2025-12-24 09:00 +0000
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2025-12-24 12:12 +0200
Article of Melissa O'Nail (Was: srand(0)) Michael S <already5chosen@yahoo.com> - 2025-12-28 02:44 +0200
Re: Article of Melissa O'Nail antispam@fricas.org (Waldek Hebisch) - 2025-12-28 05:38 +0000
Re: Article of Melissa O'Nail Michael S <already5chosen@yahoo.com> - 2025-12-28 12:35 +0200
Re: Article of Melissa O'Nail Michael S <already5chosen@yahoo.com> - 2026-01-05 14:21 +0200
Re: Article of Melissa O'Nail antispam@fricas.org (Waldek Hebisch) - 2026-01-07 10:51 +0000
Re: Article of Melissa O'Nail Michael S <already5chosen@yahoo.com> - 2026-01-08 14:03 +0200
Re: Article of Melissa O'Nail Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-01-08 09:40 -0800
Re: srand(0) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-01-08 09:26 -0800
Re: srand(0) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-12-24 13:48 -0800
Re: srand(0) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-01-07 08:41 -0800
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2026-01-08 01:06 +0200
Re: srand(0) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-02-03 05:26 -0800
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2026-02-03 16:37 +0200
Re: srand(0) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-02-17 23:47 -0800
Re: srand(0) Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-02-18 11:21 +0000
Re: srand(0) David Brown <david.brown@hesbynett.no> - 2026-02-19 10:01 +0100
Re: srand(0) James Kuyper <jameskuyper@alumni.caltech.edu> - 2026-02-19 14:33 -0500
Re: srand(0) David Brown <david.brown@hesbynett.no> - 2026-02-19 20:47 +0100
Re: srand(0) James Kuyper <jameskuyper@alumni.caltech.edu> - 2026-02-20 16:01 -0500
Re: srand(0) David Brown <david.brown@hesbynett.no> - 2026-02-21 11:09 +0100
Re: srand(0) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-02-19 14:39 -0800
Re: srand(0) David Brown <david.brown@hesbynett.no> - 2026-02-20 09:16 +0100
Re: srand(0) Paul <nospam@needed.invalid> - 2026-02-23 08:32 -0500
Re: srand(0) David Brown <david.brown@hesbynett.no> - 2026-02-23 16:05 +0100
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2026-02-23 19:59 +0200
Re: srand(0) David Brown <david.brown@hesbynett.no> - 2026-02-23 20:06 +0100
Re: srand(0) Paul <nospam@needed.invalid> - 2026-02-23 15:24 -0500
Re: srand(0) Axel Reichert <mail@axel-reichert.de> - 2026-02-24 07:08 +0100
Re: srand(0) David Brown <david.brown@hesbynett.no> - 2026-02-24 10:24 +0100
Re: srand(0) Axel Reichert <mail@axel-reichert.de> - 2026-02-26 19:13 +0100
Re: srand(0) BGB <cr88192@gmail.com> - 2025-12-24 05:22 -0600
Re: srand(0) BGB <cr88192@gmail.com> - 2025-12-24 23:09 -0600
Re: srand(0) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-12-25 09:51 +0100
Re: srand(0) BGB <cr88192@gmail.com> - 2025-12-25 04:24 -0600
Re: srand(0) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-01-07 07:50 -0800
Re: srand(0) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-01-07 07:46 -0800
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2026-01-07 18:14 +0200
Re: srand(0) Kaz Kylheku <046-301-5902@kylheku.com> - 2025-12-22 19:16 +0000
Re: srand(0) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-12-22 22:35 +0100
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-23 07:24 +0000
Re: srand(0) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-12-23 09:59 +0100
Re: srand(0) Michael Bäuerle <michael.baeuerle@stz-e.de> - 2025-12-23 11:09 +0100
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-23 14:49 +0000
Re: srand(0) scott@slp53.sl.home (Scott Lurndal) - 2025-12-23 16:13 +0000
Re: srand(0) richard@cogsci.ed.ac.uk (Richard Tobin) - 2025-12-23 19:05 +0000
Re: srand(0) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-12-23 02:16 -0800
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-23 14:47 +0000
Re: srand(0) scott@slp53.sl.home (Scott Lurndal) - 2025-12-23 16:08 +0000
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-24 15:44 +0000
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-23 07:17 +0000
Re: srand(0) David Brown <david.brown@hesbynett.no> - 2025-12-23 08:25 +0100
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-23 14:45 +0000
Re: srand(0) David Brown <david.brown@hesbynett.no> - 2025-12-23 19:15 +0100
Re: srand(0) John McCue <jmclnx@gmail.com.invalid> - 2025-12-23 00:39 +0000
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2025-12-23 02:17 +0000
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-23 14:55 +0000
Re: srand(0) BGB <cr88192@gmail.com> - 2025-12-24 23:35 -0600
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-26 08:23 +0000
Re: srand(0) BGB <cr88192@gmail.com> - 2025-12-26 14:48 -0600
Re: srand(0) BGB <cr88192@gmail.com> - 2025-12-26 15:12 -0600
Re: srand(0) Ike Naar <ike@sdf.org> - 2025-12-23 06:49 +0000
Re: srand(0) John McCue <jmclnx@gmail.com.invalid> - 2025-12-23 20:37 +0000
Re: srand(0) Ike Naar <ike@sdf.org> - 2025-12-24 15:22 +0000
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-23 07:25 +0000
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2025-12-24 06:16 +0000
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-24 15:21 +0000
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2025-12-24 19:00 +0000
Re: srand(0) BGB <cr88192@gmail.com> - 2025-12-25 03:07 -0600
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2025-12-25 19:31 +0000
Re: srand(0) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-12-25 21:14 +0100
Re: srand(0) BGB <cr88192@gmail.com> - 2025-12-25 15:29 -0600
Re: srand(0) Paul <nospam@needed.invalid> - 2025-12-25 23:25 -0500
Re: srand(0) BGB <cr88192@gmail.com> - 2025-12-25 23:41 -0600
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2025-12-26 05:42 +0000
Re: srand(0) Paul <nospam@needed.invalid> - 2025-12-26 01:52 -0500
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2025-12-26 07:56 +0000
Re: srand(0) BGB <cr88192@gmail.com> - 2025-12-26 04:48 -0600
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2025-12-24 10:51 +0200
Re: srand(0) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-12-24 00:59 -0800
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-24 15:28 +0000
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2025-12-24 17:44 +0200
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-24 16:17 +0000
Re: srand(0) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-12-24 17:53 +0100
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-24 17:27 +0000
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-24 17:33 +0000
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2025-12-24 20:16 +0200
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-25 02:01 +0000
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2025-12-25 03:17 +0000
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-26 08:13 +0000
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-25 04:30 +0000
Re: srand(0) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-12-25 09:10 +0100
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-26 08:08 +0000
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-30 06:07 +0000
Re: srand(0) scott@slp53.sl.home (Scott Lurndal) - 2025-12-30 18:42 +0000
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-31 02:01 +0000
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2025-12-31 03:10 +0000
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-31 03:28 +0000
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2025-12-31 09:37 +0000
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2026-01-01 07:32 +0000
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-01-01 19:02 +0000
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2026-01-01 19:20 +0000
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2026-01-01 21:53 +0200
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-01-01 23:50 +0000
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2026-01-02 14:32 +0200
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2026-01-02 16:18 +0200
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-01-02 20:52 +0000
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-01-02 20:46 +0000
Re: srand(0) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2026-01-03 04:08 +0000
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-01-03 04:39 +0000
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2026-01-03 14:24 +0000
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2026-01-03 20:38 +0200
Re: srand(0) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-12-30 19:37 -0800
Re: srand(0) scott@slp53.sl.home (Scott Lurndal) - 2025-12-31 17:24 +0000
Re: srand(0) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-12-31 15:17 -0800
Re: srand(0) Paul <nospam@needed.invalid> - 2025-12-31 12:30 -0500
Re: srand(0) bart <bc@freeuk.com> - 2025-12-31 18:42 +0000
Re: srand(0) Paul <nospam@needed.invalid> - 2025-12-31 15:07 -0500
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2025-12-31 22:18 +0200
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2025-12-31 20:55 +0000
Re: srand(0) bart <bc@freeuk.com> - 2025-12-31 22:57 +0000
Re: srand(0) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-12-31 16:00 -0800
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-01-01 01:03 +0000
Re: srand(0) bart <bc@freeuk.com> - 2026-01-01 14:05 +0000
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-01-01 19:03 +0000
Re: srand(0) bart <bc@freeuk.com> - 2026-01-01 20:28 +0000
Re: srand(0) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-12-31 15:29 -0800
Re: srand(0) highcrew <high.crew3868@fastmail.com> - 2026-01-01 00:31 +0100
Re: srand(0) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-12-31 16:05 -0800
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2025-12-31 15:29 +0200
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2025-12-31 20:52 +0000
Re: srand(0) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-12-31 15:14 -0800
Re: srand(0) Geoff <geoff@invalid.invalid> - 2026-01-05 20:00 -0800
Re: srand(0) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-12-31 15:03 -0800
Re: srand(0) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-12-30 19:35 -0800
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-31 04:51 +0000
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2025-12-31 15:15 +0200
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2025-12-31 20:51 +0000
Re: srand(0) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-12-31 15:00 -0800
Re: srand(0) Michael S <already5chosen@yahoo.com> - 2026-01-01 01:45 +0200
Re: srand(0) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-12-31 16:34 -0800
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2026-01-01 07:23 +0000
Re: srand(0) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2026-01-01 02:01 +0000
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-01-01 02:29 +0000
Re: srand(0) Lawrence D’Oliveiro <ldo@nz.invalid> - 2025-12-30 06:34 +0000
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-30 14:05 +0000
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-28 05:51 +0000
Re: srand(0) scott@slp53.sl.home (Scott Lurndal) - 2025-12-24 17:08 +0000
Re: srand(0) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-01-07 07:39 -0800
Re: srand(0) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-01-07 13:54 -0800
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2026-01-08 15:34 +0000
Re: srand(0) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-01-08 14:44 -0800
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2026-01-09 06:06 +0000
Re: srand(0) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-01-08 22:46 -0800
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2026-01-09 22:38 +0000
Re: srand(0) scott@slp53.sl.home (Scott Lurndal) - 2026-01-09 23:27 +0000
Re: srand(0) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-01-09 17:09 -0800
Re: srand(0) Kaz Kylheku <046-301-5902@kylheku.com> - 2026-01-10 19:44 +0000
Re: srand(0) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-01-09 00:36 -0800
Re: srand(0) Bonita Montero <Bonita.Montero@gmail.com> - 2025-12-23 11:04 +0100
Re: srand(0) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-12-23 21:44 -0800
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-24 15:41 +0000
Re: srand(0) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-12-24 18:04 +0100
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2025-12-25 05:41 +0000
Re: srand(0) Michael Sanders <porkchop@invalid.foo> - 2026-01-08 02:57 +0000
Page 2 of 10 — ← Prev page 1 [2] 3 4 … 10 Next page →
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2025-12-24 12:12 +0200 |
| Message-ID | <20251224121211.00000e8f@yahoo.com> |
| In reply to | #395935 |
On Wed, 24 Dec 2025 09:00:50 -0000 (UTC) antispam@fricas.org (Waldek Hebisch) wrote: > Michael S <already5chosen@yahoo.com> wrote: > > On Tue, 23 Dec 2025 17:54:05 -0000 (UTC) > > antispam@fricas.org (Waldek Hebisch) wrote: > > > >> Michael S <already5chosen@yahoo.com> wrote: > >> > On Mon, 22 Dec 2025 18:41:10 +0100 > >> > Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote: > >> > > > > Also, the TestU01 suit is made for generators with 32-bit output. > > M. O’Neill used ad hoc technique to make it applicable to generators > > with 64-bit output. Is this technique right? Or may be it put 64-bit > > PRNG at unfair disadvantage? > > My point of view is that generator can be used to generate long > bistream. Then you can cut the bitstream and get number of > desired size. Good tests should check that such usage leads > to reasonable properties. So, fact that one generator produces > 32-bit pieces and other produces 64-bit pieces should be irrelevant > to the test. > What you say is correct in few use cases. But there are many uses cases (in field of testing of numeric code, probably, most of them) in which "less random" LS bits are acceptable. Not that I can see why it could be the case for MT19937-64, but it could apply to one of two of other 64-bit generators tested by O'Neill. > > Besides, I strongly disagree with at least one assertion made by > > O’Neill: "While security-related applications should > > use a secure generator, because we cannot always know the future > > contexts in which our code will be used, it seems wise for all > > applications to avoid generators that make discovering their entire > > internal state completely trivial." > > No, I know exactly what I am doing/ I know exactly that for my > > application easy discovery of complete state of PRNG is not a > > defect. > > O’Neill is not a prophet, ignore what she say it you think you > know better (which is probably the above). > > > Anyway, even if I am skeptical about her criticism of popular PRNGs, > > intuitively I agree with the constructive part of the article - > > medium-quality PRNG that feeds medium quality hash function can > > potentially produce very good fast PRNG with rather small internal > > state. > > She seem to care very much about having minimal possible state. > That is may be nice on embeded systems, but in general I would > happily accept slighty bigger state (say 256 bits). But if > we can get good properties with very small state, then why not? > After all looking at state and updating it takes code, so > small state helps with having fast generator. > Agreed. > Concerning Mersenne Twister, she is not the only one to > criticise it. My personal opinion is that given large > state and not so simple update Mersenne Twister would > have to be very very good to justify its use. One theoretical advantage of MT19937 is that it has period of astronomic proportions. Which means that one instance of PRNG could be de-multiplexed into millions or billions of sub-streams with no detectable degradation of the quality of each sub-stream. However I fail to see how de-multiplexing into more than ~ one thousand of sub-streams can be practical. And for the latter one does not need to be astronomical, something like period=2**96 would be fully sufficient with many bits to spare. So, in theory I agree with the criticism. But in practice I am not bothered by the size of MT state. > But it > fails some tests, so does not look _better_ than other > generators. > It would be interesting to find out what were those tests that failed. I wonder, if tests suit can run faster on multicore computer. I don't want to wait 5-6 hours just to find out that report does not provide an information that I am looking for. > > On related note, I think that even simple counter fed into high > > quality hash function (not cryptographically high quality, far less > > than that) can produce excellent PRNG with even smaller internal > > state. But not very fast one. Although the speed depends on > > specifics of used computer. I can imagine computer that has > > low-latency Rijndael128 instruction. On such computer, running > > counter through 3-4 rounds of Rijndael ill produce very good PRNG > > that is only 2-3 times slower than, for example, LCG 128/64. > > Maybe. > May be I'd even test my hypothesis. Eventually. Except that, again, I am not thrilled by idea of waiting 6 hours for each result.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2025-12-28 02:44 +0200 |
| Subject | Article of Melissa O'Nail (Was: srand(0)) |
| Message-ID | <20251228024431.00000016@yahoo.com> |
| In reply to | #395938 |
On Wed, 24 Dec 2025 12:12:11 +0200 Michael S <already5chosen@yahoo.com> wrote: > On Wed, 24 Dec 2025 09:00:50 -0000 (UTC) > antispam@fricas.org (Waldek Hebisch) wrote: > > > Michael S <already5chosen@yahoo.com> wrote: > > > On Tue, 23 Dec 2025 17:54:05 -0000 (UTC) > > > antispam@fricas.org (Waldek Hebisch) wrote: > > > > > >> Michael S <already5chosen@yahoo.com> wrote: > > >> > On Mon, 22 Dec 2025 18:41:10 +0100 > > >> > Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote: > > >> > > > > > > Also, the TestU01 suit is made for generators with 32-bit output. > > > M. O’Neill used ad hoc technique to make it applicable to > > > generators with 64-bit output. Is this technique right? Or may be > > > it put 64-bit PRNG at unfair disadvantage? > > > > My point of view is that generator can be used to generate long > > bistream. Then you can cut the bitstream and get number of > > desired size. Good tests should check that such usage leads > > to reasonable properties. So, fact that one generator produces > > 32-bit pieces and other produces 64-bit pieces should be irrelevant > > to the test. > > > > What you say is correct in few use cases. But there are many uses > cases (in field of testing of numeric code, probably, most of them) > in which "less random" LS bits are acceptable. > Not that I can see why it could be the case for MT19937-64, but it > could apply to one of two of other 64-bit generators tested by > O'Neill. > > > > > Besides, I strongly disagree with at least one assertion made by > > > O’Neill: "While security-related applications should > > > use a secure generator, because we cannot always know the future > > > contexts in which our code will be used, it seems wise for all > > > applications to avoid generators that make discovering their > > > entire internal state completely trivial." > > > No, I know exactly what I am doing/ I know exactly that for my > > > application easy discovery of complete state of PRNG is not a > > > defect. > > > > O’Neill is not a prophet, ignore what she say it you think you > > know better (which is probably the above). > > > > > Anyway, even if I am skeptical about her criticism of popular > > > PRNGs, intuitively I agree with the constructive part of the > > > article - medium-quality PRNG that feeds medium quality hash > > > function can potentially produce very good fast PRNG with rather > > > small internal state. > > > > She seem to care very much about having minimal possible state. > > That is may be nice on embeded systems, but in general I would > > happily accept slighty bigger state (say 256 bits). But if > > we can get good properties with very small state, then why not? > > After all looking at state and updating it takes code, so > > small state helps with having fast generator. > > > > Agreed. > > > Concerning Mersenne Twister, she is not the only one to > > criticise it. My personal opinion is that given large > > state and not so simple update Mersenne Twister would > > have to be very very good to justify its use. > > One theoretical advantage of MT19937 is that it has period of > astronomic proportions. Which means that one instance of PRNG could be > de-multiplexed into millions or billions of sub-streams with no > detectable degradation of the quality of each sub-stream. > However I fail to see how de-multiplexing into more than ~ one > thousand of sub-streams can be practical. And for the latter one does > not need to be astronomical, something like period=2**96 would be > fully sufficient with many bits to spare. > So, in theory I agree with the criticism. But in practice I am not > bothered by the size of MT state. > > > But it > > fails some tests, so does not look _better_ than other > > generators. > > > > It would be interesting to find out what were those tests that failed. > I wonder, if tests suit can run faster on multicore computer. I don't > want to wait 5-6 hours just to find out that report does not provide > an information that I am looking for. > I reproduced results of M. O'Neil. Luckily, on semi-modern hardware (Coffee Lake or EPYC3) and for PRNGs in question BigCrash finishes in 2-2.5 hours. Which is a pain, but considarably less so then 5 hours. mt19937 fails all tests of scomp_LinearComp() variaty (2 in Crash and 2 in BigCrash). It passes all the rest of tests. After re-reading O'Neil, I see that she wrote that, but first time I didn't pay attention. I have read description of scomp_LinearComp(). I can't say that I understood much. Neither theory, nor parameters, in particular, even after looking though code I have no idea about the meaning of parameter r. I am not so sure that Pierre L’Ecuyer himself fully understands this test, apart from the fact that many moons ago basic algorithm for calculation of linear complexity was published in IEEE Transactions on Information Theory. Otherwise, his description would not look so much as hand waving. As to O'Neil, she likely understands it better than myself, but that's not a huge achievement :( My less than scientific feeling about this test is that one part of it is looking if test is LFSR or LFSR-family and if the answer is yes then test fails. So, eccentrically, mt19937 is punished for what it is rather than for randomness of results that it produces. I made a minimal modification to mt19937 algorithm, telling it to skip every 19936th result word. With modification it easily passes all 3 crash batteries of Pierre L’Ecuyer. Do I think that my modified mt19937 is better than original? No, I don't. IMHO, the only thing it is better in is passing batteries of L’Ecuyer. > > > On related note, I think that even simple counter fed into high > > > quality hash function (not cryptographically high quality, far > > > less than that) can produce excellent PRNG with even smaller > > > internal state. But not very fast one. Although the speed depends > > > on specifics of used computer. I can imagine computer that has > > > low-latency Rijndael128 instruction. On such computer, running > > > counter through 3-4 rounds of Rijndael ill produce very good PRNG > > > that is only 2-3 times slower than, for example, LCG 128/64. > > > > Maybe. > > > > May be I'd even test my hypothesis. Eventually. Except that, again, I > am not thrilled by idea of waiting 6 hours for each result. > I tested. It turned out that my hypothesis was wrong. Running counter through 3 rounds of Rijndael128 is not enough. Running counter through 4 rounds is still not enough - it fails 1 test (#86) in BigCrash battery. I didn't test 5 rounds, but even if it is enough, which is likely, it would almost certainly be slower than other several known methods. All that with simple 64-bit binary counter as a state variable. With 128-bit state and with partial chaining of 64 bits of Rijndael output back into part of state (the other half of state is still a counter), passing all batteries appear very easy. It only takes one round for chaining and another one for hashing. But under O'Neil's figures of merit using 128-bit PRNG state considered cheating );
[toc] | [prev] | [next] | [standalone]
| From | antispam@fricas.org (Waldek Hebisch) |
|---|---|
| Date | 2025-12-28 05:38 +0000 |
| Subject | Re: Article of Melissa O'Nail |
| Message-ID | <10iqfpd$2g8io$1@paganini.bofh.team> |
| In reply to | #396002 |
Michael S <already5chosen@yahoo.com> wrote:
> On Wed, 24 Dec 2025 12:12:11 +0200
> Michael S <already5chosen@yahoo.com> wrote:
>
>> On Wed, 24 Dec 2025 09:00:50 -0000 (UTC)
>> antispam@fricas.org (Waldek Hebisch) wrote:
>>
>> > Michael S <already5chosen@yahoo.com> wrote:
>> > > On Tue, 23 Dec 2025 17:54:05 -0000 (UTC)
>> > > antispam@fricas.org (Waldek Hebisch) wrote:
>> > >
>> > >> Michael S <already5chosen@yahoo.com> wrote:
>> > >> > On Mon, 22 Dec 2025 18:41:10 +0100
>> > >> > Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
>> > >> >
>> >
>> > > Also, the TestU01 suit is made for generators with 32-bit output.
>> > > M. O’Neill used ad hoc technique to make it applicable to
>> > > generators with 64-bit output. Is this technique right? Or may be
>> > > it put 64-bit PRNG at unfair disadvantage?
>> >
>> > My point of view is that generator can be used to generate long
>> > bistream. Then you can cut the bitstream and get number of
>> > desired size. Good tests should check that such usage leads
>> > to reasonable properties. So, fact that one generator produces
>> > 32-bit pieces and other produces 64-bit pieces should be irrelevant
>> > to the test.
>> >
>>
>> What you say is correct in few use cases. But there are many uses
>> cases (in field of testing of numeric code, probably, most of them)
>> in which "less random" LS bits are acceptable.
>> Not that I can see why it could be the case for MT19937-64, but it
>> could apply to one of two of other 64-bit generators tested by
>> O'Neill.
>>
>>
>> > > Besides, I strongly disagree with at least one assertion made by
>> > > O’Neill: "While security-related applications should
>> > > use a secure generator, because we cannot always know the future
>> > > contexts in which our code will be used, it seems wise for all
>> > > applications to avoid generators that make discovering their
>> > > entire internal state completely trivial."
>> > > No, I know exactly what I am doing/ I know exactly that for my
>> > > application easy discovery of complete state of PRNG is not a
>> > > defect.
>> >
>> > O’Neill is not a prophet, ignore what she say it you think you
>> > know better (which is probably the above).
>> >
>> > > Anyway, even if I am skeptical about her criticism of popular
>> > > PRNGs, intuitively I agree with the constructive part of the
>> > > article - medium-quality PRNG that feeds medium quality hash
>> > > function can potentially produce very good fast PRNG with rather
>> > > small internal state.
>> >
>> > She seem to care very much about having minimal possible state.
>> > That is may be nice on embeded systems, but in general I would
>> > happily accept slighty bigger state (say 256 bits). But if
>> > we can get good properties with very small state, then why not?
>> > After all looking at state and updating it takes code, so
>> > small state helps with having fast generator.
>> >
>>
>> Agreed.
>>
>> > Concerning Mersenne Twister, she is not the only one to
>> > criticise it. My personal opinion is that given large
>> > state and not so simple update Mersenne Twister would
>> > have to be very very good to justify its use.
>>
>> One theoretical advantage of MT19937 is that it has period of
>> astronomic proportions. Which means that one instance of PRNG could be
>> de-multiplexed into millions or billions of sub-streams with no
>> detectable degradation of the quality of each sub-stream.
>> However I fail to see how de-multiplexing into more than ~ one
>> thousand of sub-streams can be practical. And for the latter one does
>> not need to be astronomical, something like period=2**96 would be
>> fully sufficient with many bits to spare.
>> So, in theory I agree with the criticism. But in practice I am not
>> bothered by the size of MT state.
>>
>> > But it
>> > fails some tests, so does not look _better_ than other
>> > generators.
>> >
>>
>> It would be interesting to find out what were those tests that failed.
>> I wonder, if tests suit can run faster on multicore computer. I don't
>> want to wait 5-6 hours just to find out that report does not provide
>> an information that I am looking for.
>>
>
> I reproduced results of M. O'Neil. Luckily, on semi-modern hardware
> (Coffee Lake or EPYC3) and for PRNGs in question BigCrash finishes in
> 2-2.5 hours. Which is a pain, but considarably less so then 5 hours.
> mt19937 fails all tests of scomp_LinearComp() variaty (2 in Crash and 2
> in BigCrash). It passes all the rest of tests.
> After re-reading O'Neil, I see that she wrote that, but first time I
> didn't pay attention.
>
> I have read description of scomp_LinearComp(). I can't say that I
> understood much. Neither theory, nor parameters, in particular, even
> after looking though code I have no idea about the meaning of parameter
> r.
> I am not so sure that Pierre L’Ecuyer himself fully understands this
> test, apart from the fact that many moons ago basic algorithm for
> calculation of linear complexity was published in IEEE Transactions on
> Information Theory. Otherwise, his description would not look so much
> as hand waving. As to O'Neil, she likely understands it better than
> myself, but that's not a huge achievement :(
> My less than scientific feeling about this test is that one part of it
> is looking if test is LFSR or LFSR-family and if the answer is yes then
> test fails.
> So, eccentrically, mt19937 is punished for what it is rather than for
> randomness of results that it produces.
Well, I peeked at the code but did not read destription of the
test. In the code I see mention of Berlekamp-Massey. That is
well-known algorithm to find regularites in data, basically
tries to find linear recurence satisfied by the data. One of
things that I do is looking for reccurences, including linear
ones. Up to now I did not run any serious simulation for
such things but I may wish to do so (and IIUC other people did
run some simulations). When doing simulations I really do
not want to see artifacts due to PRNG producing sequence with
different features than random sequence. So for me, if mt19937
produces sequence with visible extra linear regulatities that is
significant failure.
> I made a minimal modification to mt19937 algorithm, telling it to skip
> every 19936th result word. With modification it easily passes all 3
> crash batteries of Pierre L’Ecuyer.
> Do I think that my modified mt19937 is better than original? No, I
> don't. IMHO, the only thing it is better in is passing batteries of
> L’Ecuyer.
Your modification is enough to fool the tests. It is not clear
to me if it is enough to fool better regularity finders, so
probably the generator is still defective.
Also, note basic priciple of statistial testing: you should collect
and process data first, than apply _once_ statitical test. Repeated
testing with tweaked data is likely to prodice false pass. If you
really want to tweak data the whole thing should be treated as
one composite test with its own acceptance criteria (which is more
stringent than separate tests). Given that you used knowledge of
failing tests to modify generator, passing test after that is much
weaker claim than passing test for generator without knowledge of
the tests.
>> > > On related note, I think that even simple counter fed into high
>> > > quality hash function (not cryptographically high quality, far
>> > > less than that) can produce excellent PRNG with even smaller
>> > > internal state. But not very fast one. Although the speed depends
>> > > on specifics of used computer. I can imagine computer that has
>> > > low-latency Rijndael128 instruction. On such computer, running
>> > > counter through 3-4 rounds of Rijndael ill produce very good PRNG
>> > > that is only 2-3 times slower than, for example, LCG 128/64.
>> >
>> > Maybe.
>> >
>>
>> May be I'd even test my hypothesis. Eventually. Except that, again, I
>> am not thrilled by idea of waiting 6 hours for each result.
>>
>
> I tested.
> It turned out that my hypothesis was wrong. Running counter through 3
> rounds of Rijndael128 is not enough. Running counter through 4 rounds
> is still not enough - it fails 1 test (#86) in BigCrash battery.
> I didn't test 5 rounds, but even if it is enough, which is likely, it
> would almost certainly be slower than other several known methods.
>
> All that with simple 64-bit binary counter as a state variable.
>
> With 128-bit state and with partial chaining of 64 bits of Rijndael
> output back into part of state (the other half of state is still a
> counter), passing all batteries appear very easy. It only takes one
> round for chaining and another one for hashing. But under O'Neil's
> figures of merit using 128-bit PRNG state considered cheating );
O'Neil writes about birtday test: if you take values from N
element set, with more than sqrt(N) samples you should get
repetitions. Consider N equal to 2 to the power 64. In
heavy use one could generate more than sqrt(N) values.
In PRNG having 64-bit state and producing state as value
all values are distinct, so generator would fail such a test.
One could try to fix this by not exposing state, say producing
only 32-bits in each step. But on 64-bit machine it looks
more efficient to use 128-bit state and produce 64-bits in
each step.
--
Waldek Hebisch
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2025-12-28 12:35 +0200 |
| Subject | Re: Article of Melissa O'Nail |
| Message-ID | <20251228123533.000062a2@yahoo.com> |
| In reply to | #396005 |
On Sun, 28 Dec 2025 05:38:55 -0000 (UTC) antispam@fricas.org (Waldek Hebisch) wrote: > Michael S <already5chosen@yahoo.com> wrote: > > On Wed, 24 Dec 2025 12:12:11 +0200 > > Michael S <already5chosen@yahoo.com> wrote: > > > >> On Wed, 24 Dec 2025 09:00:50 -0000 (UTC) > >> antispam@fricas.org (Waldek Hebisch) wrote: > >> > >> > Michael S <already5chosen@yahoo.com> wrote: > >> > > On Tue, 23 Dec 2025 17:54:05 -0000 (UTC) > >> > > antispam@fricas.org (Waldek Hebisch) wrote: > >> > > > >> > >> Michael S <already5chosen@yahoo.com> wrote: > >> > >> > On Mon, 22 Dec 2025 18:41:10 +0100 > >> > >> > Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote: > >> > >> > > >> > > >> > > Also, the TestU01 suit is made for generators with 32-bit > >> > > output. M. O’Neill used ad hoc technique to make it applicable > >> > > to generators with 64-bit output. Is this technique right? Or > >> > > may be it put 64-bit PRNG at unfair disadvantage? > >> > > >> > My point of view is that generator can be used to generate long > >> > bistream. Then you can cut the bitstream and get number of > >> > desired size. Good tests should check that such usage leads > >> > to reasonable properties. So, fact that one generator produces > >> > 32-bit pieces and other produces 64-bit pieces should be > >> > irrelevant to the test. > >> > > >> > >> What you say is correct in few use cases. But there are many uses > >> cases (in field of testing of numeric code, probably, most of them) > >> in which "less random" LS bits are acceptable. > >> Not that I can see why it could be the case for MT19937-64, but it > >> could apply to one of two of other 64-bit generators tested by > >> O'Neill. > >> > >> > >> > > Besides, I strongly disagree with at least one assertion made > >> > > by O’Neill: "While security-related applications should > >> > > use a secure generator, because we cannot always know the > >> > > future contexts in which our code will be used, it seems wise > >> > > for all applications to avoid generators that make discovering > >> > > their entire internal state completely trivial." > >> > > No, I know exactly what I am doing/ I know exactly that for my > >> > > application easy discovery of complete state of PRNG is not a > >> > > defect. > >> > > >> > O’Neill is not a prophet, ignore what she say it you think you > >> > know better (which is probably the above). > >> > > >> > > Anyway, even if I am skeptical about her criticism of popular > >> > > PRNGs, intuitively I agree with the constructive part of the > >> > > article - medium-quality PRNG that feeds medium quality hash > >> > > function can potentially produce very good fast PRNG with > >> > > rather small internal state. > >> > > >> > She seem to care very much about having minimal possible state. > >> > That is may be nice on embeded systems, but in general I would > >> > happily accept slighty bigger state (say 256 bits). But if > >> > we can get good properties with very small state, then why not? > >> > After all looking at state and updating it takes code, so > >> > small state helps with having fast generator. > >> > > >> > >> Agreed. > >> > >> > Concerning Mersenne Twister, she is not the only one to > >> > criticise it. My personal opinion is that given large > >> > state and not so simple update Mersenne Twister would > >> > have to be very very good to justify its use. > >> > >> One theoretical advantage of MT19937 is that it has period of > >> astronomic proportions. Which means that one instance of PRNG > >> could be de-multiplexed into millions or billions of sub-streams > >> with no detectable degradation of the quality of each sub-stream. > >> However I fail to see how de-multiplexing into more than ~ one > >> thousand of sub-streams can be practical. And for the latter one > >> does not need to be astronomical, something like period=2**96 > >> would be fully sufficient with many bits to spare. > >> So, in theory I agree with the criticism. But in practice I am not > >> bothered by the size of MT state. > >> > >> > But it > >> > fails some tests, so does not look _better_ than other > >> > generators. > >> > > >> > >> It would be interesting to find out what were those tests that > >> failed. I wonder, if tests suit can run faster on multicore > >> computer. I don't want to wait 5-6 hours just to find out that > >> report does not provide an information that I am looking for. > >> > > > > I reproduced results of M. O'Neil. Luckily, on semi-modern hardware > > (Coffee Lake or EPYC3) and for PRNGs in question BigCrash finishes > > in 2-2.5 hours. Which is a pain, but considarably less so then 5 > > hours. mt19937 fails all tests of scomp_LinearComp() variaty (2 in > > Crash and 2 in BigCrash). It passes all the rest of tests. > > After re-reading O'Neil, I see that she wrote that, but first time I > > didn't pay attention. > > > > I have read description of scomp_LinearComp(). I can't say that I > > understood much. Neither theory, nor parameters, in particular, even > > after looking though code I have no idea about the meaning of > > parameter r. > > I am not so sure that Pierre L’Ecuyer himself fully understands this > > test, apart from the fact that many moons ago basic algorithm for > > calculation of linear complexity was published in IEEE Transactions > > on Information Theory. Otherwise, his description would not look so > > much as hand waving. As to O'Neil, she likely understands it better > > than myself, but that's not a huge achievement :( > > My less than scientific feeling about this test is that one part of > > it is looking if test is LFSR or LFSR-family and if the answer is > > yes then test fails. > > So, eccentrically, mt19937 is punished for what it is rather than > > for randomness of results that it produces. > > Well, I peeked at the code but did not read destription of the > test. In the code I see mention of Berlekamp-Massey. That is > well-known algorithm to find regularites in data, basically > tries to find linear recurence satisfied by the data. One of > things that I do is looking for reccurences, including linear > ones. Up to now I did not run any serious simulation for > such things but I may wish to do so (and IIUC other people did > run some simulations). When doing simulations I really do > not want to see artifacts due to PRNG producing sequence with > different features than random sequence. So for me, if mt19937 > produces sequence with visible extra linear regulatities that is > significant failure. > I can't say much about Berlekamp-Massey algorithm in general. But this particular test (scomp_LinearComp) is looking for correlations between individual bits and is doing it at unusual intervals. In fact, it's even worth. It is looking not for correlations themselves but for regularity in changes of measure of correlation in a group of bits that is called linear complexity. And if it finds changes regular than it declares that PRNG is bad. I don't know, may be the test was not intentionally designed to punish long LSFRs that use relatively few bits at feedback step, but it behaves like the one. I personally don't care even if my PRNG has long-distance correlation between bits themselves, as long as the distance is long and not divisible by small integers. Much less so, when its not correlation itself, but a derivative of some abstract function of correlation. What I care about are numeric values of groups of bits taken at regular intervals, like 64 bits (most typical), 32 bits or rarely 8/16 bits. And for that MT appears to perform very well. For that I certainly trust it better than non-hashed output of LCG, esp. of LCG that has pow2 for modulo. And if said LCG happens to pass all L’Ecuyer butteries it rather makes me more suspect of quality of batteries rather than less suspect of quality of this sort of LCG. Now, if somebody cares about non-correlativity of individual bits at strange intervals then, may be, LCG(mod 2**96) with output consisting of 32 MS bits of the state is what a doctor ordered. However I suspect that my usage of PRNG is not just different from his, it also happens to be far more common than his usage. > > I made a minimal modification to mt19937 algorithm, telling it to > > skip every 19936th result word. With modification it easily passes > > all 3 crash batteries of Pierre L’Ecuyer. > > Do I think that my modified mt19937 is better than original? No, I > > don't. IMHO, the only thing it is better in is passing batteries of > > L’Ecuyer. > > Your modification is enough to fool the tests. It is not clear > to me if it is enough to fool better regularity finders, so > probably the generator is still defective. > That was my point. I manged to fool the test. Easily. But my conclusion is different. The test is defective, generator, both before and after modifications, is o.k.. > Also, note basic priciple of statistial testing: you should collect > and process data first, than apply _once_ statitical test. Repeated > testing with tweaked data is likely to prodice false pass. If you > really want to tweak data the whole thing should be treated as > one composite test with its own acceptance criteria (which is more > stringent than separate tests). Given that you used knowledge of > failing tests to modify generator, passing test after that is much > weaker claim than passing test for generator without knowledge of > the tests. > Pay attention that specific skip modulo (19936) was chosen not because it's the only modulo that cause the test to pass. It was chosen as a biggest number < 19937 in order to make least noticeable impact on the speed of PRNG. Any smaller skip modulo will pass tests as well. So, if there was feedback loop on my part, it was not strong. And that, BTW, is my main criticism of methodology of Melissa O'Neil in constructive part of your article. She seems to apply a feedback loop by tweaking her suggested PCGs until they pass L’Ecuyer butteries. > >> > > On related note, I think that even simple counter fed into high > >> > > quality hash function (not cryptographically high quality, far > >> > > less than that) can produce excellent PRNG with even smaller > >> > > internal state. But not very fast one. Although the speed > >> > > depends on specifics of used computer. I can imagine computer > >> > > that has low-latency Rijndael128 instruction. On such > >> > > computer, running counter through 3-4 rounds of Rijndael ill > >> > > produce very good PRNG that is only 2-3 times slower than, for > >> > > example, LCG 128/64. > >> > > >> > Maybe. > >> > > >> > >> May be I'd even test my hypothesis. Eventually. Except that, > >> again, I am not thrilled by idea of waiting 6 hours for each > >> result. > > > > I tested. > > It turned out that my hypothesis was wrong. Running counter through > > 3 rounds of Rijndael128 is not enough. Running counter through 4 > > rounds is still not enough - it fails 1 test (#86) in BigCrash > > battery. I didn't test 5 rounds, but even if it is enough, which is > > likely, it would almost certainly be slower than other several > > known methods. > > > > All that with simple 64-bit binary counter as a state variable. > > > > With 128-bit state and with partial chaining of 64 bits of Rijndael > > output back into part of state (the other half of state is still a > > counter), passing all batteries appear very easy. It only takes one > > round for chaining and another one for hashing. But under O'Neil's > > figures of merit using 128-bit PRNG state considered cheating ); > > O'Neil writes about birtday test: if you take values from N > element set, with more than sqrt(N) samples you should get > repetitions. Consider N equal to 2 to the power 64. In > heavy use one could generate more than sqrt(N) values. > In PRNG having 64-bit state and producing state as value > all values are distinct, so generator would fail such a test. > One could try to fix this by not exposing state, say producing > only 32-bits in each step. Using 64-bit state and generating 32-bit output at each step is exactly what I did. In theory it should suffice to pass birthday tests. And indeed the test that failed was not one of the birthday tests, but svaria_WeightDistrib test (# 62 in BigCrash). > But on 64-bit machine it looks > more efficient to use 128-bit state and produce 64-bits in > each step. > It was not about practicality, but about testing the theory that even the worst possible long-periodic PRNG (and I can not think about anything worse as PRNG than simple counter) should be good enough when fed into decent hash as long as one is not greedy and (assuming 2**64 period) one does not try to use more than 32 bits for output. I still think that the theory is correct, but I somewhat underestimated the required quality of the hash function.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-01-05 14:21 +0200 |
| Subject | Re: Article of Melissa O'Nail |
| Message-ID | <20260105142144.000074ac@yahoo.com> |
| In reply to | #396008 |
I experimented a bit more (in fact, more like a lot more) with test batteries of L’Ecuyer. It led me to conclusion that occasional failure in the either middle or big battery means nothing. Sometimes even cripto-quality PRNG does not pass one or another test. Then you try to reproduce it and see that with any other seed that you try a failure does not happen. All in all, it makes me more suspect of PRNGs that consistently pass both batteries with various seed. I start to see it as a sign of PRNG being rigged to pass tests. Said above does not apply to scomp_LinearComp() failures of mt19937. Those failures are very consistent. I just don't consider them significant for my own use of PRNGs or for any other uses of PRNG that I personally ever encountered. Overall an experience strengthened my position that general wisdom, previously shared by O'Neil herself, got it right: in absence of the special considerations people should select mt19937 and especially mt19937-64 as their default PRNGs of choice. Looking closer, apart from its properties of randomness and apart from huge period (which does not matter for me) I started to appreciate for mt19937 for the following properties that I was not aware before: - it does not use multiplier. So good fit for embedded systems that have no (or very slow) multiplier HW. - algorithm is very SIMD-friendly, so optimized implementations can be very very fast on modern x86 and ARM64 hardware. The latter property also means that very fast FPGA implementation is easily possible as long as designer is willing to through at it moderate amount of logic resources. Said above does not mean that PCG generators of O'Neil have no place. Intuitively, they appear not bad. But the theory is unproven, optimized implementation is likely slower that optimized mt19937, claimed "security" advantages are nonsense as admitted later by O'Neil herself. And, as said above, I no longer trust her empirical methodology, based on work of L’Ecuyer. So, PCG generators are valuable addition to the toolbox, but not good enough to change my default.
[toc] | [prev] | [next] | [standalone]
| From | antispam@fricas.org (Waldek Hebisch) |
|---|---|
| Date | 2026-01-07 10:51 +0000 |
| Subject | Re: Article of Melissa O'Nail |
| Message-ID | <10jldr2$1khpu$1@paganini.bofh.team> |
| In reply to | #396166 |
Michael S <already5chosen@yahoo.com> wrote:
> I experimented a bit more (in fact, more like a lot more) with
> test batteries of L’Ecuyer. It led me to conclusion that occasional
> failure in the either middle or big battery means nothing.
> Sometimes even cripto-quality PRNG does not pass one or another test.
> Then you try to reproduce it and see that with any other seed that you
> try a failure does not happen.
> All in all, it makes me more suspect of PRNGs that consistently pass
> both batteries with various seed. I start to see it as a sign of
> PRNG being rigged to pass tests.
Well, that depends on the tests and threshhold in the tests.
Some tests when fed with trurly random source will produce produce
very small variation of the results. With generous threshhold
such test will essentially never fail for trurly random source.
OTOH when expected variation of the results is larger and
threshhold is tight, then trurly random source will fail the
test from time to time. And if you test long enough you should
be able to estimate probability of failure and possibly compare
is with theoretical result if available.
To say the truth, I do not know what failures of crypto-quality PRNG
means. It may mean that the test is of tight kind that is supposed
to fail from time to time for trurly random source. Or it may mean
to PRNG improves cypto part at cost of statistics. That is
non-uniform distribution of the output is not a problem in
crypto applications. Simply for crypto purposes future output
should be not predictable from current and past output only.
And slightly non-uniform distribution can increase probablity
of test failure enough that you can observe such failures.
BTW: You mentioned using counter and hardware AES128 round.
Given cheap AES128 round I would try 128-bit state and AES128
round as state update. I do not know if hardware AES128 is
fast enough to make it wortwhile, but using AES128 round as a
state update should be much better than scrambling a counter.
> Said above does not apply to scomp_LinearComp() failures of mt19937.
> Those failures are very consistent. I just don't consider them
> significant for my own use of PRNGs or for any other uses of PRNG that
> I personally ever encountered.
>
> Overall an experience strengthened my position that general wisdom,
> previously shared by O'Neil herself, got it right: in absence of the
> special considerations people should select mt19937 and especially
> mt19937-64 as their default PRNGs of choice.
> Looking closer, apart from its properties of randomness and apart from
> huge period
Huge period alone is easy. AFAICS matrix variants of LCG can
easily get quite large periods. I did not test matrix LCG,
but on statistical tests they should be essentially as good
as multiprecision LCG, but should be cheaper to implement.
Just to be clear, I mean equation x_{n+1} = Ax_n + b, wher x_n
is a vector reprezenting n-th state, A is a matrix and b is a
vector. Matrix A may be somewhat sparse, that is have limited
number of non-zero entries, and some entries my be simple, like
1 or -1. With proper choice of a and b period should be
comparable with number of availalable states.
I see no reason to go for very long periods, already 512 bits
of state allow perids which in practice should be indistingushable
from infinite period.
> (which does not matter for me) I started to appreciate for
> mt19937 for the following properties that I was not aware before:
> - it does not use multiplier. So good fit for embedded systems that
> have no (or very slow) multiplier HW.
Biggest MCU with no hardware multiplier that I have has 2kB RAM.
I do not want mt19937 on such a machine. 64-bit multiplication
on 8-biter with hardware multiplier may be slow, so 64-bit LCG
(and improvements based on it) may be slow. But multiplication
nicely spreads out bits, so it is not clear to me if there is
equally good cheaper alternative. If needed I would investigate
matrix LCG, they may be slightly cheaper.
> - algorithm is very SIMD-friendly, so optimized implementations can be
> very very fast on modern x86 and ARM64 hardware.
Just size of the state puts limit how fast it can be. And size of
the state means that it will compete for cache with user data.
BTW: AFAICS matrix LCG can be SIMD friendly too.
> The latter property also means that very fast FPGA implementation is
> easily possible as long as designer is willing to through at it
> moderate amount of logic resources.
>
> Said above does not mean that PCG generators of O'Neil have no place.
> Intuitively, they appear not bad. But the theory is unproven, optimized
> implementation is likely slower that optimized mt19937, claimed
> "security" advantages are nonsense as admitted later by O'Neil herself.
> And, as said above, I no longer trust her empirical methodology, based
> on work of L’Ecuyer.
> So, PCG generators are valuable addition to the toolbox, but not good
> enough to change my default.
I agree that ATM it is not entirely clear if PCG-s are as good as
suggested by tests. But I am surprised by your opinion about
speed, I did not analyze deeply either of them, but PCG-s are way
simpler, so I would expect them to be faster.
--
Waldek Hebisch
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-01-08 14:03 +0200 |
| Subject | Re: Article of Melissa O'Nail |
| Message-ID | <20260108140335.00002dda@yahoo.com> |
| In reply to | #396254 |
On Wed, 7 Jan 2026 10:51:16 -0000 (UTC)
antispam@fricas.org (Waldek Hebisch) wrote:
> Michael S <already5chosen@yahoo.com> wrote:
> > I experimented a bit more (in fact, more like a lot more) with
> > test batteries of L’Ecuyer. It led me to conclusion that occasional
> > failure in the either middle or big battery means nothing.
> > Sometimes even cripto-quality PRNG does not pass one or another
> > test. Then you try to reproduce it and see that with any other seed
> > that you try a failure does not happen.
> > All in all, it makes me more suspect of PRNGs that consistently pass
> > both batteries with various seed. I start to see it as a sign of
> > PRNG being rigged to pass tests.
>
> Well, that depends on the tests and threshhold in the tests.
> Some tests when fed with trurly random source will produce produce
> very small variation of the results. With generous threshhold
> such test will essentially never fail for trurly random source.
> OTOH when expected variation of the results is larger and
> threshhold is tight, then trurly random source will fail the
> test from time to time.
Yes, there are many stable tests. But there are also many unstable
tests in Crash/BigCrash batteries. I can't say if the ratio is 50:50 or
75:25, but it is not 90:10.
svaria_WeightDistrib() and swalk_RandomWalk1() appear most unstable.
You feed them with particular pseudo-random vector (100,000,000 points)
and the test fails. Then you shift the vector by just one point, to the
left or to the right. And it passes, often not just passes, but produces
a result that is not even close to the margin.
> And if you test long enough you should
> be able to estimate probability of failure and possibly compare
> is with theoretical result if available.
>
Long enough in this case is very damn long.
> To say the truth, I do not know what failures of crypto-quality PRNG
> means. It may mean that the test is of tight kind that is supposed
> to fail from time to time for trurly random source. Or it may mean
> to PRNG improves cypto part at cost of statistics. That is
> non-uniform distribution of the output is not a problem in
> crypto applications. Simply for crypto purposes future output
> should be not predictable from current and past output only.
> And slightly non-uniform distribution can increase probablity
> of test failure enough that you can observe such failures.
>
> BTW: You mentioned using counter and hardware AES128 round.
> Given cheap AES128 round I would try 128-bit state and AES128
> round as state update. I do not know if hardware AES128 is
> fast enough to make it wortwhile, but using AES128 round as a
> state update should be much better than scrambling a counter.
>
It depends on what one considers fast.
My expectations, trained by LCGs and esp. by optimized MT, are rather
high. [On relatively modern Intel and AMD hardware] generators that do
feedback through even a single AES round (with another round for
post-processing) do not meet my expectations.
At best, fully inlined and after significant effort of removing all
non-necessary bottlenecks, such generators produce one output word per
4-5 clock cycles. More naive implementations with state read from
memory and stored back to memory on each iteration, are much slower
than that, easily takes over 10 clocks per iteration.
For comparison, a counter that goes through 5 rounds of AES without
feedback runs at 3 clocks per word when inlined and at 3.5 clocks per
word via function call.
It seems that given today's hardware limitations the only way to get
really fast PRNG with the state updated through AES round is by running
several chains interleaved. Preferably no less than 4 chains. Which
increases size of basic PRNG state to 512 bits + some more for state
management.
Another problem is that when all state bits go through AES then I can
not prove that the period of PRNG is really high. I can't even be sure
that it does not enter very short loop at some stage of its life. I
understand that it is highly unlikely, but don't like uncertainty.
Running half of the state through AES and taking another half from
counter solves it, but at cost of need for better diffusion in
post-processing (temper) state of generator. If more than 32 bits of
output produced per iteration, I would not feel good if tempering
consists of just one round of AES. I would want two rounds at least.
May be, better option is to do something like that:
interleave N times {
prnd_out = AES1R(state.w128);
state.w128 = AES1R(state.w128) ^ state.counter64;
state.counter64 = state.counter64 + 1;
}
I am still not 100% sure that the long period is guaranteed with such
arrangement, but I am far more sure of it than in case of original
arrangement.
However, it is far from simple and the state is not very small. So, the
question is "Why bother"? What's wrong with much simpler scheme that
takes 64-bit counter and runs it through 5 AES rounds? Or even 6 round
if being paranoid?
The only downside that I can see is that this simple robust scheme is
more dependent on high throughput of AES units which is not necessarily
available on somewhat older hardware.
> > Said above does not apply to scomp_LinearComp() failures of mt19937.
> > Those failures are very consistent. I just don't consider them
> > significant for my own use of PRNGs or for any other uses of PRNG
> > that I personally ever encountered.
> >
> > Overall an experience strengthened my position that general wisdom,
> > previously shared by O'Neil herself, got it right: in absence of the
> > special considerations people should select mt19937 and especially
> > mt19937-64 as their default PRNGs of choice.
> > Looking closer, apart from its properties of randomness and apart
> > from huge period
>
> Huge period alone is easy. AFAICS matrix variants of LCG can
> easily get quite large periods. I did not test matrix LCG,
> but on statistical tests they should be essentially as good
> as multiprecision LCG, but should be cheaper to implement.
>
> Just to be clear, I mean equation x_{n+1} = Ax_n + b, wher x_n
> is a vector reprezenting n-th state, A is a matrix and b is a
> vector. Matrix A may be somewhat sparse, that is have limited
> number of non-zero entries, and some entries my be simple, like
> 1 or -1. With proper choice of a and b period should be
> comparable with number of availalable states.
>
> I see no reason to go for very long periods, already 512 bits
> of state allow perids which in practice should be indistingushable
> from infinite period.
>
Didn't I agree with that in the very next statement?
> > (which does not matter for me) I started to appreciate for
> > mt19937 for the following properties that I was not aware before:
> > - it does not use multiplier. So good fit for embedded systems that
> > have no (or very slow) multiplier HW.
>
> Biggest MCU with no hardware multiplier that I have has 2kB RAM.
> I do not want mt19937 on such a machine. 64-bit multiplication
> on 8-biter with hardware multiplier may be slow, so 64-bit LCG
> (and improvements based on it) may be slow. But multiplication
> nicely spreads out bits, so it is not clear to me if there is
> equally good cheaper alternative.
64-bit multipliers spread bits nicely, indeed. But implementing 64-bit
multiplier on the core that natively has only 8x8=16 is not easy or
fast.
Even implementing 32-bit multiplier here is not easy or fast. And I
would not say that 32-bit multipliers spread bits nicely.
But I was not thinking about that sort of cores.
I had in mind minimalistic implementation of soft core architectures by
Xilinx and Altera.
These core have several useful properties:
- tested and supported much better than open-source alternatives
- occupy relative few logic and block RAM resources
- often capable to run at higher frequency than their full-featured
brethren
- the fact that they can be used without buying a license (free as
beer) does not hurt either
Of course, they are *much* slower (lower IPC) than full-featured cores,
but in plenty of cases it's o.k. One thing that these cores do not have
is multiplier. When compiler sees multiplication in source code it calls
support routine. And when it happens then instead of *much* slower
(say, 5x) than full-featured core, which is commonly acceptable, these
cores turn ALOT slower (say, 200x0 which is commonly unacceptable.
Cores like that sometimes used in applications that want good PRNG,
like various sorts of built-in tests. In such app spending 2K bytes for
mt1937 state is o.k. Using emulated 64-bit multiplication for PRMG is
sometimes o.k. but more commonly not so.
> If needed I would investigate
> matrix LCG, they may be slightly cheaper.
>
> > - algorithm is very SIMD-friendly, so optimized implementations can
> > be very very fast on modern x86 and ARM64 hardware.
>
> Just size of the state puts limit how fast it can be. And size of
> the state means that it will compete for cache with user data.
> BTW: AFAICS matrix LCG can be SIMD friendly too.
>
> > The latter property also means that very fast FPGA implementation is
> > easily possible as long as designer is willing to through at it
> > moderate amount of logic resources.
> >
> > Said above does not mean that PCG generators of O'Neil have no
> > place. Intuitively, they appear not bad. But the theory is
> > unproven, optimized implementation is likely slower that optimized
> > mt19937, claimed "security" advantages are nonsense as admitted
> > later by O'Neil herself. And, as said above, I no longer trust her
> > empirical methodology, based on work of L’Ecuyer.
> > So, PCG generators are valuable addition to the toolbox, but not
> > good enough to change my default.
>
> I agree that ATM it is not entirely clear if PCG-s are as good as
> suggested by tests. But I am surprised by your opinion about
> speed, I did not analyze deeply either of them, but PCG-s are way
> simpler, so I would expect them to be faster.
>
When used in simple way, PCG has LCG latency (IMUL+ADD) embedded in its
core.
On modern x86-64 it tends to be 4 clocks at very least. On ARM64 it's
often better, by I am more interested in x86-64.
OTOH, optimized implementations of mt19937 have [almost] no inherent
latency limits. If one has wider hardware it directly translate into
both faster state update and faster tampering phase.
More strictly speaking for state update there exists a strict
algorithmic limit of 397 32-bit words. Plus, non-heroic implementations
have limit of 624-397=237 words. Both limits are far away from
capabilities of the widest commonly available hardware (2x or 3x 512
bits, i.e. no more than 48 32-bit operations per cycle).
In practice, the biggest bottleneck , even without 512-bit processing,
is not a state update and not tampering, but fighting impedance
mismatch at the level of API. That is, implementation prefers to
generate 256 bits at once, but API insists on 32 bits. Which leads to
need for buffering and for additional management overhead. More time
spent here than within mt algorithm itself.
Still, even with overhead, when buffer management part is inlined
(which is easy to achieve in practice and does not cause significant
code bloat) modern but not the most modern Intel core (Raptor Cove)
that I have in my desktop at work is capable to deliver one 32-bit word
per exactly 3 clock cycles.
That's a little better than even most basic fully inlined LCG, so
necessarily better than any PCG.
There is little doubt that LCGs (and as result of it PCGs) can be
improved via advancing state by several steps at time instead of one
step at time. But then they will suffer from the same impedance
mismatch with APIs. Solution to mismatch would be the same as with mt -
buffering and additional management overhead. So gone simplicity, gone
tiny state size :(
I did not try it, but it is very likely that for given width of output
word the resulting speed of PCG would be almost exactly the same as
optimized mt19937, because generator will spend majority of time in the
code that not merely almost the same between the two, but exactly the
same.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-01-08 09:40 -0800 |
| Subject | Re: Article of Melissa O'Nail |
| Message-ID | <868qe8ngu2.fsf@linuxsc.com> |
| In reply to | #396254 |
antispam@fricas.org (Waldek Hebisch) writes: > Michael S <already5chosen@yahoo.com> wrote: > >> I experimented a bit more (in fact, more like a lot more) with >> test batteries of L?Ecuyer. It led me to conclusion that occasional >> failure in the either middle or big battery means nothing. >> Sometimes even cripto-quality PRNG does not pass one or another test. >> Then you try to reproduce it and see that with any other seed that you >> try a failure does not happen. >> All in all, it makes me more suspect of PRNGs that consistently pass >> both batteries with various seed. I start to see it as a sign of >> PRNG being rigged to pass tests. > > Well, that depends on the tests and threshhold in the tests. > Some tests when fed with trurly random source will produce produce > very small variation of the results. With generous threshhold > such test will essentially never fail for trurly random source. > OTOH when expected variation of the results is larger and > threshhold is tight, then trurly random source will fail the > test from time to time. And if you test long enough you should > be able to estimate probability of failure and possibly compare > is with theoretical result if available. It's inherent in the nature of statistical testing that every so often a statistical test will "fail" even for a truly random input. An input source that never fails can also be indicative of a low quality source (and perhaps one that was tuned to the particular set of tests being done). It took me a while to learn that the results of a PRNG test suite should not be seen as purely binary.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-01-08 09:26 -0800 |
| Message-ID | <86cy3knhhh.fsf@linuxsc.com> |
| In reply to | #395935 |
antispam@fricas.org (Waldek Hebisch) writes: > Michael S <already5chosen@yahoo.com> wrote: [...] >> Anyway, even if I am skeptical about her criticism of popular PRNGs, >> intuitively I agree with the constructive part of the article - >> medium-quality PRNG that feeds medium quality hash function can >> potentially produce very good fast PRNG with rather small internal >> state. > > She seem to care very much about having minimal possible state. > That is may be nice on embeded systems, but in general I would > happily accept slighty bigger state (say 256 bits). But if > we can get good properties with very small state, then why not? > [...] That depends on whether one thinks the tests done to measure quality are sufficient to determine all the axes of "good properties". I'm not inclined to think that they do. The set of tests done in the TestU01 suite are quite good IMO, but I don't think they measure all the properties of interest. I prefer to err on the side of caution.
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2025-12-24 13:48 -0800 |
| Message-ID | <10ihn34$1dbgf$1@dont-email.me> |
| In reply to | #395920 |
On 12/23/2025 2:08 PM, Michael S wrote: [...] > I don't know. Testing randomness is complicated matter. [...] Fwiw, ent is a nice little program: https://www.fourmilab.ch/random/
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-01-07 08:41 -0800 |
| Message-ID | <86tswxnznu.fsf@linuxsc.com> |
| In reply to | #395920 |
Michael S <already5chosen@yahoo.com> writes: > On Tue, 23 Dec 2025 17:54:05 -0000 (UTC) > antispam@fricas.org (Waldek Hebisch) wrote: [...] >> There is a paper "PCG: A Family of Simple Fast Space-Efficient >> Statistically Good Algorithms for Random Number Generation" >> by M. O?Neill where she gives a family of algorithms and runs >> several statistical tests against known algorithms. Mersenne >> Twister does not look good in tests. If you have enough (128) bits >> LCGs do pass tests. A bunch of generators with 64-bit state also >> passes tests. So the only reason to prefer Mersenne Twister is >> that it is implemented in available libraries. Otherwise it is >> not so good, have large state and needs more execution time >> than alternatives. > > I don't know. Testing randomness is complicated matter. > How can I be sure that L'Ecuyer and Simard's TestU01 suite tests > things that I personally care about and that it does not test > things that are of no interest for me? Especially, the latter. Do you think any of the tests in the TestU01 suite are actually counter-indicated? As long as you don't think any TestU01 test makes things worse, there is no reason not to use all of them. You are always free to disregard tests you don't care about. > Also, the TestU01 suit is made for generators with 32-bit output. > M. O'Neill used ad hoc technique to make it applicable to > generators with 64-bit output. Is this technique right? Or may > be it put 64-bit PRNG at unfair disadvantage? As long as the same mapping is applied to all 64-bit PRNGs under consideration I don't see a problem. The point of the test is to compare PRNGs, not to compare test methods. If someone thinks a different set of tests is called for they are free to run them. > Besides, I strongly disagree with at least one assertion made by > O'Neill: "While security-related applications should use a secure > generator, because we cannot always know the future contexts in > which our code will be used, it seems wise for all applications to > avoid generators that make discovering their entire internal state > completely trivial." > No, I know exactly what I am doing/ I know exactly that for my > application easy discovery of complete state of PRNG is not a > defect. You and she are talking about different things. You are talking about choosing a PRNG to be used only by yourself. She is talking about choosing a PRNG to be made available to other people without knowing who they are or what their needs are. In the second case it's reasonable to raise the bar for the set of criteria that need to be met. > Anyway, even if I am skeptical about her criticism of popular PRNGs, > intuitively I agree with the constructive part of the article - > medium-quality PRNG that feeds medium quality hash function can > potentially produce very good fast PRNG with rather small internal > state. After looking at one of the example PCG generators, I would describe it as a medium-quality PRNG that feeds a low-quality hash. The particular combination I looked at produced good results, but it isn't clear which combinations of PRNG and hash would do likewise. > On related note, I think that even simple counter fed into high > quality hash function (not cryptographically high quality, far > less than that) can produce excellent PRNG with even smaller > internal state. But not very fast one. Although the speed > depends on specifics of used computer. I can imagine computer > that has low-latency Rijndael128 instruction. On such computer, > running counter through 3-4 rounds of Rijndael ill produce very > good PRNG that is only 2-3 times slower than, for example, LCG > 128/64. I think the point of her paper where she talks about determining how much internal state is needed is to measure the efficacy of the PRNG, not to try to reduce the amount of state needed. Based on my own experience with various PRNGs I think it's a mistake to try to minimize the amount of internal state needed. My own rule of thumb is to allow at least a factor of four: for example, a PRNG with a 32-bit output should have at least 128 bits of state. My latest favorite has 256 bits of state to produce 32-bit outputs (and so might also do well to produce 64-bit outputs, but I haven't tested that).
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-01-08 01:06 +0200 |
| Message-ID | <20260108010601.00002085@yahoo.com> |
| In reply to | #396275 |
On Wed, 07 Jan 2026 08:41:25 -0800 Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > Michael S <already5chosen@yahoo.com> writes: > > > On Tue, 23 Dec 2025 17:54:05 -0000 (UTC) > > antispam@fricas.org (Waldek Hebisch) wrote: > [...] > >> There is a paper "PCG: A Family of Simple Fast Space-Efficient > >> Statistically Good Algorithms for Random Number Generation" > >> by M. O?Neill where she gives a family of algorithms and runs > >> several statistical tests against known algorithms. Mersenne > >> Twister does not look good in tests. If you have enough (128) bits > >> LCGs do pass tests. A bunch of generators with 64-bit state also > >> passes tests. So the only reason to prefer Mersenne Twister is > >> that it is implemented in available libraries. Otherwise it is > >> not so good, have large state and needs more execution time > >> than alternatives. > > > > I don't know. Testing randomness is complicated matter. > > How can I be sure that L'Ecuyer and Simard's TestU01 suite tests > > things that I personally care about and that it does not test > > things that are of no interest for me? Especially, the latter. > > Do you think any of the tests in the TestU01 suite are actually > counter-indicated? As long as you don't think any TestU01 test > makes things worse, there is no reason not to use all of them. > You are always free to disregard tests you don't care about. > Except that it's difficult psychologically. The batteries of test gains position of of authority in your mind. Well, may be, you specifically are resistant, but I am not. Nor is Melissa O'Nail, it seems. To illustrate my point, I will tell you the story about myself. Sort of confession. If you had read the rest of this thread (or paid attention to finer details in the article of O'Nail) then you already know that mt19937 consistently fails in scomp_LinearComp() subtest of Crush and BigCrush batteries of Test01. As reported, I "fixed" it by skipping every 19936th word of mt19937 output. This particular "fix" is benign. I am sure that it does not make output of generator less random. The only impact is a bit of slowness, because of the need to manage yet another modulo counter. What I did not tell so far is that I tried another "fix". I added leakage during mt state update. It means that periodically I forced two LS bits of newly generated state word to be '01', without affecting the word that goes to tampering and then to output. And according to Test01 it worked! Flew through all batteries! Luckily, I was sufficiently self-conscious to understand that I don't understand nearly enough about algebra of Galois fields to predict all consequences of my modification. But that's me. I know few people that are less aware of their limitations. > > Also, the TestU01 suit is made for generators with 32-bit output. > > M. O'Neill used ad hoc technique to make it applicable to > > generators with 64-bit output. Is this technique right? Or may > > be it put 64-bit PRNG at unfair disadvantage? > > As long as the same mapping is applied to all 64-bit PRNGs under > consideration I don't see a problem. The point of the test is to > compare PRNGs, not to compare test methods. If someone thinks a > different set of tests is called for they are free to run them. > But Melissa, following advice of L'Ecuyer, and me, following advice of Melissa, tested 64-bit generators three times - LSW then MSW, only LSW and only MSW, thus putting them under trice more serious scrutiny than 32-bit counterparts. > > Besides, I strongly disagree with at least one assertion made by > > O'Neill: "While security-related applications should use a secure > > generator, because we cannot always know the future contexts in > > which our code will be used, it seems wise for all applications to > > avoid generators that make discovering their entire internal state > > completely trivial." > > No, I know exactly what I am doing/ I know exactly that for my > > application easy discovery of complete state of PRNG is not a > > defect. > > You and she are talking about different things. You are talking > about choosing a PRNG to be used only by yourself. She is talking > about choosing a PRNG to be made available to other people without > knowing who they are or what their needs are. In the second case > it's reasonable to raise the bar for the set of criteria that need > to be met. > No, this part of her article is a mistake, plain and simple. He even sort of admitted it couple of years later in her blogg. In reality, we either need secure PRNG or do not need secure PRNG. There is no middle ground of "more or less secure insecure PRNGs". PRNGs she advocates are insecure until proven otherwise by crypto analysts. > > Anyway, even if I am skeptical about her criticism of popular PRNGs, > > intuitively I agree with the constructive part of the article - > > medium-quality PRNG that feeds medium quality hash function can > > potentially produce very good fast PRNG with rather small internal > > state. > > After looking at one of the example PCG generators, I would > describe it as a medium-quality PRNG that feeds a low-quality > hash. The particular combination I looked at produced good > results, but it isn't clear which combinations of PRNG and > hash would do likewise. > I tend to like CRC32C for hashing 64 bits into 32 bits; for no reason apart from that this primitive is available and fast on modern Intel and AMD CPUs. ARM64 CPUs as well, I think, although less than 100% sure. > > On related note, I think that even simple counter fed into high > > quality hash function (not cryptographically high quality, far > > less than that) can produce excellent PRNG with even smaller > > internal state. But not very fast one. Although the speed > > depends on specifics of used computer. I can imagine computer > > that has low-latency Rijndael128 instruction. On such computer, > > running counter through 3-4 rounds of Rijndael ill produce very > > good PRNG that is only 2-3 times slower than, for example, LCG > > 128/64. > > I think the point of her paper where she talks about determining > how much internal state is needed is to measure the efficacy of > the PRNG, not to try to reduce the amount of state needed. Based > on my own experience with various PRNGs I think it's a mistake to > try to minimize the amount of internal state needed. My own rule > of thumb is to allow at least a factor of four: for example, a > PRNG with a 32-bit output should have at least 128 bits of state. > My latest favorite has 256 bits of state to produce 32-bit > outputs (and so might also do well to produce 64-bit outputs, but > I haven't tested that). One important point that I seem to figure out recently is that the only practical way to produce both solid and very fast PRNG that adheres to standard language APIs with 32-bit and to somewhat smaller extent 64-bit output, is to use buffering. I.e. most of the time generator simply reads pre-calculated word from the buffer and only ones per N iterations runs an actual PRNG algorithm, probably in a loop, often in SIMD. In order for this approach to be effective, buffer can't be particularly small. 32 bytes (256 bits) appear to be an absolute minimum. The buffer and counter that manages buffering, are parts of the generator state. That alone sets a practical minimal limit on the size of generator and diminishes significance of the difference between PRNGs with "algorithmic" state of 64 bits, 128 bits or even 256 bits. The observation certainly applies to PCGs or to anything else that utilizes LCG for its state update primitive. Now, if one does no look for ultimate speed then said above does not apply.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-02-03 05:26 -0800 |
| Message-ID | <864inyj6ug.fsf@linuxsc.com> |
| In reply to | #396284 |
Michael S <already5chosen@yahoo.com> writes: > On Wed, 07 Jan 2026 08:41:25 -0800 > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > >> Michael S <already5chosen@yahoo.com> writes: >> >>> On Tue, 23 Dec 2025 17:54:05 -0000 (UTC) >>> antispam@fricas.org (Waldek Hebisch) wrote: >> >> [...] >> >>>> There is a paper "PCG: A Family of Simple Fast Space-Efficient >>>> Statistically Good Algorithms for Random Number Generation" >>>> by M. O?Neill where she gives a family of algorithms and runs >>>> several statistical tests against known algorithms. Mersenne >>>> Twister does not look good in tests. If you have enough (128) bits >>>> LCGs do pass tests. A bunch of generators with 64-bit state also >>>> passes tests. So the only reason to prefer Mersenne Twister is >>>> that it is implemented in available libraries. Otherwise it is >>>> not so good, have large state and needs more execution time >>>> than alternatives. >>> >>> I don't know. Testing randomness is complicated matter. >>> How can I be sure that L'Ecuyer and Simard's TestU01 suite tests >>> things that I personally care about and that it does not test >>> things that are of no interest for me? Especially, the latter. >> >> Do you think any of the tests in the TestU01 suite are actually >> counter-indicated? As long as you don't think any TestU01 test >> makes things worse, there is no reason not to use all of them. >> You are always free to disregard tests you don't care about. > > Except that it's difficult psychologically. > The batteries of test gains position of of authority in your mind. > Well, may be, you specifically are resistant, but I am not. Nor is > Melissa O'Nail, it seems. > > To illustrate my point, I will tell you the story about myself. > Sort of confession. > [very large portion] I have read through your whole posting several times, and also looked through your other postings in this thread. Despite my efforts I am still not sure what you think or what you're trying to say. Let me put it as a question. Do you think there is a good and objective test for measuring the quality of a PRNG? If so what test (or tests) do you think would suffice? Here "quality" is meant as some sort of numeric measure, which could be a monotonic metric (as in "the larger the number the higher the quality") or just a simple pass/fail. If you don't think there is any such test, how do you propose that PRNGs be evaluated? > One important point that I seem to figure out recently is that the > only practical way to produce both solid and very fast PRNG that > adheres to standard language APIs with 32-bit and to somewhat smaller > extent 64-bit output, is to use buffering. I.e. most of the time > generator simply reads pre-calculated word from the buffer and only > ones per N iterations runs an actual PRNG algorithm, probably in a > loop, often in SIMD. In order for this approach to be effective, > buffer can't be particularly small. 32 bytes (256 bits) appear to be > an absolute minimum. The buffer and counter that manages buffering, > are parts of the generator state. That alone sets a practical minimal > limit on the size of generator and diminishes significance of the > difference between PRNGs with "algorithmic" state of 64 bits, 128 bits > or even 256 bits. I understand what you're saying. These concerns are orthogonal to the question of the quality of the numbers generated, which for the purposes of this conversation is all I'm interested in.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-02-03 16:37 +0200 |
| Message-ID | <20260203163708.0000459e@yahoo.com> |
| In reply to | #396570 |
On Tue, 03 Feb 2026 05:26:47 -0800 Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > Michael S <already5chosen@yahoo.com> writes: > > > On Wed, 07 Jan 2026 08:41:25 -0800 > > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > > > >> Michael S <already5chosen@yahoo.com> writes: > >> > >>> On Tue, 23 Dec 2025 17:54:05 -0000 (UTC) > >>> antispam@fricas.org (Waldek Hebisch) wrote: > >> > >> [...] > >> > >>>> There is a paper "PCG: A Family of Simple Fast Space-Efficient > >>>> Statistically Good Algorithms for Random Number Generation" > >>>> by M. O?Neill where she gives a family of algorithms and runs > >>>> several statistical tests against known algorithms. Mersenne > >>>> Twister does not look good in tests. If you have enough (128) > >>>> bits LCGs do pass tests. A bunch of generators with 64-bit > >>>> state also passes tests. So the only reason to prefer Mersenne > >>>> Twister is that it is implemented in available libraries. > >>>> Otherwise it is not so good, have large state and needs more > >>>> execution time than alternatives. > >>> > >>> I don't know. Testing randomness is complicated matter. > >>> How can I be sure that L'Ecuyer and Simard's TestU01 suite tests > >>> things that I personally care about and that it does not test > >>> things that are of no interest for me? Especially, the latter. > >> > >> Do you think any of the tests in the TestU01 suite are actually > >> counter-indicated? As long as you don't think any TestU01 test > >> makes things worse, there is no reason not to use all of them. > >> You are always free to disregard tests you don't care about. > > > > Except that it's difficult psychologically. > > The batteries of test gains position of of authority in your mind. > > Well, may be, you specifically are resistant, but I am not. Nor is > > Melissa O'Nail, it seems. > > > > To illustrate my point, I will tell you the story about myself. > > Sort of confession. > > [very large portion] > > I have read through your whole posting several times, and also > looked through your other postings in this thread. Despite my > efforts I am still not sure what you think or what you're trying to > say. > > Let me put it as a question. Do you think there is a good and > objective test for measuring the quality of a PRNG? If so what test > (or tests) do you think would suffice? Here "quality" is meant as > some sort of numeric measure, which could be a monotonic metric (as > in "the larger the number the higher the quality") or just a simple > pass/fail. > I don't think that it is possible to create generic empirical tests of this sort. What is possible is a test that measures specific property that is known to be important for specific use. > If you don't think there is any such test, how do you propose that > PRNGs be evaluated? > I don't know. But I believe in one philosophical principle that I learned first ~40 years ago in the field unrelated to PRNGs or to Computer Science: when you don't know how to measure quality of your product then it is advisable to ask your consumer. Do not ask a random consumer, ask the one who requested improvement of the property that you have difficulties to measure. He is the most likely one to know. The field where I first heard about that principle was manufacturing of ultra-pure chemicals.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-02-17 23:47 -0800 |
| Message-ID | <86y0kqfq85.fsf@linuxsc.com> |
| In reply to | #396574 |
Michael S <already5chosen@yahoo.com> writes: > On Tue, 03 Feb 2026 05:26:47 -0800 > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > >> Michael S <already5chosen@yahoo.com> writes: >> >>> On Wed, 07 Jan 2026 08:41:25 -0800 >>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >>> >>>> Michael S <already5chosen@yahoo.com> writes: >>>> >>>>> On Tue, 23 Dec 2025 17:54:05 -0000 (UTC) >>>>> antispam@fricas.org (Waldek Hebisch) wrote: >>>> >>>> [...] >>>> >>>>>> There is a paper "PCG: A Family of Simple Fast Space-Efficient >>>>>> Statistically Good Algorithms for Random Number Generation" >>>>>> by M. O?Neill where she gives a family of algorithms and runs >>>>>> several statistical tests against known algorithms. Mersenne >>>>>> Twister does not look good in tests. If you have enough (128) >>>>>> bits LCGs do pass tests. A bunch of generators with 64-bit >>>>>> state also passes tests. So the only reason to prefer Mersenne >>>>>> Twister is that it is implemented in available libraries. >>>>>> Otherwise it is not so good, have large state and needs more >>>>>> execution time than alternatives. >>>>> >>>>> I don't know. Testing randomness is complicated matter. >>>>> How can I be sure that L'Ecuyer and Simard's TestU01 suite tests >>>>> things that I personally care about and that it does not test >>>>> things that are of no interest for me? Especially, the latter. >>>> >>>> Do you think any of the tests in the TestU01 suite are actually >>>> counter-indicated? As long as you don't think any TestU01 test >>>> makes things worse, there is no reason not to use all of them. >>>> You are always free to disregard tests you don't care about. >>> >>> Except that it's difficult psychologically. >>> The batteries of test gains position of of authority in your mind. >>> Well, may be, you specifically are resistant, but I am not. Nor is >>> Melissa O'Nail, it seems. >>> >>> To illustrate my point, I will tell you the story about myself. >>> Sort of confession. >>> [very large portion] >> >> I have read through your whole posting several times, and also >> looked through your other postings in this thread. Despite my >> efforts I am still not sure what you think or what you're trying to >> say. >> >> Let me put it as a question. Do you think there is a good and >> objective test for measuring the quality of a PRNG? If so what test >> (or tests) do you think would suffice? Here "quality" is meant as >> some sort of numeric measure, which could be a monotonic metric (as >> in "the larger the number the higher the quality") or just a simple >> pass/fail. > > I don't think that it is possible to create generic empirical tests > of this sort. > What is possible is a test that measures specific property that is > known to be important for specific use. > >> If you don't think there is any such test, how do you propose that >> PRNGs be evaluated? > > I don't know. > But I believe in one philosophical principle that I learned first ~40 > years ago in the field unrelated to PRNGs or to Computer Science: > when you don't know how to measure quality of your product then it is > advisable to ask your consumer. Do not ask a random consumer, ask the > one who requested improvement of the property that you have > difficulties to measure. He is the most likely one to know. > > The field where I first heard about that principle was manufacturing > of ultra-pure chemicals. I'm surprised to see this answer from you, primarily because it seems to confuse different aspects of the subject. The key property of a (pseudo) random number generator is that the values produced exhibit no discernible pattern. Of course this question cannot be answered absolutely, or more precisely it can be answered definitely only in the negative. Any affirmative answer must be partial and also statistical rather than absolute. If someone wants to write a PRNG for general use, there is no point in asking users what they want, because they don't know. Very few people in the entire world have the mathematical sophistication necessary to answer the question competently (I know I don't, and I would put myself in the 75 percentile or above). The sort of people who could answer the question are also likely to have written test suites like TestU01, so it seems reasonable to use one or more of those test suites to establish a lower bar for any proposed general pupose PRNG. Of course there are properties besides statistical quality measures that might be desirable, such as whether the state of the PRNG can be readily ascertained, the size of the state space, various sorts of cryptographic concerns, and so forth. For some applications there could be performance thresholds that are essential to meet, such as how long to produce a new random value, or what the memory footprint is. But these concerns are outside the domain of the question, which is only about the quality of the values produced. Do you see now what I'm getting at?
[toc] | [prev] | [next] | [standalone]
| From | Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> |
|---|---|
| Date | 2026-02-18 11:21 +0000 |
| Message-ID | <10n47bi$2io53$3@dont-email.me> |
| In reply to | #396673 |
On 18/02/2026 07:47, Tim Rentsch wrote: > The key property of a (pseudo) random number generator is that the > values produced exhibit no discernible pattern. For a PRNG, they exhibit the pattern of following the sequence of the PRNG! Is it that, for any finite sequence of numbers from a PRNG, without information about where it came from and how many numbers came before you can't predict the next number better than chance? -- Tristan Wibberley The message body is Copyright (C) 2026 Tristan Wibberley except citations and quotations noted. All Rights Reserved except that you may, of course, cite it academically giving credit to me, distribute it verbatim as part of a usenet system or its archives, and use it to promote my greatness and general superiority without misrepresentation of my opinions other than my opinion of my greatness and general superiority which you _may_ misrepresent. You definitely MAY NOT train any production AI system with it but you may train experimental AI that will only be used for evaluation of the AI methods it implements.
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2026-02-19 10:01 +0100 |
| Message-ID | <10n6jgg$3bj7e$1@dont-email.me> |
| In reply to | #396674 |
On 18/02/2026 12:21, Tristan Wibberley wrote: > On 18/02/2026 07:47, Tim Rentsch wrote: > >> The key property of a (pseudo) random number generator is that the >> values produced exhibit no discernible pattern. > > For a PRNG, they exhibit the pattern of following the sequence of the PRNG! > As a deterministic function, a PRNG will obviously follow the pattern of its generating function. But the aim is to have no /discernible/ pattern. The sequence 3, 4, 2, 1, 1, 7, 0, 6, 7 has no pattern that could be identified without knowledge of where they came from - and thus no way to predict the next number, 9, in the sequence. But there is a pattern there - it's the 90th - 100th digits of the decimal expansion of pi. > Is it that, for any finite sequence of numbers from a PRNG, without > information about where it came from and how many numbers came before > you can't predict the next number better than chance? > That's the general aim, yes. But Michael is absolutely correct that only the consumer can say what they want to measure in order to judge the quality of any piece of code. It is the customer that gives the requirement specifications, and the programmer's job is to write code that fulfils those specifications. PRNGs are no different. (In practice, many customers need help figuring out what their requirements are, and how to express those, but that's another matter.) In the case of PRNGs, there are many possible requirements beyond the "it's hard to predict the next number in the sequence". These include : * Simplicity of implementation * Cryptographic security of implementation * Running speed * Statistical distribution of values (with many possible patterns, and consideration of length of samples) * Repeat cycle length * Psychological factors (sometimes you roll five sixes in a row, but that might look like a loaded dice. Randomised playlists often use modifications to their PRNGs to avoid repetition of songs, and plotting random points in a 2-D space does not look "random" to most people) * Interaction with added entropy sources As with most requirements for most software, turning most of these into some kind of directly and objectively measurable "quality" function is difficult or impossible in practice. As Michael says, the only thing you can do is when a consumer complains that it is not good enough for their purposes, ask them how to identify when it would be good enough.
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2026-02-19 14:33 -0500 |
| Message-ID | <10n7oie$289ca$2@dont-email.me> |
| In reply to | #396679 |
On 2026-02-19 04:01, David Brown wrote: > On 18/02/2026 12:21, Tristan Wibberley wrote: >> On 18/02/2026 07:47, Tim Rentsch wrote: >> >>> The key property of a (pseudo) random number generator is that the >>> values produced exhibit no discernible pattern. >> >> For a PRNG, they exhibit the pattern of following the sequence of the PRNG! >> > > As a deterministic function, a PRNG will obviously follow the pattern of > its generating function. But the aim is to have no /discernible/ > pattern. The sequence 3, 4, 2, 1, 1, 7, 0, 6, 7 has no pattern that > could be identified without knowledge of where they came from - and thus > no way to predict the next number, 9, in the sequence. But there is a > pattern there - it's the 90th - 100th digits of the decimal expansion of pi. I think you're being overoptimistic. I suspect that the pattern could be identified, exactly, without knowing how it was generated. That's because every possible pattern has infinitely many different ways in which in can be produced. One of those other ways might be easier to describe than the way in which the numbers were actually produced, in which case that simpler way might be guessed more easily that the actual one - possibly a lot easier.
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2026-02-19 20:47 +0100 |
| Message-ID | <10n7pct$3puc5$1@dont-email.me> |
| In reply to | #396680 |
On 19/02/2026 20:33, James Kuyper wrote: > On 2026-02-19 04:01, David Brown wrote: >> On 18/02/2026 12:21, Tristan Wibberley wrote: >>> On 18/02/2026 07:47, Tim Rentsch wrote: >>> >>>> The key property of a (pseudo) random number generator is that the >>>> values produced exhibit no discernible pattern. >>> >>> For a PRNG, they exhibit the pattern of following the sequence of the PRNG! >>> >> >> As a deterministic function, a PRNG will obviously follow the pattern of >> its generating function. But the aim is to have no /discernible/ >> pattern. The sequence 3, 4, 2, 1, 1, 7, 0, 6, 7 has no pattern that >> could be identified without knowledge of where they came from - and thus >> no way to predict the next number, 9, in the sequence. But there is a >> pattern there - it's the 90th - 100th digits of the decimal expansion of pi. > > I think you're being overoptimistic. I suspect that the pattern could be > identified, exactly, without knowing how it was generated. That's > because every possible pattern has infinitely many different ways in > which in can be produced. One of those other ways might be easier to > describe than the way in which the numbers were actually produced, in > which case that simpler way might be guessed more easily that the actual > one - possibly a lot easier. How likely is it that someone would guess a formula that happened to generate the decimal digits of pi, without more knowledge than a part of the sequence? I don't believe it is possible to quantify such a probability, but I would expect it to be very low.
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2026-02-20 16:01 -0500 |
| Message-ID | <10nai2e$289cb$1@dont-email.me> |
| In reply to | #396681 |
On 2026-02-19 14:47, David Brown wrote: ... > How likely is it that someone would guess a formula that happened to > generate the decimal digits of pi, without more knowledge than a part > of the sequence? I don't believe it is possible to quantify such a > probability, but I would expect it to be very low. I'm thinking of the kind of software that looks for patterns in something, such as compression utilities. A compression utility basically converts a long string of numbers into a much shorter string that can be expanded by the decompression utility to recover the original pattern. If you look at the algorithms such code uses, you realize that they do not attempt to recreate the process that originally generated the long string, they just, in effect, characterize the resulting sequence.
[toc] | [prev] | [next] | [standalone]
Page 2 of 10 — ← Prev page 1 [2] 3 4 … 10 Next page →
Back to top | Article view | comp.lang.c
csiph-web