https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118499
--- Comment #23 from Mikael Morin <mikael at gcc dot gnu.org> ---
(In reply to Thomas Koenig from comment #20)
> Right now, I am doing unsigned**unsigned. This is already a
> bit larger than I originally thought. After this is committed,
> we can still discuss how to extend it, I think.
>
> There is actually an interesting simplification for modulo
> arithmetic, which I do not know how to do in C.
>
> Assume that power_simple() does the same as our current library
> implementation.
>
> What I would like to do is
>
> uint8_t
> power_complicated (uint8_t x, uint32_t n)
> {
> uint8_t zeros = __builtin_ctz (x);
> uint8_t n_times_zeros;
>
> if (x == 0)
> return 0;
>
> if (zeros == 0)
> return power_simple (x, n & 127);
>
> n_times_zeros = n * zeros;
> if (n_times_zeros > 8)
> return 0;
>
> return power_simple (x, n & 255);
> }
>
> (The n & 127 follows from Euler's theorem, because phi(2^n) = 2^(n-1)).
>
> So basically, a number with zeros trailing zeros to a power of x will
> be zero under modulo 2^8 arithmetic if the number of zeros times n
> is larger than 8. But I have not found a reasonable way to check if
> n * zeros has overflowed.
>
I agree it's not easy in the general case.
There is __builtin_mul_overflow that you can probably use (there are examples
in the C testsuite).
Or in this case, n can be bound beforehand to prevent overflow:
if (n >= 8)
return 0;
n_times_zeros = n * zeros;
if (n_times_zeros >= 8)
return 0;
Not very nice, but reasonable, isn't it?
