Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Sigh, don't have an SO account but if I did, I would suggest this code which I call randsort --

   #include <stdint.h>
   #include <stdio.h>
   #include <stdlib.h>

   int
   main(int argc, char *argv[]) {
       int i, ndx;
       double my_numbers[10];
       double sorted_numbers[10];
       uint16_t picked;

       for (i = 1; i < argc; i++) {
           my_numbers[i-1] = atof(argv[i]);
       }

       while (1) {
           picked = 0;
           ndx = 0;
           /* sort the numbers */
           while (picked != 0x3ff) {
               i = (rand() / 100) %  10;
               if ((picked & (1 << i)) == 0) {
                   picked |= (1 << i);
                   sorted_numbers[ndx++] = my_numbers[i];
               }
           }

           /* verify they sorted correctly */
           for (i = 8; i >= 0; i--) {
               if (( i == -1) || (sorted_numbers[i] > sorted_numbers[i+1])) {
                   break;
               }
           }
           if (i == -1) {
               printf(" Sorted: \n");
               for (i = 0; i < 10; i++) {
                   printf(" %d: %f\n", i, sorted_numbers[i]);
               }
               exit(0);
           }
       }
   }


And since `srand(time(NULL))` isn't ever called, it's deterministic, too!


Is that the case for all platforms and C libraries? Also, isn't seeding with the current time a way to guarantee deterministic behavior? An attacker of such an algorithm probably knows what time it is, and users probably don't expect all invocations within a given second to return the same results.


Nice. Is that O(e^n)?

Out of curiosity, why do you divide the rand() by 100 before applying the mod?


No reason on the divide. Just because. That is probably a reasonable guess on the big O value. Clearly O(rand) is cheeky but in accurate. And the PRNG will walk the number space so it will eventually succeed, but computing how long it will take for 'n' numbers eludes my math reasoning skills.


> the PRNG will walk the number space

Are you sure? What if there's an infinite amount of tries to get to a certain number? You can of course reason about the average case, but maybe the worst case (when there's an input number which is never found by the PRNG) does never halt.

> O(rand)

For sorting algorithms we usually compare in the number of input elements. You can reason about the average case where the numbers are found in average time so you can consider the number of iterations to find the correct number a constant (a very large constant but a constant nonetheless).




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: