Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #95355 > unrolled thread

Fair, truly random random number generator

Back to article view | Back to comp.lang.c

Contents

  Fair, truly random random number generator "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2016-10-28 20:31 +0800
    Re: Fair, truly random random number generator "Osmium" <r124c4u102@comcast.net> - 2016-10-28 07:48 -0500
      Re: Fair, truly random random number generator "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2016-10-28 21:07 +0800
        Re: Fair, truly random random number generator Richard Heathfield <rjh@cpax.org.uk> - 2016-10-28 14:21 +0100
          Re: Fair, truly random random number generator Gareth Owen <gwowen@gmail.com> - 2016-10-28 16:22 +0100
            Re: Fair, truly random random number generator Richard Heathfield <rjh@cpax.org.uk> - 2016-10-28 16:30 +0100
              Re: Fair, truly random random number generator Gareth Owen <gwowen@gmail.com> - 2016-10-28 16:32 +0100
          Re: Fair, truly random random number generator "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2016-10-29 23:11 +0800
            Re: Fair, truly random random number generator Richard Heathfield <rjh@cpax.org.uk> - 2016-10-31 11:17 +0000
              Re: Fair, truly random random number generator "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2016-10-31 20:14 +0800
                Re: Fair, truly random random number generator Melzzzzz <Melzzzzz@zzzzz.com> - 2016-10-31 12:32 +0000
                  Re: Fair, truly random random number generator Richard Heathfield <rjh@cpax.org.uk> - 2016-10-31 12:48 +0000
                    Re: Fair, truly random random number generator "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2016-11-01 15:30 +0800
                Re: Fair, truly random random number generator Richard Heathfield <rjh@cpax.org.uk> - 2016-10-31 12:47 +0000
        Re: Fair, truly random random number generator "Osmium" <r124c4u102@comcast.net> - 2016-10-28 09:32 -0500
    Re: Fair, truly random random number generator "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-10-28 07:14 -0700
      Re: Fair, truly random random number generator "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-10-28 18:07 -0700
        Re: Fair, truly random random number generator "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-11-01 17:45 -0700
          Re: Fair, truly random random number generator "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-11-01 18:57 -0700
            Re: Fair, truly random random number generator David Brown <david.brown@hesbynett.no> - 2016-11-02 10:06 +0100
              Re: Fair, truly random random number generator "Osmium" <r124c4u102@comcast.net> - 2016-11-02 04:46 -0600
              Re: Fair, truly random random number generator "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-11-02 05:06 -0700
                Re: Fair, truly random random number generator David Brown <david.brown@hesbynett.no> - 2016-11-02 13:43 +0100
                  Re: Fair, truly random random number generator "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-11-02 06:02 -0700
                    Re: Fair, truly random random number generator David Brown <david.brown@hesbynett.no> - 2016-11-02 16:08 +0100
                      Re: Fair, truly random random number generator "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-11-02 08:21 -0700
                Re: Fair, truly random random number generator Mark Storkamp <mstorkamp@yahoo.com> - 2016-11-02 08:20 -0500
            Re: Fair, truly random random number generator "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-11-03 17:56 -0700
              Re: Fair, truly random random number generator Keith Thompson <kst-u@mib.org> - 2016-11-03 18:16 -0700
                Re: Fair, truly random random number generator "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-11-03 18:48 -0700
                Re: Fair, truly random random number generator supercat@casperkitty.com - 2016-11-04 09:17 -0700
                Re: Fair, truly random random number generator raltbos@xs4all.nl (Richard Bos) - 2016-11-04 17:59 +0000
                  Re: Fair, truly random random number generator Keith Thompson <kst-u@mib.org> - 2016-11-04 11:55 -0700
                    Re: Fair, truly random random number generator "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-11-04 12:43 -0700
                  Re: Fair, truly random random number generator "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-11-04 12:40 -0700
              Re: Fair, truly random random number generator "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-11-04 12:49 -0700
                Re: Fair, truly random random number generator "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-11-04 13:23 -0700
                  Re: Fair, truly random random number generator "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-11-04 13:32 -0700
                    Re: Fair, truly random random number generator ImperiusDamian <damianblack.wolf@gmail.com> - 2016-11-05 18:48 -0400
                      Re: Fair, truly random random number generator "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-11-05 16:03 -0700
                        Re: Fair, truly random random number generator "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-11-05 16:50 -0700
                        Re: Fair, truly random random number generator ImperiusDamian <damianblack.wolf@gmail.com> - 2016-11-05 19:52 -0400
                          Re: Fair, truly random random number generator "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-11-05 17:06 -0700
      Re: Fair, truly random random number generator "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2016-10-29 23:13 +0800
        Re: Fair, truly random random number generator Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2016-10-29 12:12 -0400
          Re: Fair, truly random random number generator "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2016-10-30 00:22 +0800
          Re: Fair, truly random random number generator Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2016-10-29 12:26 -0400
          Re: Fair, truly random random number generator supercat@casperkitty.com - 2016-10-29 09:44 -0700
            Re: Fair, truly random random number generator Tim Rentsch <txr@alumni.caltech.edu> - 2016-11-01 08:13 -0700
              Re: Fair, truly random random number generator supercat@casperkitty.com - 2016-11-01 08:31 -0700
                Re: Fair, truly random random number generator Tim Rentsch <txr@alumni.caltech.edu> - 2016-11-02 12:58 -0700
        Re: Fair, truly random random number generator "James R. Kuyper" <jameskuyper@verizon.net> - 2016-10-29 12:37 -0400
        Re: Fair, truly random random number generator Keith Thompson <kst-u@mib.org> - 2016-10-29 11:57 -0700
        Re: Fair, truly random random number generator David Brown <david.brown@hesbynett.no> - 2016-10-30 17:13 +0100
          Re: Fair, truly random random number generator "Osmium" <r124c4u102@comcast.net> - 2016-10-30 11:07 -0600
            Re: Fair, truly random random number generator supercat@casperkitty.com - 2016-10-30 12:20 -0700
        Re: Fair, truly random random number generator Richard Heathfield <rjh@cpax.org.uk> - 2016-10-31 11:18 +0000
        Re: Fair, truly random random number generator Ed Prochak <edprochak@gmail.com> - 2016-11-03 10:39 -0700
          Re: Fair, truly random random number generator "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-11-03 11:13 -0700
            [OT] gigawatts = gigaseconds correlation? "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2016-11-04 02:36 +0800
              Re: [OT] gigawatts = gigaseconds correlation? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-11-03 12:07 -0700
                Re: [OT] gigawatts = gigaseconds correlation? "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2016-11-04 12:02 +0800
            Re: Fair, truly random random number generator gazelle@shell.xmission.com (Kenny McCormack) - 2016-11-03 19:56 +0000
            Re: Fair, truly random random number generator "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-11-03 16:21 -0700
    Re: Fair, truly random random number generator luser droog <luser.droog@gmail.com> - 2016-10-29 14:49 -0700
      Re: Fair, truly random random number generator jameskuyper@verizon.net - 2016-10-29 15:29 -0700
    Re: Fair, truly random random number generator Quadibloc <jsavard@ecn.ab.ca> - 2016-10-29 19:09 -0700
    Thank you all for the replies! "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2016-10-31 18:42 +0800

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

