## digitalmars.D - get random number

- somebody <somebody_member pathlink.com> Nov 11 2005
- Niko Korhonen <niktheblak hotmail.com> Nov 11 2005
- Georg Wrede <georg.wrede nospam.org> Nov 11 2005
- James Dunne <james.jdunne gmail.com> Nov 11 2005
- BCS <BCS_member pathlink.com> Nov 11 2005
- Manfred Nowak <svv1999 hotmail.com> Nov 11 2005
- Manfred Nowak <svv1999 hotmail.com> Nov 11 2005
- BCS <BCS_member pathlink.com> Nov 11 2005
- Carlos Santander <csantander619 gmail.com> Nov 11 2005
- Manfred Nowak <svv1999 hotmail.com> Nov 11 2005
- Bruno Medeiros <daiphoenixNO SPAMlycos.com> Nov 12 2005
- Manfred Nowak <svv1999 hotmail.com> Nov 12 2005
- Carlos Santander <csantander619 gmail.com> Nov 12 2005
- Bruno Medeiros <daiphoenixNO SPAMlycos.com> Nov 14 2005
- Manfred Nowak <svv1999 hotmail.com> Nov 14 2005
- Bruno Medeiros <daiphoenixNO SPAMlycos.com> Nov 15 2005
- "Walter Bright" <newshound digitalmars.com> Nov 13 2005
- Bruno Medeiros <daiphoenixNO SPAMlycos.com> Nov 14 2005
- "Walter Bright" <newshound digitalmars.com> Nov 13 2005
- Oskar Linde <Oskar_member pathlink.com> Nov 14 2005
- Don Clugston <dac nospam.com.au> Nov 14 2005
- "Uwe Salomon" <post uwesalomon.de> Nov 14 2005
- Niko Korhonen <niktheblak hotmail.com> Nov 14 2005
- kris <fu bar.org> Nov 15 2005
- Georg Wrede <georg.wrede nospam.org> Nov 15 2005
- Don Clugston <dac nospam.com.au> Nov 15 2005
- Georg Wrede <georg.wrede nospam.org> Nov 15 2005
- "Kris" <fu bar.com> Nov 15 2005

how i can get random number on interval from 1 to 100?

Nov 11 2005

somebody wrote:how i can get random number on interval from 1 to 100?

This belongs to the D.learn newsgroup. However, the answer is that you can use the rand() function from package std.random. See http://www.digitalmars.com/d/phobos/std_random.html Here is some example code: import std.random; void main() { // Range 1-100 uint r = cast(uint)((rand() / cast(double)uint.max) * 99.0) + 1; } Modulo arithmetics would be simpler (uint r = rand() % 99 + 1), but the randomness aspect might suffer from that. -- Niko Korhonen SW Developer

Nov 11 2005

Niko Korhonen wrote:somebody wrote:how i can get random number on interval from 1 to 100?

This belongs to the D.learn newsgroup. However, the answer is that you can use the rand() function from package std.random. See http://www.digitalmars.com/d/phobos/std_random.html Here is some example code: import std.random; void main() { // Range 1-100 uint r = cast(uint)((rand() / cast(double)uint.max) * 99.0) + 1; } Modulo arithmetics would be simpler (uint r = rand() % 99 + 1), but the randomness aspect might suffer from that.

If this is the correct way, then this ought to be in Phobos!

Nov 11 2005

Georg Wrede wrote:Niko Korhonen wrote:somebody wrote:how i can get random number on interval from 1 to 100?

This belongs to the D.learn newsgroup. However, the answer is that you can use the rand() function from package std.random. See http://www.digitalmars.com/d/phobos/std_random.html Here is some example code: import std.random; void main() { // Range 1-100 uint r = cast(uint)((rand() / cast(double)uint.max) * 99.0) + 1; } Modulo arithmetics would be simpler (uint r = rand() % 99 + 1), but the randomness aspect might suffer from that.

If this is the correct way, then this ought to be in Phobos!

I think we should also go with an instantiable Randomizer class. It would not be a replacement for rand(), but a welcome addition. Pseudo-random number generators are powerful things, but are quite limiting when there is only one global number generator allowed.

