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

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

Request for source code review of simple Ising model

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

Contents

  Request for source code review of simple Ising model Udyant Wig <udyant@panda.goosenet.in> - 2014-04-10 23:38 +0530
    Re: Request for source code review of simple Ising model Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-04-10 13:30 -0700
      Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-12 00:34 +0530
        Re: Request for source code review of simple Ising model Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-04-11 12:25 -0700
        Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-16 01:12 +0530
          Re: Request for source code review of simple Ising model Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-04-16 01:33 +0100
            Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-16 17:57 +0530
              Re: Request for source code review of simple Ising model Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-04-16 06:00 -0700
              Re: Request for source code review of simple Ising model James Kuyper <jameskuyper@verizon.net> - 2014-04-16 10:58 -0400
                Re: Request for source code review of simple Ising model Keith Thompson <kst-u@mib.org> - 2014-04-16 09:07 -0700
                  Re: Request for source code review of simple Ising model James Kuyper <jameskuyper@verizon.net> - 2014-04-16 12:22 -0400
                    Re: Request for source code review of simple Ising model Keith Thompson <kst-u@mib.org> - 2014-04-16 10:38 -0700
                      Re: Request for source code review of simple Ising model Kaz Kylheku <kaz@kylheku.com> - 2014-04-16 19:37 +0000
                  Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-17 12:00 +0530
                    Re: Request for source code review of simple Ising model glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-04-17 09:32 +0000
                      Re: Request for source code review of simple Ising model "BartC" <bc@freeuk.com> - 2014-04-17 12:24 +0100
                        Re: Request for source code review of simple Ising model Keith Thompson <kst-u@mib.org> - 2014-04-17 08:16 -0700
                      Re: Request for source code review of simple Ising model Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-04-17 04:41 -0700
                        Re: Request for source code review of simple Ising model Les Cargill <lcargill99@comcast.com> - 2014-04-17 07:49 -0500
                    Re: Request for source code review of simple Ising model Keith Thompson <kst-u@mib.org> - 2014-04-17 08:00 -0700
                      Re: Request for source code review of simple Ising model Kaz Kylheku <kaz@kylheku.com> - 2014-04-17 15:06 +0000
                        Re: Request for source code review of simple Ising model Tim Rentsch <txr@alumni.caltech.edu> - 2014-04-18 21:04 -0700
                      Re: Request for source code review of simple Ising model glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-04-17 18:38 +0000
                        Re: Request for source code review of simple Ising model James Kuyper <jameskuyper@verizon.net> - 2014-04-17 15:26 -0400
                          Re: Request for source code review of simple Ising model "BartC" <bc@freeuk.com> - 2014-04-17 21:00 +0100
                            Re: Request for source code review of simple Ising model James Kuyper <jameskuyper@verizon.net> - 2014-04-17 16:34 -0400
                            Re: Request for source code review of simple Ising model glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-04-18 04:31 +0000
                        Re: Request for source code review of simple Ising model Keith Thompson <kst-u@mib.org> - 2014-04-17 14:05 -0700
                          Re: Request for source code review of simple Ising model Keith Thompson <kst-u@mib.org> - 2014-04-17 17:06 -0700
                          Re: Request for source code review of simple Ising model glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-04-18 04:54 +0000
                          Re: Request for source code review of simple Ising model Tim Rentsch <txr@alumni.caltech.edu> - 2014-04-18 11:51 -0700
                Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-17 11:42 +0530
              Re: Request for source code review of simple Ising model Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-04-16 16:54 +0100
                Re: Request for source code review of simple Ising model Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-04-16 15:22 -0700
                Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-17 13:03 +0530
                  Re: Request for source code review of simple Ising model Keith Thompson <kst-u@mib.org> - 2014-04-17 08:44 -0700
                    Re: Request for source code review of simple Ising model James Kuyper <jameskuyper@verizon.net> - 2014-04-17 12:12 -0400
                      Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-18 12:38 +0530
                      Re: Request for source code review of simple Ising model Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-04-18 03:11 -0700
                    Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-18 12:32 +0530
                      Re: Request for source code review of simple Ising model James Kuyper <jameskuyper@verizon.net> - 2014-04-18 10:05 -0400
          Re: Request for source code review of simple Ising model Ike Naar <ike@iceland.freeshell.org> - 2014-04-16 07:10 +0000
          Re: Request for source code review of simple Ising model James Kuyper <jameskuyper@verizon.net> - 2014-04-17 13:10 -0400
            Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-18 18:24 +0530
              Re: Request for source code review of simple Ising model James Kuyper <jameskuyper@verizon.net> - 2014-04-18 09:52 -0400
                Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-18 20:04 +0530
                  Re: Request for source code review of simple Ising model James Kuyper <jameskuyper@verizon.net> - 2014-04-18 11:00 -0400
                    Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-20 01:49 +0530
                      Re: Request for source code review of simple Ising model glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-04-19 21:20 +0000
                        Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-20 11:11 +0530
                          Re: Request for source code review of simple Ising model Richard Damon <Richard@Damon-Family.org> - 2014-04-20 09:06 -0400
                        Re: Request for source code review of simple Ising model James Kuyper <jameskuyper@verizon.net> - 2014-04-20 10:50 -0400
                          Re: Request for source code review of simple Ising model Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-04-21 09:14 -0700
                Re: Request for source code review of simple Ising model Ike Naar <ike@iceland.freeshell.org> - 2014-04-19 05:43 +0000
              Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-18 19:47 +0530
              Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-21 01:21 +0530
                Re: Request for source code review of simple Ising model Keith Thompson <kst-u@mib.org> - 2014-04-20 14:24 -0700
                  Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-21 10:40 +0530
                Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-21 12:29 +0530
            Re: Request for source code review of simple Ising model Keith Thompson <kst-u@mib.org> - 2014-04-18 08:36 -0700
              Re: Request for source code review of simple Ising model James Kuyper <jameskuyper@verizon.net> - 2014-04-18 13:40 -0400
                Re: Request for source code review of simple Ising model Keith Thompson <kst-u@mib.org> - 2014-04-18 11:14 -0700
                Re: Request for source code review of simple Ising model Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-04-18 13:55 -0700
              Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-19 01:25 +0530
                Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-19 01:44 +0530
                Re: Request for source code review of simple Ising model Kaz Kylheku <kaz@kylheku.com> - 2014-04-18 20:24 +0000
                Re: Request for source code review of simple Ising model Keith Thompson <kst-u@mib.org> - 2014-04-18 13:36 -0700
                  Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-19 20:18 +0530
                Re: Request for source code review of simple Ising model Richard <rgrdev_@gmail.com> - 2014-04-19 14:55 +0100
                  Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-20 02:10 +0530
              Re: Request for source code review of simple Ising model Ike Naar <ike@iceland.freeshell.org> - 2014-04-19 05:40 +0000
                Re: Request for source code review of simple Ising model Keith Thompson <kst-u@mib.org> - 2014-04-19 14:39 -0700
                  Re: Request for source code review of simple Ising model Ian Collins <ian-news@hotmail.com> - 2014-04-20 10:44 +1200
                    Re: Request for source code review of simple Ising model Keith Thompson <kst-u@mib.org> - 2014-04-19 17:11 -0700
                    Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-20 11:24 +0530
                  Re: Request for source code review of simple Ising model Keith Thompson <kst-u@mib.org> - 2014-04-19 17:19 -0700
                    Re: Request for source code review of simple Ising model Ike Naar <ike@iceland.freeshell.org> - 2014-04-20 10:10 +0000
                      Re: Request for source code review of simple Ising model Keith Thompson <kst-u@mib.org> - 2014-04-20 14:21 -0700
                        Re: Request for source code review of simple Ising model Ike Naar <ike@iceland.freeshell.org> - 2014-04-20 22:18 +0000
                          Re: Request for source code review of simple Ising model Keith Thompson <kst-u@mib.org> - 2014-04-20 19:27 -0700
                            Re: Request for source code review of simple Ising model Ike Naar <ike@iceland.freeshell.org> - 2014-04-21 12:38 +0000
                            Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-21 18:12 +0530
                            Re: Request for source code review of simple Ising model Ike Naar <ike@iceland.freeshell.org> - 2014-04-21 13:13 +0000
                              Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-21 19:46 +0530
                              Re: Request for source code review of simple Ising model Keith Thompson <kst-u@mib.org> - 2014-04-21 09:06 -0700
                  Re: Request for source code review of simple Ising model jacob navia <jacob@spamsink.net> - 2014-04-21 00:26 +0200
          Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-18 01:15 +0530
          Re: Request for source code review of simple Ising model Udyant Wig <udyantw@gmail.com> - 2014-04-20 11:46 +0530

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

