improve naive base case of mzd_transpose

[Martin Albrecht]

{{{static inline mzd_t _mzd_transpose_direct(mzd_t DST, const mzd_t *A)}}} is quite naive and could be improved.

cf. http://www.codeguru.cn/Embedded/Hacker's-Delight/048.htm

[Martin Albrecht]

The old code:

sage: A = random_matrix(GF(2),10^4,10^4); t = cputime(); A.transpose(); cputime(t)
10000 x 10000 dense matrix over Finite Field of size 2                            
0.32495000000000007                                                               
sage: A = random_matrix(GF(2),10^4,2*10^4); t = cputime(); A.transpose(); cputime(t)
20000 x 10000 dense matrix over Finite Field of size 2
0.63790299999999966
sage: A = random_matrix(GF(2),2*10^4,10^4); t = cputime(); A.transpose(); cputime(t)
10000 x 20000 dense matrix over Finite Field of size 2
0.63990199999999975
sage: A = random_matrix(GF(2),2*10^4,2*10^4); t = cputime(); A.transpose(); cputime(t)
20000 x 20000 dense matrix over Finite Field of size 2
1.2918039999999995
sage: A = random_matrix(GF(2),3.2*10^4,3.2*10^4); t = cputime(); A.transpose(); cputime(t)
32000 x 32000 dense matrix over Finite Field of size 2
3.2575049999999992

With Wiki macro error: Changeset 140a8626e2ca not found. I get

sage: A = random_matrix(GF(2),10^4,10^4); t = cputime(); A.transpose(); cputime(t)
10000 x 10000 dense matrix over Finite Field of size 2
0.18697199999999992
sage: A = random_matrix(GF(2),10^4,2*10^4); t = cputime(); A.transpose(); cputime(t)
20000 x 10000 dense matrix over Finite Field of size 2
0.5399179999999999
sage: A = random_matrix(GF(2),2*10^4,10^4); t = cputime(); A.transpose(); cputime(t)
10000 x 20000 dense matrix over Finite Field of size 2
0.53291900000000014
sage: A = random_matrix(GF(2),2*10^4,2*10^4); t = cputime(); A.transpose(); cputime(t)
20000 x 20000 dense matrix over Finite Field of size 2
0.75088599999999994
sage: A = random_matrix(GF(2),3.2*10^4,3.2*10^4); t = cputime(); A.transpose(); cputime(t)
32000 x 32000 dense matrix over Finite Field of size 2
0.78888099999999994
sage: A.transpose().transpose() == A
True

[Martin Albrecht]

improve performance of mzd_transpose using Hacker's Delight bit-fiddling trick (closes: #15)

→ <<cset 1ee6b5b07417>>