Can constant propagation transform integer powers of -1 to an if/else?

General Usage Performance
1 
julia> @btime (n -> [iseven(k) ? 1 : (-1) for k in 1:n])(500);
  890.571 ns (1 allocation: 4.06 KiB)

julia> @btime (n -> [(-1)^k for k in 1:n])(500);
  6.170 μs (1 allocation: 4.06 KiB)

It would be great if the latter could be transformed into the former through constant propagation. I wonder if there are edge cases where this won’t hold?

1 Like
2

I think you should be able to add a special case here:

But, optimizing for special cases like this is detrimental for the performance of the general case, so I’m not sure this would be a good idea.

Another possibility would be using parser tricks like with literal_pow, but that has its own issues.

1 Like
3

The FastPow.jl package will do this transformation.

2 Likes
4

k is not a constant here so it’s something other than constant propagation. I’m not sure where a -1 branch should be put if that’s the way to do it. It also occurs to me, the branch shouldn’t just be for -1, right; any negative value to the power of a k::Integer can check k for evenness to calculate the sign and compute the absolute value to that power, and so (-1)^k should boil down to 1^k with its own 1 branch.

5

I sometimes like to define ^ on the function - so that I can write (-)^n instead of (-1)^n and have it be efficient

julia> Base.:(^)(::typeof(-), n::Int) = iseven(n) ? 1 : (-1);

julia> Base.literal_pow(::typeof(^), ::typeof(-), ::Val{n}) where {n} = (-)^n;

julia> (-)^-1
-1

julia> (-)^-2
1

julia> (-)^100
1
6 
Base.:(^)(::Val{-1},n)=(-1)^mod(n,2)
Base.:(^)(::Val{-1},n)=(-1)^(n & 1)