BigInteger to String in Any Base with F#
Tags: fsharp
Published: 2019-03-10 12:57:36

---
title: BigInteger to String in Any Base with F#
published: true
tags: fsharp
canonical_url: https://stu.dev/bigint-to-string-in-any-base-fsharp/
---

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`](https://docs.microsoft.com/en-us/dotnet/api/system.numerics.biginteger?view=netstandard-2.0) aka `bigint` (the [type abbreviation](https://fsharpforfunandprofit.com/posts/type-abbreviations/) 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.

```fsharp
// 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`:

```fsharp
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).

```fsharp
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:

```fsharp
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.