permanent of square matrix

[Albert Chan]

(01-24-2024 04:03 PM)John Keith Wrote:  This line, v -= 2*d[j]*M[j] results in an array (or list) multiplication in every iteration.

I guess it depends on programming language used.

Python was using numpy for fast v list update, rewritten it without multiply does not gain much.
Note: 2*d[j] is just a number, not a list

For LuaJIT, the cost is smaller still (OP 9×9 matrix, speedup under 5%)
Array access cost a lot more than multiply. Bit operations cost even more.
(this is just relatively speaking ... LuaJIT is FAST!)

Below LuaJIT version is the one I kept.

Code:

function permanent(M)
    local p,n, d,f,v = 1,#M, {},{},{}
    if n==1 then return M[1][1] end
    for j = 1,n do
        d[j] = 2
        f[j] = j
        local t = 0
        for i = 1,n do t = t+M[i][j] end -- sum col
        v[j], p = t, p*t
    end
    while true do
        local i = f[1]
        if i >= n then return -p/2^(n-1) end
        local di, r, t = d[i], M[i], 1
        for j=1,n do v[j] = v[j]-di*r[j]; t = t*v[j] end
        p = t - p
        d[i] = -d[i]
        f[1] = 1
        f[i] = f[i+1]
        f[i+1] = i+1
    end
end

I gave up on the 5% speedup, for cleaner code.

Still, for OP 9×9 matrix, its speed is doubled the bitwise version. (post #9)