| #include "stdlib.h" |
| #include "stdio.h" |
| |
| #define ARRAY_SIZE 500000 |
| #define NLOOPS1 5 |
| #define NLOOPS2 200 |
| |
| // RNG implemented localy to avoid library incongruences |
| #ifdef RAND_MAX |
| #undef RAND_MAX |
| #endif |
| #define RAND_MAX 32767 |
| static unsigned long long int next = 1; |
| |
| int rand( void ) { |
| next = next * 1103515245 + 12345; |
| return (unsigned int)(next / 65536) % RAND_MAX+1; |
| } |
| |
| void srand( unsigned int seed ) { |
| next = seed; |
| } |
| // End of RNG implementation |
| |
| int randInt(int min, int max) { |
| int k, n; |
| n = (max - min) + 1; |
| k = (int)(n * (rand() / (RAND_MAX + 1.0))); |
| return (k == n) ? k + min - 1 : k + min; |
| } |
| |
| void shuffle(int* items, int len) { |
| size_t j, k, i; |
| int aux; |
| |
| for(i = len-1; i > 0; --i) { |
| k = (int)((i + 1) * (rand() / (RAND_MAX + 1.0))); |
| j = (k == (i + 1)) ? k - 1 : k; |
| |
| aux = items[i]; |
| items[i] = items[j]; |
| items[j] = aux; |
| } |
| } |
| |
| int *createRandomArray(int size) { |
| int i, len; |
| int *result; |
| |
| len = size + 1; |
| result = (int*)malloc(len * sizeof(int)); |
| for (i = 0; i < len; i++) |
| result[i] = i; |
| result[0] = randInt(1, size); |
| shuffle(result, len); |
| return result; |
| } |
| |
| int findDuplicate(int *data, int len) { |
| int i; |
| int result = 0; |
| |
| for (i = 0; i < len; i++) |
| result = result ^ (i + 1) ^ data[i]; |
| result ^= len; |
| return result; |
| } |
| |
| int main() { |
| int i, j, duplicate; |
| int *rndArr; |
| |
| srand(1); |
| |
| for (i = 0; i < NLOOPS1; i++) { |
| rndArr = createRandomArray(ARRAY_SIZE); |
| for (j = 0; j < NLOOPS2; j++) |
| duplicate = findDuplicate(rndArr, ARRAY_SIZE+1); |
| free(rndArr); |
| printf("Found duplicate: %d\n", duplicate); |
| } |
| |
| return 0; |
| } |