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,b61052ba3fdc8c26 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-11-01 09:15:28 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!newsfeeds.belnet.be!news.belnet.be!colt.net!newspeer.clara.net!news.clara.net!news-hub.cableinet.net!blueyonder!btnet-peer!btnet-peer0!btnet!news5-gui.server.ntli.net!ntli.net!news6-win.server.ntlworld.com.POSTED!not-for-mail From: "chris.danx" Newsgroups: comp.lang.ada References: <1f26o22.1xfvwvo111pfi4N%csampson@inetworld.net> Subject: Re: Integers and Mathematical Correctness MIME-Version: 1.0 Content-Type: text/plain; charset="Windows-1252" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2600.0000 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 Message-ID: <_lfE7.52002$a14.6154112@news6-win.server.ntlworld.com> Date: Thu, 1 Nov 2001 17:10:41 -0000 NNTP-Posting-Host: 62.252.145.122 X-Complaints-To: abuse@ntlworld.com X-Trace: news6-win.server.ntlworld.com 1004634618 62.252.145.122 (Thu, 01 Nov 2001 17:10:18 GMT) NNTP-Posting-Date: Thu, 01 Nov 2001 17:10:18 GMT Organization: ntlworld News Service Xref: archiver1.google.com comp.lang.ada:15554 Date: 2001-11-01T17:10:41+00:00 List-Id: "Charles Sampson" wrote in message news:1f26o22.1xfvwvo111pfi4N%csampson@inetworld.net... > chris.danx 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