Alex said:
Thanks! I hope to package up a release early next week, and to include
these.
Alex
I downloaded the binaries and ran some Big Arithmetic tests:
First, I wanted to see how version 1.0 handled the test which
is a typical problem for which I use gmpy. A Type [1,2] Mersenne
Hailstone is an object I encounter in my Collatz Conjecture
research. There are an infinite number of them. Every 9th (starting
from the 5th) generation 1 hailstone is a generation 2 hailstone.
Every 9th (starting from the 5th) generation 2 hailstone is a
generation 3 hailstone, etc.
In this case, a closed form equation can be used to directly find
the ith member of the kth generation. But not all hailstone types
have closed form equations. For those, I use a recursive function
that uses divm().
The test makes three passes. The first is a brute force search
through every Mesenne Number from 1 to 177150 bits. A test
determines what generation each is (most are not Type [1,2] and
evaluate to generation 0). The test prints the first occurrence of
each generation.
The second pass uses the closed form equation to directly
calculate the 1st member of each generation. These results must
match those found in the brute force search.
Finally, the third pass takes each hailstone found in the second
pass, calculates it's absolute offset from the first general
Type [1,2] hailstone of the corresponding generation, and calls
the recursive function to see if it calculates the same hailstone
found in pass 2 and pass 1.
==========================================
gmpy.version: 1.0 (with divm() replaced by invert())
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
7.031 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
0.657 seconds
Verify Type12MH Hailstones:
Find ith, kth Generation Type (xyz) Hailstone
using the recursive equation
(gmpy.divm(y**(k-1)-prev_gen[2],y-x,y**(k-1))/y**(k-2))*y**(k-1)+prev_gen[3]
where i=((hailstone-geni(k,1,xyz))/(y**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
0.078 seconds
==========================================
NOTE: Brute force search could not reach generation 6 without
locking up
Switching to gmpy version 1.01
==========================================
gmpy.version: 1.01 (now using divm())
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
0.579 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
0 seconds
Verify Type12MH Hailstones:
Find ith, kth Generation Type (xyz) Hailstone
using the recursive equation
(gmpy.divm(y**(k-1)-prev_gen[2],y-x,y**(k-1))/y**(k-2))*y**(k-1)+prev_gen[3]
where i=((hailstone-geni(k,1,xyz))/(y**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
0.015 seconds
==========================================
NOTE: Wow, what an improvement!
How far can I go now?
==========================================
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
31.92 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
0.234 seconds
Verify Type12MH Hailstones:
Find ith, kth Generation Type (xyz) Hailstone
using the recursive equation
(gmpy.divm(y**(k-1)-prev_gen[2],y-x,y**(k-1))/y**(k-2))*y**(k-1)+prev_gen[3]
where i=((hailstone-geni(k,1,xyz))/(y**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
8.766 seconds
==========================================
NOTE: Brute force can now reach generation 6, but won't try
anything higher.
Generation 9 is a 129 million bit number!
Can we get to generation 10?
==========================================
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
32.14 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
51.83 seconds
Verify Type12MH Hailstones:
Find ith, kth Generation Type (xyz) Hailstone
using the recursive equation
(gmpy.divm(y**(k-1)-prev_gen[2],y-x,y**(k-1))/y**(k-2))*y**(k-1)+prev_gen[3]
where i=((hailstone-geni(k,1,xyz))/(y**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
Traceback (most recent call last):
File "C:\Python23\user\gmpy ver 1.01\MHtest.py", line 64, in ?
i = (h-a0)/(xyz[1]**g)
==========================================
NOTE: No, ran out of virtual memory. Probably due to the
recursion and having to store the pass 2 numbers.
I used to have a sign in my lab saying
"Test to Destruction"
But the paranoid schizophrenic field engineer
got freaked out by it and the boss made me
take it down.
==========================================
Excellent work guys!
Not only is the divm() bug fixed but it looks like we got a
significant performance increase.
