package euler

  1. Overview
  2. Docs

Module EulerSource

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.

Sourceval 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).

Sourceval 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

Sourcemodule Arith : sig ... end

Arithmetic on overflowing integers.

Sourcemodule Modular : sig ... end

Modular arithmetic.

Sourcemodule Diophantine : sig ... end

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

Sourcemodule Primes : sig ... end

Prime numbers and integer factorization.

Sourcemodule Farey : module type of Farey