Safe Haskell	None
Language	GHC2021

AtCoder.Extra.Math

Contents

Binary exponential

Description

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

Synopsis

power :: (a -> a -> a) -> Int -> a -> a
stimes' :: Semigroup a => Int -> a -> a
mtimes' :: Monoid a => Int -> a -> a

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

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

Strict stimes.

Complexity

\(O(\log n)\)

Constraints

\(n \gt 0\)

Since: 1.0.0

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

Strict mtimes.

Complexity

\(O(\log n)\)

Constraints

\(n \ge 0\)

Since: 1.0.0