#43086

On 04/18/2014 11:36 AM, Keith Thompson wrote:
> James Kuyper <jameskuyper@verizon.net> writes:
...
>> might not be very good, you should be aware of the fact that, in poor
>> quality implementations, lower-order bits are likely to be significantly
>> less random than higher-order ones. RAND_MAX is required to be >= 32767,
>> so 0x4000 is the highest bit that guaranteed to be <RAND_MAX. If you're
>> only going extract one bit from rand(), I'd recommend extracting that
>> one: ((rand()%0x4000) == 0x4000 ? 2 : 1).
> 
> (As discussed downthread, that "%" was meant to be "&".)
> 
> Is it still the case that the low-order bits are commonly less random
> than the high-order bits?  Question 13.18 of the FAQ
> <http://www.c-faq.com/> says so, but I suspect it's out of date.

I don't know, which is why I deliberately prefixed my remarks with "in
poor quality implementations". The average quality of implementation of
rand() may be improving, but I believe that what I've written is still
true of poor quality implementations. However, that belief is entirely
second hand - I can't claim to have performed relevant studies myself.

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

#43089

James Kuyper <jameskuyper@verizon.net> writes:
> On 04/18/2014 11:36 AM, Keith Thompson wrote:
>> James Kuyper <jameskuyper@verizon.net> writes:
> ...
>>> might not be very good, you should be aware of the fact that, in poor
>>> quality implementations, lower-order bits are likely to be significantly
>>> less random than higher-order ones. RAND_MAX is required to be >= 32767,
>>> so 0x4000 is the highest bit that guaranteed to be <RAND_MAX. If you're
>>> only going extract one bit from rand(), I'd recommend extracting that
>>> one: ((rand()%0x4000) == 0x4000 ? 2 : 1).
>> 
>> (As discussed downthread, that "%" was meant to be "&".)
>> 
>> Is it still the case that the low-order bits are commonly less random
>> than the high-order bits?  Question 13.18 of the FAQ
>> <http://www.c-faq.com/> says so, but I suspect it's out of date.
>
> I don't know, which is why I deliberately prefixed my remarks with "in
> poor quality implementations". The average quality of implementation of
> rand() may be improving, but I believe that what I've written is still
> true of poor quality implementations. However, that belief is entirely
> second hand - I can't claim to have performed relevant studies myself.