Nov 11 2005

In article <dl2of0$10km$1 digitaldaemon.com>, James Dunne says...Niko Korhonen wrote:somebody wrote: Here is some example code: import std.random; void main() { // Range 1-100 uint r = cast(uint)((rand() / cast(double)uint.max) * 99.0) + 1; }

If this is the correct way, then this ought to be in Phobos!

how about a template?? import std.stdio; import std.random; template randRange(int min, int max) { int randRange(){return cast(int)((rand()/cast(double)uint.max)*(max-min)+min);} } void main() { int i; for(i=0; i<5; i++)writef("[1,10]\t", randRange!(1,10)(), \n); for(i=0; i<5; i++)writef("[-30,0]\t",randRange!(-30,0)(), \n); for(i=0; i<5; i++)writef("[8,10]\t", randRange!(8,10)(), \n); for(i=0; i<5; i++)writef("[0,15]\t", randRange!(0,15)(), \n); }

Nov 11 2005

Georg Wrede wrote: [...]If this is the correct way, then this ought to be in Phobos!

The question is: what is correct here ;-) -manfred

Nov 11 2005

Niko Korhonen wrote:how i can get random number on interval from 1 to 100?

Here is some example code:

The question is not specified enough to give any example. It is unknown whether the interval is left- or right-closed and from what underlying distribution the random numbers should be drawn. It is quite naive to assume a uniform distribution over the natural elements contained in the interval cited and that the closed interval is meant. This question looks very much like a question of a schoolchild that does not want to solve its homework by itself. -manfred

Nov 11 2005

In article <Xns970BEDBA5BC95svv1999hotmailcom 63.105.9.61>, Manfred Nowak says...Niko Korhonen wrote:how i can get random number on interval from 1 to 100?

Here is some example code:

The question is not specified enough to give any example. It is unknown whether the interval is left- or right-closed and from what underlying distribution the random numbers should be drawn. It is quite naive to assume a uniform distribution over the natural elements contained in the interval cited and that the closed interval is meant. This question looks very much like a question of a schoolchild that does not want to solve its homework by itself. -manfred

Or the answer of someone who has some idea what the $%# the person is asking for. We can assume they are referring to ints because otherwise they should have said so. After all that's what most compilers do. As to the distribution, a uniform distribution can be transformed into any distribution you want with a little work. All of the answers that were given are correct and reasonable.

Nov 11 2005

Niko Korhonen escribió:Here is some example code: import std.random; void main() { // Range 1-100 uint r = cast(uint)((rand() / cast(double)uint.max) * 99.0) + 1; } Modulo arithmetics would be simpler (uint r = rand() % 99 + 1), but the randomness aspect might suffer from that.

I'm not familiar with what you just said, so I have to ask: what are you talking about? What's the possible suffering? -- Carlos Santander Bernal

Nov 11 2005

Carlos Santander wrote: [...]What's the possible suffering?

Its because the underlying distribution changes dramatically ;-) -manfred

Nov 11 2005

