Module Euler

This is a library for arithmetic algorithms, primarily developed to solve Project Euler problems, although it is of more general use.

Toplevel values

Commonly useful functions not related to arithmetic.

val pow : mult:('a -> 'a -> 'a) -> unit:'a -> 'a -> int -> 'a

Generic fast exponentiation. pow ~mult ~unit x n is unit composed n times to the right with x, provided that n is non‐negative. For example:

pow ~mult:(^) ~unit:"x" "y" 5

yields "xyyyyy". Complexity: 𝒪(log(n)) calls to mult.

  • parameter mult

    the composition operator; should be associative.

  • parameter unit

    the left‐most operand of the product (most often, we use a neutral element for mult).

val memoized_fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b

Memoizing fixpoint combinator. Example use:

let fib = memoized_fix@@fun fib n ->
  if n < 2 then
    1
  else
    fib (n-1) + fib (n-2)

Modules on OCaml integers

module Arith : sig ... end

Arithmetic on overflowing integers.

module Modular : sig ... end

Modular arithmetic.

module Diophantine : sig ... end

Solving diophantine equations, i.e. equations on integers.

module Primes : sig ... end

Prime numbers and integer factorization.

module Farey : module type of Farey