And the question is, are such poor quality implementations still common
enough that they're worth worrying about?  I'm not expecting you to have
a definitive answer to that (nor do I), but if someone else can provide
a concrete example it would be very interesting.

Given that the sample implementation that's been in the standard for the
last 25 years doesn't appear to suffer from this problem[*], there's
really no excuse for any current real-world implementation to be that
bad.

[*] At least it doesn't return 0, 1, 0, 1, ... for the low-order bit.
It *might* still be the case that the low-order bits are lower quality
than the high-order bits.  I lack the expertise to analyze it.

-- 
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]

#43098

On Friday, April 18, 2014 6:40:42 PM UTC+1, James Kuyper wrote:
> On 04/18/2014 11:36 AM, Keith Thompson wrote:
> 
> > James Kuyper <jameskuyper@verizon.net> writes:
> 
> I don't know, which is why I deliberately prefixed my remarks with "in
> poor quality implementations". The average quality of implementation of
> rand() may be improving, but I believe that what I've written is still
> true of poor quality implementations. However, that belief is entirely
> second hand - I can't claim to have performed relevant studies myself.
>
You have to be careful with Ising models. Obviously it depends what you're
using the model for. They're statistical models of random but coherent
systems, with emergent properties. The so called critical temperature
might well be affected by the quality of the RNG. 

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

#43092

Keith Thompson <kst-u@mib.org> writes:
| I think I've seen PRNGs where the low-order bit actually alternates 0,
| 1, 0, 1, 0, 1, ..., but the sample implementation in the standard
| doesn't do that.

 There is a discussion of this very issue (or something extremely close
 to it) in one of the assignments of Steve Summit's (fine) online C
 programming classes found here:

 http://www.eskimo.com/~scs/cclass/cclass.html

 It is Exercise 8 of the third assignment:

 http://www.eskimo.com/~scs/cclass/asgn.beg/PS3.html

 The explanation is here in the answers section:

 http://www.eskimo.com/~scs/cclass/asgn.beg/PS3a.html
 
| Here's a test program if anyone wants to try it.  If it prints either
| "01010101..." or "10101010...", please let us know what implementation
| you're using.
|
| #include <stdio.h>
| #include <stdlib.h>
|
| int main(void) {
|     for (int i = 0; i < 64; i ++) {
|         printf("%d", rand() % 2);
|     }
|     putchar('\n');
| }

 I changed it thusly to calm gcc down:
 
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int i;
    for (i = 0; i < 64; i ++) {
        printf("%d", rand() % 2);
    }
    putchar('\n');

    return 0;
}

1011110011010110000010110001111000111010111101001010100100011101

| On one of my systems, the output is
>
| 1011110011010110000010110001111000111010111101001010100100011101

 The two outputs are equal.  Independent confirmations by Emacs Lisp,

(string-equal
 "1011110011010110000010110001111000111010111101001010100100011101"
 "1011110011010110000010110001111000111010111101001010100100011101")
=> t

 and their MD5 sums,

$ md5sum # Keith Thompson's output
1011110011010110000010110001111000111010111101001010100100011101
89e91cff9eefca6a24afaee2809c0859  -

$ md5sum # Udyant Wig's output
1011110011010110000010110001111000111010111101001010100100011101
89e91cff9eefca6a24afaee2809c0859  -

 verify this.
 

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

#43094

 The output using the rand() from FreeBSD libc:


/* freebsd-rand.c begins */

/*-
 * Copyright (c) 1990, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <stdio.h>
#include <stdlib.h>

static int
do_rand(unsigned long *ctx)
{
#ifdef  USE_WEAK_SEEDING
/*
 * Historic implementation compatibility.
 * The random sequences do not vary much with the seed,
 * even with overflowing.
 */
	return ((*ctx = *ctx * 1103515245 + 12345) % ((u_long)RAND_MAX + 1));
