fixed size integer arithmetic
Hans Aberg
haberg at math.su.se
Mon Sep 3 21:35:02 CEST 2007
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
More information about the gmp-discuss
mailing list