[algogeeks] Re: Pbm with rand() function
Use Mersenne Twister to generate 32-bit integers and do something like
this:
long long x = MT.gen();
x = (x32) + MT.gen();
Don
On Feb 27, 5:58 pm, Prakash D cegprak...@gmail.com wrote:
i've another doubt. what to do when I need to generate a random long long?
On Mon, Feb 27, 2012 at 9:07 PM, Don dondod...@gmail.com wrote:
For instance, if RANDMAX= 32768, then
x = rand() % 2;
is twice as likely to result in the value 10,000 as the value 15,000.
This is because there are two output values from rand() which result
in x=1 (1 and 3), but only one output value from rand()
resulting in x=15000 (15000).
For any case where the statistical quality of the pseudo-random stream
is important, such as simulation, using the built-in rand() function
is not a good idea. Use a pseudo-random algorithm with much longer
period and better properties, such as Mersenne Twister.
But if you are using rand, it is usually recommended to use the high
order bits rather than the low order bits. Many implementations of
rand() have cycles in the low bits which are much shorter than the
period of the generator. He is one way to generate unbiased values of
quality as good as the generator can provide:
// Return pseudo-random integer in the range 0..n-1
int randRange(int n)
{
int result, div = RANDMAX / n;
do {
result = rand() / div;
} while(result = n);
return result;
}
Don
On Feb 26, 10:10 am, karthikeya s karthikeya.a...@gmail.com wrote:
RAND() func returns value between 1 to INTMAX, as we know. But when
smone tries to find out value between 1 to N he takes remainder of o/p
of RAND() with N and adds one..but isn't it wrong coz RAND() will
generate numbers with equal probability between 1 and INTMAX but
taking remainder can alter the prob. of generating numbers.
e.g.
INTMAX=50
N=30
RAND(50) gives numbers 1 to 30, then prob. will remain same but if it
gives numbers 31 to 50, they'll be mapped to the numbers 1 to 20,
which means probability of getting numbers 1 to 20 is more than the
probability for 21 to 30.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group
athttp://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Pbm with rand() function
For instance, if RANDMAX= 32768, then
x = rand() % 2;
is twice as likely to result in the value 10,000 as the value 15,000.
This is because there are two output values from rand() which result
in x=1 (1 and 3), but only one output value from rand()
resulting in x=15000 (15000).
For any case where the statistical quality of the pseudo-random stream
is important, such as simulation, using the built-in rand() function
is not a good idea. Use a pseudo-random algorithm with much longer
period and better properties, such as Mersenne Twister.
But if you are using rand, it is usually recommended to use the high
order bits rather than the low order bits. Many implementations of
rand() have cycles in the low bits which are much shorter than the
period of the generator. He is one way to generate unbiased values of
quality as good as the generator can provide:
// Return pseudo-random integer in the range 0..n-1
int randRange(int n)
{
int result, div = RANDMAX / n;
do {
result = rand() / div;
} while(result = n);
return result;
}
Don
On Feb 26, 10:10 am, karthikeya s karthikeya.a...@gmail.com wrote:
RAND() func returns value between 1 to INTMAX, as we know. But when
smone tries to find out value between 1 to N he takes remainder of o/p
of RAND() with N and adds one..but isn't it wrong coz RAND() will
generate numbers with equal probability between 1 and INTMAX but
taking remainder can alter the prob. of generating numbers.
e.g.
INTMAX=50
N=30
RAND(50) gives numbers 1 to 30, then prob. will remain same but if it
gives numbers 31 to 50, they'll be mapped to the numbers 1 to 20,
which means probability of getting numbers 1 to 20 is more than the
probability for 21 to 30.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Pbm with rand() function
i've another doubt. what to do when I need to generate a random long long?
On Mon, Feb 27, 2012 at 9:07 PM, Don dondod...@gmail.com wrote:
For instance, if RANDMAX= 32768, then
x = rand() % 2;
is twice as likely to result in the value 10,000 as the value 15,000.
This is because there are two output values from rand() which result
in x=1 (1 and 3), but only one output value from rand()
resulting in x=15000 (15000).
For any case where the statistical quality of the pseudo-random stream
is important, such as simulation, using the built-in rand() function
is not a good idea. Use a pseudo-random algorithm with much longer
period and better properties, such as Mersenne Twister.
But if you are using rand, it is usually recommended to use the high
order bits rather than the low order bits. Many implementations of
rand() have cycles in the low bits which are much shorter than the
period of the generator. He is one way to generate unbiased values of
quality as good as the generator can provide:
// Return pseudo-random integer in the range 0..n-1
int randRange(int n)
{
int result, div = RANDMAX / n;
do {
result = rand() / div;
} while(result = n);
return result;
}
Don
On Feb 26, 10:10 am, karthikeya s karthikeya.a...@gmail.com wrote:
RAND() func returns value between 1 to INTMAX, as we know. But when
smone tries to find out value between 1 to N he takes remainder of o/p
of RAND() with N and adds one..but isn't it wrong coz RAND() will
generate numbers with equal probability between 1 and INTMAX but
taking remainder can alter the prob. of generating numbers.
e.g.
INTMAX=50
N=30
RAND(50) gives numbers 1 to 30, then prob. will remain same but if it
gives numbers 31 to 50, they'll be mapped to the numbers 1 to 20,
which means probability of getting numbers 1 to 20 is more than the
probability for 21 to 30.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Pbm with rand() function
with equal probability
On Tue, Feb 28, 2012 at 5:28 AM, Prakash D cegprak...@gmail.com wrote:
i've another doubt. what to do when I need to generate a random long long?
On Mon, Feb 27, 2012 at 9:07 PM, Don dondod...@gmail.com wrote:
For instance, if RANDMAX= 32768, then
x = rand() % 2;
is twice as likely to result in the value 10,000 as the value 15,000.
This is because there are two output values from rand() which result
in x=1 (1 and 3), but only one output value from rand()
resulting in x=15000 (15000).
For any case where the statistical quality of the pseudo-random stream
is important, such as simulation, using the built-in rand() function
is not a good idea. Use a pseudo-random algorithm with much longer
period and better properties, such as Mersenne Twister.
But if you are using rand, it is usually recommended to use the high
order bits rather than the low order bits. Many implementations of
rand() have cycles in the low bits which are much shorter than the
period of the generator. He is one way to generate unbiased values of
quality as good as the generator can provide:
// Return pseudo-random integer in the range 0..n-1
int randRange(int n)
{
int result, div = RANDMAX / n;
do {
result = rand() / div;
} while(result = n);
return result;
}
Don
On Feb 26, 10:10 am, karthikeya s karthikeya.a...@gmail.com wrote:
RAND() func returns value between 1 to INTMAX, as we know. But when
smone tries to find out value between 1 to N he takes remainder of o/p
of RAND() with N and adds one..but isn't it wrong coz RAND() will
generate numbers with equal probability between 1 and INTMAX but
taking remainder can alter the prob. of generating numbers.
e.g.
INTMAX=50
N=30
RAND(50) gives numbers 1 to 30, then prob. will remain same but if it
gives numbers 31 to 50, they'll be mapped to the numbers 1 to 20,
which means probability of getting numbers 1 to 20 is more than the
probability for 21 to 30.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Pbm with rand() function
@Karthikeya: Doesn't rand() actually return numbers in the range 0 to
RANDMAX? Proceeding as if that is the case:
If N is much smaller than RANDMAX, the process probably works well
enough for most applications, but if you want numbers as good as the
numbers rand() generates, do the following:
int random(int N)
{
int m = (RANDMAX / N) * N
while(1)
{
k = rand();
if( k m ) break;
}
return k % N + 1;
}
This rejects the values of rand() that would skew the result. In your
example, m = 30, so if rand() generates a number greater than or equal
to 30, rand() is called again. The loop terminates with probability 1
if rand() truly generates uniformly distributed numbers between 0 and
RANDMAX. The average number of calls is
ceiling((double)RANDMAX / (double)((int)(RANDMAX/N)*N)),
so in your example, it would be 50/30 = 5/3.
Dave
On Feb 26, 10:10 am, karthikeya s karthikeya.a...@gmail.com wrote:
RAND() func returns value between 1 to INTMAX, as we know. But when
smone tries to find out value between 1 to N he takes remainder of o/p
of RAND() with N and adds one..but isn't it wrong coz RAND() will
generate numbers with equal probability between 1 and INTMAX but
taking remainder can alter the prob. of generating numbers.
e.g.
INTMAX=50
N=30
RAND(50) gives numbers 1 to 30, then prob. will remain same but if it
gives numbers 31 to 50, they'll be mapped to the numbers 1 to 20,
which means probability of getting numbers 1 to 20 is more than the
probability for 21 to 30.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Pbm with rand() function
int m = (RANDMAX / N) * N isn't m= RANDMAX simplyit couldn't understand the what is the logic here. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Pbm with rand() function
@Karthikeya: Integer division truncates. So m is the largest multiple of N that is less than or equal to RANDMAX. E.g., in your example, m = (50 / 30) * 30 = 1 * 30 = 30, since 50/30 truncates to 1. Dave On Feb 26, 12:33 pm, karthikeya s karthikeya.a...@gmail.com wrote: int m = (RANDMAX / N) * N isn't m= RANDMAX simplyit couldn't understand the what is the logic here. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Pbm with rand() function
oh my bad.really nice concept+1 dave. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Pbm with rand() function
@dave +1.. :) On Mon, Feb 27, 2012 at 10:55 AM, karthikeya s karthikeya.a...@gmail.comwrote: oh my bad.really nice concept+1 dave. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- AMRIT -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