#else   /* !USE_WEAK_SEEDING */
/*
 * Compute x = (7^5 * x) mod (2^31 - 1)
 * without overflowing 31 bits:
 *      (2^31 - 1) = 127773 * (7^5) + 2836
 * From "Random number generators: good ones are hard to find",
 * Park and Miller, Communications of the ACM, vol. 31, no. 10,
 * October 1988, p. 1195.
 */
	long hi, lo, x;

	/* Must be in [1, 0x7ffffffe] range at this point. */
	hi = *ctx / 127773;
	lo = *ctx % 127773;
	x = 16807 * lo - 2836 * hi;
	if (x < 0)
		x += 0x7fffffff;
	*ctx = x;
	/* Transform to [0, 0x7ffffffd] range. */
	return (x - 1);
#endif  /* !USE_WEAK_SEEDING */
}

static u_long next =
#ifdef  USE_WEAK_SEEDING
    1;
#else
    2;
#endif

int
rand()
{
	return (do_rand(&next));
}

int main(void) {
    int i;
    for (i = 0; i < 64; i ++) {
        printf("%d", rand() % 2);
    }
    putchar('\n');

    return 0;
}

/* freebsd-rand.c ends */
 
 
$ ./freebsd-rand
1101011000100110011110000010100011010001100001001101111110010001

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

#43095

On 2014-04-18, Udyant Wig <udyantw@gmail.com> wrote:
> Keith Thompson <kst-u@mib.org> writes:
>| I think I've seen PRNGs where the low-order bit actually alternates 0,
>| 1, 0, 1, 0, 1, ..., but the sample implementation in the standard
>| doesn't do that.
>
>  There is a discussion of this very issue (or something extremely close
>  to it) in one of the assignments of Steve Summit's (fine) online C
>  programming classes found here:

A nice little PRNG is WELL. Reference C code is available (not freeware,
though: non-commercial use only!)

www.iro.umontreal.ca/~panneton/WELLRNG.html
http://en.wikipedia.org/wiki/Well_Equidistributed_Long-period_Linear

I've implemented this myself also, using a "clean-room" approach (not reusing any
of the above source code), and put it under a BSD license:

http://www.kylheku.com/cgit/txr/tree/rand.c

This is not packaged for general reuse, however. The heart of it is the
struct rand_state declaration, the rand32 function, and some useful
cases in the make_random_state function for seeding in various ways.
(The reference implementation has only an API for seeding using a vector
of ints, which must have the same size as the state vector.)

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

#43096

Udyant Wig <udyantw@gmail.com> writes:
> Keith Thompson <kst-u@mib.org> writes:
> | I think I've seen PRNGs where the low-order bit actually alternates 0,
> | 1, 0, 1, 0, 1, ..., but the sample implementation in the standard
> | doesn't do that.
>
>  There is a discussion of this very issue (or something extremely close
>  to it) in one of the assignments of Steve Summit's (fine) online C
>  programming classes found here:
>
>  http://www.eskimo.com/~scs/cclass/cclass.html
>
>  It is Exercise 8 of the third assignment:
>
>  http://www.eskimo.com/~scs/cclass/asgn.beg/PS3.html
>
>  The explanation is here in the answers section:
>
>  http://www.eskimo.com/~scs/cclass/asgn.beg/PS3a.html

That merely asserts that:

    In particular, it's not uncommon for the rand funciton to produce
    alternately even and odd numbers, such that if you repeatedly
    compute rand % 2, you'll get the decidedly non-random sequence 0,
    1, 0, 1, 0, 1, 0, 1... .

I'm looking for concrete examples of real-world implementations that
behave this way.

