c, obtaining a special random number

Question

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,

Wow, I'm impressed, thanks all for suggestions. However, before accept, I need to test them these days.

Now with the first option (look-up) it's just not realistic, will complete blow my 4K RAM of entire 8051 micro controller :) As you can see in image bellow, I tested for all combinations in Code Blocks but there are way more than 300 and it's not finished yet until 5000 index...

The code I use to test

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

//#define bool  bit
//#define   true    1
//#define false 0



// returns 1 if number is not good. ie. contains at leats one 101 bit sequence
bool checkFive(uint32_t num)
{
    uint8_t 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) {


    uint32_t v,num; // count the number of bits set in v
    uint32_t c, count=0; // c accumulates the total bits set in v

    //printf("Program started \n");

    num = 0;

    printf("Program started \n");

    for(num=0; num <= 0xFFFFFFFF; num++)
    {


        //do {



                //num = (uint32_t)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));

                if(c != 10 || checkFive(num))
                    continue;

                count++;

        printf("%d: %04X\n", count, num);
    }

    printf("Complete \n");
  while(1);
}

Perhaps I can re-formulate the problem:

I need a number with:

• precise (known) amount of 1 bits, 10 in my example
• not having 11 or 101 patterns
• remaining zeroes can be any

So somehow, shuffle only the 1 bits inside.

Or, take a 0x00000000 and add just 10 of 1 bits in random positions, except the illegal patterns.

Answer 1

Solution

Given a routine r(n) that returns a random integer from 0 (inclusive) to n (exclusive) with uniform distribution, the values described in the question may be generated with a uniform distribution by calls to P(10, 4) where P is:

static uint32_t P(int a, int b)
{
    if (a == 0 && b == 0)
        return 0;
    else
        return r(a+b) < a ? P(a-1, b) << 3 | 1 : P(a, b-1) << 1;
}

The required random number generator can be:

static int r(int a)
{
    int q;

    do
        q = rand() / ((RAND_MAX+1u)/a);
    while (a <= q);

    return q;
}

(The purpose of dividing by (RAND_MAX+1u)/a and the do-while loop is to trim the range of rand to an even multiple of a so that bias due to a non-multiple range is eliminated.)

(The recursion in P may be converted to iteration. This is omitted as it is unnecessary to illustrate the algorithm.)

Discussion

If the number cannot contain consecutive bits 11 or 101, then the closest together two 1 bits can be is three bits apart, as in 1001. Fitting ten 1 bits in 32 bits then requires at least 28 bits, as in 1001001001001001001001001001. Therefore, to satisfy the constraints that there is no 11 or 101 and there are exactly 10 1 bits, the value must be 1001001001001001001001001001 with four 0 bits inserted in some positions (including possibly the beginning or the end).

Selecting such a value is equivalent to placing 10 instances of 001 and 4 instances of 0 in some order.¹ There are 14! ways of ordering 14 items, but any of the 10! ways of rearranging the 10 001 instances with each other are identical, and any of the 4! ways of rearranging the 0 instances with each other are identical, so the number of distinct selections is 14! / 10! / 4!, also known as the number of combinations of selecting 10 things from 14. This is 1,001.

To perform such a selection with uniform distribution, we can use a recursive algorithm:

• Select the first choice with probability distribution equal to the proportion of the choices in the possible orderings.
• Select the remaining choices recursively.

When ordering a instances of one object and b of a second object, a/(a+b) of the potential orderings will start with the first object, and b/(a+b) will start with the second object. Thus, the design of the P routine is:

• If there are no objects to put in order, return the empty bit string.
• Select a random integer in [0, a+b). If it is less than a (which has probability a/(a+b)), insert the bit string 001 and then recurse to select an order for a-1 instances of 001 and b instances of 0.
• Otherwise, insert the bit string 0 and then recurse to select an order for a instances of 001 and b-1 instances of 0.

(Since, once a is zero, only 0 instances are generated, if (a == 0 && b == 0) in P may be changed to if (a == 0). I left it in the former form as that shows the general form of a solution in case other strings are involved.)

Bonus

Here is a program to list all values (although not in ascending order).

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

static void P(uint32_t x, int a, int b)
{
    if (a == 0 && b == 0)
        printf("0x%x\n", x);
    else
    {
        if (0 < a) P(x << 3 | 1, a-1, b);
        if (0 < b) P(x << 1, a, b-1);
    }
}

int main(void)
{
    P(0, 10, 4);
}

Footnote

¹ This formulation means we end up with a string starting 001… rather than 1…, but the resulting value, interpreted as binary, is equivalent, even if there are instances of 0 inserted ahead of it. So the strings with 10 001 and 4 0 are in one-to-one correspondence with the strings with 4 0 inserted into 1001001001001001001001001001.