search

Bodigrim / arithmoi

Number theory: primes, arithmetic functions, modular computations, special sequences
http://hackage.haskell.org/package/arithmoi
MIT License
147 stars 40 forks source link

Reason behind Math.NumberTheory.Powers.Modular deprecation? #219

Open Javran opened 2 years ago

Javran commented 2 years ago

I see the module is deprecated in https://github.com/Bodigrim/arithmoi/commit/77e70a15456a461271412b8bccd672623389f090 but I'm not really sure about the rationale, nor do I find any migration guide on this.

Tell me if I'm not using Data.Mod.Word right, but it becomes painfully verbose when m is only available at runtime, for example powModWod becomes this:

powModWord :: Word -> Word -> Word -> Word
powModWord b e m = case someNatVal (fromIntegral m) of
  Just (SomeNat (_ :: Proxy md)) ->
    unMod (fromIntegral @_ @(Mod md) b ^% e)
  Nothing -> error "unreachable"

Not to mention language pragmas one has to enable.

Bodigrim commented 2 years ago

As described in documentation, powMod is dangerously polymorphic, as we have little idea how a behaves when multiplication overflows. And powModInteger can be accessed directly from integer-gmp, so arithmoi does not bring much added value.

Javran commented 2 years ago

I see - wasn't aware of integer-gmp and powModInteger it provides, that would also do (probably also mention that in addition to mod package in the doc?). I agree with you on powMod, but I feel powModWord is still worth keeping just so that user doesn't feel the need of type level naturals don't have to route things through it.

I also just noticed that Math.NumberTheory.Powers.Modular calls GMP interface directly while Data.Mod.Word does it a bit more on the Haskell side - performance speaking is either approach better than the others or it's a bit situational?

Bodigrim commented 2 years ago

I believe that type level numbers provide a less error-prone way of doing modular arithmetic, and API should encourage users into this route. A PR, adding a mention of powModInteger from integer-gmp and naturalPowMod from ghc-bignum, would be welcome.

Data.Mod.Word is slightly (10%-25%) faster than GMP call.

Javran commented 2 years ago

I understand the benefit of having it on type level, probably wouldn't commit to it though - my major concern are (1) the machinery is a bit much converting between type and term level (as demostrated in OP) (2) some constrants tend to spread everywhere, in this case it's KnownNat.

I'll see if I can find time to do a PR, probably also refer to this issue should powModWord be gone in future.