> | Here's a test program if anyone wants to try it.
[...]
> |     for (int i = 0; i < 64; i ++) {
[...]
>
>  I changed it thusly to calm gcc down:
>  
[...]
>     int i;
>     for (i = 0; i < 64; i ++) {
[...]

Compiling with "-std=c99" also works.

It's a pity that gcc rejects this particular C99 feature by default.
Even if the gcc maintainers don't feel they're ready to make C99 the
default standard, they could easily treat this as a GNU extension on top
of C90.

-- 
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]

#43125

Keith Thompson <kst-u@mib.org> writes:
| That merely asserts that:
|
|     In particular, it's not uncommon for the rand funciton to produce
|     alternately even and odd numbers, such that if you repeatedly
|     compute rand % 2, you'll get the decidedly non-random sequence 0,
|     1, 0, 1, 0, 1, 0, 1... .
|
| I'm looking for concrete examples of real-world implementations that
| behave this way.

 As Ike Naar writes in the article with
 Message-ID: <slrn3vfsll431q.5cm.ike@iceland.freeshell.org>:
| Here it prints
|
| 0101010101010101010101010101010101010101010101010101010101010101
|
| The implementation is gcc version 4.5.3 (NetBSD nb2 20110806).

 This is the implementation of rand() in NetBSD's libc:

/*	$NetBSD: rand.c,v 1.12 2012/06/25 22:32:45 abs Exp $	*/

/*-
 * Copyright (c) 1990, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <sys/cdefs.h>
#if defined(LIBC_SCCS) && !defined(lint)
#if 0
static char sccsid[] = "@(#)rand.c	8.1 (Berkeley) 6/14/93";
#else
__RCSID("$NetBSD: rand.c,v 1.12 2012/06/25 22:32:45 abs Exp $");
#endif
#endif /* LIBC_SCCS and not lint */

#include <sys/types.h>
#include <stdlib.h>

static u_long next = 1;

int
rand(void)
{
	/* LINTED integer overflow */
	return (int)((next = next * 1103515245 + 12345) % ((u_long)RAND_MAX + 1));
}

void
srand(u_int seed)
{
	next = seed;
}

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

#43122

Udyant Wig <udyantw@gmail.com> writes:

> Keith Thompson <kst-u@mib.org> writes:
> | I think I've seen PRNGs where the low-order bit actually alternates 0,
> | 1, 0, 1, 0, 1, ..., but the sample implementation in the standard
> | doesn't do that.
>
>  There is a discussion of this very issue (or something extremely close
>  to it) in one of the assignments of Steve Summit's (fine) online C
>  programming classes found here:
>
>  http://www.eskimo.com/~scs/cclass/cclass.html
>
>  It is Exercise 8 of the third assignment:
>
>  http://www.eskimo.com/~scs/cclass/asgn.beg/PS3.html
>
>  The explanation is here in the answers section:
>
>  http://www.eskimo.com/~scs/cclass/asgn.beg/PS3a.html
>
> | Here's a test program if anyone wants to try it.  If it prints either
> | "01010101..." or "10101010...", please let us know what implementation
> | you're using.
> |
> | #include <stdio.h>
> | #include <stdlib.h>
> |
> | int main(void) {
> |     for (int i = 0; i < 64; i ++) {
> |         printf("%d", rand() % 2);
> |     }
> |     putchar('\n');
> | }
>
>  I changed it thusly to calm gcc down:
>
> #include <stdio.h>
> #include <stdlib.h>
>
> int main(void) {
>     int i;
>     for (i = 0; i < 64; i ++) {
>         printf("%d", rand() % 2);
>     }
>     putchar('\n');
>
>     return 0;
> }
>
> 1011110011010110000010110001111000111010111101001010100100011101
>
> | On one of my systems, the output is
>>
> | 1011110011010110000010110001111000111010111101001010100100011101
>
>  The two outputs are equal.  Independent confirmations by Emacs Lisp,
>
> (string-equal
>  "1011110011010110000010110001111000111010111101001010100100011101"
>  "1011110011010110000010110001111000111010111101001010100100011101")
> => t
>
>  and their MD5 sums,
>
> $ md5sum # Keith Thompson's output
> 1011110011010110000010110001111000111010111101001010100100011101
> 89e91cff9eefca6a24afaee2809c0859  -
>
> $ md5sum # Udyant Wig's output
> 1011110011010110000010110001111000111010111101001010100100011101
> 89e91cff9eefca6a24afaee2809c0859  -
>
>  verify this.
>

Serious Q : are you taking the piss?

-- 
"Avoid hyperbole at all costs, its the most destructive argument on
the planet" - Mark McIntyre in comp.lang.c

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

#43134

Richard <rgrdev_@gmail.com> writes:
|>  The two outputs are equal.  Independent confirmations by Emacs Lisp,
|>
|> (string-equal
|>  "1011110011010110000010110001111000111010111101001010100100011101"
|>  "1011110011010110000010110001111000111010111101001010100100011101")
|> => t
|>
|>  and their MD5 sums,
|>
|> $ md5sum # Keith Thompson's output
|> 1011110011010110000010110001111000111010111101001010100100011101
|> 89e91cff9eefca6a24afaee2809c0859  -
|>
|> $ md5sum # Udyant Wig's output
|> 1011110011010110000010110001111000111010111101001010100100011101
|> 89e91cff9eefca6a24afaee2809c0859  -
|>
|>  verify this.
|>
|
| Serious Q : are you taking the piss?

 I went overboard with the confirmations.  It was _not_ my intention to
 abuse trust at all.  I apologize if that came across as mocking.

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

#43113

On 2014-04-18, Keith Thompson <kst-u@mib.org> wrote:
> Here's a test program if anyone wants to try it.  If it prints either
> "01010101..." or "10101010...", please let us know what implementation
> you're using.
>
> #include <stdio.h>
> #include <stdlib.h>
>
> int main(void) {
>     for (int i = 0; i < 64; i ++) {
>         printf("%d", rand() % 2);
>     }
>     putchar('\n');
> }
>
> On one of my systems, the output is
>
> 1011110011010110000010110001111000111010111101001010100100011101

Here it prints

0101010101010101010101010101010101010101010101010101010101010101

The implementation is gcc version 4.5.3 (NetBSD nb2 20110806).

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

#43138

Ike Naar <ike@iceland.freeshell.org> writes:
> On 2014-04-18, Keith Thompson <kst-u@mib.org> wrote:
>> Here's a test program if anyone wants to try it.  If it prints either
>> "01010101..." or "10101010...", please let us know what implementation
>> you're using.
>>
>> #include <stdio.h>
>> #include <stdlib.h>
>>
>> int main(void) {
>>     for (int i = 0; i < 64; i ++) {
>>         printf("%d", rand() % 2);
>>     }
>>     putchar('\n');
>> }
>>
>> On one of my systems, the output is
>>
>> 1011110011010110000010110001111000111010111101001010100100011101
>
> Here it prints
>
> 0101010101010101010101010101010101010101010101010101010101010101
>
> The implementation is gcc version 4.5.3 (NetBSD nb2 20110806).

Fascinating.  So there *are* modern implementations that have this
problem.

The relevant implementation is the C standard library, not the compiler.
BSD has its own C standard library implementation.  I wonder if Mac OSX
(which is based on BSD) has this problem.

The man page
    http://netbsd.gw.com/cgi-bin/man-cgi?rand+3+NetBSD-current
doesn't mention this, apart from the NAME section:

    rand, srand, rand_r -- bad random number generator

-- 
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]

