Metraipolis › archive › dc_a85c45e35005
Improved Tristate Multiplication With Formalization in Rocq — arXiv:2609.39009
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.39009
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T15:17:54.557Z
- SHA-256 of the archived text
5eaca7b788fdd5307eeb80c84a9be8f75d9cb3f150b266999f66e038249904f9- Stable URL of this page
https://metraipolis.com/documento/dc_a85c45e35005
How to cite
Improved Tristate Multiplication With Formalization in Rocq — arXiv:2609.39009 — arXiv (en), https://arxiv.org/abs/2609.39009 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a85c45e35005 (Metraipolis archive dc_a85c45e35005, sha256 5eaca7b788fdd5307eeb80c84a9be8f75d9cb3f150b266999f66e038249904f9)
BibTeX
@misc{dca85c45e35005,
title = {Improved Tristate Multiplication With Formalization in Rocq — arXiv:2609.39009},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.39009},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a85c45e35005; sha256 5eaca7b788fdd5307eeb80c84a9be8f75d9cb3f150b266999f66e038249904f9},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.39009. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We give a new multiplication algorithm for tristate numbers improving upon the state-of-the-art implementation from the Linux kernel in terms of precision and formal proofs. Our algorithm is significantly more precise as shown by experimental evaluation (at the peak, giving better results in 95.59% cases compared to the previous work for 31-bit samples). Importantly, we achieve this additional precision with performance comparable to the previous algorithm, as demonstrated by benchmarks. Finally, we formalize and prove the soundness of the algorithm in the Rocq proof assistant, adding to the trust in the resulting implementation. Our algorithm is now part of the upstream Linux kernel. Our soundness proof in Rocq for the new multiplication algorithm works for all bit widths, while the SAT/SMT-based machine-checked proof accompanying the previous algorithm was restricted to 8 bits. We also provide Rocq proofs for the soundness and optimality of the newly added tnum union operation and the existing tnum addition algorithm from the Linux kernel. Our optimality proof for tnum addition presents a simpler and straightforward lemma compared to prior work. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-01 in cs.LO). Categorie arXiv: Logic in Computer Science (cs.LO). Pagina del lavoro: https://arxiv.org/abs/2609.39009 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-07T14:51:10.184Z dalla pagina https://arxiv.org/catchup/cs.LO/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).