Re: Integer arithmetic, multiplication overflow

In article <pan.2005.06.08.19.07.10.580117@xxxxxxxxx>,
Tomek <t.koziara@xxxxxxxxx> wrote:

> Hi,
>
> I trying to solve the following thing:
> Having two finite precision unsigned integer numbers A and B,
> and knowing that maximal represented number is X,
> calculate A*B - X, in case of A*B overflow. Use only
> basic algebraic operations.
>
> Any hints welcome.
> Thanks,
>
> Tomek

You can do something similar by representing each of your numbers in
some base, say m, prefereably smaller that sqrt(X), as arrays of m-ary
"digits", and define your multiplication in terms of those arrays.
If X or X+1 should be an of form m^n for positive integers m and n, with
n between say 2 and 6 inclusive, it should be quite straightforward.

In purely algebraic terms, it can be done using m, m^2, etc, as a
moduli in modular arithmetic.
.