It is currently Fri Apr 28, 2017 10:57 am

All times are UTC - 5 hours




 Page 1 of 1 [ 6 posts ] 
Author Message
 Post subject: C++ VMK 16 - Random Numbers
PostPosted: Mon Jul 13, 2009 6:46 am 
Site Admin

Joined: Sun Feb 11, 2007 8:59 am
Posts: 1094
Location: Ontario Canada
In this video I describe how random numbers work in C++. How you can create a range of random numbers, and also what things you should look out for if you truly want a set of random numbers.

I forgot to mention in the video, when I'm using Excel to copy the formula down to all 30,000 cells, I select the first cell that contains my formula (B1 + 1) and I drag a selection down to the last row. Then I press Ctrl+D to copy the formula down.

For random floating point numbers, check out Ghost Toast VMK 22


Offline
 Profile  
 
 Post subject:
PostPosted: Mon Jul 27, 2009 6:47 am 

Joined: Sun Dec 02, 2007 3:24 am
Posts: 13
Location: Galati
Hello ... Can you explain the formula by which you generated random numbers in the video ? I understand that if I use it I will get an even distribution of random numbers.However , I don't quite understand how it works.

Thanks in advance.

BTW ... The VMKs are awesome !!!


Offline
 Profile  
 
 Post subject:
PostPosted: Mon Jul 27, 2009 7:49 pm 
Site Admin

Joined: Sun Feb 11, 2007 8:59 am
Posts: 1094
Location: Ontario Canada
Okay, lets start with the rand() function.

This function returns a number between 0 and RAND_MAX. If you want a smaller range then you'll want to specify a lower (iMin) and upper (iMax) limit.

[A] If you take rand() and divide it by (RAND_MAX + 1) then you'll get a number from 0 to 1 (but not including 1).

[B] Now lets take a look at (iMax - iMin + 1) This gives you the difference between the desired range +1. So if you want a number between 15 and 18 this would work out to 18 - 15 + 1 = 4. This is exactly how many numbers there are that you are randomizing between (15,16,17,18 that's four numbers)

If we multiply [B] by [A] we are generating a random number between 0 and 4 (but not including 4).

The final step is to add iMin to the mix which gives you a number between {iMin + 0} and {iMin + 3.999999} and for our example that works out to a number between 15 and 18.999999.

Now since we are returning an integer (not a floating point number) then all the decimal points get truncated leaving us with either 15, 16, 17 or 18!

Have a look at the Ghost Toast VMK 22 for some additional information.


Offline
 Profile  
 
 Post subject: A few more details about rand()
PostPosted: Mon Jul 27, 2009 10:28 pm 

Joined: Wed Aug 06, 2008 7:53 pm
Posts: 182
Location: Russia
A few more details.

Let’s look inside srand() and rand():

/* Seeds the random number generator with the int given. */
void __cdecl srand (
        unsigned int seed
        )
{
        _getptd()->_holdrand = (unsigned long)seed;
}

/* Returns a pseudo-random number 0 through 32767. */
int __cdecl rand (
        void
        )
{
        _ptiddata ptd = _getptd();

        return( ((ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L) >> 16) & 0x7fff );
}


What should be noticed is that seed is unsigned integer (32 bits), but resulting random value is in only 15 lowest bits (the upper 17 bits are truncated). Additionally, when another random number is generated, it is stored in 'seed' variable to be used for next generation.
The explanation of this algo and much more information about random numbers can be found in fabulous Knuth’s "The Art of Computer Programming", Volume 2, pp. 9 - 177.

As one can see srand() and rand() are thread safe, since per-thread storage is used (a set of variables unique for each thread).
But beware! Giving the same seed per thread we will get the same pseudorandom sequence!

Proof code:
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <conio.h>
#include <process.h>

#ifdef _WIN32
#define WIN32_LEAN_AND_MEAN
#include <windows.h>
#endif

const UINT THREADS_NUMBER = 4;
const UINT THREADS_DATA = 8;
static volatile SHORT g_data[THREADS_NUMBER][THREADS_DATA];
static volatile DWORD g_seed = 0;

void random_thread( void * id )
{
    ::srand( g_seed );
    const UINT ID = UINT( id );
    for ( int i = 0; i < THREADS_DATA; ++i )
        g_data[ID][i] = ::rand();
}

int _tmain(int argc, _TCHAR* argv[])
{
    g_seed = ::GetTickCount();

    HANDLE h[THREADS_NUMBER];

    for ( int n = 0; n < THREADS_NUMBER; ++n )
    {
        h[n] = (HANDLE)::_beginthread( random_thread, 0, (void*)n );
    }

    ::WaitForMultipleObjects( THREADS_NUMBER, h, TRUE, 10000 );

    for ( int n = 0; n < THREADS_NUMBER; ++n )
    {
        _tprintf( _T("Thread #%02d = { "), n );
        for ( int i = 0; i < THREADS_DATA; ++i )
            _tprintf( _T("%d "), g_data[n][i] );
        _tprintf( _T("};") _T("\n") );
    }

    _getch(); // press any key...
    return 0;
}


Other sources of random numbers:

Windows / VC:
rand_s(), RtlGenRandom(), CryptGenRandom()

Platform independent:
Boost Random Number Library
http://www.boost.org/doc/libs/1_39_0/li ... index.html



PS. At last I have found the explanation ( thanks to this video and its creator ;) ) why the application of modulo operator (%) to the rand() is usually a bad solution (from time to time I had met the warning but was not aware of the reason).
BTW, the ‘width’ of the ‘skewed bar’ is obviously proportional to the residue r of division or exactly to the r = (RAND_MAX % range). In the video value = 30000, thus residue = 2767. This could be clearly seen on the histogram. (My conjecture is that the average height of the ‘skewed bar’ is proportional to the quotient of integer division q = (RAND_MAX / range), e.g. (q+1) : (q) ).



