REIST-Division: Eine implementierungsorientierte Formulierung zentrierter Restarithmetik – Theorie, Architekturanalyse und empirische Evaluation auf ARMv8-A, x86-64 und FPGA
Zusammenfassung
Zentrierte Restdarstellungen sind in der Zahlentheorie klassisch; der Beitrag dieser Arbeit ist ihre implementierungsorientierte Formulierung. Die REIST-Division (Remainder-Extended Inversion and Subtraction Technique) behandelt den Rest als vorzeichenbehafteten Korrekturterm in einem zentrierten Intervall und führt ihn als persistente Zustandsvariable durch iterative Aktualisierungsschleifen: Additive modulare Zustände werden ohne Division im Schleifenkörper durch höchstens eine ±B-Korrektur reduziert; die Korrektur ist verzweigungsfrei formulierbar und SIMD-vektorisierbar. Die Arbeit entwickelt die formalen Eigenschaften der zentrierten Division, grenzt sie von Balanced Modulo, Barrett- und Montgomery-Reduktion sowie Compiler-Optimierungen ab und begründet die Gewinne mikroarchitektonisch. Die Evaluation auf ARMv8-A (Apple M2 Pro) und x86-64 (Intel Core i9-14900K) misst für modulare Additionszähler 2,1–4,4× (ARM) bzw. 7,9–8,9× (x86-64), für polynomielle modulare Addition bis zu 17,0× (AVX2); Die historischen Kontrollmessungen zur allgemeinen Restberechnung zeigen keinen entsprechenden Gewinn. Eine FPGA-Implementierung (Gowin GW2A-18) benötigt einen Takt pro Aktualisierung bei 161,8 MHz und 101 Logikzellen, gegenüber vier Takten, 8,1 MHz und 1276 Zellen eines herstellergenerierten Divisions-IP. Diese Zahlen dokumentieren die damaligen Implementierungen. Die vorliegende Textrevision korrigiert die CPU-Listings für ungerade Moduli; sie enthält keine neue Laufzeitmessung. Ein Vergleich mit einer ebenfalls bereichsbeschränkten nicht-negativen Additionskorrektur bleibt für einen eigenständigen Repräsentationsvorteil erforderlich.
Inhaltsübersicht
- 1. Einleitung — Beitrag und Einordnung
- 2. Die klassische Division und ihre Asymmetrie
- 3. Die REIST-Division — Definition, formale Eigenschaften, algebraische Interpretation
- 4. Abgrenzung zu bestehenden Verfahren (Balanced Modulo, Barrett, Montgomery, Compiler-Optimierung)
- 5. Implementierung — skalare und verzweigungsfreie Korrektur, SIMD-Vektorisierung
- 6. Anwendungsdomänen als Modellierungsperspektive
- 7.–8. Experimenteller Aufbau und Ergebnisse (ARMv8-A, x86-64)
- 9. Mikroarchitektonische Analyse
- 10. Hardware-Evaluation: FPGA-Implementierung (Gowin GW2A-18)
Schlagwörter
Zitierhinweis
Stepan, R. (2026). REIST-Division: Eine implementierungsorientierte Formulierung zentrierter Restarithmetik.
Zenodo. https://doi.org/10.5281/zenodo.21206471
Links & Registries
Katalogeintrag & Dokumentfassungen
Korrigierte deutsche Langfassung zu persistenten zentrierten Restzuständen. Intervallgrenzen und Implementierungsvoraussetzungen sind präzisiert; die historischen CPU-/FPGA-Werte sind keine neue Evaluation. Ein fairer Vergleich mit beschränkter nichtnegativer Addition bleibt erforderlich.