BSDNT - v0.24 nn_bitset/clear/test and nn_test_random

In today's update we make a long overdue change to bsdnt, again to improve our testing

of the library.

We are going to add a function for generating random bignums with sparse binary

representation. We'll also add some other random functions based on this primitive.

Using test integers with sparse binary representation in our test code will push our

functions harder because it will test lots of corner cases such as words that are all

zero, in the middle of routines, and so on. As it is currently, we'd be extremely

lucky for the random word generator we've been using to generate an all zero word, or

a word with all bits set to one for that matter.

The first step to generating such test randoms is to write a function for setting a

given bit in an integer. This will be an nn_linear function despite it not actually

taking linear time. In fact, it will take essentially constant time. However, it is an

nn type function, so it belongs in an nn module.

The routine is very straightforward. Given a bit index b, starting from 0 for the least

significant bit of a bignum, it will simply use a logical OR to set bit b of the bignum.

Rather than construct a bignum 2^b and OR that with our number, we simply determine

which word of the bignum needs altering and create an OR-mask for that word.

Computing which word to adjust is trivial, but depends on the number of bits in a word.

On a 64 bit machine we shift b to the right by 6 bits (as 2^6 = 64), and on a 32 bit

machine we shift b to the right by 5 bits (2^5 = 32). This has the effect of dividing

b by 64 or 32 respectively (discarding the remainder). This gives us the index of the

word we need to adjust.

Now we need to determine which bit of the word needs setting. This is given by the

remainder after dividing b by 64 or 32 respectively, and this can be determined by

logical AND'ing b with 2^6-1 or 2^5-1 respectively. This yields a value c between 0 and

63 (or 31) inclusive, which is a bit index. To turn that into our OR-mask, we simply

compute 2^c (by shifting 1 to the left by c bits).

Now that we have our OR-mask and the index of the word to OR it with, we can update the

required bit. We call this function nn_bit_set.

While we are at it we create two other functions, nn_bit_clear and nn_bit_test.

It's now straightforward to write test functions which randomly set, clear and test

bits in a random bignum.

Next we create a random bignum generator which sets random bits of a bignum. In order

to do this, we simply choose a random number of bits to set, from 0 to the number of words

in the bignum, then we set that many bits at random.

We call this function nn_test_random1.

We now add a second random bignum generator. It works by creating two bignums using the

function nn_test_random1 and subtracting one from the other. This results in test randoms

with long strings of 1's and 0's in its representation.

We call this function nn_test_random2.

Finally, we create a function nn_test_random which randomly switches between these two

algorithms and our original nn_random algorithm to generate random bignums. We switch all

our test code to use nn_test_random by changing the function randoms_of_len to use it.

At this point we can have greater confidence that our functions are all working as they

are supposed to be, as our test code has been suitably fortified at last! (Well, they are

working now, after I spent a day hunting down the bugs that these new randoms found - no,

I am not kidding. That's how good at finding bugs this trick is!)

Today's code is found here: v0.24

Previous article: v0.23 - sha1 and PRNG tests

Next article: BSDNT - interlude