_________________
«Computer scientists deal with algorithms that you may call practical in theory but unpractical in practice.» © Timothy Gowers
Offline
 Profile  
 
 Post subject:
PostPosted: Tue Jul 28, 2009 1:46 am 

Joined: Sun Dec 02, 2007 3:24 am
Posts: 13
Location: Galati
Thank you for your explanations . I get it now .


Offline
 Profile  
 
 Post subject: 32-bit integer overflow problem
PostPosted: Thu Jul 30, 2009 3:16 am 

Joined: Wed Aug 06, 2008 7:53 pm
Posts: 182
Location: Russia
Another note about refined formula for RN:

left_bound + ( ( right_bound – left_bound + 1 ) * rand() ) / ( RAND_MAX + 1 ) ;


You may get unpleasant silent 32-bit integer overflow if the range ( right_bound + left_bound ) > 131072 (= 2^17).

There are several ways to overcome this problem.

1) use assertion just to be informed in DEBUG mode about range problem, e.g.

int random_number( int left_bound, int right_bound )
{
    const int range = right_bound - left_bound + 1;
   
    _ASSERTE( range <= RAND_MAX );
 
    return left_bound + ( range * rand() ) / ( RAND_MAX + 1 ) ;
}


2) exploit ‘__int64
int random_number( int left_bound, int right_bound )
{
    const __int64 range = right_bound - left_bound + 1;
   
    return int( left_bound + ( range * rand() ) / ( RAND_MAX + 1 ) );
}


3) exploit ‘double
int random_number( int left_bound, int right_bound )
{
    const double range = right_bound - left_bound + 1;
   
    return int( left_bound + ( range * rand() ) / ( RAND_MAX + 1 ) );
}


The conversions integer-to-float and float-to-integer used to be slow on old FPU x87. The situation has changed dramatically since introduction SSE on Intel Pentium (III).

Anyway, this formula is still not recommended if the range between min (left bound) and max (right bound) is greater than RAND_MAX (32767), because rand() can not generate more that 32768 different values and in the range greater than RAND_MAX there will be “dead numbers” – values you wont be given (by this function) in eternity.


Offline
 Profile  
 
Display posts from previous:  Sort by  
 Page 1 of 1 [ 6 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Jump to:  

cron