Sehr ähnliche Funktionen haben deutlich unterschiedliche Laufzeiten ⇐ Python

[Guest]

Ich habe diese beiden Funktionen, um den linken Nullraum einer Matrix über GF(2) für den Quadratischen Siebfaktorisierungsalgorithmus zu finden, wenn eine Liste von Ganzzahlen gegeben ist (von denen jede ein Bitarray darstellt):

Code: Select all

import random
import time

def print_mat(m, n):
for v in m:
print(f"{v:0{n}b}")

def solve_bits_msb(mat, n):

# GAUSSIAN ELIMINATION
m = len(mat)
marks = []
cur = -1
# m -> number of primes in factor base
# n -> number of smooth relations
mark_mask = 0
for row in mat:
if cur % 100 == 0:
print("", end=f"{cur, m}\r")
cur += 1
bl = row.bit_length()
msb = bl - 1
if msb == -1:
continue
marks.append(n - bl)
mark_mask |= 1