Rechnen — die Mathematik-Units

27 Units, die die rechnende Lücke der Standardbibliothek schließen: exakte Brüche, 128-Bit- und beliebig große Ganzzahlen, genaue Elementarfunktionen, lineare Algebra, Signalverarbeitung und Graphalgorithmen.

→ Standard Library · std.math · Welche Unit?

Geprüft mit lyxc 1.0.21A. Alle Angaben auf dieser Seite sind an den Quellen in aurum/std/ nachgemessen, nicht übernommen.

Warum es sie gibt

Der Bestand rechnete bis dahin schmal: std.math mit 28 Funktionen, std.stats rein ganzzahlig (ArrayVariance gibt int64 zurück), dazu std.matrix, std.vector (Festkomma) und std.ml. Was fehlte, war nicht ein einzelner Name, sondern ganze Gebiete — Nullstellensuche, Integration, Brüche, große Zahlen, Graphalgorithmen auf allgemeinen Graphen.

std.graph schließt eine Lücke, die man leicht übersieht. Die 65 Graph*-Funktionen im Bestand sind ein Wissensgraph — Knoten, Kanten, Attribute, Musterabfragen — und enthalten keinen einzigen Algorithmus. Kein Dijkstra, keine topologische Sortierung, kein Spannbaum. std.grid konnte Pfadfindung, aber nur auf Gittern; Straßennetze und Ablaufpläne sind keine Gitter. Die neue Unit trägt deshalb das Präfix Gph, weil Graph belegt ist.

Die Schichten

Der Abhängigkeitsgraph ist azyklisch mit maximaler Tiefe 3 — aus den import-Zeilen der 27 Quelldateien nachgerechnet. Jede Schicht ist für sich benutzbar.

Schicht	Units
0 — Basis	`bits` `feq` `sat` `dist` `sum` `modmath` `linalg` `fft` `sparse` `grid` `graph` `tensor` `wavelet` `crypto.ec`
1	`i128`←bits · `mathx`←feq · `money`←sat · `numeric`←sum · `convolve`←fft · `decomp`←linalg
2	`bignum`←bits,i128 · `rat`←i128 · `complex`←dist,feq,mathx · `prob`/`quat`/`autodiff`←mathx
3 — Spitze	`prime`←bignum,i128

Schicht 0 kommt allein mit dem Bestand aus. Gebraucht werden daraus nur acht Units: std.alloc, std.math, std.math.constants, std.io und vier Krypto-Einheiten (std.crypto.ct, std.crypto.hmac, std.crypto.rand, std.crypto.sha256).

Kollisionsfrei. 922 neue Funktionsnamen gegen 5496 im Bestand — die Schnittmenge ist leer. Nachgezählt über alle pub fn-Zeilen von aurum/std/; auch Datei- und Unit-Namen sind frei.

Übersetzen: der Stolperstein zuerst

