BigInteger to String in Any Base with F#

I spend a lot of time persuading people that F# is not about maths and finance, it's a great general purpose language that shines in many areas (such as domain modelling). However I've been playing around with some maths lately, and F# is my go-to for this, so here's a post.

As the numbers we do arithmetic with get increasingly larger, the usual numeric types in .NET quickly fall short, with Int32.MaxValue being 2147483647, and Int64.MaxValue being 9223372036854775807. When we need to go beyond this we can use BigInteger aka bigint (the type abbreviation in F#) which can represent an arbitrarily large integer.

I had the need to print a bigint in any given base (not just decimal, binary, hexadecimal...), and to my surprise, there was nothing out of the box to do this.

The code

First I want to turn a bigint into a list of digits.

// int -> bigint -> int list
let bigintToDigits b source =
    let rec loop (b : int) num digits =
        let (quotient, remainder) = bigint.DivRem(num, bigint b)
        match quotient with
        | zero when zero = 0I -> int remainder :: digits
        | _ -> loop b quotient (int remainder :: digits)
    loop b source []

Things to note;

• The inner function is recursive (given by the rec keyword), and the outer function just kicks it off with the initial empty digit list. Here b is the base (base is a keyword, unfortunately).
• Recursion is often used in functional languages as an alternative to mutable state within loops, and in many cases can lead to a more natural expression of an algorithm/routine. Recursion in F# doesn't overflow the stack and is fast, provided it is tail call optimizable like in this case (i.e. the last thing the function does is call itself, or returns out).
• We divide by the base and take the remainder as the least significant digit, then we pass accumulated digits into the loop, along with the quotient and keep going until we get a quotient of 0.
• bigint.DivRem returns a quotient and a remainder out parameter, with F# we can treat methods without parameters as if it returned a tuple of the result and the out parameter.
• Usually, we could pattern match with 0 as a literal, but because 0I (bigint zero) is a "non-primative literal", we aren't allowed to use it as a constant pattern. Hence the when zero = 0I syntax.
• :: is the cons operator, we can use it to construct F# lists, the part to the left is prepended to the part on the right.
• F# calls a spade a spade - list<'a> is a linked list, while the C# List<T> is type abbreviated in F# to what it really is, a ResizeArray:

type ResizeArray<'T> = System.Collections.Generic.List<'T>

Now we have a list of digits, let's have a function to convert it to a string (this only supports bases up to 16 at the moment).

let digitsToString source =
    source
    |> List.map (fun (x : int) -> x.ToString("X").ToLowerInvariant())
    |> String.concat ""

Putting this together, if we want to print a bigint in base 16, we do:

let printBigintAsHex source =
    let bigintToHex = bigintToDigits 16
    source |> bigintToHex |>  digitsToString |> printf "%s"

I couldn't find anything on Google or Stack Overflow to do this, so I thought I'd share it here so that it'll show up next time someone looks for it.