fixed size integer arithmetic

[Hans Aberg]

On 3 Sep 2007, at 11:44, Evan Lavelle wrote:

> Richard B. Kreckel wrote:
>> I suppose you guys are talking about modular arithmetic, right?
>
> In principle, yes. In practice, though, a modular arithmetic  
> library is
> probably not the best way to go (in my case, anyway).
>
>> Did you try CLN <http://www.ginac.de/CLN/>? CLN is not C, though.  
>> It is
>> C++.
>>
>> (I may mention that in CLN the modulus (called "invariant" above)  
>> is a
>> dynamic attribute of the class, not determined at compile time. IOW:
>> different moduli are not different C++ types and mismatches cause
>> runtime errors.)
>
> I didn't find CLN; thanks for the link. My own app is modelling
> hardware, and the compiler constructs which let you do this. This is
> required in hardware description languages, such as VHDL and  
> Verilog. A
> simple way to look at this is to think of an N-bit processor, with  
> N-bit
> registers and an N-bit ALU, where N is arbitrary and is not  
> necessarily
> a power of 2.

Here, writing k = N, with notation as in earlier posts, you are in  
effect working in Z_n := Z/nZ, where n = 2^k.

> You then need to handle all the low-level N-bit arithmetic
> and logical/bitwise operations that you'd expect to find in a  
> processor.

When this other bitwise stuff is added, I think of it as a binary(k)  
type (see below).

> Or, alternatively, take the set of operators from a language such as C
> and re-implement them for arbitrary N, rather than the standard set of
> 8, 16, 32, and 64.
>
> CLN might have been a useful starting point, but it doesn't appear to
> have the bitwise operators, apart from << and >>, and >> seems to  
> have a
> restriction on N.

Bitwise negation of x, though, is arithmetic - x - 1 mod n. "<<" is  
multiplication by 2, and ">>" is unsigned division by 2, where the  
remainder is thrown away; the latter isn't a well-defined arithmetic  
operator on Z_n, as say 0 = n mod n giving n/2 two different values  
(see below).

> There's also the issue of operations on elements of
> different modular rings. There's nothing wrong, in principle, in  
> adding
> a 9-bit integer to a 191-bit integer, to get a 191-bit result (or
> vice-versa), but CLN won't let you do this.

Again, this is not a well-defined arithmetic operator: Z_(2^9) isn't  
naturally a subset of Z_(2^191). In mathematical terms, one will have  
to choose an embedding Z_(2^9) >-> Z_(2^191), and then add the  
numbers in Z_(2^191). This can be done by choosing a section Z_(2^9)  
 >-> Z, and then combine with the natural projection Z ->> Z_(2^191).  
If the section is 0, ..., 2^9-1, then this corresponds to treating  
the numbers of _(2^9) and Z_(2^191) as unsigned binary integers, and  
adding them in the latter.

The point is here that the mathematical language defines more exactly  
what is going on, and illustrates the problem of combining arithmetic  
and binary operations. For use in a computer, a binary(k) type might  
be useful.

> It could be handled at a
> higher level, but you'd then need an op to resize integers, which I
> can't find. This leads on to a can of worms involving truncations and
> extensions, arithmetic conversions, and so on. The actual usage of  
> these
> low-level ops turns out to be just as difficult as the low-level
> arithmetic itself.

And doing the bitwise operators on the binary level would be  
considerably faster than working on a higher level.

   Hans Aberg