Re: Integers and Mathematical Correctness

["chris.danx" <chris.danx@ntlworld.com>]

"Charles Sampson" <csampson@inetworld.net> wrote in message
news:1f26o22.1xfvwvo111pfi4N%csampson@inetworld.net...
> chris.danx <chris.danx@ntlworld.com> wrote:
>
> > Hi,
> >
> > To most this may seem insignificant but I'm more mathematically minded
and I
> > just found something out.  Many programming languages don't implement
> > division properly!
> >
> > For example -3/2 should be -2 not -1, with a remainder 1 not -1.
> >
> > I'm trying to implement integer division the "proper" way (according to
> > Euclid), just for fun (and to provide a mathematically correct package
for
> > anyone who gets annoyed by this).
>
>      I'm not sure how you determined that the "proper" definition of
> integer division is to return floor (a/b), where "/" is mathematical
> division.  The definition used by most programming languages preserves
> the very useful property -(a/b) = (-a)/b = a/(-b), where this time "/"
> represents integer division.
>
>      Please explain the Euclid reference.  I don't have any History of
> Mathematics books available, but I don't remember that Euclid had nega-
> tive numbers to work with.

According to Euclid, the "division algorithm" (which isn't an algorithm)
asserts that for a/b

a = kb + r

where r >= 0
      k <- Integers


[For anyone unfamiliar with Haskell or (possibly) other functional languages
"<-" reads as "is a member of"].

So for -4 / 3

-4 = 3k + r

r > 0, so k = -2

-4 = 3(-2) + r
-4 = -6 + r
r  = 2

however in Ada (and others) this is,

-4/3 = -1

-4 = 3k + r
-4 = 3(-1) + r
-4 = -3 + r
r  = -1

Which is wrong!  r can never be negative according to Euclid.

Tons on the division algorithm can be found on the net,
http://www.utm.edu/research/primes/glossary/DivisionAlgorithm.html is one
such resource but I'm having trouble finding any history.  I don't know if
Euclid had negatives, but the Division Algorithm works for negatives.

This page has something on it (coding it in C),

http://www.csclub.uwaterloo.ca/~mpslager/compsci/GCD.html#Division%20Algorit
hm


Bye,
Chris