#RPython 5.4.1, n ≈ 3132 (4337 seconds)
from rpython.rlib.rtime import time
from rpython.rlib.rarithmetic import r_int, r_uint
from rpython.rlib.rrandom import Random
from rpython.rlib.rposix import pipe, close, read, write, fork, waitpid
from rpython.rlib.rbigint import rbigint
from math import log, ceil
bitcounts = bytearray([0])
for i in range(16):
b = bytearray([j+1 for j in bitcounts])
bitcounts += b
def bitcount(n):
bits = 0
while n:
bits += bitcounts[n & 65535]
n >>= 16
return bits
def main(argv):
if len(argv) < 2:
write(2, 'Usage: %s NUM_THREADS [N]'%argv[0])
return 1
threads = int(argv[1])
if len(argv) > 2:
n = int(argv[2])
rnd = Random(r_uint(time()*1000))
m = []
for i in range(n):
row = []
for j in range(n):
row.append(1 - r_int(rnd.genrand32() & 2))
m.append(row)
else:
m = []
strm = ""
while True:
buf = read(0, 4096)
if len(buf) == 0:
break
strm += buf
rows = strm.split("\n")
for row in rows:
r = []
for val in row.split(' '):
r.append(int(val))
m.append(r)
n = len(m)
a = []
for row in m:
val = 0
for v in row:
val = (val << 1) | -(v >> 1)
a.append(val)
pids = []
handles = []
total = rbigint.fromint(0)
for i in range(threads):
r, w = pipe()
pid = fork()
if pid:
close(w)
pids.append(pid)
handles.append(r)
else:
close(r)
total = run(n, a, i, threads)
write(w, total.str())
close(w)
return 0
for pid in pids:
waitpid(pid, 0)
for handle in handles:
strval = read(handle, 256)
total = total.add(rbigint.fromdecimalstr(strval))
close(handle)
print total.rshift(n-1).str()
return 0
def run(n, a, mynum, threads):
start = (1 << n-1) * mynum / threads
end = (1 << n-1) * (mynum+1) / threads
batches = int(ceil(n * log(n) / (63 * log(2))))
dtotal = rbigint.fromint(0)
for delta in xrangerange(start, end):
pdelta = rbigint.fromint(1 - ((bitcount(delta) & 1) << 1))
for vi in arange(batches):
pdeltapbatch = pdelta.int_mul1
for j in range(i, n, batches):
pbatch *= n - (bitcount(delta ^ va[j]) << 1)
pdelta = pdelta.int_mul(pbatch)
dtotal = dtotal.add(pdelta)
return dtotal
def target(*args):
return main
$ time ./matrix-permanent-c 8 30
166962626444656648395059644858368
real 0m200m8.914s582s
user 2m471m8.312s656s
sys 0m0.048s000s
