This project implements a high-performance arithmetic system in Rust that reimagines how integers can be represented and manipulated. Instead of the traditional binary representation, this system encodes integers as prime exponent vectors—where each number is mapped to its unique prime factorization, stored as a vector of exponents.
This alternative representation enables elegant, vectorized implementations of arithmetic operations such as:
- GCD (Greatest Common Divisor) via componentwise
min - LCM (Least Common Multiple) via componentwise
max - Multiplication as vector addition
- Division as vector subtraction (when exact)
These operations become extremely efficient once numbers are already in this format.
The core idea is to compare three different GCD and LCM implementations:
- Native – A standard binary GCD/LCM implementation in pure Rust.
- Hybrid – A combination of native methods with prime-based optimizations.
- Pure (PFS) – A fully PFS-based approach using SIMD acceleration and lookup tables.
Unfortunately, a pure PFS approach is currently limited by the overhead of integer factorization: converting a standard integer into its PFS form (i.e., factorizing) is computationally expensive and often not practical for large inputs. Many factorization algorithms lie in NP, making them inefficient for frequent runtime use.
That said, once the numbers are in PFS form, many operations (especially multiplication and division of exact multiples) become significantly faster and more predictable. Future advances in factorization — particularly via Shor’s algorithm on quantum computers — could make full adoption of PFS-based computation viable, especially for large integers.
To evaluate performance, a benchmarking GUI was built using eframe and egui, including:
- Plotting runtime comparisons of all three styles (Native, Hybrid, Pure)
- Toggling visibility of individual curves
- Displaying metadata such as memory usage and cache hit rates
- A summary panel of system resources (e.g., memory consumption of LUTs, power tables, and prime lists)
The benchmarks span bit widths from 4 to 32 bits, each tested over 1000 iterations per size, to provide statistically meaningful runtime data.
The main goals of the project were to:
- Explore novel number representations beyond base-2 encoding
- Implement PFS-based arithmetic in practice
- Compare hybrid algorithms against classic approaches
- Visualize empirical performance data in a clean and interactive GUI
The most significant bottleneck remains conversion overhead: the need to factor numbers to enter or exit PFS form. If this step could be eliminated or greatly accelerated, PFS would become a strong candidate for replacing traditional arithmetic in niche performance-critical applications.