<WRAP alert> Die installierte Standardbibliothek ist veraltet (#1578). Unter /usr/include/lyx/units/std/ liegt eine ältere Fassung, deren SinF64 keine Argumentreduktion hat. Nachgemessen:

$ lyxc s.lyx --std-path=/pfad/zu/aurum -o s && ./s
SinF64(-6.282895) = 0.000290

$ lyxc s.lyx -o s && ./s
SinF64(-6.282895) = -11.893474

Der Sollwert ist 0.00029030717. Die zweite Fassung verlässt den Wertebereich des Sinus — ein Ergebnis, das gar nicht auftreten kann. Betroffen ist nur, wer ohne --std-path oder -I übersetzt; im Repository ist beides korrekt. </WRAP>

Alle Beispiele dieser Seiten sind deshalb so übersetzt:

lyxc mein.lyx --std-path=/pfad/zu/aurum -o mein && ./mein

Wie geprüft wurde

Jede Unit trägt eine selbstprüfende Batterie — zusammen 3700 Einzelprüfungen. Der Nachweis mischt drei Arten, und die Mischung ist der Punkt:

Art	Was sie leistet
Fremde Sollwerte	82 082 Fuzz-Vergleiche gegen numpy, `fractions`, `cmath`, `decimal` und OpenSSL — Referenzen, die sich keine Zeile Code mit der Lyx-Fassung teilen
Invarianten ohne Referenz	Parseval, Moore-Penrose, Metrikaxiome, Unitarität, Cauchy-Schwarz, kanonische Form nach jeder Bruchrechnung. Gelten unabhängig von jeder fremden Zahl
Negativkontrollen	Belegen, dass die Prüfung überhaupt anschlägt: dass die naive Divisionsformel bei 1e200 wirklich überläuft, dass der 64-Bit-Kreuzvergleich bei zwei bestimmten Brüchen wirklich das falsche Vorzeichen liefert

Warum die dritte Art nötig ist. Eine grüne Batterie ohne Negativkontrolle belegt womöglich nichts. Beim Nachweis, dass Dijkstra an negativen Kanten scheitert, lieferte das erste Gegenbeispiel zufällig das richtige Ergebnis — der Zielknoten war noch nicht abgeschlossen. Dijkstra versagt nur, wenn eine negative Kante einen bereits abgeschlossenen Knoten betrifft. Wer das nicht trifft, hat eine grüne Prüfung ohne Aussage.

Was heute noch stört

Drei Punkte, die beim Einsatz zählten. Zwei davon sind inzwischen behoben; die veraltete installierte Standardbibliothek bleibt.

Die Struct-Rückgabe legt keinen Speicher mehr an (#1580 behoben). Vorher zwei mmap je Rückgabe ohne munmap — 1,6 GB bei 200 000 Rückgaben. Mit 1.1.2E nachgemessen: 0,05 s, 6,3 MB, neun mmap im ganzen Programm. Betrifft std.quat, std.complex und std.rat.

Atan2F64 achtet auf das Vorzeichen der Null (#1577 behoben): atan2(-0.0, -1.0) ergibt mit 1.1.2E -3.141592, atan2(+0.0, -1.0) ergibt +3.141592 — die Fallreihenfolge folgt jetzt C99 F.10.1.4. Die Genauigkeit bleibt zehnstellig; wer mehr braucht, nimmt MxAtan2 aus std.mathx.
Die installierte stdlib ist veraltet (#1578, siehe oben).

Verhältnis zum Bestand

Einige neue Funktionen sind als Ersatz für Defektes entstanden. Zwei dieser Defekte sind inzwischen behoben — nachgemessen mit 1.0.21A gegen Python, über alle Randfälle (0, 1, 255, 0x12345678, −1, 2⁶³−1) identisch:

Bestand	Zustand (1.0.21A)	Entsprechung
`PopCount` (`std.math`)	behoben, #1545 geschlossen	`BitsPopCount` — gleichwertig
`RotateLeft32` (`std.conv`)	behoben, #1546 geschlossen	`BitsRotl32` — gleichwertig
`ArrayVariance` (`std.stats`)	rein ganzzahlig	`std.prob` (f64)
`IsPrime`/`NextPrime` (`std.math`)	int64, Probedivision	`std.prime` (beliebig groß)

Die ersten beiden Zeilen sind damit keine Gründe mehr, die Unit zu wechseln. std.bits bleibt trotzdem die reichere Wahl — es bringt BitsRotlN für beliebige Breiten mit, dazu Bitmengen mit Rank und Select, die es im Bestand nicht gibt.

std.crypto.ec tritt neben das vorhandene std.crypto.ecc, ohne es anzutasten. Über eine Ablösung ist damit nichts entschieden.

Die Units im Überblick

Zahldarstellung

Unit	Inhalt
std.i128	128 Bit als Wortpaar: volles 64×64-Produkt, Division mit Rest, Dezimalein- und -ausgabe bis 39 Stellen, (a·b)/c ohne Überlauf
std.bignum	Ganze Zahlen beliebiger Größe; modulare Potenz per Division und Montgomery — letztere rund 47× schneller
std.rat	Exakte Brüche auf zwei `int64`. Jeder Überlauf wird gemeldet statt abgeschnitten; beste Näherung inklusive Semikonvergenten
std.money	Geldbeträge als skalierte Ganzzahlen: sieben Rundungsarten, MwSt vor- und rückwärts, Aufteilen ohne verlorene Cents
std.sat	Sättigungsarithmetik: geprüfte und sättigende Grundrechenarten, Breitensättigung 8/16/32 Bit, Clamping

Bitebene

Unit	Inhalt
std.bits	SWAR-Popcount über alle 64 Bit, Schieben mit gesättigter Weite, Rotation in beliebiger Breite, Bitmengen mit Rank und Select
std.feq	Fließkommavergleiche: absolut, relativ, ULP; Klassifikation, `NextUp`/`NextDown`, totale Ordnung, Rundungsmodi

Analysis

Unit	Inhalt
std.mathx	Elementarfunktionen mit Argumentreduktion: exp/log bitgenau statt siebenstellig, sin/cos/tan (π/2 in sechs 21-Bit-Stücken), atan/atan2, expm1/log1p, Hyperbolische
std.complex	Komplexe Zahlen als Wert: Division nach Smith und Betrag über `hypot` (überlaufsicher bis 1e200), Verzweigungsschnitte nach C99 Annex G
std.numeric	Nullstellen (Bisektion/Brent/Newton), Integration (Simpson/Romberg/Gauß), Splines, ODE inklusive steifer Löser und Randwertprobleme
std.sum	Kompensiertes Summieren: exakte Zweiersumme, Neumaier, Shewchuk exakt, Welford für laufende Streuung

Lineare Algebra

Unit	Inhalt
std.linalg	Dichte Matrizen: LU/QR/Cholesky, Solve/Det/Inverse, Rang, Ausgleichsrechnung, Eigenwerte nach Jacobi
std.decomp	Echte SVD (einseitiges Jacobi), Pseudoinverse, Rang-k-Näherung, polare Zerlegung, allgemeine Eigenwerte per QR-Iteration
std.sparse	Dünnbesetzte Vektoren als sortierte Index/Wert-Paare: Skalarprodukt und Kosinus im Gleichlauf, Normen, Top-k
std.tensor	Komplexe Tensoren mit allgemeiner Kontraktion; darauf Quantenzustände, Gatter, reduzierte Dichtematrix, Verschränkungsentropie
std.quat	Quaternionen in Hamilton-Konvention: Produkt, Slerp, Achse/Winkel, Euler, Rotationsmatrix

Signalverarbeitung

Unit	Inhalt
std.fft	Radix-2 und Bluestein für beliebige Länge, Faltung und Korrelation, Fensterfunktionen, Spektren
std.convolve	Faltung und Filter direkt oder per FFT, vier Randmodi, 2D und separabel, Overlap-Add, fertige Kerne
std.wavelet	DWT mit Haar und Daubechies db2/db3/db4, mehrstufig, 2D nach Mallat, Schwellenwerte, Entrauschen

Diskretes

Unit	Inhalt
std.graph	Gewichtete Graphen in CSR: BFS/DFS, topologische Sortierung, Dijkstra und Bellman-Ford, Kruskal, SCC, Max-Flow nach Dinic mit minimalem Schnitt
std.grid	Gitter mit 4er- und 8er-Nachbarschaft ohne Eckenschnitt, Bresenham und Sichtlinie, BFS-Distanzkarten, Dijkstra und A*
std.modmath	Restklassen: erweiterter Euklid, CRT, Ordnung, Primitivwurzeln, Legendre/Jacobi, Tonelli-Shanks
std.prime	Miller-Rabin für beliebig große Zahlen, deterministische Zeugenmenge unter 3,3·10²⁴, Suche der nächsten Primzahl

Anwendung

Unit	Inhalt
std.prob	Statistik in f64: deskriptiv, `erf` und `lgamma`, unvollständige Gamma und Beta, neun Verteilungen, t- und Chi²-Test
std.dist	Abstandsmaße mit überlaufsicherem `hypot`: Euklid, Manhattan, Chebyshev, Minkowski, Kosinus, Hamming, Jaccard
std.autodiff	Automatische Differenzierung: Rückwärtsmodus auf Band (alle Gradienten in einem Lauf), Vorwärts-Dualzahlen
std.crypto.ec	P-256 und secp256k1: konstantzeit Montgomery-Leiter, vollständige RCB-Formeln, RFC-6979-ECDSA, ECDH, SEC1, DER

Doppelungen, die keine sind

Drei Units bringen Euclid und Manhattan mit — das ist Absicht, nicht Wildwuchs:

Unit	Darstellung
`std.dist`	dichte `f64`-Vektoren
`std.sparse`	dünnbesetzt, sortierte Index/Wert-Paare
`std.grid`	ganzzahlige Gitterkoordinaten

Drei Darstellungen, drei Implementierungen. Ebenso gibt es Gcd in std.modmath (int64) und std.bignum (beliebig groß).

Letzte Aktualisierung: 2026-08-16 · Schichtengraph, Symbolzahl und Kollisionsfreiheit aus aurum/std/ nachgerechnet; #1578 nachgemessen.