#95885

On 11/5/2016 4:03 PM, Rick C. Hodgin wrote:
> On Saturday, November 5, 2016 at 6:49:10 PM UTC-4, ImperiusDamian wrote:
>> On 2016-11-04 16:32, Rick C. Hodgin wrote:
>>>
>>> I also believe in edit-and-continue, something I call LiveCode, so you can
>>> fix and repeat again and again without the need of recompiling everything,
>>> but only the few lines that failed.  And, when the fix is big enough, then,
>>> and only then, do the full rebuild during debugging.
>>
>> That would definitely be a much more efficient way of coding! I've seen
>> a couple of "live IDEs" online that do this but I'm not sure if they
>> have C or other compiled languages. Mainly I see it done with
>> Javascript, Python or HTML.
>
> Microsoft's Visual Studio 2015 is free for use on open source projects.  It
> has a really nice and advanced edit-and-continue ability which, IIRC, also
> works for 64-bit code, whereas their older products only worked for 32-bit
> code.
>
> Microsoft has had edit-and-continue in their Visual line of developer tools
> since 1998.  Visual Studio's 2015 version also has a really amazing code
> analyzer.  It does static unit testing on your code by assuming branches
> taken, and branches not taken, to see if there are places where you could
> access a NULL pointer, access memory after it was released, etc.

