[Bug fortran/118499] Exponentiation of UNSIGNED is rejected

[tkoenig at gcc dot gnu.org via Gcc-bugs]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118499

--- Comment #20 from Thomas Koenig <tkoenig at gcc dot gnu.org> ---
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. So, I will probably settle for something like

  if (x & 1)
    return power_simple (x, n & 127);

  if (n > 8)
     return 0;

 return power_simple (x, n & 255);