Request for source code review of simple Ising model

[Keith Thompson]

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.)

 

[Udyant Wig]

| I see you're still not casting the argument to isdigit(). That causes
| undefined behavior if plain char is signed and your string contains a
| character with a negative value (which probably represents a character
| greater than 127).| [...]

That correction managed to evade commission until now.

bool is_positive_integer (char *string)
{
char *sp;

for (sp = string; *sp != '\0'; sp++) {
if (!isdigit ((unsigned char)*sp)) {
return false;
}
}

return !is_all_zeroes (string);
}

 

[Udyant Wig]

| int count_ones (int32_t *lattice)
| {
| int count = 0;
| int int_count = minimum_multiple_32 (dimension * dimension);
| int32_t *ip = lattice, *end = ip + int_count;
| int field;
| int i = 0;
|
| while (ip < end) {
| for (field = *ip; field; field >>= 1) {
| if (i == dimension * dimension) {
| return count;
| }
| count += field & 1;
| i++;
| }
| ip++;
| }
|
| return count;
| }

int count_ones (int32_t *lattice)
{
int count = 0;
int int_count = minimum_multiple_32 (dimension * dimension);
int32_t *ip = lattice, *end = ip + int_count;
int32_t field; /* <-- type change */
int i = 0;

while (ip < end) {
for (field = *ip; field; field >>= 1) {
if (i == dimension * dimension) {
return count;
}
count += field & 1;
i++;
}
ip++;
}

return count;
}

 

[Ike Naar]

Fascinating!

What size are int and long on that system?

sizeof(int)=4, sizeof(long)=8

 

[Udyant Wig]

I ran Keith Thompson's crude_rand_test on my own computer (Debian
GNU/Linux 7.4 i686):


Testing the low-order bits of the result of rand() from current implementation
1011110011010110000010110001111000111010111101001010100100011101
64 samples, 30 zeros, 34 ones

Testing the low-order bits of the result of rand() from ISO C sample implementation
0101110101010010100000110100001000011000111010001001110101111111
64 samples, 33 zeros, 31 ones

Testing the low-order bits of the result of rand() from NetBSD
1110110101100101110001010101011110001010000010111110011011010111
64 samples, 28 zeros, 36 ones


Whereas if I run this program,

/* netbsd-rand.c begins */

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

#define netbsd_RAND_MAX 0x7fffffff

static unsigned long nbsd_next = 1;

/* From crude_rand_test */
int
netbsd_rand(void)
{
/* LINTED integer overflow */
return (int)((nbsd_next = nbsd_next * 1103515245 + 12345) % \
((unsigned long)netbsd_RAND_MAX + 1));
}

static u_long next = 1;

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


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

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


return 0;
}


/* netbsd-rand.c ends */

I get:

0101010101010101010101010101010101010101010101010101010101010101
0101010101010101010101010101010101010101010101010101010101010101


I do not know what is happening.

 

[Ike Naar]

Fascinating!

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

It looks like crude_rand_test.c has a bug:

static void analyze(char *name, int (*rand_func)(void)) {
printf("Testing the low-order bits of the result of rand() from %s\n", name);
int alternating = 1;
int ones = 0;
int previous;
int i;

for (i = 0; i < COUNT; i ++) {
const int low_order_bit = rand() & 1;

I think 'rand()' should be 'rand_func()'.

If this is fixed, the output becomes:

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
0011110100110011111000111011000100110110001110110010010001111110
64 samples, 29 zeros, 35 ones

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

 

[Udyant Wig]

| It looks like crude_rand_test.c has a bug:
|
| static void analyze(char *name, int (*rand_func)(void)) {
| printf("Testing the low-order bits of the result of rand() from %s\n", name);
| int alternating = 1;
| int ones = 0;
| int previous;
| int i;
|
| for (i = 0; i < COUNT; i ++) {
| const int low_order_bit = rand() & 1;
|
| I think 'rand()' should be 'rand_func()'.
|
| If this is fixed, the output becomes:
|
| 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
| 0011110100110011111000111011000100110110001110110010010001111110
| 64 samples, 29 zeros, 35 ones
|
| Testing the low-order bits of the result of rand() from NetBSD
| 0101010101010101010101010101010101010101010101010101010101010101
| Low order bits alternate 0 and 1 (bad)

Changing rand() to rand_func(), I get:

Testing the low-order bits of the result of rand() from current implementation
1011110011010110000010110001111000111010111101001010100100011101
64 samples, 30 zeros, 34 ones

Testing the low-order bits of the result of rand() from ISO C sample implementation
0011110100110011111000111011000100110110001110110010010001111110
64 samples, 29 zeros, 35 ones

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

 

[Keith Thompson]

It looks like crude_rand_test.c has a bug:

static void analyze(char *name, int (*rand_func)(void)) {
printf("Testing the low-order bits of the result of rand() from %s\n", name);
int alternating = 1;
int ones = 0;
int previous;
int i;

for (i = 0; i < COUNT; i ++) {
const int low_order_bit = rand() & 1;

I think 'rand()' should be 'rand_func()'.

Absolutely right. Thank you for finding that!

I've updated the program with that fix.

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

If this is fixed, the output becomes:

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
0011110100110011111000111011000100110110001110110010010001111110
64 samples, 29 zeros, 35 ones

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

Which is consistent with what I now get on my system.

Further experiment with the NetBSD algorithm shows that the low-order N
bits repeat with a cycle of 2**N, at least for N equal to 1, 2, 3, and 4.

Bottom line: NetBSD has a poor implementation of rand(), even poorer
than the sample implementation given in the ISO C standard. Which means
that if you're writing code that needs to be portable, you *still* need
to avoid depending on the low-order bits of the values returned by
rand(). (Of course if you want high-quality pseudo-random numbers, you
shouldn't use rand() at all.)

 

[Malcolm McLean]

On 04/19/2014 05:20 PM, glen herrmannsfeldt wrote:


A relatively tiny number, for any program involving serious number
crunching. It's a difference of 1/327, which is fairly large number for
certain purposes, and a completely negligible one for other purposes -
the key point is making sure you know which category your particular
case involves.

As you take the temperatue down slowly enough, an Ising model will always
settle in one ground state (all blue or all white) or the other. Without
doing the maths, which is largely beyond me, a slight bias to blue or
white will mean that it always settles in that state and never the other.