Random bug -- or bug in 'randomize'?

[Cyril]

When I have upgraded my newlisp installation from version 9.3.12 to 9.3.14 and then 9.3.15 (I have skipped 9.3.13), the following script began to crash randomly:

Code Select Expand

(setq input (read-file (main-args 2)))
(setq markup "<p><em>... %s ...</em>")
(rand 0)

(setq cookies (clean empty? (parse input "rn")))
(setq cookies (0 (+ 4 (rand 7)) (randomize cookies)))
(setq cookies (map (curry format markup) cookies))

(exec "winclip -c -w" (join cookies "rn" true))
(exit)

Unfortunately I have failed to make this behavior reproducable: it just crashes (with standard windows crash window) maybe one time out of twenty or so. Then I have downgraded back to 9.3.12 and observed no problems in a three full days for the moment of writing. Because 9.3.14 has featured "improved randomize", I suspect that some problem is located there.

[Lutz]

I ran extended tests on randomize but have not been able to reproduce a problem.



Try to take away statements in your program, gradually simplifying it until you find the smallest version which can reproduce the problem on 9.3.14/15, without the "winclip -c -w" part and perhaps setting 'input' to some constant. This way I can try to reproduce the problem too.

[Cyril]

Try to take away statements in your program, gradually simplifying it until you find the smallest version which can reproduce the problem on 9.3.14/15, without the "winclip -c -w" part and perhaps setting 'input' to some constant. This way I can try to reproduce the problem too.

I have looked into your C source instead, and seems like I have found a bug. In fact, two bugs. You treat RAND_MAX constant as exclusive, while in C standard library it is inclusive. C 'rand' function can yield RAND_MAX, and sometimes does it. This is hard to notice when your RAND_MAX is 2147483647, but easy when it is 32767 as in MinGW. See this:

Code Select Expand

RANDOMIZE:
for(i = 0; i < (length - 1); i++)
{
scale = length - i;
j = i + getRandom(0.0, scale, DIST_RANDOM);
cell = vector[i];
vector[i] = vector[j];
vector[j] = cell;
}


, where appropriate part of getRandom is:

Code Select Expand

if(type == DIST_RANDOM)
{
randnum = random();
return(scale * randnum/MY_RAND_MAX + offset);
}


If random() yielded RAND_MAX, then getRandom will yield scale, j became equal to length, and the code tries to access "after the last" element of the vector. Length of my input is near 725, so chances to hit this are near 32768/725 = 45. My estimate "one out of twenty" was twice optimistic. ;-)



I've pushed into message size limit, to be continued...

[Cyril]

I've pushed into message size limit, to be continued...

BTW, the p_rand function has a similar problem. Look at the code:

Code Select Expand

rnum = ((scale * random())/(MY_RAND_MAX - 1));


If random yields RAND_MAX or RAND_MAX-1, then rnum became equal to (exclusive by specification) upper bound. Chances are one out of 16384. Proof:

Code Select Expand

> (rand 0)
true
> (dotimes (i 100000) (push (rand 1) qq -1))
0
> (length qq)
100000
> (filter (fn (x) (!= x 0)) qq)
(1 1 1 1 1 1 1)
>

I hope this can be fixed before 9.4 release.

[Lutz]

This is fixed in 9.4.0, thanks Cyril.



ps: fixed in 9.3.16