FWIW, I remember, many years ago, debugging a race-infested nest of 
really annoyed hornets using MSVC. I paused all threads, let one resume 
up to a point, paused it, then let another thread resume up to a point. 
Then analyzed the shared data structure, noticed an error, manually 
corrected it, paused the thread. Let another resume, and noticed another 
error in the shared data, and repeated the correction process. I finally 
found the error! IIRC, I posted about it in comp.programming.threads. It 
was very tedious, but edit-and-continue worked nicely in that case. It 
allowed me to run the threads in a sort of lock step fashion. Pretty nice.

:^)

[toc] | [prev] | [next] | [standalone]

#95887

On 2016-11-05 19:03, Rick C. Hodgin wrote:
> On Saturday, November 5, 2016 at 6:49:10 PM UTC-4, ImperiusDamian wrote:
>> On 2016-11-04 16:32, Rick C. Hodgin wrote:
>>>
>>> I also believe in edit-and-continue, something I call LiveCode, so you can
>>> fix and repeat again and again without the need of recompiling everything,
>>> but only the few lines that failed.  And, when the fix is big enough, then,
>>> and only then, do the full rebuild during debugging.
>>
>> That would definitely be a much more efficient way of coding! I've seen
>> a couple of "live IDEs" online that do this but I'm not sure if they
>> have C or other compiled languages. Mainly I see it done with
>> Javascript, Python or HTML.
>
> Microsoft's Visual Studio 2015 is free for use on open source projects.  It
> has a really nice and advanced edit-and-continue ability which, IIRC, also
> works for 64-bit code, whereas their older products only worked for 32-bit
> code.
>
> Microsoft has had edit-and-continue in their Visual line of developer tools
> since 1998.  Visual Studio's 2015 version also has a really amazing code
> analyzer.  It does static unit testing on your code by assuming branches
> taken, and branches not taken, to see if there are places where you could
> access a NULL pointer, access memory after it was released, etc.
>

Oh that is nice. I haven't used VS 2015 I will admit. Sadly my computer 
is kind of ancient and the most recent VS that runs halfway decently on 
it is VS Express 2010...

-- 
I read the FM, and it didn't work.

SweetSpearGirl stories and Gemstone Mod:
http://imperium.elementfx.com/ - Now With Forums

[toc] | [prev] | [next] | [standalone]

#95891

On Saturday, November 5, 2016 at 7:53:19 PM UTC-4, ImperiusDamian wrote:
> On 2016-11-05 19:03, Rick C. Hodgin wrote:
> > On Saturday, November 5, 2016 at 6:49:10 PM UTC-4, ImperiusDamian wrote:
> >> On 2016-11-04 16:32, Rick C. Hodgin wrote:
> >>>
> >>> I also believe in edit-and-continue, something I call LiveCode, so you can
> >>> fix and repeat again and again without the need of recompiling everything,
> >>> but only the few lines that failed.  And, when the fix is big enough, then,
> >>> and only then, do the full rebuild during debugging.
> >>
> >> That would definitely be a much more efficient way of coding! I've seen
> >> a couple of "live IDEs" online that do this but I'm not sure if they
> >> have C or other compiled languages. Mainly I see it done with
> >> Javascript, Python or HTML.
> >
> > Microsoft's Visual Studio 2015 is free for use on open source projects.  It
> > has a really nice and advanced edit-and-continue ability which, IIRC, also
> > works for 64-bit code, whereas their older products only worked for 32-bit
> > code.
> >
> > Microsoft has had edit-and-continue in their Visual line of developer tools
> > since 1998.  Visual Studio's 2015 version also has a really amazing code
> > analyzer.  It does static unit testing on your code by assuming branches
> > taken, and branches not taken, to see if there are places where you could
> > access a NULL pointer, access memory after it was released, etc.
> >
> 
> Oh that is nice. I haven't used VS 2015 I will admit. Sadly my computer 
> is kind of ancient and the most recent VS that runs halfway decently on 
> it is VS Express 2010...

You can sometimes find VS98 (or VC++ at least) on eBay for $50 or so.  It
has a primitive version of edit-and-continue, but it still works.  It was
the first one I ever used.  Then I got VS2003, then VS2008, VS2010, and
then I didn't get another until VS2015 because Microsoft went crazy with
VS2012 and later, and only after a lot of people complained did they finally
come back to some resemblance of their senses (backing off of the hard line
they took with Win8 and the VS toolsets during that time before Win10).

