Block Longest Run Test

In the NIST paper A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, the authors propose the Test for the Longest Run of Ones in a Block. The idea is to slice the binary string into blocks and check for the longest run of 1s within each block.

This overall idea of the test makes sense, but the way they implemented it involves arbitrary thresholds and magic numbers. For example, if $n$ is the length of the bit string and $M$ is the block size, then the following table specifies the proper way of sizing $M$ as a function of $n$.

Where did the magic numbers 128, 6272, and 750,000 come from? What happens if $n$ is a much larger number, like 10,000,000?

The more serious problems arise when considering the table of expected counts for the chi-squared test.

Why is the number of categories different depending on the value of $M$? Thankfully, the authors specify what the probabilities are in a later section, but they don't provide the formula for how the numbers were obtained, instead citing a 397-page non-free-access book without saying which page the formula came from.

The benefit of using the "runs test" described on this website is that it avoids the need for arbitrary thresholding and doesn't require knowing or computing any of those magic numbers. Although the two tests are not strictly equivalent, they tend to succeed and fail on the same test cases, which indicates that they serve roughly the same purpose.

Both tests successfully catch the alternating zeros and ones test case.

Both tests fail to catch the expected runs test case.