module confict? gmpy and operator

[mensanator at aol.com]

Tim Peters wrote:
> [mensanator at aol.com]
>
> Please try to give a complete program that illustrates the problem.
> For example, this program shows no problem on my box (Windows Python
> 2.4.3):

Sorry about that. I thought the problem was more obvious.

<working example snipped>

> I don't see a problem of any kind, and there's no way to guess from
> the above what you did that mattered.  It's hard to believe that
> merely importing any module (operator or otherwise) has any effect on
> gmpy.

That's what I was asking about. I don't know enough about low level
stuff to know. I've been using gmpy for years with the only problem
being the memory leak that was fixed in the latest version. I've never
used operator before, so I just assumed that's where the problem was.

But I don't see why the program behaves the way it does either.

Here's the complete program:

import gmpy
import random
import operator

def product(a,b):
    return a*b

def gcdlist(X):
    mingcd = 999999
    for i in xrange(1,len(X)):
        g = gmpy.gcd(X[i-1],X[i])
        if g<mingcd: mingcd = g
    return mingcd

X = [8,16,20,24,40,72,84,92]
g = gcdlist(X)
s = sum(X)

print '       X:',X
print '     gcd:',g

N = 0
while N<s:
    N = g * random.randint(s,3333)
print '       N:',N

if N>s:
    C = [1 for i in X]
    diff = N-s
    done = False
    i = -1
    XL = -len(X)
    while not done:
        while diff>=X[i]:
            C[i] += 1
            diff -= X[i]
        if diff==0:
            done = True
        else:
            i -= 1
            if i<XL:
                done = True
    NN = sum(map(operator.__mul__,X,C))
    print '       X:',X
    print '       C:',C
    print '      NN:',NN
    print '    diff:',diff
    print
    if diff>0:
        p = 0
        q = 1
        done = False
        while not done:
            gpq = gmpy.gcd(X[p],X[q])
            if diff % gpq == 0:
                done = True
            else:
                q += 1
                if q==len(X):
                    p += 1
                    q = p + 1
        print 'p: %d    q: %d' % (p,q)
        a = gmpy.divm(diff,X[p],X[q])
        b = (X[p]*a - diff)/X[q]
        print 'a: %d    b: %d    X[p]: %d    X[q]: %d' %
(a,b,X[p],X[q])
        if C[q]==b:
            print 'non-zero adjustment'
            print 'a: %d    b: %d' % (a + X[q],b + X[p])
            C[p] += a + X[q]
            C[q] -= b + X[p]
        else:
            C[p] += a
            C[q] -= b
        NN = sum(map(operator.__mul__,X,C))
        print '       X:',X
        print '       C:',C
        print '      NN:',NN
        print

This is what the output should look like

       X: [8, 16, 20, 24, 40, 72, 84, 92]
     gcd: 4
       N: 4492
       X: [8, 16, 20, 24, 40, 72, 84, 92]
       C: [1, 1, 1, 1, 1, 1, 2, 45]
      NN: 4488
    diff: 4

p: 0    q: 2
a: 3    b: 1    X[p]: 8    X[q]: 20
non-zero adjustment
a: 23    b: 9
       X: [8, 16, 20, 24, 40, 72, 84, 92]
       C: [24, 1, -8, 1, 1, 1, 2, 45]
      NN: 4492

X is a list of integers selected so that the GCD of the entire list
is >2.
N is selected to be greater than sum(X) and divisible by GCD(X).
C is initialized to [1,1,1,1,1,1,1,1].
NN is the sum of each X element multiplied by its corresponding C
element. The values of C are then adjusted until the difference
between N and NN is 0.

If a difference of 0 is unobtainable (in the example diff=4 is smaller
than the smallest element of X), then the program solves a linear
congruence by first finding a pair of X whose GCD divides diff
(8 and 20). For the solution a=3, b=1, we add three to C[0] and
subtract 1 from C[2] making
       C: [1, 1, 1, 1, 1, 1, 2, 45]
into
       C: [4, 1, 0, 1, 1, 1, 2, 45]

But I don't want any 0s in the list, only positive and negative
integers. Thus, in this example, a 0 adjustment is made:
       C: [24, 1, -8, 1, 1, 1, 2, 45]

Ok, now the problem. In the first three runs, diff was 0, so the
linear congruence was skipped. But in the fourth run, b=0
which indicates the error (8*3 evaluated to 6 resulting in b=0).


Note I tested gmpy after each run from the Idle prompt.
Once the failure occured, the problem continues to exist.
That's how I made that original demo, I wrote a simple test
AFTER gmpy had gotten funny.

>>>
       X: [8, 16, 20, 24, 40, 72, 84, 92]
     gcd: 4
       N: 12192
       X: [8, 16, 20, 24, 40, 72, 84, 92]
       C: [1, 1, 2, 1, 2, 1, 1, 129]
      NN: 12192
    diff: 0

>>> print gmpy.mpz(8)*gmpy.mpz(3)
24
>>> ================================ RESTART ================================
>>>
       X: [8, 16, 20, 24, 40, 72, 84, 92]
     gcd: 4
       N: 7340
       X: [8, 16, 20, 24, 40, 72, 84, 92]
       C: [1, 1, 1, 1, 1, 1, 2, 76]
      NN: 7340
    diff: 0

>>> print gmpy.mpz(8)*gmpy.mpz(3)
24
>>> ================================ RESTART ================================
>>>
       X: [8, 16, 20, 24, 40, 72, 84, 92]
     gcd: 4
       N: 8072
       X: [8, 16, 20, 24, 40, 72, 84, 92]
       C: [2, 1, 1, 1, 1, 2, 1, 84]
      NN: 8072
    diff: 0

>>> print gmpy.mpz(8)*gmpy.mpz(3)
24
>>> ================================ RESTART ================================
>>>
       X: [8, 16, 20, 24, 40, 72, 84, 92]
     gcd: 4
       N: 6296
       X: [8, 16, 20, 24, 40, 72, 84, 92]
       C: [2, 1, 1, 1, 2, 1, 1, 65]
      NN: 6292
    diff: 4

p: 0    q: 2
a: 3    b: 0    X[p]: 8    X[q]: 20
       X: [8, 16, 20, 24, 40, 72, 84, 92]
       C: [mpz(5), 1, mpz(1), 1, 2, 1, 1, 65]
      NN: 6286

>>> print gmpy.mpz(8)*gmpy.mpz(3)
6


Hey, maybe the gmpy divm() function isn't fixed after all:

IDLE 1.1a3
>>> import gmpy
>>> print gmpy.mpz(8)*gmpy.mpz(3)
24
>>> a = gmpy.divm(4,8,20)
>>> a
mpz(3)
>>> print gmpy.mpz(8)*gmpy.mpz(3)
6

Can you verify this?