====== 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. → [[lyx_-_programmiersprache:units|Standard Library]] · [[lyx_-_programmiersprache:units:math|std.math]] · [[lyx_-_programmiersprache:guides:welche-unit|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 ===== **Die installierte Standardbibliothek ist veraltet** ([[https://github.com/SEOLizer/LyX-Compiler/issues/1578|#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. 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** ([[https://github.com/SEOLizer/LyX-Compiler/issues/1580|#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** ([[https://github.com/SEOLizer/LyX-Compiler/issues/1577|#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**, [[https://github.com/SEOLizer/LyX-Compiler/issues/1545|#1545]] geschlossen | ''BitsPopCount'' — gleichwertig | | ''RotateLeft32'' (''std.conv'') | **behoben**, [[https://github.com/SEOLizer/LyX-Compiler/issues/1546|#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 ^ | [[lyx_-_programmiersprache:units:i128|std.i128]] | 128 Bit als Wortpaar: volles 64×64-Produkt, Division mit Rest, Dezimalein- und -ausgabe bis 39 Stellen, (a·b)/c ohne Überlauf | | [[lyx_-_programmiersprache:units:bignum|std.bignum]] | Ganze Zahlen beliebiger Größe; modulare Potenz per Division und Montgomery — letztere rund 47× schneller | | [[lyx_-_programmiersprache:units:rat|std.rat]] | Exakte Brüche auf zwei ''int64''. Jeder Überlauf wird gemeldet statt abgeschnitten; beste Näherung inklusive Semikonvergenten | | [[lyx_-_programmiersprache:units:money|std.money]] | Geldbeträge als skalierte Ganzzahlen: sieben Rundungsarten, MwSt vor- und rückwärts, Aufteilen ohne verlorene Cents | | [[lyx_-_programmiersprache:units:sat|std.sat]] | Sättigungsarithmetik: geprüfte und sättigende Grundrechenarten, Breitensättigung 8/16/32 Bit, Clamping | ==== Bitebene ==== ^ Unit ^ Inhalt ^ | [[lyx_-_programmiersprache:units:bits|std.bits]] | SWAR-Popcount über alle 64 Bit, Schieben mit gesättigter Weite, Rotation in beliebiger Breite, Bitmengen mit Rank und Select | | [[lyx_-_programmiersprache:units:feq|std.feq]] | Fließkommavergleiche: absolut, relativ, ULP; Klassifikation, ''NextUp''/''NextDown'', totale Ordnung, Rundungsmodi | ==== Analysis ==== ^ Unit ^ Inhalt ^ | [[lyx_-_programmiersprache:units:mathx|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 | | [[lyx_-_programmiersprache:units:complex|std.complex]] | Komplexe Zahlen als Wert: Division nach Smith und Betrag über ''hypot'' (überlaufsicher bis 1e200), Verzweigungsschnitte nach C99 Annex G | | [[lyx_-_programmiersprache:units:numeric|std.numeric]] | Nullstellen (Bisektion/Brent/Newton), Integration (Simpson/Romberg/Gauß), Splines, ODE inklusive steifer Löser und Randwertprobleme | | [[lyx_-_programmiersprache:units:sum|std.sum]] | Kompensiertes Summieren: exakte Zweiersumme, Neumaier, Shewchuk exakt, Welford für laufende Streuung | ==== Lineare Algebra ==== ^ Unit ^ Inhalt ^ | [[lyx_-_programmiersprache:units:linalg|std.linalg]] | Dichte Matrizen: LU/QR/Cholesky, Solve/Det/Inverse, Rang, Ausgleichsrechnung, Eigenwerte nach Jacobi | | [[lyx_-_programmiersprache:units:decomp|std.decomp]] | Echte SVD (einseitiges Jacobi), Pseudoinverse, Rang-k-Näherung, polare Zerlegung, allgemeine Eigenwerte per QR-Iteration | | [[lyx_-_programmiersprache:units:sparse|std.sparse]] | Dünnbesetzte **Vektoren** als sortierte Index/Wert-Paare: Skalarprodukt und Kosinus im Gleichlauf, Normen, Top-k | | [[lyx_-_programmiersprache:units:tensor|std.tensor]] | Komplexe Tensoren mit allgemeiner Kontraktion; darauf Quantenzustände, Gatter, reduzierte Dichtematrix, Verschränkungsentropie | | [[lyx_-_programmiersprache:units:quat|std.quat]] | Quaternionen in Hamilton-Konvention: Produkt, Slerp, Achse/Winkel, Euler, Rotationsmatrix | ==== Signalverarbeitung ==== ^ Unit ^ Inhalt ^ | [[lyx_-_programmiersprache:units:fft|std.fft]] | Radix-2 und Bluestein für beliebige Länge, Faltung und Korrelation, Fensterfunktionen, Spektren | | [[lyx_-_programmiersprache:units:convolve|std.convolve]] | Faltung und Filter direkt oder per FFT, vier Randmodi, 2D und separabel, Overlap-Add, fertige Kerne | | [[lyx_-_programmiersprache:units:wavelet|std.wavelet]] | DWT mit Haar und Daubechies db2/db3/db4, mehrstufig, 2D nach Mallat, Schwellenwerte, Entrauschen | ==== Diskretes ==== ^ Unit ^ Inhalt ^ | [[lyx_-_programmiersprache:units:graph|std.graph]] | Gewichtete Graphen in CSR: BFS/DFS, topologische Sortierung, Dijkstra und Bellman-Ford, Kruskal, SCC, Max-Flow nach Dinic mit minimalem Schnitt | | [[lyx_-_programmiersprache:units:grid|std.grid]] | Gitter mit 4er- und 8er-Nachbarschaft ohne Eckenschnitt, Bresenham und Sichtlinie, BFS-Distanzkarten, Dijkstra und A* | | [[lyx_-_programmiersprache:units:modmath|std.modmath]] | Restklassen: erweiterter Euklid, CRT, Ordnung, Primitivwurzeln, Legendre/Jacobi, Tonelli-Shanks | | [[lyx_-_programmiersprache:units:prime|std.prime]] | Miller-Rabin für beliebig große Zahlen, deterministische Zeugenmenge unter 3,3·10²⁴, Suche der nächsten Primzahl | ==== Anwendung ==== ^ Unit ^ Inhalt ^ | [[lyx_-_programmiersprache:units:prob|std.prob]] | Statistik in f64: deskriptiv, ''erf'' und ''lgamma'', unvollständige Gamma und Beta, neun Verteilungen, t- und Chi²-Test | | [[lyx_-_programmiersprache:units:dist|std.dist]] | Abstandsmaße mit überlaufsicherem ''hypot'': Euklid, Manhattan, Chebyshev, Minkowski, Kosinus, Hamming, Jaccard | | [[lyx_-_programmiersprache:units:autodiff|std.autodiff]] | Automatische Differenzierung: Rückwärtsmodus auf Band (alle Gradienten in einem Lauf), Vorwärts-Dualzahlen | | [[lyx_-_programmiersprache:units:crypto:ec|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.