[EMAIL PROTECTED] wrote:
> > > Notes
> > > ====
> > > They have not been extensively tested.
> >
> > They don't work. At least the Pentium4 binary doesn't work,
> > same problem as before. Is the patch installed?
>
> I found the problem. Updated binaries should be available in a couple
> of hours. I'll add a note to the web page. I tested the patch but then
> overwrote the patched file with the unpatched file.
>
> I should quit doing this late at night....
>
> Thanks for testing.
That's a relief. I've downloaded the 1.04a version and re-ran
all the tests where I first noticed divm() errors. I can't even
remember why I wrote this program but the important thing
is that it uses divm() with non-coprime parameters which
provokes the divm() bug.
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 a successful 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]
Here is the divm() bug in action. Note that when complete, NN=6286
which does not match N=6296.
## 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
Once the bug has corrupted gmpy, simple arithmetic no longer works:
## >>> print gmpy.mpz(8)*gmpy.mpz(3)
## 6
Now, with the patch installed into version 1.04:
>>> import gmpy
>>> gmpy.version()
'1.04'
>>> gmpy.divm(4,8,20)
mpz(3)
>>> gmpy.divm(4,8,20)
mpz(3)
>>> gmpy.mpz(20)
mpz(20)
>>> gmpy.mpz(8)
mpz(8)
>>> gmpy.mpz(4)
mpz(4)
Good! Things are now back to normal.
Re-running the above program multiple times ensuring
that divm() gets called repeatedly with non-coprime
parameters:
## changing to gmpy 1.04
## divm() should be fixed now
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 5420
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [1, 1, 1, 1, 1, 1, 1, 56]
## NN: 5416
## 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: [mpz(24), 1, mpz(-8), 1, 1, 1, 1, 56]
## NN: 5420
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 12328
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [2, 1, 1, 1, 1, 1, 1, 131]
## NN: 12324
## 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: [mpz(25), 1, mpz(-8), 1, 1, 1, 1, 131]
## NN: 12328
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 7448
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [2, 1, 1, 1, 1, 1, 1, 78]
## NN: 7448
## diff: 0
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 3212
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [1, 1, 1, 1, 1, 1, 1, 32]
## NN: 3208
## 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: [mpz(24), 1, mpz(-8), 1, 1, 1, 1, 32]
## NN: 3212
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 8648
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [2, 1, 1, 1, 1, 1, 1, 91]
## NN: 8644
## 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: [mpz(25), 1, mpz(-8), 1, 1, 1, 1, 91]
## NN: 8648
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 8756
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [1, 1, 1, 2, 1, 1, 1, 92]
## NN: 8752
## 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: [mpz(24), 1, mpz(-8), 2, 1, 1, 1, 92]
## NN: 8756
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 6740
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [2, 1, 1, 2, 1, 1, 1, 70]
## NN: 6736
## 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: [mpz(25), 1, mpz(-8), 2, 1, 1, 1, 70]
## NN: 6740
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 6528
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [2, 1, 1, 1, 1, 1, 1, 68]
## NN: 6528
## diff: 0
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 3004
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [1, 1, 1, 1, 1, 2, 1, 29]
## NN: 3004
## diff: 0
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 6772
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [1, 1, 1, 2, 2, 1, 1, 70]
## NN: 6768
## 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: [mpz(24), 1, mpz(-8), 2, 2, 1, 1, 70]
## NN: 6772
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 11320
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [1, 2, 1, 1, 1, 1, 1, 120]
## NN: 11320
## diff: 0
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 2248
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [2, 1, 1, 1, 2, 1, 1, 21]
## NN: 2244
## 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: [mpz(25), 1, mpz(-8), 1, 2, 1, 1, 21]
## NN: 2248
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 4604
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [1, 2, 1, 1, 1, 1, 1, 47]
## NN: 4604
## diff: 0
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 5820
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [2, 1, 1, 2, 1, 1, 1, 60]
## NN: 5816
## 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: [mpz(25), 1, mpz(-8), 2, 1, 1, 1, 60]
## NN: 5820
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 4092
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [1, 2, 1, 1, 2, 1, 1, 41]
## NN: 4092
## diff: 0
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 8048
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [1, 2, 1, 1, 2, 1, 1, 84]
## NN: 8048
## diff: 0
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 1992
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [1, 1, 1, 1, 1, 2, 1, 18]
## NN: 1992
## diff: 0
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 3740
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [1, 1, 1, 1, 1, 2, 1, 37]
## NN: 3740
## diff: 0
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 3336
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [2, 1, 1, 2, 1, 1, 1, 33]
## NN: 3332
## 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: [mpz(25), 1, mpz(-8), 2, 1, 1, 1, 33]
## NN: 3336
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 12460
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [2, 1, 1, 1, 2, 1, 1, 132]
## NN: 12456
## 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: [mpz(25), 1, mpz(-8), 1, 2, 1, 1, 132]
## NN: 12460
##
## >>> ================================ RESTART
================================
## >>>
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## gcd: 4
## N: 9540
## X: [8, 16, 20, 24, 40, 72, 84, 92]
## C: [1, 1, 1, 1, 1, 2, 1, 100]
## NN: 9536
## 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: [mpz(24), 1, mpz(-8), 1, 1, 2, 1, 100]
## NN: 9540
In every case, NN ended up equal to N, so divm() appears to
be working correctly now.
I also ran my Mersenne Hailstone test to check performance
(since the last time I ran it, I've added a GB of Ram to
my computer and re-coded my programs to be non-recursive).
In my Collatz research, in the place where I use divm()
the parameters are always co-prime, so I used gmpy 1.01
for months without discovering the bug.
## Python 2.4a3
## gmpy.version: 1.01
##
## Brute force search: gclass(2**i-1,xyz)
## Find 1st Generation k Type [1,2] Mersenne Hailstone
##
## 2**5-1 generation: 1
## 2**29-1 generation: 2
## 2**245-1 generation: 3
## 2**2189-1 generation: 4
## 2**19685-1 generation: 5
## 2**177149-1 generation: 6
##
## 27.97 seconds
##
## Closed form: Type12MH(k,i)
## Find ith, kth Generation Type [1,2] Mersenne Hailstone
## using the closed form equation
##
## 2**(6*((i-1)*9**(k-1)+(9**(k-1)-1)/2+1)-1)-1
##
## 2**5-1 generation: 1
## 2**29-1 generation: 2
## 2**245-1 generation: 3
## 2**2189-1 generation: 4
## 2**19685-1 generation: 5
## 2**177149-1 generation: 6
## 2**1594325-1 generation: 7
## 2**14348909-1 generation: 8
## 2**129140165-1 generation: 9
## 2**1162261469-1 generation:10
##
## 1.359 seconds
##
## Verify Type12MH Hailstones:
## Find ith, kth Generation Type (xyz) Hailstone
## using the non-recursive equation
##
##
(gmpy.divm(y**(k-1)-prev_gen[2],y-x,y**(k-1))/y**(k-2))*xyz[1]**(k-1)+prev_gen[3]
##
## where i=((hailstone-geni(k,1,xyz))/(xyz[1]**k))+1
##
## 2**5-1 generation: 1
## 2**29-1 generation: 2
## 2**245-1 generation: 3
## 2**2189-1 generation: 4
## 2**19685-1 generation: 5
## 2**177149-1 generation: 6
## 2**1594325-1 generation: 7
## 2**14348909-1 generation: 8
## 2**129140165-1 generation: 9
## 2**1162261469-1 generation:10
##
## 4.516 seconds
## Python 2.5c1
##
## gmpy.version: 1.04
##
## Brute force search: gclass(2**i-1,xyz)
## Find 1st Generation k Type [1,2] Mersenne Hailstone
##
## 2**5-1 generation: 1
## 2**29-1 generation: 2
## 2**245-1 generation: 3
## 2**2189-1 generation: 4
## 2**19685-1 generation: 5
## 2**177149-1 generation: 6
##
## 21.64 seconds
##
## Closed form: Type12MH(k,i)
## Find ith, kth Generation Type [1,2] Mersenne Hailstone
## using the closed form equation
##
## 2**(6*((i-1)*9**(k-1)+(9**(k-1)-1)/2+1)-1)-1
##
## 2**5-1 generation: 1
## 2**29-1 generation: 2
## 2**245-1 generation: 3
## 2**2189-1 generation: 4
## 2**19685-1 generation: 5
## 2**177149-1 generation: 6
## 2**1594325-1 generation: 7
## 2**14348909-1 generation: 8
## 2**129140165-1 generation: 9
## 2**1162261469-1 generation:10
##
## 1.375 seconds
##
## Verify Type12MH Hailstones:
## Find ith, kth Generation Type (xyz) Hailstone
## using the non-recursive equation
##
##
(gmpy.divm(y**(k-1)-prev_gen[2],y-x,y**(k-1))/y**(k-2))*xyz[1]**(k-1)+prev_gen[3]
##
## where i=((hailstone-geni(k,1,xyz))/(xyz[1]**k))+1
##
## 2**5-1 generation: 1
## 2**29-1 generation: 2
## 2**245-1 generation: 3
## 2**2189-1 generation: 4
## 2**19685-1 generation: 5
## 2**177149-1 generation: 6
## 2**1594325-1 generation: 7
## 2**14348909-1 generation: 8
## 2**129140165-1 generation: 9
## 2**1162261469-1 generation:10
##
## 4.25 seconds
Great! Everything seems to work perfectly.
I really, really, REALLY appreciate your making Windows binaries
of gmpy. Since all my Collatz research is now dependent on gmpy,
I can't upgrade Python until gmpy is upgraded. And with the
compiler woes I've been reading about, I was afraid gmpy might
not ever be upgraded (for Windows).
>
> Case
--
http://mail.python.org/mailman/listinfo/python-list
