473,324 Members | 2,356 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,324 software developers and data experts.

Random number in a range - speed problem

Hi

A modulo operation is a common advise for generating random numbers within
limited range:

random()%r

I've profiled my program and found that % consumes about 30% cpu time.
Is there an another method?

I have two such expression: one has r < 10^5 and the second range can be up
to RAND_MAX. They will be calculated very often - I assume much more than
10^9 times.

Any better solutions?

Jul 25 '07 #1
4 2117
Mirek wrote:
Hi

A modulo operation is a common advise for generating random numbers within
limited range:

random()%r
It is bad advice (spelled thus, and non-count). Next time, check the
FAQ before posting. Both the use of the non-standard function random()
instead of the standard function rand() and the use of '%' to reduce the
range are bad ideas.
I've profiled my program and found that % consumes about 30% cpu time.
Is there an another method?
If that operation consumes 30% of your CPU time, then you must be doing
almost nothing in the rest of your code. This has the odor of a badly
written program whose author is searching for something to blame its
inefficiency on. I suspect your profiling to be flawed.
I have two such expression: one has r < 10^5 and the second range can be up
to RAND_MAX. They will be calculated very often - I assume much more than
10^9 times.

Any better solutions?
Since there is no reason from the standard to think that RAND_MAX >
100000, it may be that all of those '%' operations are a waste, anyway.
If you are computing a billion pseudo-random numbers, or a billion of
almost anything, that will consume some time. Why would you think
otherwise?

Jul 25 '07 #2
Mirek wrote:
A modulo operation is a common advise for generating random numbers within
limited range:

random()%r

I've profiled my program and found that % consumes about 30% cpu time.
Is there an another method?

I have two such expression: one has r < 10^5 and the second range can be up
to RAND_MAX. They will be calculated very often - I assume much more than
10^9 times.

Any better solutions?
Let r = 2^k

/me ducks
Jul 26 '07 #3
Mirek wrote:
A modulo operation is a common advise for generating random numbers within
limited range: random()%r
I've profiled my program and found that % consumes about 30% cpu time.
Is there an another method?

I have two such expression: one has r < 10^5 and the second range can be up
to RAND_MAX. They will be calculated very often - I assume much more than
10^9 times.

Any better solutions?
One can try a quick and dirty pseudo-random generator
found in Numerical Recipe in C...

If r is a number in the range [0..R[
then r/(R+1) is in the range [0..1[
and n*r/(R+1) is in the range [0..n[
and if (R+1) is a power of 2, say R+1=2**p
then (n*r)>>p is in the range [0..n[

For p==32,
one can first generate numbers r in the range [0..2**64[
with a series of the form r_k= r_{k-1} * A + B
(on unsigned long long integers),
and use the 32 hi-bits of r_k for r, leading to:
(n * (r_k >32 & 0xFFFFFFFFULL)) >32 & 0xFFFFFFFULL,
a formula without any modulo operator...

-----
#define ADD_TERM 0x14A37B71ULL
#define MUL_TERM 0x0004F273ULL
#define MASK 0xFFFFFFFFULL

typedef unsigned long long ULongLong;
typedef unsigned long ULong;
static ULongLong seed, term;

ULong alt_srand (ULong seedi) {
seed= ((ULongLong) seedi) << 32;
term= seed * MUL_TERM + ADD_TERM;
}

ULong alt_rand (ULong range) {
term= term * MUL_TERM + ADD_TERM;
return range * (term >32 & MASK) >32 & MASK;
}
-----

On my machine with, generating 10**9 numbers in the range [0..13[
using alt_rand(13) vs rand()%13
gives for different optimisation levels:

compiled with gcc -O2: 12.8 sec vs 34.8 sec -2.8 x faster.
compiled with gcc -O3: 4.4 sec vs 34.8 sec- 7.9 x faster.

How bad the generator behaves is another story...

--
regis

Jul 31 '07 #4
regis wrote:
#define ADD_TERM 0x14A37B71ULL
#define MUL_TERM 0x0004F273ULL
#define MASK 0xFFFFFFFFULL

typedef unsigned long long ULongLong;
typedef unsigned long ULong;
static ULongLong seed, term;

ULong alt_srand (ULong seedi) {
seed= ((ULongLong) seedi) << 32;
term= seed * MUL_TERM + ADD_TERM;
}

just make the function above return void...

ULong alt_rand (ULong range) {
term= term * MUL_TERM + ADD_TERM;
return range * (term >32 & MASK) >32 & MASK;
}
--
regis
Jul 31 '07 #5

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

29
by: Chris Dutrow | last post by:
I searched around on the net for a bit, couldn't find anything though. I would like to find some code for a function where I input A Range Of Integers For example: Function( 1, 100 ); And the...
8
by: Aaron | last post by:
I need some help writing this function the function returns a list of random non-duplicate integers in a string, 1 parameter indicating the maximum range. string randGen(int maxRange) ...
70
by: Ben Pfaff | last post by:
One issue that comes up fairly often around here is the poor quality of the pseudo-random number generators supplied with many C implementations. As a result, we have to recommend things like...
36
by: Michael B Allen | last post by:
Someone once posted the following macro on clc: #define randint(a,b) (a)+(((b)-(a)+1)*(float)rand()/RAND_MAX) Unfortunately it's flawed. If rand() returns RAND_MAX the result can be one larger...
3
by: JoelPJustice | last post by:
I am working through a VBA book by myself to help and try and improve my skills. However, the book does not give you solutions to certain problems. I have worked through this problem up until bullet...
22
by: gagan.singh.arora | last post by:
Hi there. I want to generate random numbers with a given probability, say 80% even and 20% odd. Is it possible to implement such an algorithm in C?
13
by: Peter Oliphant | last post by:
I would like to be able to create a random number generator that produces evenly distributed random numbers up to given number. For example, I would like to pick a random number less than 100000,...
7
by: bipi | last post by:
Dear all, I found function rand(), it can create random number but this function can not define the range of number which I want to get it, such as, I want to get random number in the range from...
20
by: Robbie Hatley | last post by:
I needed a quick program called "random" that gives a random positive integer from n1 to n2. For example, if I type "random 38, 43", I want the program to print a random member of the set {38,...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.