Page 1 of 1
Random bug -- or bug in 'randomize'?
Posted: Sun Jun 15, 2008 11:18 pm
by 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 all
(setq input (read-file (main-args 2)))
(setq markup "<p><em>... %s ...</em>")
(rand 0)
(setq cookies (clean empty? (parse input "\r\n")))
(setq cookies (0 (+ 4 (rand 7)) (randomize cookies)))
(setq cookies (map (curry format markup) cookies))
(exec "winclip -c -w" (join cookies "\r\n" 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.
Posted: Mon Jun 16, 2008 12:22 am
by 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.
Posted: Mon Jun 16, 2008 2:20 am
by Cyril
Lutz wrote: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 all
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 all
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...
Posted: Mon Jun 16, 2008 2:22 am
by Cyril
Cyril wrote: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 all
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 all
> (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.
Posted: Mon Jun 16, 2008 8:13 am
by Lutz
This is fixed in 9.4.0, thanks Cyril.
ps: fixed in 9.3.16