Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #139043 > unrolled thread
| Started by | "Rick C. Hodgin" <rick.c.hodgin@gmail.com> |
|---|---|
| First post | 2018-12-24 19:54 -0500 |
| Last post | 2018-12-26 11:58 -0800 |
| Articles | 20 on this page of 87 — 14 participants |
Back to article view | Back to comp.lang.c
Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-24 19:54 -0500
Re: Multi-channel rand() "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-24 19:38 -0800
Re: Multi-channel rand() nobody@example.org (Scott) - 2018-12-25 04:05 +0000
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-24 23:57 -0500
Re: Multi-channel rand() Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2018-12-25 09:22 +0000
Professional coders??? (Was: Multi-channel rand()) gazelle@shell.xmission.com (Kenny McCormack) - 2018-12-25 10:09 +0000
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-25 07:59 -0500
Re: Multi-channel rand() Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2018-12-25 21:59 +0000
Re: Multi-channel rand() nobody@example.org (Scott) - 2018-12-26 02:43 +0000
Re: Multi-channel rand() rbowman <bowman@montana.com> - 2018-12-25 10:15 -0700
Re: Multi-channel rand() Keith Thompson <kst-u@mib.org> - 2018-12-25 10:14 -0800
Re: Multi-channel rand() Anton Shepelev <anton.txt@g{oogle}mail.com> - 2018-12-25 13:35 +0300
Re: Multi-channel rand() fir <profesor.fir@gmail.com> - 2018-12-25 02:56 -0800
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-25 08:02 -0500
Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-25 11:52 +0000
Re: Multi-channel rand() Anton Shepelev <anton.txt@g{oogle}mail.com> - 2018-12-25 14:58 +0300
Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-25 06:59 -0500
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-25 08:05 -0500
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-25 08:04 -0500
Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-26 15:48 +0000
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 07:58 -0800
Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 12:06 -0500
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 12:45 -0500
Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 13:20 -0500
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 10:30 -0800
Re: Multi-channel rand() "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-26 11:35 -0800
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 14:52 -0500
Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 16:31 -0500
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 22:28 -0500
Re: Multi-channel rand() "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-30 20:42 -0800
Re: Multi-channel rand() Keith Thompson <kst-u@mib.org> - 2018-12-26 15:32 -0800
Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-26 19:38 +0000
Re: Multi-channel rand() Keith Thompson <kst-u@mib.org> - 2018-12-26 15:35 -0800
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 12:59 -0500
Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 16:05 -0500
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 13:08 -0500
Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 15:50 -0500
Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-26 17:42 +0000
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 12:48 -0500
Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 12:58 -0500
Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-26 19:03 +0000
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 14:45 -0500
Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-26 20:46 +0000
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 16:25 -0500
Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 17:13 -0500
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 22:23 -0500
Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-26 23:39 +0000
Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 17:36 -0500
Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 16:27 -0500
Re: Multi-channel rand() rbowman <bowman@montana.com> - 2018-12-26 19:19 -0700
Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 22:17 -0500
Re: Multi-channel rand() James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-26 19:32 -0800
Re: Multi-channel rand() Keith Thompson <kst-u@mib.org> - 2018-12-26 19:34 -0800
Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-27 11:29 +0000
Re: Multi-channel rand() James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-27 05:27 -0800
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-27 09:41 -0500
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-27 09:42 -0500
Re: Multi-channel rand() James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-27 07:01 -0800
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-27 10:28 -0500
Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-27 10:48 -0500
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-27 11:08 -0500
Re: Multi-channel rand() "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-27 13:49 -0800
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-27 17:18 -0500
Re: Multi-channel rand() "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-29 13:59 -0800
Re: Multi-channel rand() "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-30 14:01 -0800
Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-30 22:07 +0000
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-30 17:20 -0500
Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-27 17:47 -0500
Re: Multi-channel rand() "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-30 20:45 -0800
Re: Multi-channel rand() James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-27 08:22 -0800
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-27 11:40 -0500
Re: Multi-channel rand() James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-27 09:21 -0800
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-27 12:45 -0500
Re: Multi-channel rand() James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-27 10:57 -0800
Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-27 14:35 -0500
Re: Multi-channel rand() Tim Rentsch <txr@alumni.caltech.edu> - 2018-12-28 09:25 -0800
Re: Multi-channel rand() Tim Rentsch <txr@alumni.caltech.edu> - 2018-12-28 09:55 -0800
Re: Multi-channel rand() Keith Thompson <kst-u@mib.org> - 2018-12-28 12:36 -0800
Re: Multi-channel rand() Robert Wessel <robertwessel2@yahoo.com> - 2018-12-27 20:34 -0600
Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-27 10:37 -0500
Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-27 14:46 +0000
Re: Multi-channel rand() James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-27 07:05 -0800
Re: Multi-channel rand() Keith Thompson <kst-u@mib.org> - 2018-12-27 11:28 -0800
Re: Multi-channel rand() James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-27 12:07 -0800
Re: Multi-channel rand() Keith Thompson <kst-u@mib.org> - 2018-12-27 12:47 -0800
Re: Multi-channel rand() James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-27 14:47 -0800
Re: Multi-channel rand() "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-26 11:58 -0800
Page 3 of 5 — ← Prev page 1 2 [3] 4 5 Next page →
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2018-12-26 19:03 +0000 |
| Message-ID | <SfQUD.95217$ck7.2645@fx02.am4> |
| In reply to | #139088 |
On 26/12/2018 17:58, Richard Damon wrote:
> On 12/26/18 12:42 PM, Bart wrote:
>> On 26/12/2018 15:58, Rick C. Hodgin wrote:
>>> On Wednesday, December 26, 2018 at 10:48:31 AM UTC-5, Bart wrote:
>>
>>>> However this depends entirely on the PRNG used. The point of my example
>>>> is to show how easy it is to superimpose a 'multi-channel' API on a
>>>> single-stream PRNG.)
>>>
>>> I agree. That's what I intended to do, but I didn't know where
>>> there was good prng source code that was in the Public Domain.
>>>
>>> I'm looking for a nicely distributed prng. I'm using the built-
>>> in one with Visual C++ presently and it has really odd patterns
>>> which, when scaled into a lesser range (like 1-10), produce oft-
>>> repeated values.
>>
>> Really? I tried the simple PRNG I showed, using a%10 to produce values
>> from 0 to 9, which is supposed to be really bad idea, and got this
>> distribution over 1 billion calls for each of the digits:
>>
>> 0: 100011113
>> 1: 99989920
>> 2: 100009423
>> 3: 100004327
>> 4: 99991057
>> 5: 100000307
>> 6: 99998986
>> 7: 100014477
>> 8: 99982849
>> 9: 99997541
>>
>> A perfect distribution would have 100,000,000 of each, so these are out
>> by 1 in 10,000 or so.
>>
>
> The low order bits of many random number gererators tend to be well
> distributed, but often have patterned between them. Try running an
> analysis of first order transition, a 2d histogram of consecutive
> values.
I get the following, which counts the transitions from 0..9 to 0..9 over
one billion random-10 calls; there should be 10 million of each:
0 1 2 3 4
0 10000414 9999532 9996911 10002996 10001089
1 10001890 9998825 9997192 9999400 10001881
2 9998577 9998102 10004200 10001680 9996506
3 10003276 9999146 10002297 9996187 10000437
4 10005587 9999423 10001425 10004535 9996548
5 10001042 9998557 10001422 10002560 9998100
6 9999956 9999384 10004437 9996324 9999880
7 9999302 10000587 10004574 10000900 9997869
8 10002703 9996356 9999180 9999575 9997773
9 9998366 10000008 9997785 10000170 10000974
5 6 7 8 9
0 10000507 10002884 10006255 9997911 10002615
1 9993337 10001477 9999119 9999063 9997736
2 10003593 10004684 10000610 10001144 10000327
3 10001675 10001016 9999818 9999108 10001367
4 9995269 9996443 9998453 9996897 9996477
5 9998838 10001826 9998264 10002608 9997090
6 9999320 9998757 10010484 9993826 9996618
7 10005658 9998981 10002985 10002377 10001243
8 10002130 9990532 9997172 9995304 10002124
9 9999980 10002386 10001317 9994611 10001944
That doesn't seem too bad. If I look at sequences of the same number, I
get maximum sequence lengths of 10 to 13 digits over 1e9 digits, which
seems a trifle high to me, but I'm not enough of an expert to say for
sure. (Testing with hex digits 0 to F avoiding a mod 10, I get sequence
lengths of 8 to 11, also higher than I expected).
The actual output, for 0..9, looks like the following, where nothing
really stands out:
172719542559972470635781476779768246152771301359732754928962007319072058
629568748614382035743833479538729684345257533742676855451529244801094767
812845890221385497061155762986727198813834346321959899873668463923055975
820941872847984046024835753195663531498820214115074959914531603749469529
447492979631267615026293843971150249392770292356156346308504037109626400
687132451528921091199043115686466904987229756385495862306971467194013476
468484351392791376862638613277276953688102523557649143386693836629518504
016857650209349040717607109415786179565319122177210867907124819031404557
671074295474450339453126838352065038456508225959989772906639803211130836
098546491616976054834068466660813854447318244159358029550917371871288233
559382917453279701389983903548012658128342595855912771991845537501860912
976324408123521349020805014641587946984532084899703614377067591706110310
790948834498366595574590346531865494008536798788697237452946718037886658
251930400805408988452350125628447321814405565496407859677929743739476726
621429906839610740551678170087472138600367142684773877141494292000077312
320161874381554917167810024319572249156985780215103297217226479280392025
790206829738083633657898496359947060064216367055190104444333906479331793
631338124102557467838758910838355710154816866412636938145300416284845446
428548049328719393982268159632293633844568486822260101894037487930916339
226189861855838502767023693362611655754742764496149337285706521711616949
693399855382774224982846899446580872169881455634183670705917669996067516
636716906082326760179831355393548519138204143743929819493599643980481592
858481977406972994238357183540253907631810947637105309470720498375266560
287541778780192967265975728848473810798583130669021704416604521336971650
235168192979034276941924284298081308416724706162288832366468331013326705
514050453012741545562675098290262635177503322692149528258143381928782237
836453498509792719958166229644782199662855436955458577685177768808947644
292329650351733644970222707237033851363747053960753560213256150579938571
754690088666533998897506573748269695873868473355069182432798294585939087
278614458798264473506096765847363924798340269581734932741387794163201871
078290103150044878351589723445743034895043139210736415367258653754399198
023197879472133976639766535804598838828953469418250017654927135906875846
934096369352398596684887099923454796612367818293932918695749329867409088
482478021464904782075560097494715000964144323132023490179441227566281015
421387236254870048522174392492217458519998931129460646332813111227570768
163112564571256040832661928009657915893955653952998651842209696218767618
656675909074262127764692649315272831253557167983530950602093480083542017
894425060519253627433048099634677052985647589666589604117822779983193064
501674821191063378701930188846124370319410694418600855887622424865536764
172907859770891252606835105041927847157957921838968869530564914941111572
960099042041803230361820792030432141848619023953206708204713708656463684
369929960741907430398234662361336624842148687125876462407783572837395626
036470723189190384233999710230258825227977775136577341133293624903917442
621226665165497741097844919110132409321295921170680447094461217476637027
649450490580660153504840671641235998383330021704703991269242734229725965
158768137260143224119998456064902402619320787836945426883479737439370944
638295708490754603910071698384361185677013147547245140566515644772891404
824257451069703703689838531548011192327048355483143749496746522124654119
292061715703807462288918706509773091431279820363073377315168500196979787
340380690820333367901502670217623988614790539089599630563755373073070336
576100796813754529442081386347201545860973561168890077934255341151020125
449089818407416317212138515451522093771067384699270227244960241118608885
197809465314272383974874416867271031912614104866893442587344579292454012
955941943291725923504426365240012122269940429183474102774916276764977846
....
--
bart
[toc] | [prev] | [next] | [standalone]
| From | "Rick C. Hodgin" <rick.c.hodgin@gmail.com> |
|---|---|
| Date | 2018-12-26 14:45 -0500 |
| Message-ID | <q00lmq$sqr$1@dont-email.me> |
| In reply to | #139093 |
On 12/26/2018 2:03 PM, Bart wrote:
> I get the following, which counts the transitions from 0..9 to 0..9 over one
> billion random-10 calls; there should be 10 million of each:
>
> [samples snip]
>
> That doesn't seem too bad. If I look at sequences of the same number, I get
> maximum sequence lengths of 10 to 13 digits over 1e9 digits, which seems a
> trifle high to me, but I'm not enough of an expert to say for sure. (Testing
> with hex digits 0 to F avoiding a mod 10, I get sequence lengths of 8 to 11,
> also higher than I expected).
>
> The actual output, for 0..9, looks like the following, where nothing really
> stands out:
In the 3,888 character sequence you provided, this variation was found:
Note: An occurrence count of 357 to 424 of the various digits, range
of 67 (should be 389, -32, +35).
0 found 360 times
1 found 379 times
2 found 376 times
3 found 394 times
4 found 412 times
5 found 357 times
6 found 399 times
7 found 406 times
8 found 381 times
9 found 424 times
Repeating sequences:
00 found 27 times
11 found 26 times
22 found 32 times
33 found 35 times
44 found 40 times
55 found 36 times
66 found 36 times
77 found 36 times
88 found 27 times
99 found 35 times
000 found 2 times
111 found 5 times
222 found 3 times
333 found 3 times
444 found 2 times
666 found 4 times
777 found 2 times
888 found 3 times
999 found 5 times
0000 found 1 times
1111 found 1 times
3333 found 1 times
4444 found 1 times
6666 found 1 times
7777 found 1 times
No 5+ digit repeating sequences found.
What srand() value are you using? Repeat the test using only 4,096
generated rand() values for each srand() seed, and then search for
sequences of repeating values.
Here's the Visual FoxPro code I used. Something similar in a high
level language can analyze the strings easily:
lcResults = SPACE(0)
FOR lnI = 1 TO 7
FOR lnJ = 0 TO 9
lcSearch = REPLICATE(TRANSFORM(lnJ), lnI)
IF OCCURS(lcSearch, lcText) > 0
lcResults = lcResults + " " + lcSearch + " found " + ;
TRANSFORM(OCCURS(lcSearch, lcText)) + ;
" times" + CHR(13)
ENDIF
NEXT
NEXT
_cliptext = lcResults && Copy to clipboard
I can do this later tonight (it's 2:35pm here) when I have time.
--
Rick C. Hodgin
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2018-12-26 20:46 +0000 |
| Message-ID | <KMRUD.535900$gPr.113520@fx08.am4> |
| In reply to | #139096 |
On 26/12/2018 19:45, Rick C. Hodgin wrote:
> On 12/26/2018 2:03 PM, Bart wrote:
>> I get the following, which counts the transitions from 0..9 to 0..9
>> over one billion random-10 calls; there should be 10 million of each:
>>
>> [samples snip]
>>
>> That doesn't seem too bad. If I look at sequences of the same number,
>> I get maximum sequence lengths of 10 to 13 digits over 1e9 digits,
>> which seems a trifle high to me, but I'm not enough of an expert to
>> say for sure. (Testing with hex digits 0 to F avoiding a mod 10, I get
>> sequence lengths of 8 to 11, also higher than I expected).
>>
>> The actual output, for 0..9, looks like the following, where nothing
>> really stands out:
>
> In the 3,888 character sequence you provided, this variation was found:
>
> Note: An occurrence count of 357 to 424 of the various digits, range
> of 67 (should be 389, -32, +35).
>
> 0 found 360 times
> 1 found 379 times
> 2 found 376 times
> 3 found 394 times
> 4 found 412 times
> 5 found 357 times
> 6 found 399 times
> 7 found 406 times
> 8 found 381 times
> 9 found 424 times
Is that bad? If there was a perfect distribution (of 388 or 389
instances of each digit), then to me that would be suspect.
I'm not enough of a mathematician to tell if a deviation of +/- 8% from
a perfect distribution is reasonable or not for this size of data.
However, I download some random bytes from an on-line generator,
isolated the bottom 4 bits, and looked only at the cases where those
bits had values 0 to 9.
The results for the first 3888 such values were:
0: 376
1: 374
2: 405
3: 368
4: 406
5: 424
6: 370
7: 406
8: 366
9: 393
A span of 58 from 366 to 424. Not that much different from mine.
If I look at 9 more snapshots of 3888 numbers 10KB apart, I can see
deviation spans of 52, 109, 90, 48, 66, 57, 75, 103 and 66.
I then looked at the first 3888 digits of the square root of two, and
got a deviation of 72: 357 to 428. Not really random, but close enough.
(See below.)
> 0000 found 1 times
> 1111 found 1 times
> 3333 found 1 times
> 4444 found 1 times
> 6666 found 1 times
> 7777 found 1 times
How many instances of each nnnn would your perfect distribution have
over 3888 numbers? Over that root 2 expansion, I found:
1111 1 times
3333 1 times
4444 1 times
5555 1 times
7777 1 times
9999 1 times
99999 1 times
------------------------------------------
1.414213562373095048801688724209698078
5696718753769480731766797379907324784621
0703885038753432764157273501384623091229
7024924836055850737212644121497099935831
4132226659275055927557999505011527820605
7147010955997160597027453459686201472851
7418640889198609552329230484308714321450
8397626036279952514079896872533965463318
0882964062061525835239505474575028775996
1729835575220337531857011354374603408498
8471603868999706990048150305440277903164
5424782306849293691862158057846311159666
8713013015618568987237235288509264861249
4977154218334204285686060146824720771435
8548741556570696776537202264854470158588
0162075847492265722600208558446652145839
8893944370926591800311388246468157082630
1005948587040031864803421948972782906410
4507263688131373985525611732204024509122
7700226941127573627280495738108967504018
3698683684507257993647290607629969413804
7565482372899718032680247442062926912485
9052181004459842150591120249441341728531
4781058036033710773091828693147101711116
8391658172688941975871658215212822951848
8472089694633862891562882765952635140542
2676532396946175112916024087155101351504
5538128756005263146801712740265396947024
0300517495318862925631385188163478001569
3691768818523786840522878376293892143006
5586956868596459515550164472450983689603
6887323114389415576651040883914292338113
2060524336294853170499157717562285497414
3899918802176243096520656421182731672625
7539594717255934637238632261482742622208
6711558395999265211762526989175409881593
4864008345708518147223181420407042650905
6532333398436457865796796519267292399875
3666172159825788602633636178274959942194
0377775368142621773879919455139723127406
6898329989895386728822856378697749662519
9665835257761989393228453447356947949629
5216889148549253890475582883452609652409
6542889394538646625744927556381964410316
9798330618520193793849400571563337205480
6854057586799967012137223947582142630658
5132217408832382947287617393647467837431
9600015921888073478576172522118674904249
7736692920731109636972160893370866115673
4585334833295254675851644710757848602463
6008344491148185876555542864551233142199
2631133251797060843655970435285641008791
8500760361009159465670676883605571740076
7569050961367194013249356052401859991050
6210816359772643138060546701029356997104
2425105781749531057255934984451126922780
3449135066375687477602831628296055324224
2695753452902883876844642917328277088831
8087025339852338122749990812371892540726
4753678503048215918018861671089728692292
0119759988070381854333253646021108229927
9293072871780799888099176741774108983060
8003263118164279882311715436386966170299
9934161614878686018045505553986913115186
0103863753250045581860448040750241195184
3056745336836136745973744239885532851793
0896037389891517319587413442881784212502
1916951875593444387396189314549999906107
5870490902608835176362247497578588583680
3745793115733980209998662218694992259591
3276423619410592100328026149874566599688
8740679561673918595728886424734635858868
6449682238600698335264279905628316561391
3942557649062065186021647263033362975075
6978706066068564981600927187092921531323
6828135698893709741650447459096053747279
6524477094099241238710614470543986743647
3384774548191008728862221495895295911878
9214917983398108378827815306556231581036
0648675873036014502273208829351341387227
6841766784369052942869849083845574457940
9598626074249954916802853077398938296036
2133539875320509199893607513906444495768
4569934712763645071632791547015977335486
3893942325727754003826027478567417258095
1416307159597849818009443560379390985590
1682721540345815815210049366629534488271
0729239660232163823826661262683050257278
1169451035379371568823365932297823192986
0646797898640920856095581426143636310046
1559433255047449397593399912541953230093
2175304476533964706627611661753518754646
2096763455873861648801988484974792640450
6544489691004079421181692579685756378488
1498986416854994916357614484047021033989
2153423770372333531156459443897036531667
2194904935188290580630740134686264167247
01106534634
--
bart
[toc] | [prev] | [next] | [standalone]
| From | "Rick C. Hodgin" <rick.c.hodgin@gmail.com> |
|---|---|
| Date | 2018-12-26 16:25 -0500 |
| Message-ID | <q00rgm$vhi$1@dont-email.me> |
| In reply to | #139099 |
On 12/26/2018 3:46 PM, Bart wrote: > How many instances of each nnnn would your perfect distribution have over > 3888 numbers? For this application, I do not want more than 2 repeating sequences at any point, and not more than 3 repeating sequences in five draws. -- Rick C. Hodgin
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2018-12-26 17:13 -0500 |
| Message-ID | <T1TUD.84205$AX6.8939@fx13.iad> |
| In reply to | #139102 |
On 12/26/18 4:25 PM, Rick C. Hodgin wrote: > On 12/26/2018 3:46 PM, Bart wrote: >> How many instances of each nnnn would your perfect distribution have >> over 3888 numbers? > > For this application, I do not want more than 2 repeating sequences at > any point, and not more than 3 repeating sequences in five draws. > IF your requirements are random, but with sequence limits, then filtering the results (at that point of use) make sense. My guess is that this is to limit 'luck' in the game (good or bad) that might be perceived from the somewhat rare longish repeated sequence.
[toc] | [prev] | [next] | [standalone]
| From | "Rick C. Hodgin" <rick.c.hodgin@gmail.com> |
|---|---|
| Date | 2018-12-26 22:23 -0500 |
| Message-ID | <q01gga$4p6$2@dont-email.me> |
| In reply to | #139105 |
On 12/26/2018 5:13 PM, Richard Damon wrote: > On 12/26/18 4:25 PM, Rick C. Hodgin wrote: >> On 12/26/2018 3:46 PM, Bart wrote: >>> How many instances of each nnnn would your perfect distribution have >>> over 3888 numbers? >> >> For this application, I do not want more than 2 repeating sequences at >> any point, and not more than 3 repeating sequences in five draws. >> > > IF your requirements are random, but with sequence limits, then > filtering the results (at that point of use) make sense. My guess is > that this is to limit 'luck' in the game (good or bad) that might be > perceived from the somewhat rare longish repeated sequence. Chris Thomasson posted a link to a different type of prng generator invented in 2014. I implemented that in the game tonight and added one constraint that there can't be any twice-repeating numbers gen- erated, and it's made all the difference. The test players are loving the game now. It used to make them angry because the repeating pieces would make it difficult to play without being set back quite a bit. Now, it's just challenging continually rather than making you feel like a failure periodically. :-) -- Rick C. Hodgin
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2018-12-26 23:39 +0000 |
| Message-ID | <bjUUD.130999$nd2.8280@fx22.am4> |
| In reply to | #139102 |
On 26/12/2018 21:25, Rick C. Hodgin wrote: > On 12/26/2018 3:46 PM, Bart wrote: >> How many instances of each nnnn would your perfect distribution have >> over 3888 numbers? > > For this application, I do not want more than 2 repeating sequences at > any point, and not more than 3 repeating sequences in five draws. > You don't want a purely random or pseudo-random sequence then, because that would be impossible to guarantee. You need an extra application-specific layer. You can't take a general purpose PRNG and rate it according to how well the numbers tie in with your application.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2018-12-26 17:36 -0500 |
| Message-ID | <GnTUD.113140$nY5.45047@fx15.iad> |
| In reply to | #139099 |
On 12/26/18 3:46 PM, Bart wrote: > On 26/12/2018 19:45, Rick C. Hodgin wrote: >> On 12/26/2018 2:03 PM, Bart wrote: >>> I get the following, which counts the transitions from 0..9 to 0..9 >>> over one billion random-10 calls; there should be 10 million of each: >>> >>> [samples snip] >>> >>> That doesn't seem too bad. If I look at sequences of the same number, >>> I get maximum sequence lengths of 10 to 13 digits over 1e9 digits, >>> which seems a trifle high to me, but I'm not enough of an expert to >>> say for sure. (Testing with hex digits 0 to F avoiding a mod 10, I >>> get sequence lengths of 8 to 11, also higher than I expected). >>> >>> The actual output, for 0..9, looks like the following, where nothing >>> really stands out: >> >> In the 3,888 character sequence you provided, this variation was found: >> >> Note: An occurrence count of 357 to 424 of the various digits, range >> of 67 (should be 389, -32, +35). >> >> 0 found 360 times >> 1 found 379 times >> 2 found 376 times >> 3 found 394 times >> 4 found 412 times >> 5 found 357 times >> 6 found 399 times >> 7 found 406 times >> 8 found 381 times >> 9 found 424 times > > Is that bad? If there was a perfect distribution (of 388 or 389 > instances of each digit), then to me that would be suspect. > Looking at each number individually (as it is a lot simpler, and should be close enough) we have events with probability p = 1/10 Expected value = pN = 388.8 Expected Standard Deviation = sqrt(2*p*(1-p)*N) = 26.5 Looking over all 10 values, we really should use more complicated statistics (as they aren't independent of each other) but we would expect many of the deviations being with 1 SD (362-405) but a few to go beyond. Getting to 2 SD wouldn't be surprising, and 3 SD just slightly unexpected. The numbers seem to fit.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2018-12-26 16:27 -0500 |
| Message-ID | <RmSUD.278269$_35.137168@fx46.iad> |
| In reply to | #139093 |
On 12/26/18 2:03 PM, Bart wrote: > On 26/12/2018 17:58, Richard Damon wrote: >> On 12/26/18 12:42 PM, Bart wrote: >>> On 26/12/2018 15:58, Rick C. Hodgin wrote: >>>> On Wednesday, December 26, 2018 at 10:48:31 AM UTC-5, Bart wrote: >>> >>>>> However this depends entirely on the PRNG used. The point of my >>>>> example >>>>> is to show how easy it is to superimpose a 'multi-channel' API on a >>>>> single-stream PRNG.) >>>> >>>> I agree. That's what I intended to do, but I didn't know where >>>> there was good prng source code that was in the Public Domain. >>>> >>>> I'm looking for a nicely distributed prng. I'm using the built- >>>> in one with Visual C++ presently and it has really odd patterns >>>> which, when scaled into a lesser range (like 1-10), produce oft- >>>> repeated values. >>> >>> Really? I tried the simple PRNG I showed, using a%10 to produce values >>> from 0 to 9, which is supposed to be really bad idea, and got this >>> distribution over 1 billion calls for each of the digits: >>> >>> 0: 100011113 >>> 1: 99989920 >>> 2: 100009423 >>> 3: 100004327 >>> 4: 99991057 >>> 5: 100000307 >>> 6: 99998986 >>> 7: 100014477 >>> 8: 99982849 >>> 9: 99997541 >>> >>> A perfect distribution would have 100,000,000 of each, so these are out >>> by 1 in 10,000 or so. >>> >> >> The low order bits of many random number gererators tend to be well >> distributed, but often have patterned between them. Try running an >> analysis of first order transition, a 2d histogram of consecutive >> values. > > I get the following, which counts the transitions from 0..9 to 0..9 over > one billion random-10 calls; there should be 10 million of each: > > 0 1 2 3 4 > 0 10000414 9999532 9996911 10002996 10001089 > 1 10001890 9998825 9997192 9999400 10001881 > 2 9998577 9998102 10004200 10001680 9996506 > 3 10003276 9999146 10002297 9996187 10000437 > 4 10005587 9999423 10001425 10004535 9996548 > 5 10001042 9998557 10001422 10002560 9998100 > 6 9999956 9999384 10004437 9996324 9999880 > 7 9999302 10000587 10004574 10000900 9997869 > 8 10002703 9996356 9999180 9999575 9997773 > 9 9998366 10000008 9997785 10000170 10000974 > > 5 6 7 8 9 > 0 10000507 10002884 10006255 9997911 10002615 > 1 9993337 10001477 9999119 9999063 9997736 > 2 10003593 10004684 10000610 10001144 10000327 > 3 10001675 10001016 9999818 9999108 10001367 > 4 9995269 9996443 9998453 9996897 9996477 > 5 9998838 10001826 9998264 10002608 9997090 > 6 9999320 9998757 10010484 9993826 9996618 > 7 10005658 9998981 10002985 10002377 10001243 > 8 10002130 9990532 9997172 9995304 10002124 > 9 9999980 10002386 10001317 9994611 10001944 > > That doesn't seem too bad. If I look at sequences of the same number, I > get maximum sequence lengths of 10 to 13 digits over 1e9 digits, which > seems a trifle high to me, but I'm not enough of an expert to say for > sure. (Testing with hex digits 0 to F avoiding a mod 10, I get sequence > lengths of 8 to 11, also higher than I expected). With a bit of statistics, you could compute the expected variation in the values and see if they seem right. With 100 numbers you would EXPECT to get a value about 3 standard deviations off the nominal (and in fact, if all the value are too close to the expected value that is a sign that the generator has issues with being random). With 1E9 digits, I would expect on average 1 run of 9 of each digit, and one sequence of 10 digits, but that is just the expected value, but wouldn't expect it that unlikely to get a few more. I don't feel like digging out the formulas to see how strong that value would rate the hypothesis that the generator is biased to generate repeating number over the null hypothesis of totally random numbers (gut check is it may not be strong enough to suggest a statistical significant result).
[toc] | [prev] | [next] | [standalone]
| From | rbowman <bowman@montana.com> |
|---|---|
| Date | 2018-12-26 19:19 -0700 |
| Message-ID | <g8ir3lFk9tiU2@mid.individual.net> |
| In reply to | #139081 |
On 12/26/2018 08:48 AM, Bart wrote:
>
> This doesn't seem too hard, but it's obviously not in the standard
> library (which AFAIK only has rand()). Example:
Seems to be in mine...
RANDOM(3) Linux Programmer's Manual RANDOM(3)
NAME
random, srandom, initstate, setstate - random number generator
SYNOPSIS
#include <stdlib.h>
long int random(void);
void srandom(unsigned int seed);
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2018-12-26 22:17 -0500 |
| Message-ID | <2vXUD.115697$gk1.112420@fx47.iad> |
| In reply to | #139110 |
On 12/26/18 9:19 PM, rbowman wrote: > On 12/26/2018 08:48 AM, Bart wrote: >> >> This doesn't seem too hard, but it's obviously not in the standard >> library (which AFAIK only has rand()). Example: > > Seems to be in mine... > > > RANDOM(3) Linux Programmer's Manual RANDOM(3) > > NAME > random, srandom, initstate, setstate - random number generator > > SYNOPSIS > #include <stdlib.h> > > long int random(void); > > void srandom(unsigned int seed); > > > random() isn't is ISO C, but is (I beleive) defined in the POSIX standard. Note, that is a Linux man page.
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2018-12-26 19:32 -0800 |
| Message-ID | <223bed7e-3970-44d4-942a-9a80f5d819e6@googlegroups.com> |
| In reply to | #139110 |
On Wednesday, December 26, 2018 at 9:18:37 PM UTC-5, rbowman wrote: > On 12/26/2018 08:48 AM, Bart wrote: > > > > This doesn't seem too hard, but it's obviously not in the standard > > library (which AFAIK only has rand()). Example: > > Seems to be in mine... > > > RANDOM(3) Linux Programmer's Manual RANDOM(3) > > NAME > random, srandom, initstate, setstate - random number generator ... Mine says something similar, but the key point is the following section: > CONFORMING TO > POSIX.1-2001, POSIX.1-2008, 4.3BSD. This is comp.lang.c, so the standard library he's referring to is the C standard library. The C standard is not on that list.
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2018-12-26 19:34 -0800 |
| Message-ID | <lnbm57bq2b.fsf@kst-u.example.com> |
| In reply to | #139110 |
rbowman <bowman@montana.com> writes:
> On 12/26/2018 08:48 AM, Bart wrote:
>> This doesn't seem too hard, but it's obviously not in the standard
>> library (which AFAIK only has rand()). Example:
>
> Seems to be in mine...
>
>
> RANDOM(3) Linux Programmer's Manual RANDOM(3)
>
> NAME
> random, srandom, initstate, setstate - random number generator
>
> SYNOPSIS
> #include <stdlib.h>
>
> long int random(void);
>
> void srandom(unsigned int seed);
Scroll down, and you'll see this:
CONFORMING TO
POSIX.1-2001, POSIX.1-2008, 4.3BS
It's defined by POSIX, but not by ISO C (which is what Bart
presumably meant by "standard library").
--
Keith Thompson (The_Other_Keith) kst@mib.org <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2018-12-27 11:29 +0000 |
| Message-ID | <aI2VD.166136$9q81.71538@fx12.am4> |
| In reply to | #139115 |
On 27/12/2018 03:34, Keith Thompson wrote: > rbowman <bowman@montana.com> writes: >> On 12/26/2018 08:48 AM, Bart wrote: >>> This doesn't seem too hard, but it's obviously not in the standard >>> library (which AFAIK only has rand()). Example: >> >> Seems to be in mine... >> >> >> RANDOM(3) Linux Programmer's Manual RANDOM(3) >> >> NAME >> random, srandom, initstate, setstate - random number generator >> >> SYNOPSIS >> #include <stdlib.h> >> >> long int random(void); >> >> void srandom(unsigned int seed); > > Scroll down, and you'll see this: > > CONFORMING TO > POSIX.1-2001, POSIX.1-2008, 4.3BS > > It's defined by POSIX, but not by ISO C (which is what Bart > presumably meant by "standard library"). > Also the fact that rand() doesn't support the 'multi-channel' requirement. The Posix set of functions might enable that, but it's difficult to tell. If they do, then they rely on global state which is fiddly to change; it might be better to apply an API like mine. -- bart
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2018-12-27 05:27 -0800 |
| Message-ID | <e99ff17d-697e-4535-8734-094130ee79fc@googlegroups.com> |
| In reply to | #139116 |
On Thursday, December 27, 2018 at 6:29:18 AM UTC-5, Bart wrote: ... > Also the fact that rand() doesn't support the 'multi-channel' requirement. > > The Posix set of functions might enable that, but it's difficult to > tell. If they do, then they rely on global state which is fiddly to > change; it might be better to apply an API like mine. > > -- > bart The documentation for random() says: "Threaded applications should use erand48(), nrand48(), or jrand48() instead of random() when an independent random number sequence in multiple threads is required."
[toc] | [prev] | [next] | [standalone]
| From | "Rick C. Hodgin" <rick.c.hodgin@gmail.com> |
|---|---|
| Date | 2018-12-27 09:41 -0500 |
| Message-ID | <q02o8d$2gl$1@dont-email.me> |
| In reply to | #139119 |
On 12/27/2018 8:27 AM, James Kuyper wrote: > The documentation for random() says: > "Threaded applications should use erand48(), nrand48(), or jrand48() > instead of random() when an independent random number sequence in > multiple threads is required." In my particular case I'm not running a single thread. I just happen to need multiple random sources. Given the implementation of the algorithm, I'm surprised they didn't provide a native one that uses pointers to external values so you can have multiple rand() seeds and sources all working together. -- Rick C. Hodgin
[toc] | [prev] | [next] | [standalone]
| From | "Rick C. Hodgin" <rick.c.hodgin@gmail.com> |
|---|---|
| Date | 2018-12-27 09:42 -0500 |
| Message-ID | <q02oa9$2gl$2@dont-email.me> |
| In reply to | #139120 |
On 12/27/2018 9:41 AM, Rick C. Hodgin wrote: > On 12/27/2018 8:27 AM, James Kuyper wrote: >> The documentation for random() says: >> "Threaded applications should use erand48(), nrand48(), or jrand48() >> instead of random() when an independent random number sequence in >> multiple threads is required." > > In my particular case I'm not running a single thread. I just happen > to need multiple random sources. Should say "I'm not running multiple threads, but running a single thread only." > Given the implementation of the algorithm, I'm surprised they didn't > provide a native one that uses pointers to external values so you can > have multiple rand() seeds and sources all working together. -- Rick C. Hodgin
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2018-12-27 07:01 -0800 |
| Message-ID | <4e3785c7-aae8-4f61-9ac7-8a6b34fce17d@googlegroups.com> |
| In reply to | #139121 |
On Thursday, December 27, 2018 at 9:41:20 AM UTC-5, Rick C. Hodgin wrote: > On 12/27/2018 9:41 AM, Rick C. Hodgin wrote: > > On 12/27/2018 8:27 AM, James Kuyper wrote: > >> The documentation for random() says: > >> "Threaded applications should use erand48(), nrand48(), or jrand48() > >> instead of random() when an independent random number sequence in > >> multiple threads is required." > > > > In my particular case I'm not running a single thread. I just happen > > to need multiple random sources. > > Should say "I'm not running multiple threads, but running a single > thread only." Sorry - there have been several mentions of threading by other people on this thread, and I hadn't bothered reading your own messages, so I assumed "multi-channel" was your own personal way of saying "multi- threaded". > > Given the implementation of the algorithm, I'm surprised they didn't > > provide a native one that uses pointers to external values so you can > > have multiple rand() seeds and sources all working together. If POSIX functions are an acceptable solution, then, as Scott has already pointed out, the initstate() and setstate() functions can be used to make random() use different sets of state information, totally under your control. You responded to his message with a message about a Windows function, so it's not clear whether you noticed that part of what he was saying.
[toc] | [prev] | [next] | [standalone]
| From | "Rick C. Hodgin" <rick.c.hodgin@gmail.com> |
|---|---|
| Date | 2018-12-27 10:28 -0500 |
| Message-ID | <q02r0a$ldd$1@dont-email.me> |
| In reply to | #139123 |
On 12/27/2018 10:01 AM, James Kuyper wrote:
> On Thursday, December 27, 2018 at 9:41:20 AM UTC-5, Rick C. Hodgin wrote:
>> On 12/27/2018 9:41 AM, Rick C. Hodgin wrote:
>>> On 12/27/2018 8:27 AM, James Kuyper wrote:
>>>> The documentation for random() says:
>>>> "Threaded applications should use erand48(), nrand48(), or jrand48()
>>>> instead of random() when an independent random number sequence in
>>>> multiple threads is required."
>>>
>>> In my particular case I'm not running a single thread. I just happen
>>> to need multiple random sources.
>>
>> Should say "I'm not running multiple threads, but running a single
>> thread only."
>
> Sorry - there have been several mentions of threading by other people on
> this thread, and I hadn't bothered reading your own messages, so I
> assumed "multi-channel" was your own personal way of saying "multi-
> threaded".
>
>>> Given the implementation of the algorithm, I'm surprised they didn't
>>> provide a native one that uses pointers to external values so you can
>>> have multiple rand() seeds and sources all working together.
>
> If POSIX functions are an acceptable solution, then, as Scott has
> already pointed out, the initstate() and setstate() functions can be
> used to make random() use different sets of state information, totally
> under your control. You responded to his message with a message about a
> Windows function, so it's not clear whether you noticed that part of
> what he was saying.
I did. It seems an undesirable solution due to the spill/fill overhead,
so I discounted it as a viable solution for me.
I was able to get the solution working based on Chris Thomasson's link
to the Permuted Congruential Generator (say that five times fast).
https://en.wikipedia.org/wiki/Permuted_congruential_generator
The code there can be modified easily to point to inputs for its "in-
ternal" values. No spill/fill required.
I think this type of solution is what should've been included in the
C standard's implementation. I think the need to potentially draw
multiple independently seeded pseudo-random values is a real need in
some coding models. And it's very little additional work to add the
ability natively.
--
Rick C. Hodgin
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2018-12-27 10:48 -0500 |
| Message-ID | <Zu6VD.66707$hN7.61301@fx23.iad> |
| In reply to | #139125 |
On 12/27/18 10:28 AM, Rick C. Hodgin wrote: > > I did. It seems an undesirable solution due to the spill/fill overhead, > so I discounted it as a viable solution for me. > > I was able to get the solution working based on Chris Thomasson's link > to the Permuted Congruential Generator (say that five times fast). > > https://en.wikipedia.org/wiki/Permuted_congruential_generator > > The code there can be modified easily to point to inputs for its "in- > ternal" values. No spill/fill required. > > I think this type of solution is what should've been included in the > C standard's implementation. I think the need to potentially draw > multiple independently seeded pseudo-random values is a real need in > some coding models. And it's very little additional work to add the > ability natively. > In my experience, most of the time I want multiple independent random sequences, what I also need is stability of algorithm, so that the random number sequence will be consistent, even if I recompile with a new version, or different implementation. This means that I can't use a library function where the exact algorithm isn't specified, so I need to include my own function so I KNOW that sequence will be stable.
[toc] | [prev] | [next] | [standalone]
Page 3 of 5 — ← Prev page 1 2 [3] 4 5 Next page →
Back to top | Article view | comp.lang.c
csiph-web