AtCoder.Extra.Math

Extra math module.

Examples

>>> import AtCoder.Extra.Math qualified as M
>>> import Data.Semigroup (Product(..), Sum(..))
>>> getProduct $ M.power (<>) 32 (Product 2)
4294967296

>>> getProduct $ M.stimes' 32 (Product 2)
4294967296

>>> getProduct $ M.mtimes' 32 (Product 2)
4294967296

Since: 1.0.0.0

Binary exponential

power :: (a -> a -> a) -> Int -> a -> a

Calculates \(s^n\) with custom multiplication operator using the binary exponentiation technique.

The internal implementation is taken from stimes, but power uses strict evaluation and is often much faster.

Complexity

• \(O(\log n)\)

Constraints

• \(n \gt 0\)

Since: 1.0.0.0

stimes' :: Semigroup a => Int -> a -> a

Strict stimes.

Complexity

• \(O(\log n)\)

Constraints

• \(n \gt 0\)

Since: 1.0.0.0

mtimes' :: Monoid a => Int -> a -> a

Strict mtimes.

Complexity

• \(O(\log n)\)

Constraints

• \(n \ge 0\)

Since: 1.0.0.0