https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97459
--- Comment #11 from Thomas Koenig <tkoenig at gcc dot gnu.org> --- Created attachment 49438 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49438&action=edit Numbers a, b so that 2^b ≡ 1 mod a up to b=64, larger b taken if several solutions exist Here is the promised table of divisors for which this optimization is possible. For example, the line 9 60 means that the remainder of a division by 9 can be calculated by #define MASK60 ((1ul << 60) - 1) unsigned rem_9 (__uint128_t n) { __uint64_t a, b, c; a = n & MASK60; b = (n >> 60) && MASK60; c = (n >> 120); return (a+b+c) % 9; } The number of terms varies; for b=64, it is two terms; for 63 >= b >= 43, it is three terms, and for the rest, it is four terms. 67 is the first odd divisor for which there is no such shortcut, the next one is 83. Those are the only gaps below 100. Of course, if a is in the list, then a*2^n can be treated by shifting (like it was shown for a=10). Now, the interesting question, what to make of it.
