Please see the disclaimer.
Introduction
By this point, it should be wellknown among my nonexistent readership that I
wrote an implementation of POSIX bc
. It is less wellknown that I work
for SchedMD, LLC supporting Slurm, the number one supercomputer
scheduler.
When submitting a job to a Slurm “cluster,” we can either submit a normal executable or a shell script. When I am working with Slurm on a daytoday basis, I usually use shell scripts.
However, I ran into a problem about two months ago: I needed a highquality seeded pseudorandom number generator (PRNG) in my shell scripts.
I did not need a nonseeded PRNG because Linux has /dev/urandom
, which is
also as close to cryptographically secure as I could get in shell.
Now, bash
, which is the shell I use, has the special variable, $RANDOM
,
but it is only guaranteed to return 15 bits of random data. Also, because it
probably uses C’s rand()
, which is low quality, the random stream is not
good. And because C’s rand()
is not good (and also is only guaranteed to
return 15 bits of random data), I can’t just write a simple C program to
generate random numbers either.
After thinking about it awhile, I realized that a pseudorandom number generator
in my bc
would be worth the effort.
There are a few reasons for this:
 The
bc
could make sure the output is unbiased when generating a random number within a range.  The
bc
could generate integers of any size, since it can handle integers of any size.  The
bc
could generate reals with arbitrary precision as well.
So I got to work.
Choosing the Algorithm
The first step was choosing which PRNG algorithm I would use. I had a few requirements:
 The PRNG should be a family of PRNG’s able to generate either 32 or 64 bits
of random data on each call. This is because my
bc
can be compiled for 32bit and 64bit platforms.  The PRNG should be relatively fast.
 The PRNG should at least pass BigCrush and PractRand.
Starting from this list, I began doing my research.
The choices quickly narrowed to two: either the xoroshiro family or the PCG family, and I started reading about both.
I first came across this critique of the PCG generators, and I must admit, it took me a bit to realize that it was written by the author of the xoroshiro generators. Once I did, I started looking for other sources.
This link says that some members of the xoroshiro family fail BigCrush. It also says that the PCG family pass BigCrush.
This link says that the xoroshiro family failed PractRand, but that the PCG generators passed.
There were more, but I did not find anyone who managed to break the PCG generators after trying, while there were several people who managed to show instances of the xoroshiro generators not passing the PRNG test suites.
Then I came upon the Reddit discussion of the PCG critique. And from there, I found the PCG author’s response to the PCG critique.
The difference in tone between the critique and the response was…enlightening. The critique had vitriol, but the response showed a willingness to admit mistakes and learn.
Then I began reading the blog by the PCG author, and I learned more about PRNG’s than I ever expected too.
When it came down to it, I was leaning towards the PCG generators, but I freely admit that I was emotionally swayed, by the difference in tone between the two authors plus the plethora of information on the PCG blog, to choose the PCG family of PRNG’s.
However, which PCG generators I use was still important; Melissa O’Neill,
the author of the PCG generators, has made it clear which of the generators she
would recommend for generalpurpose use when speed isn’t paramount and
prediction difficulty is needed: pcg32
for 32 bits and pcg64
for 64 bits.
And those were the ones I went with. No, they are not the fastest (thought they are still fast), but I trust, from what was written by other, unbiased experts, that the quality of those generators would be as high as I could get in 32 or 64 bits.
Designing the API
The next step was designing the API, which was a surprisingly hard thing to do.
Well, designing the way to generate random numbers was easy: builtin functions.
For querying the maximum value generated by the PRNG, I added the
maxrand()
function. Users can use it to see what the maximum integer generated
by the rand()
builtin function.
rand()
is the function that generates a random number without any extra
processing. It just generates the 64 or 32bit random integer, turns it into a
form bc
understands, and returns it.
irand(x)
takes an integer x
and returns an integer in the range [0,x)
.
When doing so, it removes bias. It can generate integers of arbitrary size as
well. If x
is greater than the value returned by maxrand()
, it generates
more than one integer, multiplying some by correct powers to grow the integer to
the correct size. So irand(x)
can generate a massive integer if x
is
massive itself.
These three builtin functions are also available as commands in dc
.
From there, I added functions to bc
’s extended math library, instead of
builtin functions. The reason for this is because all of these other functions
could easily be implemented with the builtin functions.
frand(p)
generates a real in the range[0,1)
that hasp
digits after the decimal point.ifrand(x,p)
does a combination ofirand(x)
andfrand(p)
.srand(x)
returnsx
with its sign flipped with a probability of0.5
. In other words, it randomizes the sign ofx
.brand()
: returns a random boolean value.
The implementation of these three functions is in gen/lib2.bc
.
The API Problems
Didn’t I say that designing the API was hard? Yes, but only one thing was actually hard: handling the seed.
Users of bc
should be able to both query and set the seed. And that’s only
part of what made it difficult.
In the PCG family of generators, there are actually two parts to the seed: the
seed itself and the “stream selector.” Each of these has twice the number
of bits than the PRNG returns on every call,^{1} e.g., pcg64
’s seed and stream
selector both have 128 bits, and pcg32
’s seed and stream have 64 bits.
These aspects caused two problems:
 I needed 128bit math for the 64bit
