# Thread: Random function confusion

1. ## Random function confusion

Hello all,

I hope everybody is having a wonderful January day.

Ok, so I wrote this thread a few minutes ago, but for some reason my browser refreshed the page while I was writing it and I got logged out, so my thread was all gone. I apologize if I leave out specific details pertaining to my problem, but here goes round 2 for writing this thing.

I'm using a PIC18F4520 green board built by my school with MPLABX IDE v1.95 (C18 compiler). For a particular assignment (mission #1 if you read the comments in the code), we students are supposed to program the green board so that when RB0 (button) is pressed, a "random" LED (RC0, RC1, RC2, or RC3) is lit up. Upon releasing RB0, all LEDs are off.

When I run my code (see below) and press RB0, only RC0 lights up. When RB0 is released, the code works as it should and all LEDs are off.

I have attempted putting a watch on the variable num (which I set as the value returned from the rand function), pausing the debugger, and trying to step through the code with RB0 pressed and not pressed at different times. No matter what, the value of num is always 0. My perception of the way a random function works is that when it is called, literally a random number is generated within a certain range (in this case, [0, 32767]). My plan was to use if statements to divide up this range and see which section of the range the value of num ends up in. Depending on which section it fell into, a specific LED would light up. I understand I have some magic numbers involved in my if statements. Those are the sections of the range I was referring to.

One potential cause for this problem is the magic numbers themselves. I'm not sure if the if statements are seeing them as chars, ints, or longs, so they may be out of scope for the conditional statements. I don't think this is the problem though because the num variable always has a value of 0. It's as though the rand function isn't even working (or, that it's not working the way I think it'd work).

One stipulation for this assignment, we are not supposed to use the srand() function and I don't think we are supposed to include <timers.h>. I have done some research before this and seen people using the srand() function and <timers.h>, but no examples of code that doesn't use either of those. Another thing I've noticed that commonly occurs with this random function, the value returned from the random function is almost always manipulated with the % operator. I understand this returns the remainder of a simple division, but I don't understand why its effect on the value returned by the rand function is so important. I would sincerely appreciate any advice or explanations as to what I've missed in my code. Thank you in advance for your help.

Code:
```/********************************************************************
* FileName:        LEDs following buttons example.c
* Compiler:        MPLAB C18 v.3.06
*
* This program monitors Button RB0 (ie Port B bit 0)
*   when it is pressed LED RC1 comes on.
*
*   #1 - Make RB0 turn on a random LED from RC3 to RC0
*   #2 - Make RB1 turn on RC0 on the first press, then RC1 on
*        next press, RC2 on the next, RC3 next, then RC0, . . .
*
* Author               Date        Comment
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
//

/** Processor Header Files *****************************************/
#include <p18f4520.h>
#include <stdlib.h>

/** Define Constants Here ******************************************/
#define PRESSED 0
#define UNPRESSED 1
char recentButtonState = UNPRESSED;
volatile int num;

/** Local Function Prototypes **************************************/
int rand(void);

// ============================================================
// Configuration Bits
// ============================================================
#pragma config OSC = INTIO67
#pragma config WDT = OFF
#pragma config LVP = OFF
#pragma config BOREN = OFF
#pragma config XINST = OFF
/** Declarations *************************************************/

/*****************************************************************
* Function:        void main(void)
*
******************************************************************/
#pragma code
void main(void) {
ADCON1 = 0x0F; // Make sure the pins are digital
TRISBbits.TRISB0 = 1; // Makes RB0 an input
TRISC = 0b11110000; // Makes Port C bits RC0-RC3 output
PORTC = 0x00; // Start with all of the lights off
while (1) {
num = rand();

if ((PORTBbits.RB0 == PRESSED) && (recentButtonState == UNPRESSED)) {
recentButtonState = PRESSED;
}
else if ((PORTBbits.RB0 == PRESSED) && (recentButtonState == PRESSED)) {
}
else {
recentButtonState = UNPRESSED;
}

if ((PORTBbits.RB0 == 0) && (num >= 0) && (num <= 8191)) {
PORTCbits.RC0 = 1;
}
else if ((PORTBbits.RB0 == 0) && (num > 8191) && (num <= 16382)) {
PORTCbits.RC1 = 1;
}
else if ((PORTBbits.RB0 == 0) && (num > 16382) && (num <= 24573)) {
PORTCbits.RC2 = 1;
}
else if ((PORTBbits.RB0 == 0) && (num > 24573) && (num <= 32767)) {
PORTCbits.RC3 = 1;
}
else {
PORTCbits.RC0 = 0, PORTCbits.RC1 = 0, PORTCbits.RC2 = 0, PORTCbits.RC3 = 0;
}
}
}
/*****************************************************************
* Function:        int rand(void)
*
******************************************************************/
int rand(void) {
}```

