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 3 of 10 — ← Prev page 1 2 [3] 4 5 … 10 Next page →
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2026-02-21 11:09 +0100 |
| Message-ID | <10nc088$15gea$1@dont-email.me> |
| In reply to | #396688 |
On 20/02/2026 22:01, James Kuyper wrote: > 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. > One of the characteristics of a good PRNG is that its unpredictability and its statistical properties (typically they aim to be like white noise, but other distributions are sometimes useful) make them uncompressible with generic algorithms. Since the PRNG's sequence is generated from an algorithm, it is of course always possible to re-create that algorithm as a "compressed" form of the sequence. But generic algorithms will never manage it. Indeed, you can /define/ a random sequence as a series x(i) such that for any given compression algorithm Z, there is an integer n such that the Z-compressed version of x is always bigger than the original x for a sequence length n or more. And for any given compression algorithm Z, you can find a PRNG algorithm that Z cannot compress (after a possible initial segment). I haven't dug through the details, but I am confident that you could show this with a diagonalisation algorithm over Turing machines, or something akin to the halting problem proofs. Or you can just try it yourself: $ dd if=/dev/urandom of=rand bs=1M count=1 $ cp rand rand1 $ cp rand rand2 $ gzip rand1 $ bzip2 rand2 $ ls -l -rw-rw-r-- 1 david david 1048576 Feb 20 09:12 rand -rw-rw-r-- 1 david david 1048760 Feb 20 09:12 rand1.gz -rw-rw-r-- 1 david david 1053414 Feb 20 09:12 rand2.bz2
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <Keith.S.Thompson+u@gmail.com> |
|---|---|
| Date | 2026-02-19 14:39 -0800 |
| Message-ID | <87ikbsgxy2.fsf@example.invalid> |
| In reply to | #396679 |
David Brown <david.brown@hesbynett.no> writes:
[...]
> 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.
[...]
A Google search for 342117067 gives numerous hits referring to the
digits of pi.
--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2026-02-20 09:16 +0100 |
| Message-ID | <10n9584$7int$1@dont-email.me> |
| In reply to | #396685 |
On 19/02/2026 23:39, Keith Thompson wrote: > David Brown <david.brown@hesbynett.no> writes: > [...] >> 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. > [...] > > A Google search for 342117067 gives numerous hits referring to the > digits of pi. > That is using knowledge of where the sequence comes from - something else's knowledge rather than your own, but it's the same principle.
[toc] | [prev] | [next] | [standalone]
| From | Paul <nospam@needed.invalid> |
|---|---|
| Date | 2026-02-23 08:32 -0500 |
| Message-ID | <10nhktn$31293$1@dont-email.me> |
| In reply to | #396687 |
On Fri, 2/20/2026 3:16 AM, David Brown wrote:
> On 19/02/2026 23:39, Keith Thompson wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>> [...]
>>> 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.
>> [...]
>>
>> A Google search for 342117067 gives numerous hits referring to the
>> digits of pi.
>>
>
> That is using knowledge of where the sequence comes from - something else's knowledge rather than your own, but it's the same principle.
>
"In the following sequence, what is the next digit 7,7,7,7,7,7,7,7,7 ? " :-)
PI=3.
1415926535 8979323846 2643383279 5028841971 6939937510
...
7777777772 4846769425 9310468643 5260899021 0266057232 # Line 517834
I suspect seeing that, that's not good.
Using pgmp-chudnovsky.c , and dumping pi as a binary float to a file,
I get this:
(text version of PI) 100,000,022 bytes
PI-Binary.bin 41,524,121 bytes exponent and limbs
PI-Binary.bin.7Z 41,526,823 bytes 7Z Ultra compression, running on 1 core
The entropy property looks pretty good, but I doubt I would
be using that for my supply of random numbers :-)
https://gmplib.org/list-archives/gmp-discuss/2008-November/003444.html
https://stackoverflow.com/questions/3318979/how-to-serialize-the-gmp-mpf-type
https://gmplib.org/list-archives/gmp-discuss/2007-November/002981.html
gcc -DNO_FACTOR -fopenmp -Wall -O2 -o pgmp-chudnovsky pgmp-chudnovsky.c -lgmp -lm
Paul
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2026-02-23 16:05 +0100 |
| Message-ID | <10nhqc9$32dop$1@dont-email.me> |
| In reply to | #396691 |
On 23/02/2026 14:32, Paul wrote: > On Fri, 2/20/2026 3:16 AM, David Brown wrote: >> On 19/02/2026 23:39, Keith Thompson wrote: >>> David Brown <david.brown@hesbynett.no> writes: >>> [...] >>>> 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. >>> [...] >>> >>> A Google search for 342117067 gives numerous hits referring to the >>> digits of pi. >>> >> >> That is using knowledge of where the sequence comes from - something else's knowledge rather than your own, but it's the same principle. >> > > "In the following sequence, what is the next digit 7,7,7,7,7,7,7,7,7 ? " :-) > > PI=3. > > 1415926535 8979323846 2643383279 5028841971 6939937510 > ... > 7777777772 4846769425 9310468643 5260899021 0266057232 # Line 517834 > > I suspect seeing that, that's not good. > > Using pgmp-chudnovsky.c , and dumping pi as a binary float to a file, > I get this: > > (text version of PI) 100,000,022 bytes > PI-Binary.bin 41,524,121 bytes exponent and limbs > PI-Binary.bin.7Z 41,526,823 bytes 7Z Ultra compression, running on 1 core > > The entropy property looks pretty good, but I doubt I would > be using that for my supply of random numbers :-) > In a random sequence of decimal digits, you would expect a sequence of nine identical digits to turn up on average every 10 ^ 8 digits or so. You calculated 10 ^ 8 digits, so it's not surprising to see that here. As for your compression, remember that your text file contains only the digits 0 to 9, spaces and newlines - 12 different characters in 8-bit bytes. If these were purely randomly distributed, you'd expect a best compression ratio of log(12) / log(256), or 0.448. But they are not completely random - your space characters and newlines are predictably spaced so you get marginally better compression ratios. Without spaces and newlines, you'd expect log(10) / log(256) compression - 0.415241012. What a coincidence - this matches your "exponent and limbs", and your compressor can't improve on it. (I downloaded a billion digits of pi and gzip'ed it, for a compression ration of 0.469.) It turns out that the pseudo-randomness here is extremely good. While it has not been proven that pi is "normal" (that is to say, its digits are all evenly distributed), it is strongly believed to be so. Of course it's not a great source of entropy for secure random numbers, but the digits of pi form a fine pseudo-random generator function (if you don't mind the calculation time). > https://gmplib.org/list-archives/gmp-discuss/2008-November/003444.html > https://stackoverflow.com/questions/3318979/how-to-serialize-the-gmp-mpf-type > https://gmplib.org/list-archives/gmp-discuss/2007-November/002981.html > > gcc -DNO_FACTOR -fopenmp -Wall -O2 -o pgmp-chudnovsky pgmp-chudnovsky.c -lgmp -lm > > Paul >
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-02-23 19:59 +0200 |
| Message-ID | <20260223195917.000028af@yahoo.com> |
| In reply to | #396692 |
On Mon, 23 Feb 2026 16:05:45 +0100 David Brown <david.brown@hesbynett.no> wrote: > On 23/02/2026 14:32, Paul wrote: > > On Fri, 2/20/2026 3:16 AM, David Brown wrote: > >> On 19/02/2026 23:39, Keith Thompson wrote: > >>> David Brown <david.brown@hesbynett.no> writes: > >>> [...] > >>>> 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. > >>> [...] > >>> > >>> A Google search for 342117067 gives numerous hits referring to the > >>> digits of pi. > >>> > >> > >> That is using knowledge of where the sequence comes from - > >> something else's knowledge rather than your own, but it's the same > >> principle. > > > > "In the following sequence, what is the next digit > > 7,7,7,7,7,7,7,7,7 ? " :-) > > > > PI=3. > > > > 1415926535 8979323846 2643383279 5028841971 6939937510 > > ... > > 7777777772 4846769425 9310468643 5260899021 0266057232 # Line > > 517834 > > > > I suspect seeing that, that's not good. > > > > Using pgmp-chudnovsky.c , and dumping pi as a binary float to a > > file, I get this: > > > > (text version of PI) 100,000,022 bytes > > PI-Binary.bin 41,524,121 bytes exponent and limbs > > PI-Binary.bin.7Z 41,526,823 bytes 7Z Ultra > > compression, running on 1 core > > > > The entropy property looks pretty good, but I doubt I would > > be using that for my supply of random numbers :-) > > > > In a random sequence of decimal digits, you would expect a sequence > of nine identical digits to turn up on average every 10 ^ 8 digits or > so. You calculated 10 ^ 8 digits, so it's not surprising to see that > here. > > As for your compression, remember that your text file contains only > the digits 0 to 9, spaces and newlines - 12 different characters in > 8-bit bytes. If these were purely randomly distributed, you'd expect > a best compression ratio of log(12) / log(256), or 0.448. But they > are not completely random - your space characters and newlines are > predictably spaced so you get marginally better compression ratios. > Without spaces and newlines, you'd expect log(10) / log(256) > compression - 0.415241012. What a coincidence - this matches your > "exponent and limbs", and your compressor can't improve on it. (I > downloaded a billion digits of pi and gzip'ed it, for a compression > ration of 0.469.) > > It turns out that the pseudo-randomness here is extremely good. > While it has not been proven that pi is "normal" (that is to say, its > digits are all evenly distributed), it is strongly believed to be so. > > Of course it's not a great source of entropy for secure random > numbers, but the digits of pi form a fine pseudo-random generator > function (if you don't mind the calculation time). > Would be interesting to find out if it passes Big Crash of L’Ecuyer. Of course, one would need far more than a billion of decimal digits to have a chance. Something like 100B hexadecimal digits appears to be a minimum. > > > https://gmplib.org/list-archives/gmp-discuss/2008-November/003444.html > > https://stackoverflow.com/questions/3318979/how-to-serialize-the-gmp-mpf-type > > https://gmplib.org/list-archives/gmp-discuss/2007-November/002981.html > > > > gcc -DNO_FACTOR -fopenmp -Wall -O2 -o pgmp-chudnovsky > > pgmp-chudnovsky.c -lgmp -lm > > > > Paul > > >
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2026-02-23 20:06 +0100 |
| Message-ID | <10ni8ff$38dk0$1@dont-email.me> |
| In reply to | #396693 |
On 23/02/2026 18:59, Michael S wrote: > On Mon, 23 Feb 2026 16:05:45 +0100 > David Brown <david.brown@hesbynett.no> wrote: > >> On 23/02/2026 14:32, Paul wrote: >>> On Fri, 2/20/2026 3:16 AM, David Brown wrote: >>>> On 19/02/2026 23:39, Keith Thompson wrote: >>>>> David Brown <david.brown@hesbynett.no> writes: >>>>> [...] >>>>>> 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. >>>>> [...] >>>>> >>>>> A Google search for 342117067 gives numerous hits referring to the >>>>> digits of pi. >>>>> >>>> >>>> That is using knowledge of where the sequence comes from - >>>> something else's knowledge rather than your own, but it's the same >>>> principle. >>> >>> "In the following sequence, what is the next digit >>> 7,7,7,7,7,7,7,7,7 ? " :-) >>> >>> PI=3. >>> >>> 1415926535 8979323846 2643383279 5028841971 6939937510 >>> ... >>> 7777777772 4846769425 9310468643 5260899021 0266057232 # Line >>> 517834 >>> >>> I suspect seeing that, that's not good. >>> >>> Using pgmp-chudnovsky.c , and dumping pi as a binary float to a >>> file, I get this: >>> >>> (text version of PI) 100,000,022 bytes >>> PI-Binary.bin 41,524,121 bytes exponent and limbs >>> PI-Binary.bin.7Z 41,526,823 bytes 7Z Ultra >>> compression, running on 1 core >>> >>> The entropy property looks pretty good, but I doubt I would >>> be using that for my supply of random numbers :-) >>> >> >> In a random sequence of decimal digits, you would expect a sequence >> of nine identical digits to turn up on average every 10 ^ 8 digits or >> so. You calculated 10 ^ 8 digits, so it's not surprising to see that >> here. >> >> As for your compression, remember that your text file contains only >> the digits 0 to 9, spaces and newlines - 12 different characters in >> 8-bit bytes. If these were purely randomly distributed, you'd expect >> a best compression ratio of log(12) / log(256), or 0.448. But they >> are not completely random - your space characters and newlines are >> predictably spaced so you get marginally better compression ratios. >> Without spaces and newlines, you'd expect log(10) / log(256) >> compression - 0.415241012. What a coincidence - this matches your >> "exponent and limbs", and your compressor can't improve on it. (I >> downloaded a billion digits of pi and gzip'ed it, for a compression >> ration of 0.469.) >> >> It turns out that the pseudo-randomness here is extremely good. >> While it has not been proven that pi is "normal" (that is to say, its >> digits are all evenly distributed), it is strongly believed to be so. >> >> Of course it's not a great source of entropy for secure random >> numbers, but the digits of pi form a fine pseudo-random generator >> function (if you don't mind the calculation time). >> > > Would be interesting to find out if it passes Big Crash of L’Ecuyer. > Of course, one would need far more than a billion of decimal digits to > have a chance. Something like 100B hexadecimal digits appears to be a > minimum. > Weirdly (at least /I/ think it is weird), it is easier to calculate hexadecimal digits of pi than decimal digits. At least, it is possible to calculate them independently, without having to calculate and remember all the previous digits. So it should be possible to split the task up and run it in parallel on multiple systems. Of course, confirming that the hexadecimal digits of pi are random enough to pass such a test does not ensure that the decimal digits would do so too. >> >>> https://gmplib.org/list-archives/gmp-discuss/2008-November/003444.html >>> https://stackoverflow.com/questions/3318979/how-to-serialize-the-gmp-mpf-type >>> https://gmplib.org/list-archives/gmp-discuss/2007-November/002981.html >>> >>> gcc -DNO_FACTOR -fopenmp -Wall -O2 -o pgmp-chudnovsky >>> pgmp-chudnovsky.c -lgmp -lm >>> >>> Paul >>> >> > >
[toc] | [prev] | [next] | [standalone]
| From | Paul <nospam@needed.invalid> |
|---|---|
| Date | 2026-02-23 15:24 -0500 |
| Message-ID | <10nid1m$3a655$1@dont-email.me> |
| In reply to | #396694 |
On Mon, 2/23/2026 2:06 PM, David Brown wrote:
>>>> (text version of PI) 100,000,022 bytes
>>>> PI-Binary.bin 41,524,121 bytes exponent and limbs
>
> Weirdly (at least /I/ think it is weird), it is easier to calculate hexadecimal digits of pi than decimal digits.
I computed the decimal representation and the hex representation
(by dumping the exponent and limbs), in the same run.
int mpf_out_raw (FILE *f, mpf_t X) {
int expt; mpz_t Z; size_t nz;
expt = X->_mp_exp;
fwrite(&expt, sizeof(int), 1, f);
nz = X->_mp_size;
Z->_mp_alloc = nz;
Z->_mp_size = nz;
Z->_mp_d = X->_mp_d;
return (mpz_out_raw(f, Z) + sizeof(int));
}
And that's called this way.
/* Open the destination file in binary write mode */
FILE *destination = fopen("PI-Binary.bin", "wb");
if (!destination) {
perror("Error opening PI-Binary.bin file");
} else {
mpf_out_raw(destination, qi); /* qi happens to hold 100 million digits of PI */
fflush(destination);
fclose(destination);
}
You can do them in the same run.
The 7,7,7,7,7,7,7,7,2 sequence was detected in a 32 million digit run
of SuperPi 1.5 XS. The 100 million digit sequence is too large
for SuperPI, and pgmp-chudnovsky.c (with OpenMP) was
used for that, with a little extra code thrown in so I could get
the floating point storage in raw format. It takes a bit more
than one minute, to generate 100 million digits (16 cores). The
compression attempt was done on a single core, to ensure the best
attempt at compression with 7ZIP.
The order of the PI method O() used is covered here.
https://en.wikipedia.org/wiki/Chudnovsky_algorithm
Paul
[toc] | [prev] | [next] | [standalone]
| From | Axel Reichert <mail@axel-reichert.de> |
|---|---|
| Date | 2026-02-24 07:08 +0100 |
| Message-ID | <87342qlll7.fsf@axel-reichert.de> |
| In reply to | #396694 |
David Brown <david.brown@hesbynett.no> writes: > Of course, confirming that the hexadecimal digits of pi are random > enough to pass such a test does not ensure that the decimal digits > would do so too. I was puzzled by the "Of course": To me, this is not intuitively clear. Is there any easy (not too technical) way to "see this"/make it plausible? My gut feeling (wrongly?) said that the base should not affect the randomness of a numerical pattern. "Of course" I am aware (and taught to dozens of numerical beginners) that, say, 0.5 in base 10 has a non terminating representation in base 2, but "random" is neither representation. Pointers or simple counter-examples highly welcome! Axel
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2026-02-24 10:24 +0100 |
| Message-ID | <10njqoi$3n9gd$1@dont-email.me> |
| In reply to | #396696 |
On 24/02/2026 07:08, Axel Reichert wrote: > David Brown <david.brown@hesbynett.no> writes: > >> Of course, confirming that the hexadecimal digits of pi are random >> enough to pass such a test does not ensure that the decimal digits >> would do so too. > > I was puzzled by the "Of course": To me, this is not intuitively clear. > Is there any easy (not too technical) way to "see this"/make it > plausible? My gut feeling (wrongly?) said that the base should not > affect the randomness of a numerical pattern. "Of course" I am aware > (and taught to dozens of numerical beginners) that, say, 0.5 in base 10 > has a non terminating representation in base 2, but "random" is neither > representation. > > Pointers or simple counter-examples highly welcome! > > Axel Numbers can be normal in some bases and not in others. This is easy to see if we pick related bases, such as base 2 and base 16. For example, let x be 1/3. Then x is 0.0101010101... in base 2. That is clearly normal in base 2. But in base 16, it is 0.55555555..., which is clearly very far from normal. I think (but I am not sure) that if a number is normal in base B, then it will be normal in any other bases co-prime to B. If the bases are not co-prime, then things are not as clear (as shown by my simple example). Almost all (in the technical mathematical sense) real numbers are normal in all bases. And lots of numbers (including pi) are believed to be normal, and have been checked to various lengths in many bases. But it is extremely difficult to prove that any given number is normal, unless it can be seen from its construction. Being normal in a base is not sufficient to have the digits form a good pseudo-random sequence, but it is a necessary condition for a uniform distribution random sequence. (I know you set the follow-ups to exclude comp.lang.c, since it is off-topic in that group, but I added it again as I don't follow sci.math.num-analysis, so I would not see any replies. People have different opinions on the pros and cons of limiting follow-up groups. My opinion is that it is better to leave all groups there as long as there are people from different groups in the discussion, even if it is moving off-topic for a group, because limiting follow-up groups can lead to fragmentation. It is better for comp.lang.c to have one off-topic thread than to have multiple threads that are part of the same discussion but appear separately as groups are added and removed. If the discussion goes on for long, and becomes dominated by s.m.n regulars and of no interest to c.l.c regulars, then it becomes time to move it over to just that one group. Others can have different opinions on such matters.)
[toc] | [prev] | [next] | [standalone]
| From | Axel Reichert <mail@axel-reichert.de> |
|---|---|
| Date | 2026-02-26 19:13 +0100 |
| Message-ID | <87342njru2.fsf@axel-reichert.de> |
| In reply to | #396697 |
David Brown <david.brown@hesbynett.no> writes: > Numbers can be normal in some bases and not in others. This is easy to > see if we pick related bases, such as base 2 and base 16. For example, > let x be 1/3. Then x is 0.0101010101... in base 2. That is clearly > normal in base 2. But in base 16, it is 0.55555555..., which is > clearly very far from normal. I had to look up "normal" on Wikipedia and was in for a delightful read. Thanks for the pointer and the nice explanation! Best regards Axel
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@gmail.com> |
|---|---|
| Date | 2025-12-24 05:22 -0600 |
| Message-ID | <10igid7$vddk$1@dont-email.me> |
| In reply to | #395915 |
On 12/23/2025 11:54 AM, 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:
>>
>>> On 2025-12-22 18:13, James Kuyper wrote:
>>>> On 2025-12-22 07:18, Janis Papanagnou wrote:
>>>>> On 2025-12-22 12:44, James Kuyper wrote:
>>>>>> On 2025-12-22 03:48, Michael Sanders wrote:
>>>>>>> Is it incorrect to use 0 (zero) to seed srand()?
>>>>>>>
>>>>>>> int seed = (argc >= 2 && strlen(argv[1]) == 9)
>>>>>>> ? atoi(argv[1])
>>>>>>> : (int)(time(NULL) % 900000000 + 100000000);
>>>>>>>
>>>>>>> srand(seed);
>>>>>>
>>>>>> No, why whould you think so?
>>>>>
>>>>> There's number sequence generators that produce 0 sequences if
>>>>> seeded with 0. ...
>>>>
>>>> The details of how the seed affects the random number sequence are
>>>> unspecified by the standard. I personally would consider a
>>>> pseudo-random number generator to be quite defective if there were
>>>> any seed that produced a constant output.
>>>
>>> I wouldn't have mentioned that if there weren't a whole class of
>>> such functions that expose exactly that behavior by design. Have
>>> a look for PN-(Pseudo Noise-)generators and LFSR (Linear Feedback
>>> Shift Registers). These have been defined to produce random noise
>>> (bit pattern with good statistical distribution). With sophisticated
>>> generator polynomials they produce also sequences of maximum period;
>>> say, for N=31 a non-repeating sequence of length 2^N - 1. The one
>>> element that is missing from the sequence is the 0 (that reproduces
>>> itself).
>>>
>>> Technically you pick some bit-values from fixed positions (depending
>>> on the generator polynomial) of the register and xor the bits to shift
>>> the result into the register. Here's ad hoc an example...
>>>
>>> #include <stdio.h>
>>> #include <stdint.h>
>>>
>>> int main ()
>>> {
>>> uint32_t init = 0x00000038;
>>> uint32_t reg = init;
>>> uint32_t new_bit;
>>> int count = 0;
>>> do {
>>> new_bit = ((reg >> 2) + (reg >> 4) + (reg >> 6) + (reg >>
>>> 30)) & 0x1;
>>> reg <<= 1;
>>> reg |= new_bit;
>>> reg &= 0x7fffffff;
>>> count++;
>>> } while (reg != init);
>>> printf ("period: %d\n", count);
>>> }
>>>
>>>
>>> Janis
>>>
>>>>> [...]
>>>
>>
>> Pay attention that C Standard only requires for the same seed to always
>> produces the same sequence. There is no requirement that different
>> seeds have to produce different sequences.
>> So, for generator in your example, implementation like below would be
>> fully legal. Personally, I wouldn't even consider it as particularly
>> poor quality:
>>
>> void srand(unsigned seed ) { init = seed | 1;}
>>
>> [O.T.]
>> In practice, using LFSR for rand() is not particularly bright idea for
>> different reason: LFSR is a reasonably good PRNG for a single bit, but
>> not when you want to generate a group of 31 pseudo-random bits. In
>> order to get 31 new bits, without predictable repetitions from the
>> previous value, you would have to do 31 steps. That's slow! The process
>> can be accelerate by generation of several bits at time via look up
>> tables, but in order to get decent speed the table has to be rater big
>> and using big tables in standard library is bad sportsmanship.
>>
>> It seems that overwhelming majority C RTLs use Linear Congruential
>> Generators, probably because for Stanadard library compactness of both
>> code and data is considered more important than very high speed (not
>> that on modern HW LCGs are slow) or superior random properties of
>> Mersenne Twisters.
>
> 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.
>
A lot can depend on what one wants as well...
Fast/Simple:
seed=seed*65521+17;
val=(seed>>16)&32767;
At first glance, this approach seems random enough, but these type of
RNGs have a type of repeating pattern that can become obvious, say, if
using them to generate random noise images.
Or, can also work OK (also fast/simple):
seed=(seed<<1)^(~(seed>>7));
val=(seed>>8)&32767;
Some people seem to really like using lookup tables.
64-bit multiply can potentially be very slow, and multiply in general
isn't always cheap, so can make sense to avoid using it if not necessary.
So, shift-and-XOR is fast, above approach is also trivially extended to
64 bits.
Its randomness can be improved somewhat (at the cost of speed), say:
seed1=(seed1<<1)^(~(seed1>>13));
seed2=(seed2<<3)^(~(seed2>>19));
seed1^=seed2>>23;
seed2^=seed1>>23;
val=(seed1>>11)^(seed2>>11);
val=(val^(val>>17))&32767;
Where seed1 and seed2 are two 64-bit values.
Not much formal testing here, mostly just sort of approaches that seemed
to work OK IME.
Had also noted that there are ways to do checksums that are a lot faster
and simpler than more widespread algorithms and also seem to still do
reasonably well at error detection.
Say, for example:
sum1=1; sum2=1;
for(i=0; i<szWords; i++)
{ sum1+=data[i]; sum2+=sum1; }
sum1=((uint32_t)sum1)+(sum1>>32);
sum2=((uint32_t)sum2)+(sum2>>32);
csum=sum1^sum2;
Where, sum1/sum2 are 64-bit, and data is interpreted as 32-bit words,
all unsigned.
But, yeah...
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@gmail.com> |
|---|---|
| Date | 2025-12-24 23:09 -0600 |
| Message-ID | <10iigu8$1kph3$1@dont-email.me> |
| In reply to | #395939 |
On 12/24/2025 5:22 AM, BGB wrote:
> On 12/23/2025 11:54 AM, 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:
>>>
>>>> On 2025-12-22 18:13, James Kuyper wrote:
>>>>> On 2025-12-22 07:18, Janis Papanagnou wrote:
>>>>>> On 2025-12-22 12:44, James Kuyper wrote:
>>>>>>> On 2025-12-22 03:48, Michael Sanders wrote:
>>>>>>>> Is it incorrect to use 0 (zero) to seed srand()?
>>>>>>>>
>>>>>>>> int seed = (argc >= 2 && strlen(argv[1]) == 9)
>>>>>>>> ? atoi(argv[1])
>>>>>>>> : (int)(time(NULL) % 900000000 + 100000000);
>>>>>>>>
>>>>>>>> srand(seed);
>>>>>>>
>>>>>>> No, why whould you think so?
>>>>>>
>>>>>> There's number sequence generators that produce 0 sequences if
>>>>>> seeded with 0. ...
>>>>>
>>>>> The details of how the seed affects the random number sequence are
>>>>> unspecified by the standard. I personally would consider a
>>>>> pseudo-random number generator to be quite defective if there were
>>>>> any seed that produced a constant output.
>>>>
>>>> I wouldn't have mentioned that if there weren't a whole class of
>>>> such functions that expose exactly that behavior by design. Have
>>>> a look for PN-(Pseudo Noise-)generators and LFSR (Linear Feedback
>>>> Shift Registers). These have been defined to produce random noise
>>>> (bit pattern with good statistical distribution). With sophisticated
>>>> generator polynomials they produce also sequences of maximum period;
>>>> say, for N=31 a non-repeating sequence of length 2^N - 1. The one
>>>> element that is missing from the sequence is the 0 (that reproduces
>>>> itself).
>>>>
>>>> Technically you pick some bit-values from fixed positions (depending
>>>> on the generator polynomial) of the register and xor the bits to shift
>>>> the result into the register. Here's ad hoc an example...
>>>>
>>>> #include <stdio.h>
>>>> #include <stdint.h>
>>>>
>>>> int main ()
>>>> {
>>>> uint32_t init = 0x00000038;
>>>> uint32_t reg = init;
>>>> uint32_t new_bit;
>>>> int count = 0;
>>>> do {
>>>> new_bit = ((reg >> 2) + (reg >> 4) + (reg >> 6) + (reg >>
>>>> 30)) & 0x1;
>>>> reg <<= 1;
>>>> reg |= new_bit;
>>>> reg &= 0x7fffffff;
>>>> count++;
>>>> } while (reg != init);
>>>> printf ("period: %d\n", count);
>>>> }
>>>>
>>>>
>>>> Janis
>>>>
>>>>>> [...]
>>>>
>>>
>>> Pay attention that C Standard only requires for the same seed to always
>>> produces the same sequence. There is no requirement that different
>>> seeds have to produce different sequences.
>>> So, for generator in your example, implementation like below would be
>>> fully legal. Personally, I wouldn't even consider it as particularly
>>> poor quality:
>>>
>>> void srand(unsigned seed ) { init = seed | 1;}
>>>
>>> [O.T.]
>>> In practice, using LFSR for rand() is not particularly bright idea for
>>> different reason: LFSR is a reasonably good PRNG for a single bit, but
>>> not when you want to generate a group of 31 pseudo-random bits. In
>>> order to get 31 new bits, without predictable repetitions from the
>>> previous value, you would have to do 31 steps. That's slow! The process
>>> can be accelerate by generation of several bits at time via look up
>>> tables, but in order to get decent speed the table has to be rater big
>>> and using big tables in standard library is bad sportsmanship.
>>>
>>> It seems that overwhelming majority C RTLs use Linear Congruential
>>> Generators, probably because for Stanadard library compactness of both
>>> code and data is considered more important than very high speed (not
>>> that on modern HW LCGs are slow) or superior random properties of
>>> Mersenne Twisters.
>>
>> 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.
>>
>
> A lot can depend on what one wants as well...
>
> Fast/Simple:
> seed=seed*65521+17;
> val=(seed>>16)&32767;
>
> At first glance, this approach seems random enough, but these type of
> RNGs have a type of repeating pattern that can become obvious, say, if
> using them to generate random noise images.
>
Turns out more true of the one below than the one above, though both are
still pretty weak.
Usually, one very quick/dirty way to test a RNG is to generate an image
filled with random numbers:
If it looks like white noise, the RNG works OK;
If the image has repeating patterns or any other sort of obvious
structure, the RNG is broken.
Not a great test, but for many practical use cases may be good enough.
The above example shows evidence of "structural" features, implying the
RNG may not be particularly strong.
>
> Or, can also work OK (also fast/simple):
> seed=(seed<<1)^(~(seed>>7));
> val=(seed>>8)&32767;
>
Got around to testing, this particular one was kinda broken (breaks down
into repeating patterns).
A tweak, say:
seed=(seed<<1)^(~(seed>>7))^(seed>>21);
val=(seed>>8)&32767;
Is much better...
Also seems to work:
seed=(seed<<3)^(~(seed>>19))^(seed>>13);
Etc.
Seems the simple pattern with one XOR may be too little, and at least
two XORs may be needed here. But, this approach is still fragile and
prone to break down into repeating patterns. Also seems to need a mix of
a prime and non-prime for some reason.
A lot may depend on on how quickly the random numbers need to be
generated vs the quality of the needed randomness (and whether or not
the target machine has a fast integer multiply).
Where, say, one down-side of more traditional "multiply 64-bit value by
constant" RNGs is that performance suffers badly in the absence of fast
64-bit multiply.
one other tradeoff being if the target machine is natively 32 or 64 bit.
In some cases, it may make sense to do a fast RNG with a simpler
algorithm, but then ever N numbers, reseed the fast RNG with a number
generated by a slower but more powerful RNG.
Where, say, fast RNG may be needed for things like genetic algorithms
where often the performance of the mutation step depends highly on
having fast random numbers (with the actual goodness of the RNG being
secondary, but a certain minimum is needed to avoid the process breaking
down).
> Some people seem to really like using lookup tables.
>
I don't really get the point of lookup table driven RNGs.
A lot of these ones are, say, a table with 256 spots, and an index.
Each time one generates a random number (usually a byte), it returns the
value at that location in the table and advances to the next index.
Sometimes some get clever and use an algorithm to jitter the table index.
I have mostly seen this strategy used in old game engines.
These typically fail the image test as by design they give repeating
patterns.
> 64-bit multiply can potentially be very slow, and multiply in general
> isn't always cheap, so can make sense to avoid using it if not necessary.
>
> So, shift-and-XOR is fast, above approach is also trivially extended to
> 64 bits.
>
> Its randomness can be improved somewhat (at the cost of speed), say:
> seed1=(seed1<<1)^(~(seed1>>13));
> seed2=(seed2<<3)^(~(seed2>>19));
> seed1^=seed2>>23;
> seed2^=seed1>>23;
> val=(seed1>>11)^(seed2>>11);
> val=(val^(val>>17))&32767;
>
> Where seed1 and seed2 are two 64-bit values.
>
> Not much formal testing here, mostly just sort of approaches that seemed
> to work OK IME.
>
The strategy used above is closer to what I had often used IME.
If more randomness is needed, the pattern can be extended to 4 seeds and
with more variability in the shifts.
Or, can also be trimmed down if it needs to be faster.
> Had also noted that there are ways to do checksums that are a lot faster
> and simpler than more widespread algorithms and also seem to still do
> reasonably well at error detection.
>
> Say, for example:
> sum1=1; sum2=1;
> for(i=0; i<szWords; i++)
> { sum1+=data[i]; sum2+=sum1; }
> sum1=((uint32_t)sum1)+(sum1>>32);
> sum2=((uint32_t)sum2)+(sum2>>32);
> csum=sum1^sum2;
>
> Where, sum1/sum2 are 64-bit, and data is interpreted as 32-bit words,
> all unsigned.
>
A variant running 2 or 4 sets of sums in parallel can also be faster,
but the single pair of sums demonstrates the basic idea.
Though, special handling may be needed if the data is not a multiple of
the working size (if this needs to be handled, one may need special case
logic to deal with the last N bytes).
Note here that a single linear sum of all the values, while fast, is
often unreasonably weak (and will miss many types of errors).
A second sum of the first sum can greatly increase error detection.
While, at the same time, being significantly faster than something like
CRC32 (one may find that for various use-cases, things like CRC32 or
Adler32 checksums may be unacceptably slow).
I have yet to find an ideally fast strategy for hashing strings.
One simple strategy is, say:
h=0; cs=str;
while(*cs)h=h*251+(*cs++);
h=h*251+1;
v=(h>>8)&4095; //or, whatever is the size of the hash table.
But, this isn't particularly fast.
But, then another problem is that strings are usually short and one
doesn't know the length in advance. Using "strlen()" also being not
exactly fast either (trying to use "strlen()") may be slower than the
naive approach.
one variation of the above is, say:
cs=str+1; c=*str; h=0;
while(c) { h=h*251+c; c=*cs++; }
Or, say:
cs=str+1; c=*str; h=0;
while(c) { h=(h<<7)+(c-h); c=*cs++; }
Or, ...
But, gains are small, and usually not really an obvious way to speed it
up when the majority of string lengths are between 3 and 7 characters
(most strategies being more effective against longer strings).
while, at least, excluding wonk like:
c0=str[0]; c1=str[1]; ...
if(!c0) { return(0); }
if(!c1) { return(c0); }
if(!c2) { return((c0*31+c1)&4095); }
...
Then falling back to a generic strategy for 8+ characters.
...
> But, yeah...
>
[toc] | [prev] | [next] | [standalone]
| From | Janis Papanagnou <janis_papanagnou+ng@hotmail.com> |
|---|---|
| Date | 2025-12-25 09:51 +0100 |
| Message-ID | <10iitu3$25ihi$8@dont-email.me> |
| In reply to | #395962 |
On 2025-12-25 06:09, BGB wrote: > On 12/24/2025 5:22 AM, BGB wrote: >> >> Some people seem to really like using lookup tables. Of course; they can speed up things significantly. And simplify the operations for contemporary data sizes (bytes, 64 bit words, etc.). > > I don't really get the point of lookup table driven RNGs. In e.g. bit-oriented algorithms (e.g. based on LFSR) you can speed up processing significantly by processing larger quantities (like octets/bytes) and processing/accessing values then byte-wise.[*] Someone already mentioned that a bit-wise operating PN-generator for random numbers could make use of such a table driven approach. (You can extend that principle to larger quantities than bits, e.g. to gain from larger processor word lengths, especially it you need those larger entities as result in the first place.) > A lot of these ones are, say, a table with 256 spots, and an index. > Each time one generates a random number (usually a byte), it returns the > value at that location in the table and advances to the next index. > > Sometimes some get clever and use an algorithm to jitter the table index. > > I have mostly seen this strategy used in old game engines. > > These typically fail the image test as by design they give repeating > patterns. > > [...] Janis [*] Here's some old "C" example for a CRC-16 using table-lookup... http://random.gridbug.de/ccitt_crc16.c
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@gmail.com> |
|---|---|
| Date | 2025-12-25 04:24 -0600 |
| Message-ID | <10ij3cc$1pj2a$1@dont-email.me> |
| In reply to | #395968 |
On 12/25/2025 2:51 AM, Janis Papanagnou wrote:
> On 2025-12-25 06:09, BGB wrote:
>> On 12/24/2025 5:22 AM, BGB wrote:
>>>
>>> Some people seem to really like using lookup tables.
>
> Of course; they can speed up things significantly. And simplify
> the operations for contemporary data sizes (bytes, 64 bit words,
> etc.).
>
>>
>> I don't really get the point of lookup table driven RNGs.
>
> In e.g. bit-oriented algorithms (e.g. based on LFSR) you can speed
> up processing significantly by processing larger quantities (like
> octets/bytes) and processing/accessing values then byte-wise.[*]
>
> Someone already mentioned that a bit-wise operating PN-generator
> for random numbers could make use of such a table driven approach.
> (You can extend that principle to larger quantities than bits, e.g.
> to gain from larger processor word lengths, especially it you need
> those larger entities as result in the first place.)
>
I meant, more like this (from Doom):
<==
unsigned char rndtable[256] = {
0, 8, 109, 220, 222, 241, 149, 107, 75, 248, 254, 140, 16, 66 ,
74, 21, 211, 47, 80, 242, 154, 27, 205, 128, 161, 89, 77, 36 ,
95, 110, 85, 48, 212, 140, 211, 249, 22, 79, 200, 50, 28, 188 ,
52, 140, 202, 120, 68, 145, 62, 70, 184, 190, 91, 197, 152, 224 ,
149, 104, 25, 178, 252, 182, 202, 182, 141, 197, 4, 81, 181, 242 ,
145, 42, 39, 227, 156, 198, 225, 193, 219, 93, 122, 175, 249, 0 ,
175, 143, 70, 239, 46, 246, 163, 53, 163, 109, 168, 135, 2, 235 ,
25, 92, 20, 145, 138, 77, 69, 166, 78, 176, 173, 212, 166, 113 ,
94, 161, 41, 50, 239, 49, 111, 164, 70, 60, 2, 37, 171, 75 ,
136, 156, 11, 56, 42, 146, 138, 229, 73, 146, 77, 61, 98, 196 ,
135, 106, 63, 197, 195, 86, 96, 203, 113, 101, 170, 247, 181, 113 ,
80, 250, 108, 7, 255, 237, 129, 226, 79, 107, 112, 166, 103, 241 ,
24, 223, 239, 120, 198, 58, 60, 82, 128, 3, 184, 66, 143, 224 ,
145, 224, 81, 206, 163, 45, 63, 90, 168, 114, 59, 33, 159, 95 ,
28, 139, 123, 98, 125, 196, 15, 70, 194, 253, 54, 14, 109, 226 ,
71, 17, 161, 93, 186, 87, 244, 138, 20, 52, 123, 251, 26, 36 ,
17, 46, 52, 231, 232, 76, 31, 221, 84, 37, 216, 165, 212, 106 ,
197, 242, 98, 43, 39, 175, 254, 145, 190, 84, 118, 222, 187, 136 ,
120, 163, 236, 249
};
int rndindex = 0;
int prndindex = 0;
int P_Random (void)
{
prndindex = (prndindex+1)&0xff;
return rndtable[prndindex];
}
int M_Random (void)
{
rndindex = (rndindex+1)&0xff;
return rndtable[rndindex];
}
void M_ClearRandom (void)
{
rndindex = prndindex = 0;
}
==>
Like, why?...
There are different/better ways of doing RNG.
Granted, can't really change this in Doom, because modifying it means
that demos will desync (or, at least, more than they desync already).
Apparently some source-ports (like ZDoom) put significant effort into
immitating the behavior of each version of the Doom engine such that the
demos from the corresponding IWADs work (with magic to try to identify
the Doom version by pattern-matching the IWAD).
My port is based on linuxdoom, and doesn't go this far (there was a
combination of both algorithmic differences and also Doom to some extent
being sensitive to the contents of memory from out-of-bounds memory
accesses).
Had tried copying a few simple tricks from ZDoom, but were not enough to
get desync free demo-playback (though, it plays out the same between
builds for different targets, ...).
Kind of a similar issue with my ROTT port, except that ROTT is more of a
mess, and there isn't even consistency between runs, or even necessarily
between different runs of the same demo within the demo loop.
Had sort of got it stabilized, but in the past could seemingly only get
consistent desync-free playback when built for 32-bit x86.
But, then again, did at one point investigate why a feature had broken
in ROTT, and realized that the code in question was sensitive to (among
other things) the specific behavior of a signed-integer overflow when
promoting to a larger type (it only worked correctly if it first
overflowed at the narrower size and was then promoted; rather than one
where it simply did the operation at the wider size with no
wrap-on-overflow behavior).
Well, and also a lot of cases where there was a lot of out-of-bounds
accesses, which I then needed to try to hack around to handle in some
way "sensible" that was still mostly consistent with the original
out-of-bounds access behavior.
And, some amount of "YOLO" array access, namely accessing one array out
of bounds to access stuff in another array mostly depending on their
relative locations in memory (this is not a coding style that I
particularly consider acceptable, unless maybe the application itself
directly controls the memory layout, rather than something that is
mostly in the domain of the C compiler or linker).
Though, there did still end up being a certain amount of "characteristic
behavior" changes resulting from fixing up OOB issues.
Say, for example, if the player manages to get outside the map, rather
than the game corrupting memory and crashing; one may find themselves on
an infinite plane where the map just wraps around (once every 128 blocks).
But, despite everything, there is still some sort of lingering
non-determinism in the mix here.
...
Well, at least my Hexen port seemingly has non-desync'ing demos. And my
Heretic port seemingly works correctly with the Shareware WAD I have
(but not with a registered WAD; but the registered WAD has a lot more
maps vs the Shareware version).
As with Doom, behavior is mostly consistent across targets. Though, each
did require modification to work on ARM, since ARM defaults to unsigned
char and the various versions of the Doom engine had contained code that
assumed that 'char' was signed (well, along with a lot of obligatory
changes in "r_data.c" and similar to deal with 64-bit targets having
64-bit pointers and similar, etc).
...
Some later games (mostly starting with Quake) had instead avoided desync
issues by recording game event messages. Rather than trying to record
and playback player keyboard inputs and similar.
Though, in my attempt to port Quake3, I ended up dropping the original
QVM as it was designed in a way that wasn't really compatible with
64-bit machines (but, the "game" code was also written in C and so could
be compiled to native code).
In my case, one possibility could be (if I want to move away from native
code) compiling the "game VM" scripts as RISC-V or similar and then
using an RV64 VM in place of the QVM (well, this or figure out how to
make the QVM work on a 64-bit host, but this is harder as it also
assumes sharing structs between the host and VM, which only really works
if both have the same layout).
Some fudging was needed with the Quake 1 "progs.dat" VM, but had been a
little simpler as less was required here (went from absolute addresses
to hunk-relative addresses for things like strings, etc). Well, because
again the VM was designed in a way that it was not particularly
amendable to changing memory layout for some structures based on things
like pointer size. In this case, there was a relatively smaller cross
section, so switching to functions to wrap/unwrap strings and similar
was less of an issue.
...
>> A lot of these ones are, say, a table with 256 spots, and an index.
>> Each time one generates a random number (usually a byte), it returns
>> the value at that location in the table and advances to the next index.
>>
>> Sometimes some get clever and use an algorithm to jitter the table index.
>>
>> I have mostly seen this strategy used in old game engines.
>>
>> These typically fail the image test as by design they give repeating
>> patterns.
>>
>> [...]
>
> Janis
>
> [*] Here's some old "C" example for a CRC-16 using table-lookup...
> http://random.gridbug.de/ccitt_crc16.c
>
Not exactly the same thing, but works.
Even as such though, lookup table driven CRC still isn't particularly
fast if compared with "linear sums of 32-bit words" or similar.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-01-07 07:50 -0800 |
| Message-ID | <86y0m9o21a.fsf@linuxsc.com> |
| In reply to | #395915 |
antispam@fricas.org (Waldek Hebisch) writes: [...] > 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. Interesting paper. Thank you.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-01-07 07:46 -0800 |
| Message-ID | <86344hpgrj.fsf@linuxsc.com> |
| In reply to | #395887 |
Michael S <already5chosen@yahoo.com> writes:
[regarding rand() and srand()]
> Pay attention that C Standard only requires for the same seed to always
> produces the same sequence. There is no requirement that different
> seeds have to produce different sequences.
> So, for generator in your example, implementation like below would be
> fully legal. Personally, I wouldn't even consider it as particularly
> poor quality:
>
> void srand(unsigned seed ) { init = seed | 1;}
It seems better to do, for example,
void srand(unsigned seed ) { init = seed - !seed;}
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-01-07 18:14 +0200 |
| Message-ID | <20260107181414.000001f6@yahoo.com> |
| In reply to | #396268 |
On Wed, 07 Jan 2026 07:46:40 -0800
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Michael S <already5chosen@yahoo.com> writes:
>
> [regarding rand() and srand()]
>
> > Pay attention that C Standard only requires for the same seed to
> > always produces the same sequence. There is no requirement that
> > different seeds have to produce different sequences.
> > So, for generator in your example, implementation like below would
> > be fully legal. Personally, I wouldn't even consider it as
> > particularly poor quality:
> >
> > void srand(unsigned seed ) { init = seed | 1;}
>
> It seems better to do, for example,
>
> void srand(unsigned seed ) { init = seed - !seed;}
>
Yes, it is better.
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <046-301-5902@kylheku.com> |
|---|---|
| Date | 2025-12-22 19:16 +0000 |
| Message-ID | <20251222105904.410@kylheku.com> |
| In reply to | #395886 |
On 2025-12-22, Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
> On 2025-12-22 18:13, James Kuyper wrote:
>> On 2025-12-22 07:18, Janis Papanagnou wrote:
>>> On 2025-12-22 12:44, James Kuyper wrote:
>>>> On 2025-12-22 03:48, Michael Sanders wrote:
>>>>> Is it incorrect to use 0 (zero) to seed srand()?
>>>>>
>>>>> int seed = (argc >= 2 && strlen(argv[1]) == 9)
>>>>> ? atoi(argv[1])
>>>>> : (int)(time(NULL) % 900000000 + 100000000);
>>>>>
>>>>> srand(seed);
>>>>
>>>> No, why whould you think so?
>>>
>>> There's number sequence generators that produce 0 sequences if seeded
>>> with 0. ...
>>
>> The details of how the seed affects the random number sequence are
>> unspecified by the standard. I personally would consider a pseudo-random
>> number generator to be quite defective if there were any seed that
>> produced a constant output.
>
> I wouldn't have mentioned that if there weren't a whole class of
> such functions that expose exactly that behavior by design. Have
> a look for PN-(Pseudo Noise-)generators and LFSR (Linear Feedback
> Shift Registers).
The entire class of LFRS's is not homogeneous in this way; it
is possible for a Linear Boolean function to generate a nonzero
out of zero inputs.
The LFSR page in the Wikipedia references this definition:
https://en.wikipedia.org/wiki/Linearity#Boolean_functions
A Boolean linear function of the inputs x1, ... xn is
a kind of polynomial with coefficients C0, C1, ... CN combined
with the inputs using AND for multiplication, and XOR for addition:
f(x1, ... xn) = C0 ^ (C1 & x1) ^ (C2 & x2) ^ .. ^ (Cn ^ xn)
If c0 is chosen as 1, then we get a 1 output when all the x's are
zero. (The article uses "b" for the parameters and "a" for the
coefficients, which I'm not crazy about.)
Also see the two conditions, given in the description, one of which has
to be true for Boolean linearity. For condition (2) the remark is given
that under that condition f(F, F, F, ... F) = T.
So if we have a "condition 2" linear function, our LSFR avoids
the behavior.
I don't recall having paid attention to this exact material in the
past so it is a "TIL" for me.
> #include <stdint.h>
>
> int main ()
> {
> uint32_t init = 0x00000038;
> uint32_t reg = init;
> uint32_t new_bit;
> int count = 0;
> do {
> new_bit = ((reg >> 2) + (reg >> 4) + (reg >> 6) + (reg >> 30))
> & 0x1;
These could of course be XOR, without it making a difference; the least
significant bit in a binary addition is the XOR of the LSB's of the
inputs.
> reg <<= 1;
> reg |= new_bit;
So to have that C0 = 1 coefficient in the linear function, we just make
it "reg |= (new_bit ^ 1);".
--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
[toc] | [prev] | [next] | [standalone]
| From | Janis Papanagnou <janis_papanagnou+ng@hotmail.com> |
|---|---|
| Date | 2025-12-22 22:35 +0100 |
| Message-ID | <10icdj7$25ihi$4@dont-email.me> |
| In reply to | #395888 |
On 2025-12-22 20:16, Kaz Kylheku wrote:
> On 2025-12-22, Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
[...]
> I don't recall having paid attention to this exact material in the
> past so it is a "TIL" for me.
What does "TIL" mean?
I actually had used PN-generators in the past; used it in a Pascal
program to make statistical tests, and also in assembler for a DSP
codec to create reproducible random payload data to compare after
transmission. For that purpose it was the perfect choice.
>
>> #include <stdint.h>
>>
>> int main ()
>> {
>> uint32_t init = 0x00000038;
>> uint32_t reg = init;
>> uint32_t new_bit;
>> int count = 0;
>> do {
>> new_bit = ((reg >> 2) + (reg >> 4) + (reg >> 6) + (reg >> 30))
>> & 0x1;
>
> These could of course be XOR, without it making a difference; the least
> significant bit in a binary addition is the XOR of the LSB's of the
> inputs.
Actually the pluses are a remnant of my decades old piece of Pascal
code that I wrote back then that I now just transcribed. The Pascal
version I used back then didn't support XOR so I used the addition.
Being in a boolean context I'd nowadays (in C) have rather written
purely new_bit = ((reg>>2)^(reg>>4)^(reg>>6)^(reg>>30)) & 0x1;
but since it's unimportant, as you say, I lazily left it as it was.
Janis
> [...]
[toc] | [prev] | [next] | [standalone]
Page 3 of 10 — ← Prev page 1 2 [3] 4 5 … 10 Next page →
Back to top | Article view | comp.lang.c
csiph-web