bc
.  The seed in the
bc
needed to be two separate values.
128bit Math
While POSIX, which is the standard my bc
depends on for portability, requires
implementations to have a uint64_t
type (required for a 32bit
implementation), it does not require them to have a uint128_t
type. Thus, I
could not depend on having 128bit math available for my bc
, even though gcc
and clang
provide 128bit math most of the time. I implemented the required
math by hand, though my build system detects if 128bit math is already
available and uses it if it is.
This solved problem 1.
Two Values for the Seed
The other problem, two values for the seed, was much harder.
I knew that I would need to make the seed values special variables, like
ibase
, obase
, and scale
. That way, they could both be set (by assignment)
and queried (by putting them in an expression).
However, I did not like the thought of adding two new variables, mostly because it would make an awkward upgrade path for my users if I later switched to an algorithm that only needed one seed value since one special variable would become a regular variable.
It took a long time for me to find the solution: have only one value and use both sides of the decimal point.
The current seed API for my bc
is this: there is a special value called
seed
, and unlike ibase
, obase
, or scale
, which must all be integers,
seed
can be, and always is (because of a quirk in the PCG family), a real
number. The integer portion is converted to a 128bit (for 64bit) or 64bit
(for 32bit) integer and is used as the stream selector. The noninteger portion
is multiplied by a certain value and truncated to turn it into a 128bit (for
64bit) or 64bit (for 32bit) integer and is used as the seed value.
Do NOT make bc
scripts that depend on the above information because it
could become invalid if I change the PRNG implementation later.
Any guarantees that bc
provides regarding the PRNG API are spelled out clearly
in the bc
manual, which can be accessed by man bc
in the shell if you
installed it with man pages. These guarantees will remain the same regardless of
which PRNG algorithm is used.
Global Stacks
But even that wasn’t all.
My bc
has an option, g
that turns globals into stacks. This means
that if a global is changed in a function, the change is not seen outside the
function.
This is one of my bc
’s greatest features because it makes writing bc
much
easier; however, it creates a problem with the PRNG because seed
is changed
every time the PRNG is used, which should be visible to other functions.
I struggled for a long time, and finally came up with an answer: if seed
is
assigned to in a function, then any calls to the PRNG after the assignment do
not change seed
’s value outside the function. If the PRNG is used before an
assignment to seed
in a function, then changes to seed
are visible outside
the function.
Seems simple enough, but the code to implement it was not.
After figuring that out, it was just of matter of implementing it and the rest
of my design, which took some time to do while following the style I already had
for bc
. It also took some time to test.
Interesting Tidbits
To do this, I had to do many things that were new and interesting. Here are some of them.
 As mentioned before, I had to implement 128bit math.
 I learned how to unbias a PRNG when generating with a smaller range.
 I had to make sure the
seed
was set if it was queried before any random number was generated.  I had to learn how to generate an integer of arbitrary size.
That last one is the most interesting to me because I almost got it wrong. Twice. In fact, I did get it wrong for a time.
At first, I thought that I could just generate a bunch of integers in the range
[0,maxrand()]
, or in other words, just use rand()
, and only the integer
that was placed at the most significant position had to be generated with a
smaller range. That is not quite the case, but it was close.
However, the second mistake I made was thinking that it was not close. My next
try was to generate a number, but each integer portion had to be less than the
one in the target. This was completely wrong; irand(2^64+1)
would only
generate two numbers, 0
and 2^64
.
My next try was to check each to see if each integer portion was larger than its equivalent in the target. If it was, I subtracted one from the next portion, which was more significant.
Anyway, I think I got it right this time, but I may be wrong. Bug reports are welcome.
Status of the PRNG
After I did all of this work, readers may be surprised to know that I am not
putting out an official release of bc
with the PRNG. The reason is that I
asked the majority of my users if they had a use for it, and the answer was
unanimous: no, they did not.
This change bloats bc
by almost 5 kb when building with size optimizations;
that is massive, and since bc
is not really used nowadays (most people use
Python or another arbitraryprecision calculator), except to build the Linux
kernel, I can’t justify putting it in a release, especially when some of my
users want a small bc
.
That said, if you want bc
with its PRNG, you can build it from the rand
branch, and you can rest assured that it is not disappearing anytime soon
because I use it. It is also heavily tested, just like real releases are.
And if, over time, more and more users decide that they want to use it, then maybe someday, I will put out an official release with the PRNG.
Update (27 Feb 2022): I sort of lied above because I got fed up with using a
separate branch and merged the rand
branch into master
soon thereafter. If
you want the PRNG, you can use the latest version.
So if you decide to use it, let me know.

Technically, the stream selector has 1 less bit than the seed, but in Melissa’s C code, which I adapted for
bc
, the stream selector is implemented with the full bit range, shifted left by one bit and bitwise or’ed with 1 since the stream selector must be odd. ↩︎