[Python-Dev] Memory size overflows

[Jeff Epler]

On Wed, Oct 16, 2002 at 11:12:05AM -0400, Gerald S. Williams wrote:
> Guido van Rossum wrote:
> > I.e. a macro callable as
> >   SAFE_MULTIPLY(destination, src1, src2, on_overflow);
> > meaning roughly
> >   destination = src1 * src2;
> >   if (<overflow detected>)
> >      on_overflow;
> 
> > There are also additions...These are easier to test: if you add a small
> > positive constant to a size_t, and the result is smaller than the
> > original size_t, an overflow occurred.
> 
> Why not use the same trick for multiplication? For src1,src2 > 0,
> dest should always be >= MAX(src1,src2). SAFE_MULTIPLY 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