Channels ▼
RSS

Design

Algorithm Improvement through Performance Measurement: Part 5


Visualization

To visually confirm these results, several images were created (see Figures 1-9). 256x256 pixel images were used to represent the first 64K values of the array. Each 32-bit value was broken into bytes, where byte 0 was used as the x-coordinate and byte 1 was used as the y-coordinate, with a white pixel drawn at this coordinate. The image was initialized to black.

Figure 1: Images 1,2,3,4. 1-bit, 2-bit, 4-bit, and 5-bit using Windows rand(), respectively.

Figure 2: Image 5. 15-bit using Windows rand()

Figure 3: Images 6, 7, 8, 9. 1-bit, 2-bit, 4-bit, and 5-bit using ran2()

The Windows rand() function shows a low density of values in Image 1 and patterns in Images 2 through 4, whereas Image 5 (15-bits per call) appears more random, visually confirming issues displayed in Table 1. Images 6 through 9 show ran2() which appears random for 1-bit, 2-bit, 3 and 4-bits extracted per function call.

A Flaw

The implementation in Listing 1 has a subtle flaw. Functions ran0(), ran1(), and ran2() generate a random number between 0.0 (inclusive) and 1.0 (exclusive) [4]. This random number (0.0 to almost 1.0) is then multiplied by 65535, causing the value of 65535 (0xffff) to not be generated. Tables 1 through 4 show statistics for the following experiment. For 100 million random 16-bit values, a count of each possible value was gathered. Tables 1 through 4 show the minimum count value, the maximum count value, and the average count values. Not created column shows how many values had a count of zero; i.e., the random-number generator did not create that value. The left side of the tables shows the results for the flawed usage in Listing 1.

Table 2: ran0() flawed versus proper usage

Table 3: ran1() flawed versus proper usage

Table 4: ran2() flawed versus proper usage

Table 5: Windows C rand() usage

Table 6: Mersenne twister usage

From the left side of Tables 1 through 3 several trends can be seen. When extracting 13-bits or more per call, ran0(), ran1(), and ran(2) do not generate evenly distributed all possible 16-bit values, with one value (0xffff) not generated at all by ran1() and ran2(). Table 4 shows an issue with the Windows C rand() function, where 6-bits or fewer do not create a significant number of possible values, thus skewing the statistics significantly.

To work around this problem, I used the following code:


float f1 = ranX( &randState );              // 0.0 .. 1.0
float f2 = ranX( &randState );              // 0.0 .. 1.0
unsigned long tmp1   = (unsigned long)( ( 1 << 16 ) * f1 );
unsigned long tmp2   = (unsigned long)( ( 1 << 16 ) * f2 );
unsigned long result = ( tmp1 << 16 ) | tmp2;

This fix is not necessary for the Windows C rand() function, since it generates 15-bits per call, and not floating-point numbers. Also, the ((1 << 16) - 1) multiplier is not used. This fix is also not necessary for Mersenne twister implementation, since it does not return a floating-point value.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video