Re: Quality systems (Was: Using Ada for device drivers? (Was: the Ada mandate, and why it collapsed and died))

["Robert I. Eachus" <rieachus@attbi.com>]

Hyman Rosen wrote:
> Vinzent Hoefler wrote:
>  > (and that sometimes might be not that easy as it looks at the first 
> glance).
> 
> That's because the Ada folks got clever and decided that the
> modulus didn't need to be a power of two. Doesn't Dewar rant
> on this subject occasionally?

As the sort of guilty party in this, let me explain why Ada allows 
modular types with bases other than powers of two, and what you can and 
can't do with the feature.

There is an operation in almost all hardware that allows quickly 
calculating (X * Y) mod N for any N smaller than the machine's natural 
word size:
           X * Y --> r1,r2 (or some register pair)
           (r1,r2) mod N --> r2

All other arithmetic operations on modular types are fast.  Well 
actually sometimes weird people like me want the non-arithmetic integer 
divide.  (If X, Y are all relatively prime, that is their pairwise GCDs 
are all 1, then there exists a unique Z such that Y * Z = X.)  But if we 
want it, it can be written in Ada and the "normal" divide for that type 
can be overridden.  The problem is that the Ada semantics make it very 
difficult to specify the modular multiplication for moduli that are 
non-powers of two, although all hardware has the two instructions above 
available, if you want to write an efficient version in Ada you have to 
use embedded assembler or the like.  If the feature of non-power of two 
moduli is supported in the language, the code generation is easy.

Why are these types needed?  The actual need is very small, but 
important.  Pulse doppler radar for example use a technique called the 
Chinese remainder theorem to disambiguate target ranges.  If you use 
pulse repetition frequencies A and B with a rational ratio A/B, then you 
can disambiguate the ranges to targets which are futher away than half 
the distance the radar signal can travel between pulses.  The two (or 
more) pulse rates are usually chosen so that the range ambiguity is a 
few kilometers.  For a simple example let's choose a ratio of 11 and 13.

If you get a return that could be at 7, 18, 29, 40, 51, 62, 73,... 
kilometers and from the other rep rate, a return at 2, 15, 38, 51,... 
kilometers, you conclude that the target is 51 kilometers away.  In 
practice target disambiguation and range disambiguation is much more 
complex.  But all you really need to know is that all the work is done 
with numbers in two different non-power of two modular types.

Other cases where non-power of two moduli crop up are in pseudo-random 
number generation, cryptography, and discrete Fast Fourier Transforms. 
So non-power of two moduli are very useful in a number of embedded 
applications where the cost of having the operations supported is 
trivial compared to the benefits.  And cryptography and random number 
generation make the types more generally useful.

So why does Robert Dewar rant occasionally about the types?  In a highly 
portable compiler like GNAT, the code generator has to support 
instructions that are not needed for any other language.  So this 
feature is a code-generation issue for GNAT that needed to be added to 
the gcc backend.  Technically, GNAT could have chosen the largest 
permitted non-power-of-two modulus to be 2^16-1.  But GNAT went to the 
effort to support non-power-of-two moduli up to Integer'LAST, and 
integrated the support into the code generator instead of doing the 
multiplies by using a two instruction code insert.  Which means that in 
discrete FFTs and Chinese Remainder Theorem implementations you get very 
high-quality code.  So he is in my book entitled to rant, and every time 
I use the feature I try to think of something nice to do for GNAT. ;-)