(42S) matrix permanent

[Albert Chan]

(01-15-2024 02:45 PM)Werner Wrote:  dj=2 if >>k MOD 4 equals 3, else dj=-2 (I *add* dj*Mj, so my signs are swapped).

If matrix cells are non-negative, product of initial v (column sums) is biggest.
This is the reason my code does v[j] = v[j] - d[i]*M[i][j]

Trivia:
If n×n matrix are all ones, its' permanent = n!
First term alone give upper limit:            n^n / 2^(n-1) = 2 * (n/2)^n
For comparison, Stirling's approximation:     n! ~ √(2*pi*n) * (n/e)^n

n=1 --> 2*(n/2)^n = 1 = 1!
n=2 --> 2*(n/2)^n = 2 = 2!
n=3 --> 2*(n/2)^n = 6.75 > (6 = 3!)
n=4 --> 2*(n/2)^n = 32 > (24 = 4!)
...

Quote:Instead of trying to find the least significant bit of k, successively dividing by 2, I perform k MOD 4 right away ...

Nice optimizing trick!

Quote:I had a version using v,f and d vectors (even one using only the stack), but this latest version runs almost twice as fast.

Interestingly, LuaJIT code is faster (almost twice as fast) using v,f and d vectors.
This despite I already use C to code bit.ffs and bit.test.

It is perhaps due to LuaJIT have only 1 kind of number = IEEE double.
Bit manipulations required conversion of double to integer, then back to double.

Guessing which way is faster is hard. We have to code it to know it.