In any event, it's well worth it.  I make a million little mistakes in my
coding.  Sometimes it's correct in my mind, but comes out of my fingers
wrong and I don't even catch it because when I read it back it reads as
correct because I'm not seeing the mistake, but am remembering what I
intended to type, and that's what goes into my brain (dyslexia).  So, I
actually use edit-and-continue continually in my C/C++ development.  It
is a feature I'm targeting in all of my toolsets.

Best regards,
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#95380

On 28/10/2016 10:14 PM, Rick C. Hodgin wrote:
> Several CPU manufacturers have introduced hardware which generates truly
> random sequences based on internal circuits which monitor heat radiation
> ...
> Others CPU manufacturers have done similarly.

Intel CPU?

> If you really want a true random number generator locally, you can buy
> add-on boards which provide that functionality through an API call:
> http://www.idquantique.com/random-number-generation/quantis-random-number-generator/

NO plan to invest in hardware solution.

I just want to play my MP3 songs in shuffle mode. I noticed that most 
shuffling algorithms are not random enough, as I could hear a pattern 
being repeated. :)

[toc] | [prev] | [next] | [standalone]

#95384

On Saturday October 29 2016 11:13, in comp.lang.c, "Mr. Man-wai Chang"
<toylet.toylet@gmail.com> wrote:

> On 28/10/2016 10:14 PM, Rick C. Hodgin wrote:
>> Several CPU manufacturers have introduced hardware which generates truly
>> random sequences based on internal circuits which monitor heat radiation
>> ...
>> Others CPU manufacturers have done similarly.
> 
> Intel CPU?
> 
>> If you really want a true random number generator locally, you can buy
>> add-on boards which provide that functionality through an API call:
>>
http://www.idquantique.com/random-number-generation/quantis-random-number-generator/
> 
> NO plan to invest in hardware solution.
> 
> I just want to play my MP3 songs in shuffle mode. I noticed that most
> shuffling algorithms are not random enough, as I could hear a pattern
> being repeated. :)

In my experience, most common, modern PRNGs have a period that should suffice
for even the most patient listener. The xorshift algorithm, for instance, has
a maximal period of 2^128 - 1 (two to the power of 128, minus 1) or about
10^38 (100,000,000,000,000,000,000,000,000,000,000,000,000).

That's a lot of music played before a repeat.

Perhaps it's not the PRNG, but how the PRNG is used, that is causing your "not
random enough" problem. Taking a period that large, and subdividing it,
modulo some much smaller number can introduce unintended repeating patterns.

For instance, if each piece of music averages 4 minutes in length, and you
notice repeats within the first 1 hour of playing time, that indicates a
periodicity about 15. Any competent PRNG, including the default PRNG for your
development environment, will have a period that well exceeds 15. Even a
straight 8-bit linear increment has a period greater than 15 (such a linear
increment would repeat a song, in your usage, once every 17 hours or so).

So, it's probably not the PRNG, but how it is used.

HTH
-- 
Lew Pitcher
"In Skills, We Trust"
PGP public key available upon request

[toc] | [prev] | [next] | [standalone]

#95385

>
> For instance, if each piece of music averages 4 minutes in length, and you
> notice repeats within the first 1 hour of playing time, that indicates a
> periodicity about 15. Any competent PRNG, including the default PRNG for your
> development environment, will have a period that well exceeds 15. Even a
> straight 8-bit linear increment has a period greater than 15 (such a linear
> increment would repeat a song, in your usage, once every 17 hours or so).
>
> So, it's probably not the PRNG, but how it is used.

Thanks! Learning...

[toc] | [prev] | [next] | [standalone]

#95386

On Saturday October 29 2016 12:12, in comp.lang.c, "Lew Pitcher"
<lew.pitcher@digitalfreehold.ca> wrote:

