C
CBFalconer
copx said:
Reconsider MT. I find the code object module occupies
approximately 512 bytes. For most applications this is trivial.
It is available (as cokusmt) within the hashlib code on my page.
Reconsider MT. I find the code object module occupies
approximately 512 bytes. For most applications this is trivial.
It is available (as cokusmt) within the hashlib code on my page.
M
Morris Dovey
jacob said:
I doubt it, I wasn't, and yes I did.
It would have been more appropriate to have re-directed the OP to
n'est ce pas?
R
Richard Heathfield
jacob navia said:
So what? I set it to zero in mine. I see nothing in the documentation you
provided to suggest that srandom should not be called with a 0 argument.
It's not all that obvious, really. Since I wanted repeatable results whilst
testing, 0 was the obvious value to choose. If you think it "obvious" that
srandom should not be passed 0, I suggest that you make it refuse to
accept 0.
I certainly didn't choose the value 0 to expose a bug, if that's what you
mean. I had no idea that choosing that value would so dramatically break
your code.
Now that you have told me that you meant bitwise-AND rather than mod, and
that I shouldn't pass 0 to srandom, I have conducted a third test, and the
numbers look reasonable. I suggest you amend your documentation so that it
explains the limitations of your srandom function.
When I play word games, it's with a serious purpose. I don't criticise your
articles in bad faith. And I certainly don't hate you. So I'm afraid
you're completely wrong again.
So what? I set it to zero in mine. I see nothing in the documentation you
provided to suggest that srandom should not be called with a 0 argument.
It's not all that obvious, really. Since I wanted repeatable results whilst
testing, 0 was the obvious value to choose. If you think it "obvious" that
srandom should not be passed 0, I suggest that you make it refuse to
accept 0.
I certainly didn't choose the value 0 to expose a bug, if that's what you
mean. I had no idea that choosing that value would so dramatically break
your code.
Now that you have told me that you meant bitwise-AND rather than mod, and
that I shouldn't pass 0 to srandom, I have conducted a third test, and the
numbers look reasonable. I suggest you amend your documentation so that it
explains the limitations of your srandom function.
When I play word games, it's with a serious purpose. I don't criticise your
articles in bad faith. And I certainly don't hate you. So I'm afraid
you're completely wrong again.
D
David Tiktin
[code sample snipped]
I'm all for good enough ;-), but just for fun you might want to run
the output of your PRNG through the Diehard test suite.
http://en.wikipedia.org/wiki/Diehard_tests
It will give you a pretty good reading on how close "good enough" is
to good. There are some free implementations running around. Also,
the author of the Diehard tests, George Marsaglia, has published a
several free, fast PRNGs that pass the Dieheard tests. You might
want to take a look at those.
Dave
I'm all for good enough ;-), but just for fun you might want to run
the output of your PRNG through the Diehard test suite.
http://en.wikipedia.org/wiki/Diehard_tests
It will give you a pretty good reading on how close "good enough" is
to good. There are some free implementations running around. Also,
the author of the Diehard tests, George Marsaglia, has published a
several free, fast PRNGs that pass the Dieheard tests. You might
want to take a look at those.
Dave
B
Bartc
Richard Heathfield said:
[random number code]
You were reporting a bug and it's customary to provide enough info to
replicate the bug.
I also copied the code and spent some time trying to replicate the
behaviour, admittedly before reading the rest of the thread.
Unless the low 16 bits were always 1, how could truncating to the first 16
bits make them always 1? (I read mod 2^16-1, although sloppily written, as
taking the low word)
I think you were being a little mischievous in not mentioning the seed value
of zero earlier.
A version of this code I've seen elsewhere explicitly states, "Can't be
initialised with 0..." and chooses a different value. This is the real
problem with the code.
R
Richard Heathfield
Bartc said:
If I'd deliberately omitted that information, I'd agree. But it hadn't
occurred to me that it was even relevant - as I have already explained.
If I'd deliberately omitted that information, I'd agree. But it hadn't
occurred to me that it was even relevant - as I have already explained.
J
jacob navia
Bartc said:
This is the point.
1) He answers a perfectly valid question about a random number generator
with just a sarcastic answer where he laughs at the OP.
2) Trying to erase that bad impression, I hurry to post the code I use
for random numbers
3) He says that my code "Will produce always zero"
4) I compile (again) my code. It works. I send here my full
example. The initialized value is ONE.
5) He insists. And later he sends his code and "He doesn't realize
that he shouldn't initialize it to zero". He doesn't say that
in my example code it is initialized to ONE. He ignores that
6) It is this *hypocrisy* that I find disgusting.
I tried to help the OP. He could have pointed out "You should say that
zero is not a valid value". That would have been fair. But he isn't.
He is just a *pedant*!
J
jacob navia
Richard said:
Incredible!
You have READ this code and you did NOT find the bug?
But two days ago you said that you find bugs without even
reading the source!
That it is enough to READ the code (no debugger needed)
to find out the bugs?
And NOW with the FULL SOURCE code you aren't able
to find a simple BUG like that in a program less than 20 lines???
E
Eric Sosman
jacob said:
Let's note that the bug was right there in your source
for all to see. I saw it as soon as I read your post. How
much debugger time did you spend failing to find it?
R
Richard Heathfield
jacob navia said:
Go back and read it again. What I said was that I *have* found bugs without
even reading the source *on occasion*. I *also* said that usually this
cannot be done. Your continual attempts to set up strawmen (i.e. to extend
your opponents' positions beyond what they have actually claimed) do you
no credit whatsoever.
That is often the case, yes.
Your code, your bug, your problem. Had I been sufficiently motivated to
find the bug myself, I would have spent some time looking for it. Since I
didn't look for it, I didn't find it.
Go back and read it again. What I said was that I *have* found bugs without
even reading the source *on occasion*. I *also* said that usually this
cannot be done. Your continual attempts to set up strawmen (i.e. to extend
your opponents' positions beyond what they have actually claimed) do you
no credit whatsoever.
That is often the case, yes.
Your code, your bug, your problem. Had I been sufficiently motivated to
find the bug myself, I would have spent some time looking for it. Since I
didn't look for it, I didn't find it.
B
Ben Pfaff
copx said:
Here is a portable PRNG:
http://www.stanford.edu/~blp/writings/clc/random.html
I don't know whether it is fast enough for you, but it is fairly
fast.
R
Richard Tobin
[/QUOTE]
Yes, and for a sufficiently simple algorithm there is no creative
expression. If there's basically one natural way to implement an
algorithm, you can't copyright it. See for example the arguments in
the USL vs BSDI case.
That's absurd. Anyone taking a usenet article that made no mention
of patents as a definitive statement that there are none would be
out of their mind.
Furthermore, Jacob obviously believed there was no encumbrance,
since he used it in his own code.
In any case, the algorithm in question is a linear congruential
random number generator and the modulus it uses was first suggested
in 1969, see
http://www.research.ibm.com/journal/sj/082/ibmsj0802D.pdf
-- Richard
U
user923005
If you want to test your PRNG for uniformity, use the standard NIST
tests for that.
http://csrc.nist.gov/groups/ST/toolkit/rng/index.html
J
jacob navia
Eric said:
You are lyi^h^h^hmisrepresenting the truth!
1) I did initialize the seed to ONE.
2) I never called with zero.
S
santosh
Eric said:
Of course, I figured out the bug even before the code was posted. All it
took me was a few scribbles on an evenlope.
E
Eric Sosman
jacob said:
You have misunderstood me (again). To illustrate,
would you say the following code is or is not buggy?
/* Return the larger of two int arguments. */
int grog(int x, int y) {
return x < y ? x : y;
}
To my way of thinking, this is buggy code. It's perfectly
legal, strictly-conforming C, but it's buggy anyhow. Why
is it buggy? Because it does something different than what
it's advertised to do, that's why. What it does is well-
defined, all above-board, completely kosher -- but it doesn't
fulfill the contract.
Here's one possible fix:
/* Return the smaller of two int arguments. */
int grog(int x, int y) {
return x < y ? x : y;
}
You will notice that not one character of the compilable code
has changed, that the revised function does exactly the same
thing the original did -- except this version is no longer
bug-ridden. Why not? Because it now fulfills its contract.
So, back to your code. It begins
.... and does not actually behave as described. It will never
return zero. It will only return 2^31 - 1 if seeded with zero
or with 2^31 - 1, in which cases it will return nothing else
but 2^31 - 1 forevermore, a distinctly non-uniform distribution.
In short, your function is buggy because it does not live up
to its stated contract; it is buggy for the same reason as the
first version of grog(). And the fix is similar (and has been
pointed out to you before this, too).
Did you find the debugger helpful in solving this problem?
C
CBFalconer
Richard said:
And there has been an available thorough discussion of linear
congruential generators at least since the first issuance of
TAOCP. Somewhere around 1970 or so.
G
George Marsaglia
copx said:
/* initialize with any 32-bit seed x and any 32-bit y not 0 */
static unsigned long x=2282008, y=362436069;
#define sK ( x=69069*x+123, y^=y<<13, y^=y>>17, y^=y<<5, x+y )
/* example main() should generate 10^9 integers in ~5 seconds,
with final j=1105441147. Try it.
*/
#include <stdio.h>
int main()
{unsigned long i,j;
for(i=0;i<1000000000;i++) j=sK;
printf("%U\n",j);
}
------------------- C code ends ------------------------
Use of sK in any expression will produce a random 32-bit integer,
(unsigned), so that, for example, u=sK*2.328306437e-10 will
produce a uniform real u in the interval [0,1),
while I=sK*f will produce an integer I from 0 to n-1
if f=n*2.328306437e-10.
If float operations must be avoided, and you want a random integer
from 0 to n-1, you can mask off bits after invoking sK, so that enough
remain to provide your integer, rejecting those outside the range.
For example, a random integer k in 0<=k<12345 needs 14 bits,
so generate
k=(sK>>18);
and keep those for which k<12345.
The inline sK returns x+y. The congruential x=69069*x+123
is chosen because the multiplier is easy to remember and
produces a good lattice in studying "random numbers fall
mainly in the planes", the Marsaglia effect. (123 can be any odd integer).
The xorshift y^=y<<13, y^=y>>17, y^=y<<5,
uses shifts 13,17,5 from the 648 available in the article Xorshift RNGs,
http://www.jstatsoft.org/v08/i14/paper
Here, sK stands for simple KISS, one of a class I call KISS RNGs,
based on the principle: Keep It Simple, Stupid.
sK should provide around 200 million random integers per second,
period about 2^64 and pass all the tests in Diehard,
http://i.cs.hku.hk/~diehard/
Other KISS versions combine three simple methods to produce 32-bit integer
sequences with periods 2^125, 2^993, 2^5147, 2^12153 or 2^31311,
or a dKISS version produces double precision, IEEE754 standard,
uniform [0,1) reals using only + /- float operations,
period exceeding 2^1748.
Send requests if interested.
George Marsaglia
A
Anand Hariharan
Most Unices (at least those that have BSD in their lineage) include a
quartet of functions viz., initstate, setstate, random and srandom that
generate random numbers of *much* higher quality than rand and srand.
IIRC, gcc also provides these (if certain preprocessor flags are enabled),
so it must be available on a wide variety of platforms.
Not sure about the 16 bit requirement though. Should you research and
find out, please let me / the group know.
C
copx
George Marsaglia said:
Looks good! I would like to use that, but..
I have to admit, that I do not really understand this. (just a hobby coder
here, almost no experience with bit level data manipulation)
Could you show me how can I use sK (without any floating point math) to
create a function like the one I posted, I mean:
/*
* generate int between lb and ub (inclusive)
*/
int mrand(int lb, int ub)
{
....
}