Algorithmische Konsequenzen algebraischer Formeln für die Partitionsfunktion?

Bruinier und Ono haben eine algebraische Formel für die Partitionsfunktion gefunden , von der weithin berichtet wurde, dass sie einen Durchbruch darstellt. Ich kann das Papier nicht verstehen, aber hat es algorithmische Konsequenzen für die schnelle Berechnung der Partitionsfunktion?

algorithms complexity-theory number-theory sdcvvc
quelle

Können Sie bitte einen Link zu der Erklärung zum Durchbruch bereitstellen? Ich würde gerne sehen, inwiefern es ein Durchbruch ist.

Jernej

@Jernej Es ist eine endliche explizite Formel für

. Zuvor hatten wir die Rademacher-Erweiterung, die eine unendliche Reihe ist, und verschiedene Rekursionsformeln.

p (n)

$p(n)$

Yuval Filmus

Antworten:

$p(n)$ $p(n)$ . Nach Calkin et al. "Die exakte Formel von Rademacher liefert einen sehr schnellen Algorithmus".

$\mathcal{Q}_n$ $h(-24n+1)$ $h(-24n+1) = \Theta(n)$ $\Theta(n)$ $p(n)$ (rechnerisch gesehen), obwohl Letzteres zugegebenermaßen erfordert $\Omega(n)$ Erinnerung.

Yuval Filmus
quelle

In der Tat zeige ich in (1), dass die Rademacher-Formel theoretisch quasi-optimal (und heuristisch praktisch optimal) ist, wenn sie sehr sorgfältig implementiert wird.

Fredrik Johansson