> On Saturday October 29 2016 11:13, in comp.lang.c, "Mr. Man-wai Chang"
> <toylet.toylet@gmail.com> wrote:
> 
>> On 28/10/2016 10:14 PM, Rick C. Hodgin wrote:
>>> Several CPU manufacturers have introduced hardware which generates truly
>>> random sequences based on internal circuits which monitor heat radiation
>>> ...
>>> Others CPU manufacturers have done similarly.
>> 
>> Intel CPU?
>> 
>>> If you really want a true random number generator locally, you can buy
>>> add-on boards which provide that functionality through an API call:
>>>
>
http://www.idquantique.com/random-number-generation/quantis-random-number-generator/
>> 
>> NO plan to invest in hardware solution.
>> 
>> I just want to play my MP3 songs in shuffle mode. I noticed that most
>> shuffling algorithms are not random enough, as I could hear a pattern
>> being repeated. :)
> 
> In my experience, most common, modern PRNGs have a period that should
> suffice for even the most patient listener. The xorshift algorithm, for
> instance, has a maximal period of 2^128 - 1 (two to the power of 128, minus
> 1) or about 10^38 (100,000,000,000,000,000,000,000,000,000,000,000,000).
> 
> That's a lot of music played before a repeat.
> 
> Perhaps it's not the PRNG, but how the PRNG is used, that is causing your
> "not random enough" problem. Taking a period that large, and subdividing it,
> modulo some much smaller number can introduce unintended repeating patterns.
> 
> For instance, if each piece of music averages 4 minutes in length, and you
> notice repeats within the first 1 hour of playing time, that indicates a
> periodicity about 15. Any competent PRNG, including the default PRNG for
> your development environment, will have a period that well exceeds 15. Even
> a straight 8-bit linear increment has a period greater than 15 (such a
> linear increment would repeat a song, in your usage, once every 17 hours or
> so).

For instance, here's a linear increment number generator (I hesitate to call
it a PRNG) that repeats after 256 calls, or (given the parameters of an MP3
player, 17 playing hours of music)

unsigned char lirng(void)
{
  static unsigned char seed = 0;

  seed += 31;
  return seed;
}

HTH
-- 
Lew Pitcher
"In Skills, We Trust"
PGP public key available upon request

[toc] | [prev] | [next] | [standalone]

#95389

On Saturday, October 29, 2016 at 11:12:38 AM UTC-5, Lew Pitcher wrote:
> In my experience, most common, modern PRNGs have a period that should suffice
> for even the most patient listener. The xorshift algorithm, for instance, has
> a maximal period of 2^128 - 1 (two to the power of 128, minus 1) or about
> 10^38 (100,000,000,000,000,000,000,000,000,000,000,000,000).

If one iteration of the xorshift algorithm yields a certain value in some
bits, performing a single iteration will cause those bits to (collectively)
hold one of two values.  It may take a long time for a long pattern to repeat,
but if e.g. the code used the bottom 14 bits of the xorshift to select one of
16,384 songs and only ran a single iteration between steps, then every time
a particular song played, a listener would quickly be able to predict that
one of two songs was going to come next.  The listener might not know which
of the two songs, but would know that it wasn't going to be any of the other
16,382 songs.

