Seminar Details
Modular Arithmetic with Trinomial Moduli
- Start Date: April 24, 2025
- Event Start Time: 5:00 PM
- Event End Time: 6:00 PM
- Seminar Series: Experimental Math Seminar
- Presenter(s): Robert Dougherty-Bliss - Dartmouth College
- Event Location: Online Event
- Event Additional Info: <p>Presented Via Zoom: <a href="https://rutgers.zoom.us/j/91865817691">https://rutgers.zoom.us/j/91865817691</a></p> <p>Password: 6564120420</p> <p>For further information see: <a href="https://sites.math.rutgers.edu/~zeilberg/expmath/">https://sites.math.rutgers.edu/~zeilberg/expmath/</a></p>
- Presentation Type: Stand Alone Presentation
- Abstract:
A popular approach to speed up computations is to reduce the input modulo several relatively prime numbers, do arithmetic on the residues, then reconstruct the result at the end. This improves the running time if the moduli (and their pairwise inverses) have "nice" binary shapes, but only a limited number of such moduli are known. I will discuss a new system of moduli related to a family of trinomials. This system has shown promising real-world performance, can produce arbitrarily many moduli, and its elements can be computed quickly. I will mention some theoretical limitations of the system based on roots of unity and graph colorings, and point out what remains to be discovered.
Joint work with Mits Kobayashi, Natalya Ter-Saakov, and Eugene Zima.