1) Currently, the calculations always use integers (mpz) for computation, on the assumption that integer arithmetic is fastest. Investigate whether rational number arithmetic (with mpqs) is just as fast.
2) If part 1 is successful, transition to calculating directly on the canonical form, instead of inflating and then computing.
2) If part 2 of this issue is done, consider removing the "mergesort-style" computation, and making a specialized matrix multiplication that makes use of the fact that at every step, 3 out of the 4 matrix elements are either 0 or 1, which should theoretically make computation of each step very simple.
1) Currently, the calculations always use integers (
mpz) for computation, on the assumption that integer arithmetic is fastest. Investigate whether rational number arithmetic (withmpqs) is just as fast. 2) If part 1 is successful, transition to calculating directly on the canonical form, instead of inflating and then computing. 2) If part 2 of this issue is done, consider removing the "mergesort-style" computation, and making a specialized matrix multiplication that makes use of the fact that at every step, 3 out of the 4 matrix elements are either 0 or 1, which should theoretically make computation of each step very simple.