A simple improvement to xorshift is to use two generators that have
different periods and shift in opposite directions, and xor together some
bits from each.  That still won't be superb, but it will yield much better
results than using two generators that shift the same direction (if both
generators which shift the same direction are run a single iteration and
code used the xor of the bottom 14 bits, then after each song a listener
could predict that the next song would be one of four, and not one of the
remaining 16,380.  If the generators were run in opposite directions, then
any song could follow any other.

[toc] | [prev] | [next] | [standalone]

#95512

supercat@casperkitty.com writes:

> On Saturday, October 29, 2016 at 11:12:38 AM UTC-5, Lew Pitcher wrote:
>> In my experience, most common, modern PRNGs have a period that should suffice
>> for even the most patient listener.  The xorshift algorithm, for instance, has
>> a maximal period of 2^128 - 1 (two to the power of 128, minus 1) or about
>> 10^38 (100,000,000,000,000,000,000,000,000,000,000,000,000).
>
> If one iteration of the xorshift algorithm yields a certain value in some
> bits, performing a single iteration will cause those bits to (collectively)
> hold one of two values.

Not right.  Probably you are thinking of a simple linear feedback
shift register.  The xorshift family of transforms do not fall
into that category.

[toc] | [prev] | [next] | [standalone]

#95519

On Tuesday, November 1, 2016 at 10:13:53 AM UTC-5, Tim Rentsch wrote:
> > If one iteration of the xorshift algorithm yields a certain value in some
> > bits, performing a single iteration will cause those bits to (collectively)
> > hold one of two values.
> 
> Not right.  Probably you are thinking of a simple linear feedback
> shift register.  The xorshift family of transforms do not fall
> into that category.

There are a couple of ways of implementing a linear feedback shift register,
of which the more common is to have each value be the previous value shifted
right one, with the new bit being the xor of existing bits.  Another
variation is equivalent to a random number generator pattern that I've often
seen in machine-language games, and in simplest form is equivalent to:

    if (oldValue & 0x8000)  // Assume it's 16 bits
      oldValue = (oldValue << 1) ^ 0xDB;
    else
      oldValue = oldValue << 1;

I thought the latter is what was meant by "xorshift" (since that would seem
a logical name for the above).

[toc] | [prev] | [next] | [standalone]

#95615

supercat@casperkitty.com writes:

> On Tuesday, November 1, 2016 at 10:13:53 AM UTC-5, Tim Rentsch wrote:
>>> If one iteration of the xorshift algorithm yields a certain value in some
>>> bits, performing a single iteration will cause those bits to (collectively)
>>> hold one of two values.
>>
>> Not right.  Probably you are thinking of a simple linear feedback
>> shift register.  The xorshift family of transforms do not fall
>> into that category.
>
> There are a couple of ways of implementing a linear feedback shift register,
> [.. snip elaboration ..]

Yes I know.  Next time you might want to check your facts before
going ahead full steam on an assumption.  And that is true generally,
not just in regard to things like xorshift, etc.

[toc] | [prev] | [next] | [standalone]

#95388

On 10/29/2016 11:13 AM, Mr. Man-wai Chang wrote:
...
> I just want to play my MP3 songs in shuffle mode. I noticed that most
> shuffling algorithms are not random enough, as I could hear a pattern
> being repeated. :)

Then you don't need "truly" random. Pseudo-random should be adequate, 
and you shouldn't even need a particularly sophisticated algorithm to 
get results good enough for this purpose. Footnote 295 in the C standard 
says: "There are no guarantees as to the quality of the random sequence 
produced and some implementations are known to produce sequences with 
distressingly non-random low-order bits. Applications with particular 
requirements should use a generator that is known to be sufficient for 
their needs."
Because there are no quality requirements, a conforming implementation 
of rand() could, in principle, always return exactly the same value 
every time it's called. However, in reality you're unlikely to see 
anything significantly worse than the simple linear congruential 
algorithm that was given as an example in earlier versions of the 
standard (it was dropped because many implementors misinterpreted that 
algorithm as being either mandatory, or at least recommended - it was 
neither).

Avoid relying on the low order bits: use rand()*8/(RAND_MAX + 1) rather 
than rand()%8, to generate numbers from 0 to 7. If you do so, even a low 
quality implementation of rand() should be adequate for this purpose. 
Beware of overflow from the multiplication - if the number of songs 
you're shuffling is large enough, and RAND_MAX is close enough to 
INT_MAX, you may need to use long, long long, or possibly even a 
floating point type to avoid overflow. A floating point type is only 
likely to be needed if INT_MAX==LLONG_MAX, which is unlikely, but 
permitted, and somewhat more likely to come up than many of the other 
weird possibilities I occasionally bring up.

[toc] | [prev] | [next] | [standalone]

#95397

"Mr. Man-wai Chang" <toylet.toylet@gmail.com> writes:
[...]
> I just want to play my MP3 songs in shuffle mode. I noticed that most 
> shuffling algorithms are not random enough, as I could hear a pattern 
> being repeated. :)

You don't need an unusually high-quality PRNG to shuffle songs,
unless you're using the shuffle order for cyptography.

It's very likely that you're hearing patterns that aren't really
there.  Humans in general are *very* good at detecting patterns --
whether they're real or not.

If you're using a random number generator to shuffle songs, you won't
be able to tell the difference between a typical low-quality rand()
implementation and a high-quality hardware implementation.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#95410

