C++

Forum

 
 
NEGATIVE NUMBERS WITH RAND

phztfte1 (195)
Write your question here. Why am I getting negative numbers when using the rand function?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
  /* find
*

* Usage: find needle
*
* where needle is the value to find in a haystack of values
***************************************************************************/


#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <array>

using namespace std;

// maximum amount of hay
const int HAY_MAX = 65536;

int main(int argc, char *argv[])
{
		// ensure proper usage
	if (argc != 2)
	{
		printf("Usage: %s needle\n", argv[0]);
		return 1;
	}

	// remember needle
	int needle = atoi(argv[1]);

	// fill the haystack with random numbers
	int haystack[HAY_MAX];
	srand((unsigned)time(0));
	haystack[0] = NULL;
	
	for (int i = 1; i < 100; i++)
	{
		haystack[i] = rand() % 100 + 1;
	}

	sort(begin(haystack), end(haystack));

	for (int i = 1; i < 100; i++)
	{
		printf_s("Sort: %i\n", haystack[i]);
	}
}




Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Sort: -858993460
Press any key to continue . . .
Chervil (7320)
Your code puts random numbers into 99 elements of the array, but sorts all 65536 elements. The strange numbers are just initialised data. Try this:
 
 
sort(haystack, haystack + 100);


Alternatively, change this:
const int HAY_MAX = 100;
and use the defined constant in your for loops too:
for (int i = 0; i < HAY_MAX; i++)
Last edited on
coder777 (8439)
The reason is on line 43: You sort the whole array while you set only the first 100 elements. The rest remains uninitialized (and thus negative or whatever).

Try this:
sort(haystack, haystack + 100);
AbstractionAnon (6954)
 
 
sort(begin(haystack), end(haystack));


What does end(haystack) point to?

You only initialized 99 entries. The remainder of haystack is uninitialized (garbage). It so happens the garbage are negative numbers and therefore sort first. end(haystack) points to haystack[65536], not haystack[100]. haystack is a simple array. C++ does not keep track of how many entries you initialized.


phztfte1 (195)
Thank you all for your help. My program works. It's pretty neat using a random number generator to provide lots of numbers, a sort library function that is faster than the bubble sort or selection sort, and a library binary search function. Here is my code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
/* find
*
* Usage: find needle
* where needle is the value to find in a haystack of random number
*
*	Objective:
*		Use a library container
*		Use a library sort function - Complexity O(N log(N))
*		Use binary search function
*
***************************************************************************/


#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <array>

using namespace std;

const int HAY_MAX = 65536;

int main(int argc, char *argv[])
{
	// ensure proper usage
	if (argc != 2)
	{
		printf("Usage: %s needle\n", argv[0]);
		return 1;
	}
	// remember needle
	int needle = atoi(argv[1]);
	array<int, HAY_MAX> haystack;


	// fill the haystack with random numbers
	srand((unsigned)time(0));

	printf_s("Filling haystack with random numbers!\n");
	for (int i = 1; i < HAY_MAX; i++)
	{
		haystack[i] = rand() % HAY_MAX + 1;
	}

	printf_s("Sorting haystack...\n");
	sort(haystack.begin(), haystack.end());

	printf_s("Binary search of haystack for needle.\n");
	if (binary_search(haystack.begin(), haystack.end(), needle))
	{
		printf_s("Needle %i found!\n", needle);
	}
	else printf_s("Needle %i not found.\n", needle);
}


Chervil (7320)
A couple of comments. At line 41, the for loop begins at i=1 which means the first element is not initialised. However, after sorting, that uninitialised value could be somewhere in the middle of the array. Usually it is better to put for (int i = 0; ... etc.

Also worth noting is that HAY_MAX may be bigger than RAND_MAX, which is the upper limit of the numbers generated by the rand() function, hence the numbers generated may not cover the entire range 1 to HAY_MAX.

Since you are using some of the standard algorithms, you might also replace this code:
1
2
3
4
 
    for (int i = 0; i < HAY_MAX; i++)
    {
        haystack[i] = rand() % HAY_MAX + 1;
    }

with this:
 
 
    generate(haystack.begin(), haystack.end(), my_rand);


Where my_rand is some function which returns a suitable value, in this case looking like this:
1
2
3
4
 
int my_rand() 
{ 
    return rand() % HAY_MAX + 1; 
}
phztfte1 (195)
Chervil,

Thank you for commenting on my program.

1. The for loop where i begins at 1 is from my earlier version in which I set haystack[0] = NULL. I don't recall the reason why I did this.

2. HAY_MAX is much bigger than RAND_MAX. The value I have for RAND_MAX is 32767.

3. Thank you for pointing out the generate function.

4. Since RAND_MAX is much less than HAY_MAX, shouldn't the my_rand() function be return rand() % RAND_MAX + 1?
Chervil (7320)
Since RAND_MAX is much less than HAY_MAX, shouldn't the my_rand() function be return rand() % RAND_MAX + 1?

Fair question. Though once you're aware of the problem, you might decide that the rand() function isn't adequate for the purpose, and use some other random number generator instead. But in this case
rand() % RAND_MAX
and
rand() % HAY_MAX
each leave the value unchanged. So you might simply put return rand() + 1;, the advantage of using HAY_MAX here is that if its value was changed to something smaller, such as HAY_MAX = 100 then it would actually do something useful.
phztfte1 (195)
Chervil,

Thank you for the education and your feedback. I wanted to generate a lot of numbers so that I could see the how fast the sort and binary search functions would work. For 60,000 numbers with a lot of duplicates, it worked really fast, faster than a blink of the eye. What other random number generators are there so I can have a large population without duplicates?

Chervil (7320)
If you compiler supports C++11 (recent compilers should), you can use the new <random> header, which offers many different facilities. Here's one example, but there are lots of other possibilities:
http://www.cplusplus.com/reference/random/mersenne_twister_engine/operator%28%29/

Without using the built-in header, you could try google for possible ready-written random number generators. On a windows system, you may be able to use RtlGenRandom()
http://msdn.microsoft.com/en-us/library/windows/desktop/aa387694%28v=vs.85%29.aspx

Quote:
a large population without duplicates?

Checking for duplicates is another matter. Random numbers alone may produce duplicates. You would need to add a mechanism to check for duplicates. One way is to search the numbers previously stored each time, but that would be inefficient for a large population. You might consider the std::set instead of an array as a container, which will force all elements to be different.
http://www.cplusplus.com/reference/set/set/
Last edited on
phztfte1 (195)
Chervil,

Thank you for showing me other random number generators. I've learned a lot.
Topic archived. No new replies allowed.