From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,583275b6950bf4e6 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2003-05-19 20:03:33 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news.uchicago.edu!newsswitch.lcs.mit.edu!newsfeed.mathworks.com.MISMATCH!newsfeed!wn13feed!worldnet.att.net!204.127.198.203!attbi_feed3!attbi.com!sccrnsc01.POSTED!not-for-mail Message-ID: <3EC99B03.4010903@attbi.com> From: "Robert I. Eachus" User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.0.2) Gecko/20021120 Netscape/7.01 X-Accept-Language: en-us, en MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: Quality systems (Was: Using Ada for device drivers? (Was: the Ada mandate, and why it collapsed and died)) References: <9fa75d42.0305130543.60381450@posting.google.com> <254c16a.0305140549.3a87281b@posting.google.com> <9fa75d42.0305141747.5680c577@posting.google.com> <3ec4b1c9$1@news.wineasy.se> <9fa75d42.0305161748.1735fc32@posting.google.com> <4W%xa.28765$cK5.11964@nwrdny02.gnilink.net> <1053353256.804734@master.nyc.kbcfp.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit NNTP-Posting-Host: 24.62.164.137 X-Complaints-To: abuse@attbi.com X-Trace: sccrnsc01 1053399812 24.62.164.137 (Tue, 20 May 2003 03:03:32 GMT) NNTP-Posting-Date: Tue, 20 May 2003 03:03:32 GMT Organization: AT&T Broadband Date: Tue, 20 May 2003 03:03:32 GMT Xref: archiver1.google.com comp.lang.ada:37544 Date: 2003-05-20T03:03:32+00:00 List-Id: 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. ;-)