2. The "rand()" function is included in <stdlib.h>, so you don't need to declare it yourself. I suspect your empty version of the function is overriding the implementation in stdlib.

Try commenting out lines 28 (function prototype), 85 and 86 (function definition) and see if you start getting values.

You can find information on this function on page 124 (actual) of the C18 compiler library document: http://ww1.microchip.com/downloads/e...ies_51297f.pdf

3. A few more notes:

One stipulation for this assignment, we are not supposed to use the srand() function and I don't think we are supposed to include <timers.h>. I have done some research before this and seen people using the srand() function and <timers.h>, but no examples of code that doesn't use either of those. Another thing I've noticed that commonly occurs with this random function, the value returned from the random function is almost always manipulated with the % operator. I understand this returns the remainder of a simple division, but I don't understand why its effect on the value returned by the rand function is so important. I would sincerely appreciate any advice or explanations as to what I've missed in my code. Thank you in advance for your help.
The "srand()" function seeds the random number generator. By not including this (or seeding with a fixed value), you're ensuring the same numbers will come up predictably to each call of "rand()". To someone reviewing the code (e.g. a professor), such predictability would make checking the results of the program easier.

'%' is used when you want to constrain the results within certain boundaries. For instance, if you want a number from one to six, you would do something like:

Code:
`x = rand() % 6 + 1;   // rand()%6 gives you a number in the range of 0 - 5, so the +1 makes it 1 - 6`
If you want a number between "min" and "max", you would use something like:

Code:
`x = rand() % (max - min) + min;`
These are simplistic approaches to pseudo-random number generation, and has its issues (such as no guarantee of an even distribution of results), but should be sufficient for learning the general concept.

4. Thank you very much for solving my problem, the num variable now has a different value each time I pause the debugger. It makes sense that my code didn't work because I was essentially redefining the rand function to do absolutely nothing. Now I need to work on my button press if statements, because all LEDs light up instead of just one. I shouldn't need help with this, but figured I'd mention for anyone looking for code like this that the program still needs further adjustment to work properly. Thank you again! (:

5. >> int rand(void) ...
You are calling your empty version of rand() instead of the one provided in <stdlib.h>

>> One stipulation for this assignment, we are not supposed to use the srand() function
That is strange. Just know that rand() will return the same sequence of numbers on every run (according to the manual).

>> ... the value returned ... is almost always manipulated with the % operator. ... [what is] its effect on the value(s?) returned by the rand function ... so important.
It's an attempt map the values returned by rand() to a smaller domain. Let's say we only wanted 4 possible outcomes, then we could divide by 5 and get the remainder. The remainder will always be a value between 0 and 4.

That and other methods are not the best way to map to a smaller domain while maintaining a uniform distribution. This is the best known method for an int within [0, RAND_MAX]:
Code:
```// return a random integer in the range [0, n)
int nrand(int n)
{
if (n <= 0 || n > RAND_MAX)
return -1; // C++: throw domain_error("Argument to nrand is out of range");

const int bucket_size = RAND_MAX / n;
int r;

do r = rand() / bucket_size;
while (r >= n);

return r;
}```
Full disclosure - nrand() is from "Accelerated C++".
Accelerated C++: Practical Programming by Example: Andrew Koenig, Barbara E. Moo: 0785342703535: Amazon.com: Books

gg

6. You're welcome. And for the record, as far as first posts go, yours was a pleasure to read. Clear descriptions of the assignment and the problem, along with well-formatted code in code tags. That doesn't happen around here as often as it should. Happy programming!

7. I try to be as clear and concise as possible when I ask questions. It doesn't help me or the person(s) trying to assist me if I fail to communicate effectively.

