```
Subject:
```**Re: What's up with IEEE Scheme?**

From: rpw3@rigden.engr.sgi.com (Rob Warnock)

Date: 17 Oct 2000 04:15:34 GMT

Newsgroups: comp.lang.scheme

Message-ID: <8sgjp6$a9u3e$1@fido.engr.sgi.com>

David Rush <kumo@bellsouth.net> wrote: +--------------- | Isn't GF(2^n) identical to Z/(2^n)Z when the generator polynomial | is 2^n-1? +--------------- No, not at all, sorry. First of all, 2^n-1 is probably not even prime (such numbers are called "Mersenne numbers", and only a *very* few "Mersenne primes" have been found), so that arithmetic with that modulus might not even produce a field. [Note: 2^31-1 *is* prime, but 2^32-1 isn't.] But more importantly, if by "Z/(2^n)Z" you mean the usual "machine arithmetic" on "n"-bit integers (say, as in C's notion of addition and multiplication of signed or unsigned ints), well, that's probably not a field either (though it will be a ring, as you note, but IMHO rings are *much* less interesting than fields). As a simple demonstration of this, try to find the "multiplicative inverse" of 3 (modulo 2^n), that is, the number "x" such that "x * 3 == 1 (modulo 2^n)". For n==8, 16, 32, and 64, at least, there is no such number, and thus unsigned integer arithmetic in C isn't a field. [There *is* an inverse for n==31, that 3 * 715827883 == 1 (modulo 2^31), but this doesn't help you in C, since even with signed ints (which you'd expect to have 31 bits of precision -- but they don't!), 3 * 715827883 produces -2147483647, not 1.] +--------------- | Regardless of my errors in the above, there is a serious deficiency in | the Scheme standards when it comes to manipulation of machine-oriented | integers. I know that this is by design, in an attempt to avoid the | deficiency of *only* having machine integers, but it makes it very | difficult to use *many* published algorithms (e.g. the FFT). You end | up recasting them in terms of extra modulo and quotient operations, | which is tedious (at the least), and horribly inefficient. +--------------- What the other poster quite nicely pointed out is that there are *many* different kinds of "machine-oriented integers" [including such things as 60-bit *ones*-complement arithmetic!!!]. If the Scheme standard provided an "efficient" version of one particular machine's arithmetic, it would *necessarily* be "horribly inefficient" on other machines (some of them important to their users). Therefore such things should *not* be part of the standard. +--------------- | This should be fixed, even from the point of view that Scheme is a | teaching language. The fact that computers do integer arithmetic in a | ring is a crucial fact of programming life that should *not* be hidden | from students. +--------------- I don't agree that it's all that "crucial", but in any case it doesn't have to be "hidden" even when teaching with Scheme. Simply define routines that do the kind of arithmetic you're teaching that day -- DEC PDP-10, CDC 6600, Cray 1, Intel 8080, AMD x86-64, whatever -- and have the students explore the consequences of using arithmetic that is "broken" in various and wonderful ways with respect to the more regular truths of "ordinary arithmetic". +--------------- | ...nor gracefully demonstrate algorithms which exploit this fact. +--------------- Of course you can! Just define routines "+/32" and "*/32" (with the modular arithmetic incorporated inside them), for example, and then let the students see what happens when you use them instead of "+" and "*". Plus, every implementation of Scheme that I know of makes it almost *trivial* to link in your own libraries of C code, often at runtime, so if you want to link in an FFT library written in C, you can do that, and then compare the speed *and* the [lack of] precision to the same algorithm written with default Scheme arithmetic. -Rob ----- Rob Warnock, 31-2-510 rpw3@sgi.com Network Engineering http://reality.sgi.com/rpw3/ Silicon Graphics, Inc. Phone: 650-933-1673 1600 Amphitheatre Pkwy. PP-ASEL-IA Mountain View, CA 94043