Modular arithmetic

[WorldSEnder]

I wanted to come up with a better implementation for primality. Basic modular arithmetic should probably be tackled first but they might go hand in hand.

[MatthewDaggitt]

What are the current problems? And what would your suggestion be?

[WorldSEnder]

My biggest suggestion would be implementing finite field operations for Fin - multiplication, addition, subtraction and division alongside with the usual theorems - as binary operations on Fin. If those exist, I'm sorry for overlooking them.

After that, it might be beneficial to be less dependent on the representation of Nat. As numbers get bigger, modular arithmetic under some power of 2, say 2^1024 is - in my mind - better formulated in terms of Bin rather than Nat.

[MatthewDaggitt]

My biggest suggestion would be implementing finite field operations for Fin - multiplication, addition, subtraction and division alongside with the usual theorems - as binary operations on Fin. If those exist, I'm sorry for overlooking them.

Nope, you haven't missed them. If you'd be interested in coming up with an efficient implementation that'd be great!

After that, it might be beneficial to be less dependent on the representation of Nat. As numbers get bigger, modular arithmetic under some power of 2, say 2^1024 is - in my mind - better formulated in terms of Bin rather than Nat.

Yup, I think @mechvel has suggested something similar in #65. It's quite a big project though as Data.Bin isn't very developed and probably needs to be slightly rethought at some point.

[oisdk]

I tried to do this a little in the past. I found that Fin didn't really work well as a modular arithmetic type. I had better luck with the following:

infix 4 _≥_
data _≥_ (m : ℕ) : ℕ → Set where
  m≥m : m ≥ m
  m≥p : ∀ {n} → m ≥ suc n → m ≥ n

Mod : ℕ → Set
Mod = ∃ ∘ _≥_

(The Mod is kind of a misnomer: numbers in base-10, for instance, would be "mod-9")

Addition can be implemented with the same efficiency as on N:

infixl 6 _+_
_+_ : ∀ {n} → Mod n → Mod n → Mod n
(_ , x) + (ys , y) = go x ys y
  where
  go : ∀ {n m} → n ≥ m → ∀ ys → n ≥ ys → Mod n
  go m≥m ys y = ys , y
  go (m≥p x) zero y = _ , x
  go (m≥p x) (suc ys) y = go x ys (m≥p y)

I also have linear implementations of to/from N.

With Fin, the issue is that to check for "overflow" takes O(n) time, so + and so on implemented in the usual way are O(n^2).

[MatthewDaggitt]

Interesting read, thanks!

I found that Fin didn't really work well as a modular arithmetic type.

Yup, I've also run into this problem!

With Fin, the issue is that to check for "overflow" takes O(n) time, so + and so on implemented in the usual way are O(n^2).

I think you can implement it in O(n) time (with a big constant) by converting both to Nat, performing the addition, checking for overflow, subtracting if necessary, and then converting back again. But obviously it's incredibly ugly to work with and prove anything about...

It looks like your definitions might be a good fit for using to reimplement Data.Digit at some point...

[oisdk]

Yeah, I think I might have an O(n) conversion from Fin -> Mod and back lying around somewhere, which would allow for O(n) _+_. There's also this blog post for modular types

[oisdk]

this is a slightly fuller working through of the technique

[mechvel]

Fast modular arithmetic needs fast divMod, and fast divMod needs fast comparison <-cmp on natural nubmers. The Binary representation helps to exponentially reduce the cost order of these operations.
For Binary, there are libraries by A. Alekseev
https://github.com/Rotsor/BinDivMod,
by M. Escardo
http://www.cs.bham.ac.uk/~mhe/agda-new/BinaryNaturals.html,
and of mine
https://github.com/mechvel/Binary-3.2,
https://github.com/mechvel/Binary-4

There is a particular point about the performance of <-cmp on Bin in Binary-4.
If the user program analyses the proof construction in the result of <-cmp, this may cause exponential cost growth for evaluation.
Binary-3.2 is free of this danger, because _<_ on Bin is defined there as a lexicographic order on bit lists. But Binary-4 is more clearly written.

[Taneb]

I've been working on "unnormalised" modulo arithmetic here: https://github.com/Taneb/antlion/blob/master/src/NumberTheory/ModularArithmetic.agda

[mechvel]

Currently standard library applies built-in arithmetic for Nat. If we take this, then there does not remain any performance question about modulo arithmetic. Because divMod works fast, "almost in constant time".
If we insist on really proved arithmetic on natural numbers NN, with representing a number by a list of macro-digits, then the modulo arithmetic performance is the performance of really proved divMod for NN.

[MatthewDaggitt]

I've been working on "unnormalised" modulo arithmetic here: https://github.com/Taneb/antlion/blob/master/src/NumberTheory/ModularArithmetic.agda

Looks pretty good. We'd welcome a contribution to the library! My only comment is that it might be useful to expose a more obviously ternary version of the relation, i.e. _≈_%_