"Johann Hibschman" <johann / physics.berkeley.edu> wrote in message
news:mtitgbmy34.fsf / astron.berkeley.edu...
> MikkelFJ  writes:

> But with division,

I may not be entirely correct in my previous statement about (+, -, *, /)
being supported by modulo arithmetic.
The division is only defined by introducing a reminder. On the other hand
division never goes outside its domain like multiplication does, so you
wouldn't need modulo in the first place. When multiplying two integers such
that your number wraps around in the 32bit integer, you are effectively
taking modulo 2^32 of the operation. Therefore the result within this
algebraic construct is still perfectly correct.

> This seems bad, or do you have a weird definition of multiplication
> and division that makes it work out?  I always thought even the
> integers mod something were a ring and not a field.  Rational support
> seems like the only sane option.

Uh - I can't remember this stuff properly - it's been a while and I'm no
expert on the topic.

But it is a ring. A ring requires a set of elements, a null element, a one
element, addition and multiplication, some commutative and associate
criterias, all of which are all present. On top of this comes a lot
different domain classes, depending on whether inverse elements exists or
not etc. Division does not exists, but is defined by multiplying by the
inverse element, if it exists. It doesn't in general. If the number of
elements in the domain is prime, all elements have an inverse element
defined (except the null element).

But the 2^n sized integers are also GF(n) Galois fields if I remember
correctly. Viewed as a Galois field division is suddenly defined by
polynomial division: xn*2^n +xn-1*2^n-1 + ... + x where xn is a bit in an
n-sized integer. You will get reminders, and I think this is actually how
division is implemented. But I may be mixing different concepts here.

The topic as such is interesting because you suddenly realise that all the
math in a dump microprocessor has a very profound algebraic background.

Mikkel