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