I fixed the code to work properly. With the explanations involving the % operator, I used it to reduce my domain to be from 0-3 (4 different possible values that num could be, and they are all 8 bit length so I don't have to worry about values being out of scope!). The completed mission #1 is below. Thank you everybody for helping out! I hope other people find this thread useful.

Code:
```/********************************************************************
* FileName:        LEDs following buttons example.c
* Compiler:        MPLAB C18 v.3.06
*
* This program monitors Button RB0 (ie Port B bit 0)
*   when it is pressed LED RC1 comes on.
*
*   #1 - Make RB0 turn on a random LED from RC3 to RC0
*   #2 - Make RB1 turn on RC0 on the first press, then RC1 on
*        next press, RC2 on the next, RC3 next, then RC0, . . .
*
* Author               Date        Comment
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
//

/** Processor Header Files *****************************************/
#include <p18f4520.h>
#include <stdlib.h>
/** Define Constants Here ******************************************/
#define PRESSED 0
#define UNPRESSED 1
char recentButtonState = UNPRESSED;
volatile int num;
/** Local Function Prototypes **************************************/
// ============================================================
// Configuration Bits
// ============================================================
#pragma config OSC = INTIO67
#pragma config WDT = OFF
#pragma config LVP = OFF
#pragma config BOREN = OFF
#pragma config XINST = OFF
/** Declarations *************************************************/

/*****************************************************************
* Function:        void main(void)
*
******************************************************************/
#pragma code
void main(void) {
ADCON1 = 0x0F; // Make sure the pins are digital
TRISBbits.TRISB0 = 1; // Makes RB0 an input
TRISC = 0b11110000; // Makes Port C bits RC0-RC3 output
PORTC = 0x00; // Start with all of the lights off
while (1) {
num = rand()%5;
if ((PORTBbits.RB0 == PRESSED) && (recentButtonState == UNPRESSED)) {
if ((PORTBbits.RB0 == 0) && (num == 0)) {
PORTCbits.RC0 = 1;
} else if ((PORTBbits.RB0 == 0) && (num == 1)) {
PORTCbits.RC1 = 1;
} else if ((PORTBbits.RB0 == 0) && (num == 2)) {
PORTCbits.RC2 = 1;
} else if ((PORTBbits.RB0 == 0) && (num == 3)) {
PORTCbits.RC3 = 1;
} else {
PORTCbits.RC0 = 0, PORTCbits.RC1 = 0, PORTCbits.RC2 = 0, PORTCbits.RC3 = 0;
}
recentButtonState = PRESSED;
} else if ((PORTBbits.RB0 == PRESSED) && (recentButtonState == PRESSED)) {
} else {
PORTCbits.RC0 = 0, PORTCbits.RC1 = 0, PORTCbits.RC2 = 0, PORTCbits.RC3 = 0;
recentButtonState = UNPRESSED;
}
}
}```

8. I would move the rand() call inside the first 'if' - otherwise you'll be blowing through random numbers at CPU speed

Also consider removing duplicate logic for better readability:
Code:
```if ((PORTBbits.RB0 == PRESSED) && (recentButtonState == UNPRESSED)) {
switch (rand()%5) {
case 0:
PORTCbits.RC0 = 1;
break;
case 1:
PORTCbits.RC1 = 1;
break;
case 2:
PORTCbits.RC2 = 1;
break;
case 3:
PORTCbits.RC3 = 1;
break;
}
recentButtonState = PRESSED;
} else if ((PORTBbits.RB0 == PRESSED) && (recentButtonState == PRESSED)) {
} else {
PORTCbits.RC0 = 0, PORTCbits.RC1 = 0, PORTCbits.RC2 = 0, PORTCbits.RC3 = 0;
recentButtonState = UNPRESSED;
}```
gg

9. Full disclosure - nrand() is from "Accelerated C++".
O_o

The `randn' from "Accelerated C++" has a known bug, or at least "had" a known bug; I haven't checked for any errata to that book in a long time. Certainly, the variation you posted carries the bug.

I've updated the code. I didn't realize at first this was the C board. If anyone managed to try the original version, please apply the updated code before posting.
[/Edit]

Code:
```int nrand(int f)
{
if(f <= 1 || f >= RAND_MAX)
{
return(-1); /* throw domain_error(); */
}
else
{
int s = ((RAND_MAX - f + 1) / f + 1);
int r;
do {r = rand() / s;} while(r >= f);
return(r);
}
}```
I did type this in manually so this implementation may have some bug, but I did check the turn over the size of buckets so you can see the problem in any event.

Soma

*): I call this "my version", but the fix is to simple to imply that kind of creativity.

10. num = rand()%5; gives 0 to 4. So in one out of 5 cases none of the 'else' code (or Codeplug's cases) is executed.

11. Originally Posted by Codeplug
Also consider removing duplicate logic for better readability
Indeed, I realized it only minutes after posting those. I felt pretty dumb about it, but did remove them in my own code. Doesn't hurt to be too thorough (except maybe speed). (:

12. >> Certainly, the variation you posted carries the bug.
Nothing mentioned in the online errata, and I don't see any bugs (I'm no math wiz though). Excluding 1 does make sense however.

I ran some tests and most of the time both functions return identical distributions. I took a look at some of the sample sizes where they do differ (64 and 16384) and the distributions are very similar with no outliers.

gg

13. Found nrand() bug here: https://groups.google.com/forum/#!to...ed/WubxFdSppKw

Koenig proposes: "const unsigned bucket_size = (unsigned(RAND_MAX)+1)/n;"

gg

14. I took a look at some of the sample sizes where they do differ (64 and 16384) and the distributions are very similar with no outliers.
O_o

You didn't test enough, or your tests are broken. The original version produces a more pronounced bias by reducing the bucket size for most random number generators.

Koenig proposes: "const unsigned bucket_size = (unsigned(RAND_MAX)+1)/n;"
Well then, Koenig is wrong to propose that.

I read the thread; Koenig specifically mentions that the simple "+1" version may overflow so while this post is still relevant, Koenig is clearly aware of the issues. I just now make you aware of the issues.
[/Edit]

Trust me, you should use my version for the sake of portability, or don't trust me; use my version anyway: the version I posted does not overflow.

*shrug*

Unfortunately, I lack the mathematics vocabulary to precisely define the situation so you'll have to forgive me for jumping into explanation by way of example.

With these examples I am sometimes implying integer division as in C and traditional division in other cases. I apologize for any confusion, but if any remains, feel free to ask.
[/Edit]

Consider an environment where int is 4 bits and both `RAND_MAX' and `INT_MAX' are 7 (The expectation matches many "real world" implementations in form if not values.):

The original `nrand' produces slightly biased buckets because `RAND_MAX' does not represent the number of possible values `rand' produces. The function `rand' is designed for [0, RAND_MAX]--inclusive for locales using other notation--which forces us to count the possibility of 0 as a return value. To simplify, the number of possible results from `rand' is `RAND_MAX + 1' not `RAND_MAX'.

By specifying a limit that should evenly divide the number of possible results, the full range of values should be at our disposal, but with the original, we "lose" some values--the reduced size of the bucket--to bias. You can easily see this in `1 = 7/4' which should actually be `1 = 8/4'. Even without being great at mathematics or pseudorandom properties, it is obvious that dividing `rand()' by 1 to split the range is different than using 2 to split the range into buckets.

Now, you might think that `RAND_MAX + 1' is correct, but you are wrong because `INT_MAX + 1' results in overflow--often `INT_MIN'. To limit the possibility of overflow, we must reduce the possible largest value without changing the value of the expression. The expression in the corrected form, `((RAND_MAX - f + 1) / f + 1)', accomplished this protection against overflow by a simple application of mathematics.

We know that `f' is positive, at least two, and less than `RAND_MAX' so we continue considering different chunks:

The expression `RAND_MAX - f + 1'--limiting `RAND_MAX - 2 + 1' and `RAND_MAX - (RAND_MAX - 1) + 1'--can not overflow `INT_MAX' even when `RAND_MAX' is `INT_MAX'.

By applying the distributive rules of division over `(RAND_MAX - f + 1) / f', we get `(RAND_MAX / f) - (f / f) + (1 / f)' and know that `f / f' is one--remember we exclude 0. We add one after the division in my form so we correct the adjustment--no change--by, essentially, subtracting one and then adding one.

With this in mind, we continue in seeing that `(RAND_MAX - f + 1) / f + 1' is the same as `(RAND_MAX + 1) / f' under our planned constraints.

So, the adjustments seen in my version produces the same value as what Koenig offered as a correction, which you like, with the added benefit that mine version doesn't overflow as Koenig notes the correction may overflow.
[/Edit]

Soma

15. >> You didn't test enough, or your tests are broken.
I looked at *all* bucket sizes where the algorithms differ. I did not find any outliers, but perhaps my RAND_MAX or sample size isn't large enough to produce any...

(forgive the C++ on the C forum...)
Code:
```#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

int nrand1(int f)
{
//     if (f <= 1 || f >= RAND_MAX)
//     {
//         return(-1); /* throw domain_error(); */
//     }

int s = ((RAND_MAX - f + 1) / f + 1);
int r;
do {r = rand() / s;} while(r >= f);
return(r);
}//nrand1

int nrand2(int n)
{
//     if (n <= 0 || n > RAND_MAX)
//         return -1; // C++: throw domain_error("Argument to nrand is out of range");

const int bucket_size = RAND_MAX / n;
int r;

do r = rand() / bucket_size;
while (r >= n);

return r;
}//nrand2

#include <vector>

bool test(const size_t bucket_sz)
{
static std::vector<int> samples1;
static std::vector<int> samples2;

samples1.resize(bucket_sz);
samples2.resize(bucket_sz);

memset(&samples1[0], 0, sizeof(int) * samples1.size());
memset(&samples2[0], 0, sizeof(int) * samples2.size());

// try to get 50,000 samples per bucket
const size_t n_samples = 50000;
size_t n, i;

srand(1);
for (i = 0; i < n_samples; ++i)
for (n = 0; n < bucket_sz; ++n)
++samples1[nrand1(bucket_sz)];

srand(1);
for (i = 0; i < n_samples; ++i)
for (n = 0; n < bucket_sz; ++n)
++samples2[nrand2(bucket_sz)];

if (samples1 != samples2)
{
int sum1 = 0;
for (n = 0; n < bucket_sz; ++n)
sum1 += samples1[n];

int sum2 = 0;
for (n = 0; n < bucket_sz; ++n)
sum2 += samples2[n];

double avg1 = (double)sum1 / samples1.size();
double avg2 = (double)sum2 / samples2.size();

double maxdiff = 0;
for (n = 0; n < bucket_sz; ++n)
{
double diff = abs(samples1[n] - samples2[n]);
if (diff > maxdiff)
maxdiff = diff;
}//for

printf("#buckets,avg1,avg2,max bucket diff\n");
printf("%u,%f,%f,%f\n\n", bucket_sz, avg1, avg2, maxdiff);

char filename[128];
sprintf(filename, "bucket_%u.csv", bucket_sz);

FILE *f = fopen(filename, "w");
if (!f)
{
fprintf(stderr, "Failed to open %s for writing\n", filename);
return true;
}//if

fprintf(f, "bucket, nrand1, nrand2, diff\n");
for (n = 0; n < bucket_sz; ++n)
fprintf(f, "%u,%d,%d,%d\n", n, samples1[n], samples2[n],
(int)abs(samples1[n] - samples2[n]));

fclose(f);
return true;
}//if

return false;
}//test

int main()
{
size_t bucket_sz;
#if 0
// this results in diffs at 4,8,16,32,etc..
for (bucket_sz = 2; bucket_sz < RAND_MAX; ++bucket_sz)
test(bucket_sz);
#else
// run test only where they differ
for (bucket_sz = 4; bucket_sz < RAND_MAX; bucket_sz *= 2)
test(bucket_sz);
#endif
return 0;
}//main```
>> The function `rand' is designed for [0, RAND_MAX]--inclusive
That's what I was missing originally - before Koenig's proposal.

>> as Koenig notes the correction may overflow.
Right, there is no guarantee that UINT_MAX > INT_MX - so it may overflow on some platform.

I'll take yours as the new "best known method for an int within [0, RAND_MAX)"

gg

Popular pages Recent additions