[Python-Dev] Memory size overflows (original) (raw)

Jeff Epler jepler@unpythonic.net
Wed, 16 Oct 2002 10:26:10 -0500

On Wed, Oct 16, 2002 at 11:12:05AM -0400, Gerald S. Williams wrote:

Guido van Rossum wrote: > I.e. a macro callable as > SAFEMULTIPLY(destination, src1, src2, onoverflow); > meaning roughly > destination = src1 * src2; > if () > onoverflow;

> There are also additions...These are easier to test: if you add a small > positive constant to a sizet, and the result is smaller than the > original sizet, an overflow occurred. Why not use the same trick for multiplication? For src1,src2 > 0, dest should always be >= MAX(src1,src2). SAFEMULTIPLY could be implemented something like this: [...]

Is this correct for all operands? Consider 4-bit types, with valid values 0..15. 3*9 == 27, but 27%16 == 11 and 11>max(3, 9) There seem to be 15 distinct operand pairs for which this fails in the 4-bit case.

def check(m):
    for x in range(m):
        for y in range(x, m):
            z = x*y
            w = z % m
            if z != w and w>x and w>y: yield x, y, z, w

>>> print list(check(16))
[(3, 9, 27, 11), (3, 10, 30, 14), (4, 6, 24, 8), (4, 7, 28, 12), (4,
11, 44, 12), (5, 5, 25, 9), (5, 6, 30, 14), (5, 9, 45, 13), (6, 7,
42, 10), (6, 10, 60, 12), (6, 13, 78, 14), (7, 9, 63, 15), (7, 11,
77, 13), (10, 11, 110, 14), (11, 13, 143, 15)]

>>> print len(list(check(256))
9915

Jeff