jeudi 25 janvier 2018

c, obtaining a special random number

I have a algorithm problem that I need to speed up :)

I need a 32bit random number, with exact 10 bits set to 1. But in the same time, patterns like 101 (5 dec) and 11 (3 dec) to be considered illegal.

Now the MCU is a 8051 (8 bit) and I tested all this in Keil uVision. My first attempt completes, giving the solution

0x48891249
1001000100010010001001001001001   // correct, 10 bits 1, no 101 or 11

The problem is that it completes in 97 Seconds or 1165570706 CPU cycles which is ridiculous!!!

Here is my code

// returns 1 if number is not good. ie. contains at leats one 101 bit sequence
bool checkFive(unsigned long num)
{
    unsigned char tmp;

    do {

            tmp = (unsigned char)num;

        if(
            (tmp & 7) == 5 
        || (tmp & 3) == 3
        ) // illegal pattern 11 or 101
                return true; // found 

            num >>= 1;
    }while(num);

    return false;
}

void main(void) {


    unsigned long v,num; // count the number of bits set in v
    unsigned long c; // c accumulates the total bits set in v

    do {
            num = (unsigned long)rand() << 16 | rand(); 
            v = num;

            // count all 1 bits, Kernigen style
            for (c = 0; v; c++)
                    v &= v - 1; // clear the least significant bit set

    }while(c != 10 || checkFive(num));

  while(1);
}

The big question for a brilliant mind :) Can be done faster? Seems that my approach is naive.

Thank you in advance,




Aucun commentaire:

Enregistrer un commentaire