#43142

Keith Thompson wrote:
> Ike Naar <ike@iceland.freeshell.org> writes:
>> Here it prints
>>
>> 0101010101010101010101010101010101010101010101010101010101010101
>>
>> The implementation is gcc version 4.5.3 (NetBSD nb2 20110806).
>
> Fascinating.  So there *are* modern implementations that have this
> problem.
>
> The relevant implementation is the C standard library, not the compiler.
> BSD has its own C standard library implementation.  I wonder if Mac OSX
> (which is based on BSD) has this problem.

It doesn't.

1110000011010011110011110110011001011111101011010111000000010010

> The man page
>      http://netbsd.gw.com/cgi-bin/man-cgi?rand+3+NetBSD-current
> doesn't mention this, apart from the NAME section:
>
>      rand, srand, rand_r -- bad random number generator
>

But it does have the same man page!

-- 
Ian Collins

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

#43150

ram@zedat.fu-berlin.de (Stefan Ram) writes:
> Ian Collins <ian-news@hotmail.com> writes:
>>But it does have the same man page!
>
>   IIRC, one version of the C standard contained a simplistic
>   example of how rand() might be implemented, and many
>   implementation manufacturers seemed to have copied this.

The 1990, 1999, and 2011 ISO C standards all include a non-normative
sample implementation of rand() (one that assume RAND_MAX==32767) -- but
it doesn't suffer from the problem that the low-order bits consistently
alternate between 0 and 1.

>   I am using rand() in my courses, because rand() is a simple
>   example of a function that can be called before function-call
>   arguments are introduced, and I therefore hope that rand()
>   will not be removed from the standard library of C.
>
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3841.pdf

The link is to proposal to discourage the use of rand() in C++14.  I
don't think there's much chance rand() will be removed from C any time
soon.  If it were removed, there would have to be a better replacement
for it.  There's no shortage of better PRNGs, but I expect that deciding
which one (if any) to mandate would be difficult.

I suppose that a future standard could add a new PRNG that can be seeded
with more information than the existing srand(), which only takes a
single unsigned int.

One requirement that rand() must satisfy is that it always yields the
same sequence of numbers for a given seed.  That might not be compatible
with the requirements of cryptography, for example, unless you also
provide way to feed it a high-quality seed.

-- 
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]

#43165

Ian Collins <ian-news@hotmail.com> writes:
| Keith Thompson wrote:
|> The relevant implementation is the C standard library, not the
|> compiler.  BSD has its own C standard library implementation.  I
|> wonder if Mac OSX (which is based on BSD) has this problem.
|
| It doesn't.
|
| 1110000011010011110011110110011001011111101011010111000000010010

It uses the same rand() as FreeBSD:
 
http://www.opensource.apple.com/source/Libc/Libc-997.1.1/stdlib/FreeBSD/rand.c

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

#43151

Keith Thompson <kst-u@mib.org> writes:
> Ike Naar <ike@iceland.freeshell.org> writes:
>> On 2014-04-18, Keith Thompson <kst-u@mib.org> wrote:
>>> Here's a test program if anyone wants to try it.  If it prints either
>>> "01010101..." or "10101010...", please let us know what implementation
>>> you're using.
>>>
>>> #include <stdio.h>
>>> #include <stdlib.h>
>>>
>>> int main(void) {
>>>     for (int i = 0; i < 64; i ++) {
>>>         printf("%d", rand() % 2);
>>>     }
>>>     putchar('\n');
>>> }
>>>
>>> On one of my systems, the output is
>>>
>>> 1011110011010110000010110001111000111010111101001010100100011101
>>
>> Here it prints
>>
>> 0101010101010101010101010101010101010101010101010101010101010101
>>
>> The implementation is gcc version 4.5.3 (NetBSD nb2 20110806).
>
> Fascinating.  So there *are* modern implementations that have this
> problem.
>
> The relevant implementation is the C standard library, not the compiler.
> BSD has its own C standard library implementation.  I wonder if Mac OSX
> (which is based on BSD) has this problem.
>
> The man page
>     http://netbsd.gw.com/cgi-bin/man-cgi?rand+3+NetBSD-current
> doesn't mention this, apart from the NAME section:
>
>     rand, srand, rand_r -- bad random number generator

I've grabbed a copy of source code for the NetBSD libc implementation of
rand() and run the same test on it on some of my own systems (64-bit
Linux Mint 14, 32-bit Ubuntu 12.10ish, and Cygwin on Windows 7), and I
*didn't* see alternating 0 and 1 low-order bits.  I even examined all
available versions from the NetBSD CVS repository (the history goes back
to 1993), and I see no differences in the available history that would
explain this behavior.  Obviously I'm missing something.

Ike: What is "NetBSD nb2 20110806"?  The latest release of NetBSD is
6.1.4; how does it relate to that?

I've set up a GitHub project for this at
https://github.com/Keith-S-Thompson/crude_rand_test

-- 
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]

#43170

On 2014-04-20, Keith Thompson <kst-u@mib.org> wrote:
> Keith Thompson <kst-u@mib.org> writes:
>> Ike Naar <ike@iceland.freeshell.org> writes:
>>> On 2014-04-18, Keith Thompson <kst-u@mib.org> wrote:
>>>> Here's a test program if anyone wants to try it.  If it prints either
>>>> "01010101..." or "10101010...", please let us know what implementation
>>>> you're using.
>>>>
>>>> #include <stdio.h>
>>>> #include <stdlib.h>
>>>>
>>>> int main(void) {
>>>>     for (int i = 0; i < 64; i ++) {
>>>>         printf("%d", rand() % 2);
>>>>     }
>>>>     putchar('\n');
>>>> }
>>>>
>>>> On one of my systems, the output is
>>>>
>>>> 1011110011010110000010110001111000111010111101001010100100011101
>>>
>>> Here it prints
>>>
>>> 0101010101010101010101010101010101010101010101010101010101010101
>>>
>>> The implementation is gcc version 4.5.3 (NetBSD nb2 20110806).
>>
>> Fascinating.  So there *are* modern implementations that have this
>> problem.
>>
>> The relevant implementation is the C standard library, not the compiler.
>> BSD has its own C standard library implementation.  I wonder if Mac OSX
>> (which is based on BSD) has this problem.
>>
>> The man page
>>     http://netbsd.gw.com/cgi-bin/man-cgi?rand+3+NetBSD-current
>> doesn't mention this, apart from the NAME section:
>>
>>     rand, srand, rand_r -- bad random number generator
>
> I've grabbed a copy of source code for the NetBSD libc implementation of
> rand() and run the same test on it on some of my own systems (64-bit
> Linux Mint 14, 32-bit Ubuntu 12.10ish, and Cygwin on Windows 7), and I
> *didn't* see alternating 0 and 1 low-order bits.  I even examined all
> available versions from the NetBSD CVS repository (the history goes back
> to 1993), and I see no differences in the available history that would
> explain this behavior.  Obviously I'm missing something.
>
> Ike: What is "NetBSD nb2 20110806"?  The latest release of NetBSD is
> 6.1.4; how does it relate to that?

$ uname -a
NetBSD iceland 6.1_STABLE NetBSD 6.1_STABLE (SDF6.amd64) #0: Tue Nov 26 12:49:14 UTC 2013  root@bjork:/spare/netbsd/src/sys/arch/amd64/compile/SDF6.amd64 amd64

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

#43190

Ike Naar <ike@iceland.freeshell.org> writes:
> On 2014-04-20, Keith Thompson <kst-u@mib.org> wrote:
>> Keith Thompson <kst-u@mib.org> writes:
>>> Ike Naar <ike@iceland.freeshell.org> writes:
[...]
>>>> Here it prints
>>>>
>>>> 0101010101010101010101010101010101010101010101010101010101010101
>>>>
>>>> The implementation is gcc version 4.5.3 (NetBSD nb2 20110806).
>>>
>>> Fascinating.  So there *are* modern implementations that have this
>>> problem.
>>>
>>> The relevant implementation is the C standard library, not the compiler.
>>> BSD has its own C standard library implementation.  I wonder if Mac OSX
>>> (which is based on BSD) has this problem.
>>>
>>> The man page
>>>     http://netbsd.gw.com/cgi-bin/man-cgi?rand+3+NetBSD-current
>>> doesn't mention this, apart from the NAME section:
>>>
>>>     rand, srand, rand_r -- bad random number generator
>>
>> I've grabbed a copy of source code for the NetBSD libc implementation of
>> rand() and run the same test on it on some of my own systems (64-bit
>> Linux Mint 14, 32-bit Ubuntu 12.10ish, and Cygwin on Windows 7), and I
>> *didn't* see alternating 0 and 1 low-order bits.  I even examined all
>> available versions from the NetBSD CVS repository (the history goes back
>> to 1993), and I see no differences in the available history that would
>> explain this behavior.  Obviously I'm missing something.
>>
>> Ike: What is "NetBSD nb2 20110806"?  The latest release of NetBSD is
>> 6.1.4; how does it relate to that?
>
> $ uname -a
> NetBSD iceland 6.1_STABLE NetBSD 6.1_STABLE (SDF6.amd64) #0: Tue Nov 26 12:49:14 UTC 2013  root@bjork:/spare/netbsd/src/sys/arch/amd64/compile/SDF6.amd64 amd64