On 29/10/16 17:13, Mr. Man-wai Chang wrote:
> On 28/10/2016 10:14 PM, Rick C. Hodgin wrote:
>> Several CPU manufacturers have introduced hardware which generates truly
>> random sequences based on internal circuits which monitor heat radiation
>> ...
>> Others CPU manufacturers have done similarly.
>
> Intel CPU?
>
>> If you really want a true random number generator locally, you can buy
>> add-on boards which provide that functionality through an API call:
>> http://www.idquantique.com/random-number-generation/quantis-random-number-generator/
>>
>
> NO plan to invest in hardware solution.
>
> I just want to play my MP3 songs in shuffle mode. I noticed that most
> shuffling algorithms are not random enough, as I could hear a pattern
> being repeated. :)
>

It depends on what you mean by "a pattern being repeated".  Suppose you 
have a dozen songs, shuffled randomly, which you listen to.  Then you 
shuffle them again, and listen again.  Then you notice that a particular 
pair of songs follow each other, just as they did in the previous set. 
A pattern!

In fact, even if the shuffling was perfectly random, you are going to 
get such pairs.  I haven't bothered doing the maths, but my guess is the 
chances are millions to one against you /not/ having such pairs with a 
dozen songs in your mix.  If you have a few dozen songs on your list, 
you are going to get runs of three or more matches on a regular basis.

So if a shuffle algorithm is /not/ producing such combinations, it is a 
strong sign that it is not actually very random.

[toc] | [prev] | [next] | [standalone]

#95411

"David Brown" wrote:

> On 29/10/16 17:13, Mr. Man-wai Chang wrote:
>> On 28/10/2016 10:14 PM, Rick C. Hodgin wrote:
>>> Several CPU manufacturers have introduced hardware which generates truly
>>> random sequences based on internal circuits which monitor heat radiation
>>> ...
>>> Others CPU manufacturers have done similarly.
>>
>> Intel CPU?
>>
>>> If you really want a true random number generator locally, you can buy
>>> add-on boards which provide that functionality through an API call:
>>> http://www.idquantique.com/random-number-generation/quantis-random-number-generator/
>>>
>>
>> NO plan to invest in hardware solution.
>>
>> I just want to play my MP3 songs in shuffle mode. I noticed that most
>> shuffling algorithms are not random enough, as I could hear a pattern
>> being repeated. :)
>>
>
> It depends on what you mean by "a pattern being repeated".  Suppose you 
> have a dozen songs, shuffled randomly, which you listen to.  Then you 
> shuffle them again, and listen again.  Then you notice that a particular 
> pair of songs follow each other, just as they did in the previous set. A 
> pattern!
>
> In fact, even if the shuffling was perfectly random, you are going to get 
> such pairs.  I haven't bothered doing the maths, but my guess is the 
> chances are millions to one against you /not/ having such pairs with a 
> dozen songs in your mix.  If you have a few dozen songs on your list, you 
> are going to get runs of three or more matches on a regular basis.
>
> So if a shuffle algorithm is /not/ producing such combinations, it is a 
> strong sign that it is not actually very random.

If I were to write a shuffle program such as the one being discussed, I 
would take pains to make sure it *was not* random. If the average citizen 
hears song A followed by song A, he is going to be annoyed. Might as well 
fix it now rather than a post-release "fix". 

[toc] | [prev] | [next] | [standalone]

#95414

On Sunday, October 30, 2016 at 12:07:30 PM UTC-5, Osmium wrote:
> If I were to write a shuffle program such as the one being discussed, I 
> would take pains to make sure it *was not* random. If the average citizen 
> hears song A followed by song A, he is going to be annoyed. Might as well 
> fix it now rather than a post-release "fix".

The first CD player I ever bought had an interesting shuffle algorithm;
like many such algorithms, it would play some arbitrary permutation of
the tracks on the disk, then a generally-different one, and so forth,
but the "next" button would advance to the next track in the current
permutation, if any, or else to the first track of a new permuation, and
the back button would undo the effect of the "next" button--**even across
permutation boundaries**.

I suspect that the unit had a function that would generate a permutation
given a seed, along with a reversible function that could be applied to
the seed.  Hitting "next" while playing the last song of a permutation
would use the reversible function on the seed, generate a new permutation
with the resulting seed, and start playing the first song of that.
Pressing "prev" while playing the first song of a permutation would use
the inverse of the reversible function on the seed, generate a new
permuation with that result, and start playing the last song of that.

[toc] | [prev] | [next] | [standalone]

