Saturday, 20 November 2010

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

1 comment:

  1. Is it just me or is the code not actually on GitHub?

    ReplyDelete