Speed up euler function

[bawolk]

For high precision calculations, this simple change more than doubles the speed. Raising [0,1] to the kth power requires a large number of multiplications, most of which involve zero.

[akc]

I'm not against this change, but I wonder if there might be a more general solution. E.g. the weight transform and the (^!) function (in Series) might also benefit from this type of optimization. Would the modification of mul you suggested a while ago provide the desired optimization?

[bawolk]

The proposal would certainly be applicable to the weight transform as well. It doesn't work for the (^!) function though. That function operates on more general series so there is no easy way to construct the powers other than actual multiplication. My mul optimization has the potential to speed up multiplication where one or both of the multiplicands have degree much lower than the precision. Thus, if the precision is p and the degrees m and n, normal multiplication (i.e., convolution), is O(p^2), but my mul would be O(mn). Taking x^k using my mul would be O(k^2), better than straight convolution, but the "euler speedup" approach requires no multiplications to compute x^k.

[bawolk]

I take back what I said about (^!). I see that you indeed compute powers of x in the case where the exponent is not an integer, so the euler speedup approach would be useful there.

[akc]

Thanks for explaining. How about we add xpow as an exported function of Series?

...
module HOPS.GF.Series
    ( module HOPS.GF.Rat
    , Series (..)
    -- * Constructions
    , polynomial
    , series
    , xpow
    -- * Accessors
...

xpow :: KnownNat n => Int -> Series n
xpow k = polynomial (Proxy :: Proxy n) $ replicate k 0 ++ [1]

...

We can then use it in euler and weight, and maybe more places.

For the purpose of keeping the code clean, we should probably get rid of mkX too.

[bawolk]

We would lose a little speed, since we would then have an additional p subtractions or additions when 1 (+/-) x^k is computed. But I think the clarity of the code is much better and probably worth the extra cpu cycles. Should I revise the pull request accordingly?

[akc]

That would be great.

[bawolk]

I made the proposed changes and also removed a few unneeded KnownNat n constraints in euler, o, leadingExponent, and isConstant functions. The compiler kept complaining about them.

[akc]

Thanks!