Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!eecae!tank!uxc!uxc.cso.uiuc.edu!mcdurb!aglew
From: aglew@mcdurb.Urbana.Gould.COM
Newsgroups: comp.lang.c
Subject: Re: Contiguous Arrays
Message-ID: <28700035@mcdurb>
Date: 15 Mar 89 19:00:00 GMT
References: <2508@ssc-vax.UUCP>
Lines: 15
Nf-ID: #R:ssc-vax.UUCP:2508:mcdurb:28700035:000:843
Nf-From: mcdurb.Urbana.Gould.COM!aglew    Mar 15 13:00:00 1989


>I have never found the discussion of computer arithmetic as a
>topic in abstract mathematics very attractive.

Topic for another newsgroup, but abstractions of computer arithmetic
can be interesting. For example, binary encoding gives us O(lg N) in the number
of bits addition and parallel multiplication and comparisons; redundant
encodings give us O(1) parallel addition at the cost of more difficult
comparisons; residues give you O(1) parallel addition and multiplication
(well, actually O(lg M), where M is a number related to the number of 
primes within the range you want to work on) but considerably more
complicated comparisons; logarithmic encoding gives you O(1) parallel
multiplication and division, at the cost of subtraction...
    Q: is there any sort of "Conservation of [parallel] complexity"
theorem for finite arithmetic?