Can you try running the code from my new GitHub project on your system?

https://github.com/Keith-S-Thompson/crude_rand_test

Thanks.

-- 
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]

#43198

On 2014-04-20, Keith Thompson <kst-u@mib.org> wrote:
> Ike Naar <ike@iceland.freeshell.org> writes:
>> On 2014-04-20, Keith Thompson <kst-u@mib.org> wrote:
>>> Keith Thompson <kst-u@mib.org> writes:
>>>> Ike Naar <ike@iceland.freeshell.org> writes:
> [...]
>>>>> Here it prints
>>>>>
>>>>> 0101010101010101010101010101010101010101010101010101010101010101
>>>>>
>>>>> The implementation is gcc version 4.5.3 (NetBSD nb2 20110806).
>>>>
>>>> Fascinating.  So there *are* modern implementations that have this
>>>> problem.
>>>>
>>>> The relevant implementation is the C standard library, not the compiler.
>>>> BSD has its own C standard library implementation.  I wonder if Mac OSX
>>>> (which is based on BSD) has this problem.
>>>>
>>>> The man page
>>>>     http://netbsd.gw.com/cgi-bin/man-cgi?rand+3+NetBSD-current
>>>> doesn't mention this, apart from the NAME section:
>>>>
>>>>     rand, srand, rand_r -- bad random number generator
>>>
>>> I've grabbed a copy of source code for the NetBSD libc implementation of
>>> rand() and run the same test on it on some of my own systems (64-bit
>>> Linux Mint 14, 32-bit Ubuntu 12.10ish, and Cygwin on Windows 7), and I
>>> *didn't* see alternating 0 and 1 low-order bits.  I even examined all
>>> available versions from the NetBSD CVS repository (the history goes back
>>> to 1993), and I see no differences in the available history that would
>>> explain this behavior.  Obviously I'm missing something.
>>>
>>> Ike: What is "NetBSD nb2 20110806"?  The latest release of NetBSD is
>>> 6.1.4; how does it relate to that?
>>
>> $ uname -a
>> NetBSD iceland 6.1_STABLE NetBSD 6.1_STABLE (SDF6.amd64) #0: Tue Nov 26 12:49:14 UTC 2013  root@bjork:/spare/netbsd/src/sys/arch/amd64/compile/SDF6.amd64 amd64
>
> Can you try running the code from my new GitHub project on your system?
>
> https://github.com/Keith-S-Thompson/crude_rand_test

Testing the low-order bits of the result of rand() from current implementation
0101010101010101010101010101010101010101010101010101010101010101
Low order bits alternate 0 and 1 (bad)

Testing the low-order bits of the result of rand() from ISO C sample implementation
0101010101010101010101010101010101010101010101010101010101010101
Low order bits alternate 0 and 1 (bad)

Testing the low-order bits of the result of rand() from NetBSD
0101010101010101010101010101010101010101010101010101010101010101
Low order bits alternate 0 and 1 (bad)

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

#43205

Ike Naar <ike@iceland.freeshell.org> writes:
> On 2014-04-20, Keith Thompson <kst-u@mib.org> wrote:
>> Ike Naar <ike@iceland.freeshell.org> writes:
[...]
>>> $ uname -a
>>> NetBSD iceland 6.1_STABLE NetBSD 6.1_STABLE (SDF6.amd64) #0: Tue Nov 26 12:49:14 UTC 2013  root@bjork:/spare/netbsd/src/sys/arch/amd64/compile/SDF6.amd64 amd64
>>
>> Can you try running the code from my new GitHub project on your system?
>>
>> https://github.com/Keith-S-Thompson/crude_rand_test
>
> Testing the low-order bits of the result of rand() from current implementation
> 0101010101010101010101010101010101010101010101010101010101010101
> Low order bits alternate 0 and 1 (bad)
>
> Testing the low-order bits of the result of rand() from ISO C sample implementation
> 0101010101010101010101010101010101010101010101010101010101010101
> Low order bits alternate 0 and 1 (bad)
>
> Testing the low-order bits of the result of rand() from NetBSD
> 0101010101010101010101010101010101010101010101010101010101010101
> Low order bits alternate 0 and 1 (bad)

Fascinating!

What size are int and long on that system?  (I might have to install
NetBSD in a virtual machine and try this myself.)

-- 
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]

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

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

csiph-web