Carlos Santander wrote:Niko Korhonen escribió:Here is some example code: import std.random; void main() { // Range 1-100 uint r = cast(uint)((rand() / cast(double)uint.max) * 99.0) + 1; } Modulo arithmetics would be simpler (uint r = rand() % 99 + 1), but the randomness aspect might suffer from that.

I'm not familiar with what you just said, so I have to ask: what are you talking about? What's the possible suffering?

I think it is because if you use modulo arithmetics, the numbers in the range from 0 to (uint.max % rangelength) occur 1 times more often that the numbers from (uint.max % rangelength + 1) to rangelength-1. For example lets suppose uint.max = 255 and rangelength = 100: 0-55 : There are 3 possible matches (example for 18: 18, 118, 218) 56-99 : There are 2 possible matches (example for 58: 58, 158) This has a very small impact for small ranges since uint.max is very big. -- Bruno Medeiros - CS/E student "Certain aspects of D are a pathway to many abilities some consider to be... unnatural."

Nov 12 2005

Bruno Medeiros wrote: [...]0-55 : There are 3 possible matches (example for 18: 18, 118, 218) 56-99 : There are 2 possible matches (example for 58: 58, 158)

Quite true, because you enumerate all the 256 cases, 56*3+44*2=256, you describe the distribution correctly. But now have a closer look on the computation with casting to double as suggested by the first answerer:uint r= cast(uint)((rand() / cast(double)uint.max) * 99.0) + 1;

The value of the subexpression `rand() / cast(double)uint.max' equals `1.0' at most once, because if `rand()' is not equal to `uint.max' the value of this subexpression is less than `1.0'. Therefore `100', the largest integer value form the given range, is drawn only once. Continuing your example with `uint.max==255' yields, that the remaining 255 cases of 2 respectiveley 3 possible matches occur 42 respectiveley 57 times, because 57*3+42*2=255. Whereas with the modulo computation one knows which numbers are preferred, in the example the numbers from the range [0..55], the numbers preferred ar unknown in case of casting to double: it depends on the rounding during the cast, which numbers are preferred. Is it even possible, that the rounding errors accumulate and that some numbers will even occur 4 times, whereas others only occur once? Who can prove, that this will not happen? In total: under the assumption, that `uint.max' is big enough the probability, that the `100' is drawn at random in the casting-to-double-suggestion is near to zero and the remaining numbers are drawn with nearly the same probability, which underlies a variation. Whereas with the modulo-suggestion all numbers are drawn with nearly the same probability with even less variation. Quite a difference, isn't it? -manfred

Nov 12 2005

Manfred Nowak escribió:Bruno Medeiros wrote: [...]0-55 : There are 3 possible matches (example for 18: 18, 118, 218) 56-99 : There are 2 possible matches (example for 58: 58, 158)

[...] Quite true, because you enumerate all the 256 cases, 56*3+44*2=256, you describe the distribution correctly. ... -manfred

Ok, I understand. Thanks. -- Carlos Santander Bernal

Nov 12 2005

Manfred Nowak wrote: ...uint r= cast(uint)((rand() / cast(double)uint.max) * 99.0) + 1;

The value of the subexpression `rand() / cast(double)uint.max' equals `1.0' at most once, because if `rand()' is not equal to `uint.max' the value of this subexpression is less than `1.0'. Therefore `100', the largest integer value form the given range, is drawn only once. Continuing your example with `uint.max==255' yields, that the remaining 255 cases of 2 respectiveley 3 possible matches occur 42 respectiveley 57 times, because 57*3+42*2=255. Whereas with the modulo computation one knows which numbers are preferred, in the example the numbers from the range [0..55], the numbers preferred ar unknown in case of casting to double: it depends on the rounding during the cast, which numbers are preferred. Is it even possible, that the rounding errors accumulate and that some numbers will even occur 4 times, whereas others only occur once? Who can prove, that this will not happen? In total: under the assumption, that `uint.max' is big enough the probability, that the `100' is drawn at random in the casting-to-double-suggestion is near to zero and the remaining numbers are drawn with nearly the same probability, which underlies a variation. Whereas with the modulo-suggestion all numbers are drawn with nearly the same probability with even less variation. Quite a difference, isn't it? -manfred

that *all* target numbers except the last one (0-98) would "occur" 3 times at least, meaning that the original random numbers would have to be at least 3*99 + 1 (near 300 basically, not just 255). This stuff reminds me of line to pixel rasterization algorithms :P -- Bruno Medeiros - CS/E student "Certain aspects of D are a pathway to many abilities some consider to be... unnatural."

Nov 14 2005

Bruno Medeiros wrote: [...]No, there are no numbers who "occur" 4 times, since that would imply that *all* target numbers except the last one (0-98) would "occur" 3 times at least, meaning that the original random numbers would have to be at least 3*99 + 1 (near 300 basically, not just 255).

I do not agree with this try of a proof. What I meant with my question is, that there might be three consecutive "buckets", that are drawn with the absolute values 232 if and only if there would not be any rounding erros resulting from the divison. If rounding errors occur, then one draw normally falling into the middle bucket might be actually drawn from the left bucket, resulting in the absolute values 322, which is no problem, but if the normal draw would be out of the right bucket but because of the rounding error is actually drawn from the middle bucket the absolute values are 241. Do you agree, that in all cases the total sum of draws does not change? -manfred

Nov 14 2005

Manfred Nowak wrote:Bruno Medeiros wrote: [...]No, there are no numbers who "occur" 4 times, since that would imply that *all* target numbers except the last one (0-98) would "occur" 3 times at least, meaning that the original random numbers would have to be at least 3*99 + 1 (near 300 basically, not just 255).

I do not agree with this try of a proof. What I meant with my question is, that there might be three consecutive "buckets", that are drawn with the absolute values 232 if and only if there would not be any rounding erros resulting from the divison. If rounding errors occur, then one draw normally falling into the middle bucket might be actually drawn from the left bucket, resulting in the absolute values 322, which is no problem, but if the normal draw would be out of the right bucket but because of the rounding error is actually drawn from the middle bucket the absolute values are 241.

"but if the normal draw would be out of the right bucket but because of the rounding error is actually drawn from the middle bucket the absolute values are 241." -> And I was telling why that doesn't happen. It's not a formal or detailed proof, I am aware, but I was hoping you would understand (or just believe..) that it was so, without having to explain in detail. :pDo you agree, that in all cases the total sum of draws does not change? -manfred

-- Bruno Medeiros - CS/E student "Certain aspects of D are a pathway to many abilities some consider to be... unnatural."

Nov 15 2005

"Bruno Medeiros" <daiphoenixNO SPAMlycos.com> wrote in message news:dl5306$30ec$1 digitaldaemon.com...I think it is because if you use modulo arithmetics, the numbers in the range from 0 to (uint.max % rangelength) occur 1 times more often that the numbers from (uint.max % rangelength + 1) to rangelength-1. For example lets suppose uint.max = 255 and rangelength = 100: 0-55 : There are 3 possible matches (example for 18: 18, 118, 218) 56-99 : There are 2 possible matches (example for 58: 58, 158) This has a very small impact for small ranges since uint.max is very big.

True, however, the floating point version has the same issue.

Nov 13 2005

Walter Bright wrote:"Bruno Medeiros" <daiphoenixNO SPAMlycos.com> wrote in message news:dl5306$30ec$1 digitaldaemon.com...I think it is because if you use modulo arithmetics, the numbers in the range from 0 to (uint.max % rangelength) occur 1 times more often that the numbers from (uint.max % rangelength + 1) to rangelength-1. For example lets suppose uint.max = 255 and rangelength = 100: 0-55 : There are 3 possible matches (example for 18: 18, 118, 218) 56-99 : There are 2 possible matches (example for 58: 58, 158) This has a very small impact for small ranges since uint.max is very big.

True, however, the floating point version has the same issue.

at least distributes the offness across the range. -- Bruno Medeiros - CS/E student "Certain aspects of D are a pathway to many abilities some consider to be... unnatural."

Nov 14 2005

"Niko Korhonen" <niktheblak hotmail.com> wrote in message news:dl1tpv$aam$1 digitaldaemon.com...import std.random; void main() { // Range 1-100 uint r = cast(uint)((rand() / cast(double)uint.max) * 99.0) + 1; } Modulo arithmetics would be simpler (uint r = rand() % 99 + 1), but the randomness aspect might suffer from that.

Using the integer arithmetic method is better (i.e. faster and simpler) and it does not suffer from randomness problems. And actually, it should be: (uint r = rand() % 100 + 1)

Nov 13 2005

In article <dl8f8c$cfj$1 digitaldaemon.com>, Walter Bright says..."Niko Korhonen" <niktheblak hotmail.com> wrote in message news:dl1tpv$aam$1 digitaldaemon.com...import std.random; void main() { // Range 1-100 uint r = cast(uint)((rand() / cast(double)uint.max) * 99.0) + 1; } Modulo arithmetics would be simpler (uint r = rand() % 99 + 1), but the randomness aspect might suffer from that.

Using the integer arithmetic method is better (i.e. faster and simpler) and it does not suffer from randomness problems.

I think Niko may be referring to the fact that some poor implementations of rand() suffer from having a lower degree of "randomness" in the less significant bits than in the more significant bits. Though, if you need a random number generator that is uniform and gives a high degree of "randomness", rand() is a very poor choice. Other generators, such as a Mersenne Twister, will perform better. /Oskar

Nov 14 2005

Oskar Linde wrote:In article <dl8f8c$cfj$1 digitaldaemon.com>, Walter Bright says..."Niko Korhonen" <niktheblak hotmail.com> wrote in message news:dl1tpv$aam$1 digitaldaemon.com...import std.random; void main() { // Range 1-100 uint r = cast(uint)((rand() / cast(double)uint.max) * 99.0) + 1; } Modulo arithmetics would be simpler (uint r = rand() % 99 + 1), but the randomness aspect might suffer from that.

Using the integer arithmetic method is better (i.e. faster and simpler) and it does not suffer from randomness problems.

I think Niko may be referring to the fact that some poor implementations of rand() suffer from having a lower degree of "randomness" in the less significant bits than in the more significant bits.

Yes, although I think those days are long gone.Though, if you need a random number generator that is uniform and gives a high degree of "randomness", rand() is a very poor choice. Other generators, such as a Mersenne Twister, will perform better. /Oskar

I find it a little disturbing that the docs for std.random don't give the name of the algorithm which is being used, or any information about its statistical properties. There's a useful listing of random generators at www.agner.org (though note that most of his code is GPL'ed), and another one in www.boost.org std.random could be greatly improved upon.

Nov 14 2005

std.random could be greatly improved upon.

You can find a GPL'd implementation of the Mersenne Twister in Indigo: http://www.uwesalomon.de/code/indigo Ciao uwe

Nov 14 2005

Oskar Linde wrote:I think Niko may be referring to the fact that some poor implementations of rand() suffer from having a lower degree of "randomness" in the less significant bits than in the more significant bits.

Yes, that's exactly it. I remember reading about it from a Donald Knuth textbook as well as some Java-related articles. Somehow it stuck to my mind. But by all means, when we're talking about D, I would prefer Walter's advice against mine :) -- Niko Korhonen SW Developer

Nov 14 2005

Niko Korhonen wrote:Oskar Linde wrote:I think Niko may be referring to the fact that some poor implementations of rand() suffer from having a lower degree of "randomness" in the less significant bits than in the more significant bits.

Yes, that's exactly it. I remember reading about it from a Donald Knuth textbook as well as some Java-related articles. Somehow it stuck to my mind. But by all means, when we're talking about D, I would prefer Walter's advice against mine :)

Here's a really great, and very fast, function. It's the one employed by Mango: KISS (via George Marsaglia & Paul Hsieh) the idea is to use simple, fast, individually promising generators to get a composite that will be fast, easy to code have a very long period and pass all the tests put to it. The three components of KISS are x(n)=a*x(n-1)+1 mod 2^32 y(n)=y(n-1)(I+L^13)(I+R^17)(I+L^5), z(n)=2*z(n-1)+z(n-2) +carry mod 2^32 The y's are a shift register sequence on 32bit binary vectors period 2^32-1; The z's are a simple multiply-with-carry sequence with period 2^63+2^32-1. The period of KISS is thus 2^32*(2^32-1)*(2^63+2^32-1) > 2^127 private static uint kiss_x = 1; private static uint kiss_y = 2; private static uint kiss_z = 4; private static uint kiss_w = 8; private static uint kiss_carry = 0; private static uint kiss_k; private static uint kiss_m; static final uint get () { kiss_x = kiss_x * 69069 + 1; kiss_y ^= kiss_y << 13; kiss_y ^= kiss_y >> 17; kiss_y ^= kiss_y << 5; kiss_k = (kiss_z >> 2)+(kiss_w >> 3)+(kiss_carry >> 2); kiss_m = kiss_w + kiss_w + kiss_z + kiss_carry; kiss_z = kiss_w; kiss_w = kiss_m; kiss_carry = kiss_k >> 30; return kiss_x + kiss_y + kiss_w; } I still use this on tiny 10MHz MCUs ~ code generators love the design. Just for jollies, I'll throw down a challenge that this is the best compromise in terms of period & execution time <g>

Nov 15 2005

kris wrote:Here's a really great, and very fast, function. It's the one employed by Mango: KISS (via George Marsaglia & Paul Hsieh) static final uint get () { kiss_x = kiss_x * 69069 + 1; kiss_y ^= kiss_y << 13; kiss_y ^= kiss_y >> 17; kiss_y ^= kiss_y << 5; kiss_k = (kiss_z >> 2)+(kiss_w >> 3)+(kiss_carry >> 2); kiss_m = kiss_w + kiss_w + kiss_z + kiss_carry; kiss_z = kiss_w; kiss_w = kiss_m; kiss_carry = kiss_k >> 30; return kiss_x + kiss_y + kiss_w; } I still use this on tiny 10MHz MCUs ~ code generators love the design. Just for jollies, I'll throw down a challenge that this is the best compromise in terms of period & execution time <g>

Had somebody shown that to me, at first sight I'd dissed it as a toy. But then the idea of having "a random generator" whose output is added to "less random, but long-period" things is intriguing. And the fact that there's no cross transport of information between these is kind of neat. At brief googling I didn't find any white papers or such about it. Any pointers? BTW, that 10MHz stuff souded interesting. May I ask what you do for a daytime job?

Nov 15 2005

Georg Wrede wrote:kris wrote:Here's a really great, and very fast, function. It's the one employed by Mango: KISS (via George Marsaglia & Paul Hsieh) static final uint get () { kiss_x = kiss_x * 69069 + 1; kiss_y ^= kiss_y << 13; kiss_y ^= kiss_y >> 17; kiss_y ^= kiss_y << 5; kiss_k = (kiss_z >> 2)+(kiss_w >> 3)+(kiss_carry >> 2); kiss_m = kiss_w + kiss_w + kiss_z + kiss_carry; kiss_z = kiss_w; kiss_w = kiss_m; kiss_carry = kiss_k >> 30; return kiss_x + kiss_y + kiss_w; } I still use this on tiny 10MHz MCUs ~ code generators love the design. Just for jollies, I'll throw down a challenge that this is the best compromise in terms of period & execution time <g>

Had somebody shown that to me, at first sight I'd dissed it as a toy. But then the idea of having "a random generator" whose output is added to "less random, but long-period" things is intriguing. And the fact that there's no cross transport of information between these is kind of neat. At brief googling I didn't find any white papers or such about it. Any pointers?

http://www.agner.org/random/ has some interesting articles and highly optimised asm code, and good links, including http://random.mat.sbg.ac.at/ At Agner's site I found that the low-bits-not-random issue is a property of lagged Fibonnacci generators.

Nov 15 2005

At brief googling I didn't find any white papers or such about it. Any pointers?

http://www.agner.org/random/ has some interesting articles and highly optimised asm code, and good links, including http://random.mat.sbg.ac.at/ At Agner's site I found that the low-bits-not-random issue is a property of lagged Fibonnacci generators.

Excellent links!

Nov 15 2005

"Georg Wrede" <georg.wrede nospam.org> wrote...At brief googling I didn't find any white papers or such about it. Any pointers?

Here: http://www.helsbreth.org/random/unbiased.htmlBTW, that 10MHz stuff souded interesting. May I ask what you do for a daytime job?

Sure ~ I work at PARC (would like to get D adopted here, but ...) However, the MCU was for this project: http://www.gizmag.com/go/3409/ http://www.techimo.com/articles/i231.html http://www.gopro.at/flash_jack_neu.htm The latter (slow) link has some fun, very 70's oriented, video shot by an Austrian reseller. It briefly shows some of the audio-driven animations (spectrum analysis, strange-attractors, genetic-algorithms, etc) in addition to the textual stuff. The device itself has 4K RAM + 56K ROM. Used this particular MCU since it has 32-bit registers ~ came in handy for real-time audio/mic feature-extraction, and fast bitblt ops. It's hooked up to to outside world via a BT-radio and a cell-phone (such as a Treo). Much of the ROM is filled with glyphs for the three fonts. The rest is populated with a kernel, bios, graphics engine, networking, audio analysis, a pseudo SVG compiler & animation engine, window-manager, widgets, pub/sub layer, etc; plus the various applications. A fun project.

Nov 15 2005