Elm Natural

A pure Elm library for computing with the natural numbers, ℕ = { 0, 1, 2, ... }.

What's available?

The natural numbers from 0 to 10

• zero
• one
• two
• three
• four
• five
• six
• seven
• eight
• nine
• ten

Ways to create natural numbers from an Int

• fromSafeInt
• fromInt

Ways to create natural numbers from a String

• fromSafeString
• fromString (supports binary, octal, decimal, and hexadecimal inputs)
• fromBinaryString
• fromOctalString
• fromDecimalString
• fromHexString
• fromBaseBString

Comparison operators

• ==
• /=
• compare
• isLessThan
• isLessThanOrEqual
• isGreaterThan
• isGreaterThanOrEqual
• max
• min

Predicates for classification

• isZero (i.e. == 0)
• isOne (i.e. == 1)
• isPositive (i.e. > 0)
• isEven
• isOdd

Arithmetic

• add
• sub (saturating subtraction)
• mul
• divModBy (Euclidean division)
• divBy
• modBy
• exp

A way to convert to an Int

• toInt (use with caution since it discards information)

Ways to convert to a String

• toString (same as toDecimalString)
• toBinaryString
• toOctalString
• toDecimalString
• toHexString
• toBaseBString

Examples

Factorial

The factorial of a natural number n, denoted by n!, is the product of all positive natural numbers less than or equal to n. The value of 0! is 1 by convention.

import Natural as N exposing (Natural)

fact : Natural -> Natural
fact n =
    if N.isZero n then
      N.one

    else
      N.mul n <| fact (N.sub n N.one)

What's 100!?

N.toString (fact (N.fromSafeInt 100)) == "93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000"

More examples

A few more examples can be found in the examples/src directory.

• Fibonacci.elm - Computes up to the 1000th Fibonacci number.
• Pi.elm - Computes the first 100 digits of π.
• E.elm - Computes the first 100 digits of e.
• BaseConversion.elm - Converts decimal numbers to their binary, octal, and hexadecimal representations.

Performance

This library tries to provide a reasonably efficient implementation of extended-precision arithmetic over the natural numbers while being written purely in Elm and making extensive use of lists. Within that context it gives reasonable performance.

Natural / comparison

  compare (2^26)^9999-1 and (2^26)^9999-2
  runs/second     = 5,839
  goodness of fit = 99.86%

Natural / multiplication

  999..9 (100 9's) * 999..9 (100 9's)
  runs/second     = 53,038
  goodness of fit = 99.79%

Natural / division with remainder

  (999..9 (100 9's))^2 / 999..9 (100 9's)
  runs/second     = 6,852
  goodness of fit = 99.91%

Natural / exponentiation

  2 ^ 1000
  runs/second     = 15,623
  goodness of fit = 99.7%

N.B. You can read benchmarks/README.md to learn how to reproduce the above benchmark report and to see how this library compares against cmditch/elm-bigint.

Resources

• Chapter 17 - Extended-Precision Arithmetic of C Interfaces and Implementations: Techniques for Creating Reusable Software helped me to design, organize and implement the library.
• Lua Bint inspired the examples.
• Per Brinch Hansen, Multiple-Length Division Revisited: A Tour of the Minefield helped me implement an efficient divide-and-correct algorithm for division with remainder.