Turning to my own blog these days as a faster way to find my own previous code is perhaps worrying in a sense1 but it's also absolutely working. Yet another one of those "unexpected" ways in which past work pays now and current work pays later but all the more so for accumulated dividends! So here I am taking the time to write up and publish my code, mainly so that *next* time when I end up looking for it, I can find it straight away and with context too, such a wonder.
The code in question is the Ada implementation of the Mersenne Twister pseudo-random number generator (MT prng). I already had implemented MT in Ada and even packed it for easy use as a standalone library, but I published it only as a patch on a different v-tree, since my need for it at the time was simply as part of my testing code for a UDP library. Meanwhile though and quite as usual, I have found of course a lot of *other* uses for it, especially for computer graphics generation. And those uses come with their own context that turns out - again, as usual - to have some specific requirements, of which two are most significant:
- As I am moving away from the exploratory stage in which awk combined easiest with the reference C implementation and worked great otherwise *for prototyping*, I really want Ada code rather than C, CPP or anything else.
- It's not enough to have just one prng sequence at any given time, since there can and indeed will be in principle any number of graphics artefacts generated in parallel.
For the first point above, simply plucking my previous MT lib out of the tester's vtree would be quite enough. So as a first step I did that anyway, since a prng is not all that related otherwise with UDP communication or its testing and I'd rather have it therefore as a separate v-tree with its own genesis, neatly on my Reference Code Shelf and linked here as well for easy access:
The second requirement of being able to run in parallel any number of MT prng sequences imposes a more significant change to the implementation approach, because MT has an internal state and the reference implementation (that my Ada code above follows otherwise) is essentially sequential: at any given time, one can either reset the state by changing the seed or request the next number in the current sequence but there is no direct way to keep track of several sequences at the same time. Depending on your background, you may reach perhaps as an easy solution for this to either some sort of object encapsulation (basically the OO - Object Oriented - approach) or threads/tasks (essentially parallelization - spawning a new thread for each sequence). Both solutions seem to me rather unnecessarily complex though. There isn't much need for a "MT object" as such, especially if otherwise the application doesn't yet suffer from being Object Oriented (and mine doesn't, nor do I wish it to start on that path). At the same time, there isn't much need for separate threads (with their corresponding overhead, too) either: the MT algorithm itself is not resource intensive and otherwise the caller(s) in my case have to wait for the prng value anyway, there isn't anything worth parallelizing at that level.
As usual, Ada provides an option - generics - that fits those requirements better than either OO or threads and has the added advantage of simply making impossible that ugly case when the prng is not initialized (i.e. when a number is requested before a seed is given). Since what I need is simply a way to have any number of different sequences (hence, different seeds) available and ready to question sequentially at any time, I simply changed the MT package to require the seed as a parameter and initialize the sequence directly in its body (hence, the code is run as soon as the package is instantiated aka given a specific seed and before any call to any of its functions or procedures can be executed).
The Ada approach of using a generic package as described above reflects quite accurately2 the fact that MT as such is just an algorithm (hence, a generic package since that's exactly what generic stands for - the algorithm), while an actual prng based on MT can only be obtained when a specific seed is given (hence, when the generic package is instantiated with a specific value for its seed parameter). Once MT becomes a generic package, using any number of MT prngs is as simple as writing "package MT_123 is new MT(123)" and going with the MT_123 afterwards, without any concern about "have to initialize before using" (since it IS already initialized, as soon as the seed is specified). And since every new sequence is essentially a new package, there is no trouble with the internal state either - each has its own and doesn't have anything to do with any of the others.
The corresponding code for the above is packed as a v-tree of its own3, the mt_generic lib on my Reference Code Shelf and linked here, as usual:
The easy conclusion to jump to on this would be that "her non-published code repositories and archives are a mess". Jump that way if you are so inclined, what's it to me? When you're dizzy enough from all that jumping on the first thing that seems like a thought at all in your head, consider for instance that it might simply be the size, number, variety and even age (in other words history and more specifically preserved history) of accumulated code that has something to do with it, too. My blog may be relatively old enough to have accumulated things too but first of all the very act of writing something up for publishing includes both filtering and basically indexing for easier later finding, what else IS publishing if not this, after all? ↩
This by the way is the precise sort of thing that makes Ada such a great language to work with, from my point of view: it provides the matching abstractions, allowing one to implement precisely what they mean rather than having to make do with some vague approximation and then going nuts trying to keep in check all the various fuzzy edges where the whole thing fails. Admittedly, some take the path of just ignoring those fuzzy edges and so they find Ada "hard" precisely because it makes such ignorance difficult and otherwise they find assorted other languages "easier" for not forcing them to pay attention to what they don't want to pay attention to - until the whole thing fails, of course but that is just... how things are, right? ↩
Arguably it could just as well be a branch on the MT vtree as such but I can't say I found a compelling argument for basically forcing one to have two vpatches instead of one here. I can see the argument of "it's a refinement of MT for a specific type of use" so perhaps there is something to it but at the moment at least my answer to that is that branching basically immediately after genesis seems to me not all that different from just making two trees to start with. I'm still in two minds about this though, so let me know in the comments if you have some compelling arguments for either case. ↩
Comments feed: RSS 2.0
[...] coordinates alone and the vision undisturbed but inject instead some controlled chaos by using a mersenne twister (MT) as a generator of more interesting complex polynomials: simply set all coefficients of the [...]
[...] idea behind the Diamond Square method (DS) is deceptively simple: take a set of pseudo-random values and keep mixing (averaging) those on symmetrical positions, storing the result of the mixing at the [...]