#95428

On 29/10/16 16:13, Mr. Man-wai Chang wrote:
> On 28/10/2016 10:14 PM, Rick C. Hodgin wrote:
>> Several CPU manufacturers have introduced hardware which generates truly
>> random sequences based on internal circuits which monitor heat radiation
>> ...
>> Others CPU manufacturers have done similarly.
>
> Intel CPU?
>
>> If you really want a true random number generator locally, you can buy
>> add-on boards which provide that functionality through an API call:
>> http://www.idquantique.com/random-number-generation/quantis-random-number-generator/
>>
>
> NO plan to invest in hardware solution.
>
> I just want to play my MP3 songs in shuffle mode. I noticed that most
> shuffling algorithms are not random enough, as I could hear a pattern
> being repeated. :)

It's called 4/4.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#95669

On Saturday, October 29, 2016 at 11:13:37 AM UTC-4, Mr. Man-wai Chang wrote:
> On 28/10/2016 10:14 PM, Rick C. Hodgin wrote:
> > Several CPU manufacturers have introduced hardware which generates truly
> > random sequences based on internal circuits which monitor heat radiation
> > ...
> > Others CPU manufacturers have done similarly.
> 
> Intel CPU?
> 
> > If you really want a true random number generator locally, you can buy
> > add-on boards which provide that functionality through an API call:
> > http://www.idquantique.com/random-number-generation/quantis-random-number-generator/
> 
> NO plan to invest in hardware solution.
> 
> I just want to play my MP3 songs in shuffle mode. I noticed that most 
> shuffling algorithms are not random enough, as I could hear a pattern 
> being repeated. :)

Be careful. The human brain is tuned to see patterns. Sometimes we
see or hear patterns that when analyzed do not really exist.

ed

[toc] | [prev] | [next] | [standalone]

#95671

On Thursday, November 3, 2016 at 1:39:37 PM UTC-4, Ed Prochak wrote:
> Be careful. The human brain is tuned to see patterns. Sometimes we
> see or hear patterns that when analyzed do not really exist.

Here's an interesting "pattern" I saw that may not really exist.  The
Back to the Future movie ... if you take the release date of Back to
the Future (July 3, 1985), and add 1.21 gigawatts, I mean 1.21 giga-
seconds to it, it lands on a day that's exactly seven years to the day
ahead of this Saturday, November 5, 2016.

November 5 is Guy Fawkes Day ("Remember, remember the 5th of November")
when Fawkes tried to blow up the British Parliament in 1605.  He nearly
succeeded, but was caught last minute.

    https://en.wikipedia.org/wiki/Back_to_the_Future
    http://www.wolframalpha.com/input/?i=July+3,+1985+%2B+1.21+billion+seconds+-+7+years

November 5 is also the day Doc. Brown went back to in the year 1955, the
day he "invented time travel."

Back to the Future 2 is 108 minutes 6 seconds long, and it has the Cubs
winning the World Series in baseball (which they did yesterday after
108 years).

All kinds of "patterns" emerging from that movie series.  Biff/Tump is
another interesting one for this same timeframe (2015 he came on the
scene, and if he's elected and re-elected, it would carry through to
2025).

There's a two-part episode of DS9 which has a similar theme as the
future seen in Back to the Future 2, and for that same general
timeframe as the date indicated by July 3, 1985 + 1.21 billion seconds
(it was August 2024 in the DS9 episodes, "Future Tense," just about
nine months after November 5, 2023).

A similar general premise was in the TV show Sliders, where they once
slide into a world divided by tech and online people, and non-tech and
offline people.  Of course an onliner falls in love with an offliner.
:-)

Just some patterns I've noticed thanks to that one thing popping into my
head about the gigawatts = gigaseconds correlation.  I've found them, at
least, interesting to ponder.

Best regards,
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#95676 — [OT] gigawatts = gigaseconds correlation?

On 4/11/2016 2:13 AM, Rick C. Hodgin wrote:
> Just some patterns I've noticed thanks to that one thing popping into my
> head about the gigawatts = gigaseconds correlation.  I've found them, at
> least, interesting to ponder.

Is this proven? Or just an interesting coincidence, in the movies?

[toc] | [prev] | [next] | [standalone]

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

Back to top | Article view | comp.lang.c

csiph-web