News for hackers. Stuff that matters.
Re:Finding a billion factorials in 60 ms with SIMD by tmyklebu on Monday June 23, 2025 @04:41PM (#44359848)
Well, modular multiplication is faster than modular inverse, both asymptotically for large moduli and practically for almost all moduli I can think of. (2, 3, and 4 being notable exceptions!)

The article computes modular inverses of a_1, ..., a_n by:

- Computing (a_1 * ... * a_i) = (a_1 * ... * a_{i-1}) * a_i recursively

- Computing (a_1 * ... * a_n)^(-1) by square-and-multiply

- Computing (a_1 * ... * a_i)^(-1) = (a_1 * ... * a_{i+1})^(-1) a_{i+1} recursively.

- Computing a_i^(-1) = (a_1 * ... * a_i)^(-1) * (a_1 * ... * a_{i-1}) for each i.

The second step is a scalar operation, so its running time is immaterial as long as you aren't doing something too silly.

For my caveman brain, both Fermat's little theorem and square-and-multiply exponentiation are pretty easy to understand. Moreover, the code is going to be "defect-evident"---if I've gotten the logic wrong or forgotten integer promotions or modular reductions as in qsort's post, it'll quickly be clear by skimming the code.

There are no comments on this comment yet.