unsigned 32 bit arithmetic type?

"Martin v. Löwis" martin at v.loewis.de
Wed Oct 25 19:46:33 CEST 2006


Robin Becker schrieb:
> I can see the advantage in the summation case where all the numbers are
> known positive, however the full problem includes cases where there's an
> "adjustment" to the sum and that usually ends up like this
> 
>     adjustment = unpack('>l', table[8:8+4])[0]
>     checksum = add32(checksum, -adjustment)
> 
> so in those cases I just assumed I needed to force the result into the
> right form before doing the addition.

No, you don't. In modular arithmetic, congruency extends to all integral
numbers (of a congruency class), both positive and negative.
Computations always yield the same result no matter what representative
of the congruency class is chosen. IOW,

  if a ≡ b (mod n) and c ≡ d (mod n), then
  (a+b) ≡ (c+d) ≡ (a+d) ≡ (b+d) (mod n)

> Clearly we can only overflow the
> 31 bits just once, but don't negative numbers have a potentially
> infinite number of ones at the top?

The representation of negative numbers is finite (or else it wouldn't
fit into memory). This is achieved by not storing negative number
in two-th complement, but instead as (sign, absolute-value) pair.

This doesn't cause any problems for the modular arithmetic.

>>>> hex(0xFFFFFFFFL-1)
> '0xFFFFFFFEL'
>>>> hex(0xFFFFFFFFL + (-1&0xFFFFFFFFL))
> '0x1FFFFFFFEL'
> 
> so I think maybe I need to fix at least some of the numbers going into
> the add32 function.

As I said: you need to fix the final outcome:

py> x = 0xFFFFFFFFL
py> hex(x)
'0xFFFFFFFFL'

py> x += (-1&0xFFFFFFFFL)
py> hex(x)
'0x1FFFFFFFEL'
py> hex(x & 0xFFFFFFFFL)
'0xFFFFFFFEL'

py> x += (-1&0xFFFFFFFFL)
py> hex(x)
'0x2FFFFFFFDL'
py> hex(x & 0xFFFFFFFFL)
'0xFFFFFFFDL'

py> x += (-1&0xFFFFFFFFL)
py> hex(x)
'0x3FFFFFFFCL'
py> hex(x & 0xFFFFFFFFL)
'0xFFFFFFFCL'

and so on. Whether you perform the modulo operation after
each step, or only at the end, has no impact on the result.

Regards,
Martin



More information about the Python-list mailing list