So uhhh, yeah. Writing is hard, time-consuming, and often frustrating. Coming up with topics worth writing about is even harder and littered with false starts. I figured I should try to get out something (as long as that something isn't about AI 🙄). So, let's try a "simple" article about a topic I had to learn the hard way early in my career: numerical instability.

AI use disclaimer:

• 🧠 Article concept and outline
• 🧠 Article body and writing
• 🧠 + 🤖 Proofreading
• 🧠 Code Examples
• 🤖 Performance optimization and correctness review

So my day job involves a lot of processing of credit card payments. Most of the time we don't have to do much math on them. Our system gets a request for a payment, we send it along to a bank, more or less as-is. But sometimes we do, and when we do we have to be careful that we do so in a way that doesn't cause people to become confused or very, very angry.

Although my day job is mostly C#, F# is always in my heart and never far from my mind because idiomatic F# presents interesting solutions that are often simpler than their C# or Java counterparts. So, partly for myself and partly for the reader's edification, this post will use F# code examples. That being said, and to be flatly honest, there are some painful surprises when working with advanced features in F# that you expect to work, but sometimes they don't because of an exotic compiler bug. I was eventually able to work around it and get all my code to compile successfully. I'm still glad I chose F# for this post, warts and all.

What is F#

Let's start with a brief introduction to F#. F# is a programming language for the .NET platform that descends from the Caml family of functional programming languages. It brings a compact syntax and a style that emphasizes reusing smaller building blocks of code that I and many others believe can lead to fewer bugs.

The first thing that you need to know about F# is that all of your favorite .NET types and methods are the same. The way that you instantiate those types and call those methods looks pretty much the same. So that is easy to pick up on. The main differences in F# are going to be in the following areas:

• Code blocks are whitespace-delimited, like Python
• Big emphasis on records, union types and match expressions
• Writing and composing functions is very easy
• Recursion is often preferred over iteration
• Basically everything is immutable by default
• Basically everything is generic by default
• Some fancy features that might blow your mind 🤯

Of special note in this post will be the F# types double/float and single/float32 which are identical to double/System.Double and float/System.Single in C# respectively. In F# a literal with a decimal point (e.g. 1.1 or even .1) is implicitly a double and a numeric literal with a suffix of f (e.g. 1.1f) is a single/float32.

Ok, so back to the actual topic.

The problem with floating-point numbers: they almost work

Before I start trashing floats, I do want to say that IEEE 754 is an incredibly powerful, flexible, and successful specification. It works for many, many use cases. However, it has some specific weaknesses...

One codebase I worked in many years ago used float32. Something like this:

type CheckItem = { Name:string; Price:float32 }
type CheckPayment = { AuthCode:string; Amount:float32 }
type Check = {
    Items: CheckItem list
    Payments: CheckPayment list
    Subtotal : float32
    RemainingBalance: float32
}

These are F# record type declarations. They look and behave pretty similarly to C# record types except in F#, the type annotations come after the variable name, not before.

Now as some of you might already know, using floats in this way is perilous. But for those who don't, the first big problem arises when you need to perform arithmetic on these values.

> 1.0f + 2.0f;;//let's add two float32 values
val it: float32 = 3.0f //great it works exactly!

> 0.1f + 0.2f;;
val it: float32 = 0.3000000119f //oh no! 😱

There is a lot to say on this topic, but basically floating-point numbers are weird, and they use many tricks to try to be not weird. But sometimes these tricks fail, and this is one of those times.

The kinds of numbers that humans deal with are called real numbers. These are numbers like 1, 50, 2.378, -5.3, π, and almost anything else you can "imagine" 😉. Computer floating-point numbers try to behave similarly to real numbers, but they're not the same. For example, real numbers are equipped with many mathematical operations, the most common ones being addition, subtraction, multiplication, and division. When you perform any of these arithmetic operations on a computer floating-point number, the computer tries to get close to the real result, but it can't always get there exactly.

The reason for this is simply that there are only about 4.2 billion possible float32 values, and there are infinitely many real numbers (in fact there are more than infinity). So when the computer tries to produce a real number that isn't exactly representable as a floating-point number, it uses the next closest value, and this is where the problems creep in.

Similar to floating point math itself, the above statement isn't exactly correct, but it is close enough to make my point.

Basically, any time you do math using floating-point numbers, you're going to have to be prepared for the result to be slightly wrong. And as you can imagine, "slightly wrong" isn't good enough for financial computations. You can get around this to some extent by rounding your values to squash the errors down, but even this strategy introduces a bit of risk if you are performing long chains of computations.

Let's take a look at a larger example:

// check and item definitions from above...

let computeItemTotal itemList =
    let mutable total = 0.0f
    for item in itemList do
        total <- total + item.Price
    total //👈 implicit return value

let computePaymentTotal paymentList =
    let mutable total = 0.0f
    for payment in paymentList do
        total <- total + payment.Amount
    total //👈 implicit return value

let buildCheckFromParts itemList paymentList = 
    let itemTotal = computeItemTotal itemList
    let paymentTotal = computePaymentTotal paymentList

  //this record is also an implicit return value 👇
    {
        Items = itemList
        Payments = paymentList
        Subtotal = computeItemTotal itemList
        RemainingBalance = itemTotal - paymentTotal
    }
    
let sampleItems = [
    { Name = "Coffee"; Price = 1.99f }
    { Name = "Oatmeal"; Price = 7.49f }
    { Name = "BACON"; Price = 2.99f }
]

let samplePayments  = [
    { AuthCode = "ABC123"; Amount = 10.00f }
]

let sampleCheck = buildCheckFromParts sampleItems samplePayments

printfn $"check subtotal {sampleCheck.Subtotal}"
printfn $"check balance {sampleCheck.RemainingBalance}"

I should take a moment to explain that F#'s syntax is highly implicit. We don't have to explicitly declare that sampleItems is a list of CheckItem objects. But unlike Python or JavaScript, the compiler knows exactly what the type is. It just used process of elimination to figure out that there was only one type that had those properties and auto-selected CheckItem. Also, return values in F# are implicit, so the last value/expression at the end of a function is returned automatically.

Anyway, when I run this code it produces the following output:

❯ dotnet fsi .\basicCheck1.fsx
check subtotal 12.469999
check balance   2.4699993

If I extend the formatting out to 15 digits we get this:

check subtotal 12.469999313354492
check balance   2.469999313354492

This isn't great. The correct subtotal is $12.47 and the correct balance is $2.47. For the check subtotal, we performed three addition operations and accumulated an error of about $0.0000007, which is about what we should expect from a float32.

You can read the wikiik article on it but basically, a 32-bit floating point (according to the IEEE745 spec that basically everything supports) uses 23 bits to store the whole number part of it's data. 23 bits can store 8,388,608 values, which covers about 7 decimal digits of precision. So our calculation being off by a decimal with 7 digits makes some sense intuitively.

Now we can just call Math.Round(..., 2) to clamp this back to the correct value. But first we need to realize that .NET itself has been playing tricks on us. If I include this line in the script:

printfn $"{sampleCheck}"

Then we get some output that looks like this...

{ Items = [
    { Name = "Coffee";  Price = 1.99000001f }
    { Name = "Oatmeal"; Price = 7.489999771f }
    { Name = "BACON";   Price = 2.99000001f }
  ]
  Payments = [{ AuthCode = "ABC123"; Amount = 10.0f }]
  Subtotal = 12.46999931f
  RemainingBalance = 2.469999313f 
}

As we can see, all of our values are incorrect, even the ones that we declared as literals that have not undergone any arithmetic. We were doomed from the start. Switching to double won't save us either; it just makes the problem smaller. This also illustrates the second big problem with floating-point numbers: comparisons.

Shall I compare thee to an approximated value?

To illustrate the dangers of directly comparing floating-point numbers, let's extend our example to include the concept of taxes and a new business rule. Let's imagine there is a special resort fee that should be applied to any checks with a value of $1.25 or greater.

open System.Numerics

type CheckItem<'money when INumber<'money>> = 
  { Name:string; ItemPrice:'money }

type CheckPayment<'money when INumber<'money>> = 
  { AuthCode:string; PaymentAmount:'money }

type CheckTaxItem<'money when INumber<'money>> = 
  { Name:string; TaxAmount:'money }
  
type Check<'money when INumber<'money>> = {
  Items: CheckItem<'money> list
  Payments: CheckPayment<'money> list
  Taxes: CheckTaxItem<'money> list
  Subtotal : 'money
  RemainingBalance: 'money
}

let computeTaxesForItems itemList = [
  let itemTotal = List.sumBy _.ItemPrice itemList

  if itemTotal <> 0f then
    { Name = "Resort Tax"; TaxAmount = 0.25f } 
]

let buildCheckFromParts itemList paymentList =
  let taxes = computeTaxesForItems itemList

  let itemTotal     = List.sumBy _.ItemPrice itemList
  let paymentTotal  = List.sumBy _.PaymentAmount paymentList
  let taxTotal      = List.sumBy _.TaxAmount taxes
  
  {
    Items = itemList
    Payments = paymentList
    Taxes = taxes
    Subtotal = itemTotal
    RemainingBalance = itemTotal + taxTotal - paymentTotal
  }

There are a few notable changes. First off, we have made our object model generic so that we can experiment with different underlying types more easily. The syntax here is basically the same as in C#.

Next, I got rid of the computePaymentTotal and computeItemTotal functions; I only added them for clarity at first anyway. They have been replaced with calls to the List.sumBy F# library function. As you can guess, List.sumBy sums the items in a list with the help of a selector function. This is very similar to the family of C# LINQ Sum methods. I say "family" of methods because C# has overloads for each type, such as int, long, double, and the other numeric primitives. This is because at the time LINQ was introduced, C# didn't have the INumber<TSelf> interface, so we couldn't write generic math functions. But F# could.

The F# type signature for List.sumBy looks like this:

val inline sumBy:
   projection: ('T -> ^U) ->
   list      : list<'T>
            -> 'U (requires static member ( + ) and static member Zero)

The syntax looks kinda funky, but let's break it down: arrows (->) in a type signature indicate the flow of data from the input to the output of a function. 'a -> 'b means a function takes an input of type 'a and produces an output of type 'b. 'a -> 'b -> 'c sort of means that a function takes two inputs of types 'a and 'b and produces an output of type 'c (the real answer is more subtle, but you can think of it this way for now). Basically, the thing to the right of the arrow is the output type of the function, and the other side represents the input types. List.sumBy takes a projection, which is itself a function of type 'T -> 'U, and a list, and produces a sum of the projected values.

Additionally, you can see that there is a constraint that requires output type 'U to support the + operator and a static member Zero. In F# we don't actually need a type to implement an interface to use it generically, we can use structural typing to pick and choose specific members we need a type to implement. In this way, F# brought generic math to .NET decades before C# did.

The last code change I want to highlight is the strange _.ItemPrice syntax. This is a shorthand lambda expression. In F#, we write lambdas like this: fun x -> x + 2, which is the same as the C# lambda x => x + 2. But F# has shorthand for a common type of lambda where you just need to access a property or method on an object. So the C# lambda x => x.MyProp can be written in F# as fun x -> x.MyProp or, in shorthand, _.MyProp. Neat!

So the type definitions are now defined as generic, but what about the function buildCheckFromParts? Shouldn't it need generics too? Let's look at the C# version:

public PosCheck buildCheckFromParts(IEnumerable<PosCheckItem<TNumber>> itemList, IEnumerable<PosCheckPayment<TNumber>> paymentList)
  where TNumber : INumber<TNumber>
{
  var taxes = computeTaxesForItems(itemList);
  
  var itemTotal = itemList.Sum(static item => item.Price);
  var paymentTotal = paymentList.Sum(static payment => payment.Amount);
  var taxTotal  = taxes.Sum(static tax => tax.TaxAmount);

  return new PosCheck {
    Items = itemList,
    Payments = paymentList,
    Taxes = taxes,
    Subtotal = itemTotal,
    RemainingBalance = itemTotal + taxTotal - paymentList
  };
}

Well, believe it or not, in F# buildCheckFromParts is a generic function with the same constraints; the compiler just knows that automatically. This is the exact signature of buildCheckFromParts:

val buildCheckFromParts:
   itemList   : list<CheckItem<'a>> ->
   paymentList: list<CheckPayment<'a>>
             -> PosCheck<'a> (requires :> INumber<'a>)

The symbol 'a is a generic argument, much like T commonly is in C#, that the compiler has automatically plumbed through for us. It saves a lot of typing! As a general rule of thumb, you need to annotate generics on your types, but not really on your functions.

Now let's take a look at the function we use to add the tax.

let computeTaxesForItems itemList = [
  let itemTotal = List.sumBy _.ItemPrice itemList

  if itemTotal >= 1.25f then
    { Name = "Resort Tax"; TaxAmount = 0.25f } 
]

The first detail to notice is that square brackets wrap the function body. These aren't the same as C#'s curly braces, which delimit blocks; remember, F# uses whitespace to delimit code blocks. Instead, in F#, these [] brackets are list-expression syntax. These are conceptually similar to C#'s iterator syntax. You can write pretty much any code you need and then yield values that you want to end up in the final list. A somewhat important detail is that list expressions are "eager," unlike C# iterators, which are lazy. So don't write infinite sequences in them or your program will explode. If you need a lazy IEnumerable, you can use F#'s seq { ... } syntax instead.

So computeTaxesForItems is a function that accepts a list of items, totals them, and then evaluates the result to see if it is greater than or equal to $1.25. If it is, we yield (implicitly) a new tax item into the list expression. If not, we do nothing and the list ends up empty.

So let's look at an example input:

let sampleItems = [
    { Name = "Coffee"; ItemPrice = 3.55f }
    { Name = "Employee Discount"; ItemPrice = -1.20f }
    { Name = "Coupon Discount"; ItemPrice = -1.10f }
]

let sampleCheck = buildCheckFromParts sampleItems []

printfn $"{sampleCheck}"

Here we have a fake check with an item and two discounts that have negative prices. These total exactly $1.25, according to my calculator. So let's see what happens when we execute the script:

{ Items =
   [{ Name = "Coffee" ItemPrice = 3.549999952f }; 
    { Name = "Employee Discount" ItemPrice = -1.200000048f };
    { Name = "Coupon Discount" ItemPrice = -1.100000024f }]
  Payments = []
  Taxes = []
  Subtotal = 1.249999881f
  RemainingBalance = 1.249999881f }

Uhhh, our tax didn't get added when it should have. In this example, we accidentally found a sequence of arithmetic operations that produced an observably incorrect result. The float value 1.249999881 is not equal to nor greater than 1.25f. So using a normal comparison without rounding has introduced a bug in our software. The bad part about these bugs is that the code works most of the time. I had to hunt around a bit to find numbers that triggered this kind of bug. But trust me, the bugs are there, and they'll cause you serious problems.

To reiterate the core issues with floating point arithmetic:

1. Floating-point math quietly allows small errors to accumulate, more or less at random.
2. Comparing floating-point numbers for equality can sometimes fail unexpectedly because of those small errors.

But hasn't this been solved already?

Sure, nothing I'm going to say in this post is novel. But if you're asking about built-in types in .NET, then no, not really. What about .NET's decimal type? The docs say it is suitable for financial computations; can't we use it to solve this? Well, let's see. Because we made our code generic, we can just update our numeric literals to be decimal instead of float32.

let computeTaxesForItems itemList = [
  let itemTotal = List.sumBy _.ItemPrice itemList

  if itemTotal >= 1.25M then
    { Name = "Resort Tax"; TaxAmount = 0.25M } 
]

//...

let sampleItems = [
    { Name = "Coffee"; ItemPrice = 3.55M }
    { Name = "Employee Discount"; ItemPrice = -1.20M }
    { Name = "Coupon Discount"; ItemPrice = -1.10M }
]

This produces correct output!

{ Items =
   [{ Name = "Coffee" ItemPrice = 3.55M }; 
    { Name = "Employee Discount" ItemPrice = -1.20M }; 
    { Name = "Coupon Discount" ItemPrice = -1.10M }]
  Payments = []
  Taxes = [{ Name = "Resort Tax" TaxAmount = 0.25M }]
  Subtotal = 1.25M
  RemainingBalance = 1.50M }

The tax got added! And heck, even the raw values look perfect now! We're saved!

Btw, in this example the literal suffix M indicates a decimal literal value in F#. Why M? It stands for "Money," which is ironic because it still isn't really safe for our monetary computations for one major reason: division. Take a look at this example:

> (1M / 3M) * 3M;;
val it: decimal = 0.9999999999999999999999999999M {Scale = 28uy;}

We all know that 1 ÷ 3 × 3 should equal 1 exactly, but decimal fails this test. What is funny, however, is that this famous misbehavior no longer affects float32 or double in .NET, although I am fairly sure it did in the past.

> (1f / 3f) * 3f;;
val it: float32 = 1.0f

> (1.0 / 3.0) * 3.0;;
val it: float = 1.0

There are complex reasons for this, but basically, .NET tries very hard these days to avoid this kind of instability. The JIT will also try very hard to avoid floating point math at runtime if it can, doing all kinds of complicated tricks called peephole optimizations. If you're curious about these, here is a great post about them. In general more optimizations are more better, but we can't count on an optimization always applying, and it can change the results. The whole reason we are in this mess is that the behavior of floating-point values is inconsistent with real numbers, seemingly at random.

But all of this glosses over the biggest issue with floating-point values as a general principle in financial computation: they are, by design, approximations. They are designed with the idea that when total amounts are large, small amounts don't matter as much. This design simply isn't good enough in the world of finance.

So if not floating-point numbers, then what? Let's go back and look at one of our older outputs again:

{ Items = [
    { Name = "Coffee";  Price = 1.99000001f }
    { Name = "Oatmeal"; Price = 7.489999771f }
    { Name = "BACON";   Price = 2.99000001f }
  ]
  Payments = [{ AuthCode = "ABC123"; Amount = 10.0f }]
  Subtotal = 12.46999931f
  RemainingBalance = 2.469999313f 
}

All of the numeric values are imprecise. Except the $10.00 value. That is not an accident. We mentioned before that a 32-bit float has 23 bits dedicated to the "number" part of it's representation. The other bits belong to either the sign bit or a part called the exponent that determines how big the scale of the number is. The direct consequence is that we can perfectly store and perform arithmetic on integers up to 2^23 without error (almost...). But this is the path for us to follow.

Back to basics: integer arithmetic

Integers present an attractive option for several reasons, but chiefly because they are predictable. We know cleanly that computer integers within a certain range are guaranteed to produce exactly correct results for addition, subtraction, and multiplication. And the times that they won't we can catch perfectly when they happen. Integer comparisons are also simple and predictable; there is no rounding error. In fact, we can perform millions of integer operations without accumulating any error at all. So why don't we just use them everywhere? Because they require us to know the scale of our operations up front.

So where do we start? First, we need to recognize that most currency values have a fixed number of decimal places to worry about. USD has two digits after the decimal because there are 100 cents in a dollar. The most common thing to do is to treat the integer as a fixed-point decimal, which for our purposes means that we don't allow the decimal point to move around depending on the values of our variables. In practical terms, it means we must scale up all our math to work in cents instead of dollars. Let's do that now:

type CheckItem<'money> = 
  { Name:string; ItemPriceCents:'money }

type CheckPayment<'money> = 
  { AuthCode:string; PaymentAmountCents:'money }

type CheckTaxItem<'money> = 
  { Name:string; TaxAmountCents:'money }
  
type Check<'money> = {
    Items: CheckItem<'money> list
    Payments: CheckPayment<'money> list
    Taxes: CheckTaxItem<'money> list
    Subtotal : 'money
    RemainingBalance: 'money
}

let computeTaxesForItems itemList = [
  let itemTotal = List.sumBy _.ItemPriceCents itemList

  if itemTotal >= 125 then
    { Name = "Resort Tax"; TaxAmountCents = 25 } 
]

let buildCheckFromParts itemList paymentList =
  let taxes = computeTaxesForItems itemList

  let itemTotal     = List.sumBy _.ItemPriceCents itemList
  let paymentTotal  = List.sumBy _.PaymentAmountCents paymentList
  let taxTotal      = List.sumBy _.TaxAmountCents taxes
  
  {
      Items = itemList
      Payments = paymentList
      Taxes = taxes
      Subtotal = itemTotal
      RemainingBalance = itemTotal + taxTotal - paymentTotal
  }

let sampleItems = [
    { Name = "Coffee"; ItemPriceCents = 355 }
    { Name = "Employee Discount"; ItemPriceCents = -120 }
    { Name = "Coupon Discount"; ItemPriceCents = -110 }
]

let sampleCheck = buildCheckFromParts sampleItems []

printfn $"{sampleCheck}"

We have updated our property names to be more correct now that we are using integer cents instead of decimal dollars. We also updated the numeric literals by multiplying them by 100, so the value 1.50 becomes 150. This produces correct output based on our above example:

{ Items =
   [{ Name = "Coffee"; ItemPriceCents = 355 }; 
    { Name = "Employee Discount"; ItemPriceCents = -120 };
    { Name = "Coupon Discount"; ItemPriceCents = -110 }]
  Payments = []
  Taxes = [{ Name = "Resort Tax"; TaxAmountCents = 25 }]
  Subtotal = 125
  RemainingBalance = 150 }

Perfect! All we need to do is scale the final printed output back to a decimal dollar value, and everything just works! Right?

Well what about division?

> (1/3)*3;;
val it: int = 0

Uhh, 0 is completely wrong. The result should be 1! This is because integer division collapses when the resulting value is between 0 and 1. In this case, 1 ÷ 3 should be 0.3333…, and integer arithmetic falls apart. This might seem like a deal breaker, but we can manage it by being more specific about what we mean when we try to divide numbers.

Divided we fall...

In my day job, we have two main reasons to divide monetary values. The first is when we split a check into parts, such as friends splitting the bill at lunch. What we are really trying to do is partition a value into several parts. For example, it is easy to split a check between 2, 3, or 4 people equally. Let's imagine a check valued at $45.00. A split by two naturally yields two $22.50 parts. A split by three yields three $15.00 parts, and a split by four yields four $11.25 parts. All nice and clean.

But now let's imagine a check valued at $21.94. A split by two yields two exact $10.97 parts, but a split by three presents a problem because $21.94 ÷ 3 = 7.3133333…. Now what do we do?

In these situations, we basically have to fall back to yielding several uneven partitions of the value. Perhaps two partitions worth $7.31 and one partition worth $7.32; the three total up to the original $21.94. With this in mind, we realize that the traditional signature of a division operation doesn't line up with our needs.

The binary division operation is typically defined as (left: 'T * right: 'T) -> 'T, where 'T is some numeric type such as int or float. This is a function that receives a single input, a 2-tuple where each item is of type 'T, and returns a single output of 'T. Note that * is the tuple-item separator in an F# type signature. But in our example above, we need to return more than one value. In my system, I chose to return a list of "partitions," so the function signature would look more like this: (left: 'Integer * right: 'Integer) -> 'Integer list. This makes the behavior of the system very explicit and guides the user of the API to a more clear understanding of the consequences of splitting a value.

The second use case is tip proration, which deserves an appendix of its own.

A more Rational approach

A Rational number is a mathematical object, similar to a Real or an Integer. In fact, all 3 of these types of objects are part of a family of objects called Fields with computer integers and rationals being part of a subfamily called Finite fields. We don't need to get into Field Theory, but all you need to know is that any Field (such as an Integer, Rational or Real), supports all 4 of our core Arithmetic operations, addition, subtraction, multiplication and division which makes them simple for us to understand and use them. And rationals are a very convenient Field for us to use because they balance our concerns well.

One issue, however, is that .NET doesn't provide a Rational type natively, so we need to build our own. We can start like this:

type Rational = { Num: int; Dem: int }

Yep, that's it. If this construct looks familiar, it is because you probably learned about it when you were young, but your teacher probably called them fractions or ratios. But just the same, a rational number is made up of two integers: a numerator and a denominator. Back in grade school, we learned how to manipulate fractions, but you are probably a little foggy, so I'll fill in the blanks.

type Rational = { Num: int; Dem: int }

type Rational with
    static member (+) (left:Rational, right:Rational) = { 
        Num = (left.Num * right.Dem) + (left.Dem * right.Num)
        Dem = left.Dem * right.Dem 
    }
    static member (-) (left:Rational, right:Rational) = { 
        Num = (left.Num * right.Dem) - (left.Dem * right.Num)
        Dem = left.Dem * right.Dem 
    }
    static member (*) (left:Rational, right:Rational) = 
        { Num = left.Num * right.Num; Dem = left.Dem * right.Dem }
    static member (/) (left:Rational, right:Rational) = 
        { Num = left.Num * right.Dem; Dem = left.Dem * right.Num  }

And that's about it. We can drop this into our check implementation, and voila:

{ Items =
   [{ Name = "Coffee"; ItemPriceCents = { Num = 355; Dem = 1 } }
    { Name = "Employee Discount"; ItemPriceCents = { Num = -120; Dem = 1 } }
    { Name = "Coupon Discount"; ItemPriceCents = { Num = -110; Dem = 1 } } ]
  Payments = []
  Taxes = [{ Name = "Resort Tax"; TaxAmountCents = { Num = 25; Dem = 1 } }]
  Subtotal = { Num = 125; Dem = 1 }
  RemainingBalance = { Num = 150; Dem = 1 } }

The math works perfectly, just like the integers, and the custom tax is applied as expected. But what about division?

> let third = { Num = 1; Dem = 1; } / { Num = 3; Dem = 1 };;
val third: Rational = { Num = 1; Dem = 3 }

> third * { Num = 3; Dem = 1 };;
val it: Rational = { Num = 3; Dem = 3 }

The final result here is 3/3 -> 1/1 -> 1, which is exactly correct, albeit not in canonical form (but we can fix that later). The point here is that rationals allow us to perform arbitrary arithmetic operations without loss of precision. They do this by delaying the execution of the division operation until the last possible moment. Then, when we are ready to format the results using decimals for display, such as $12.32, we can do so in a controlled way without worrying about unpredictable rounding issues.

Our implementation is reasonably efficient in time and space. Running a quick benchmark of 1 billion arithmetic operations yields this.

❯ dotnet fsi .\RationalBenchmark.fsx
Warming up...
Running benchmark...
Real: 00:00:22.993, CPU: 00:00:45.312, GC gen0: 1924, gen1: 3, gen2: 2
Final result: { Num = -1268204542; Dem = -1781585917 }
Total allocations: 72,005,133,240 bytes
Operations per second: 43,279,270.69

We did 1 billion operations in 22 seconds. That works out to 43 million operations per second on a single thread, which is plenty fast for most practical uses. But you might notice that we allocated 72 GB of memory and triggered almost 2,000 garbage collections, which isn't great. This is because F# records, like C# records, are reference types (aka classes) by default. But we can change that easily.

[<Struct>]
type Rational = { Num: int; Dem: int }

Rerunning the benchmark now shows this:

❯ dotnet fsi .\RationalBenchmark.fsx
Warming up...
Running benchmark...
Real: 00:00:00.661, CPU: 00:00:00.625, GC gen0: 0, gen1: 0, gen2: 0
Final result: { Num = -1268204542; Dem = -1781585917 }
Total allocations: 5,140,720 bytes
Operations per second: 1,300,274,461.93

We now run with zero garbage collections and execute over 1.3 billion operations per second. Same exact numeric result, 30 times faster. Neat! Now we have to bring that number back down to earth by including a reduce operation that ensures that our rationals are always in canonical, reduced form. Computing the reduced form of a fraction or rational requires computing the greatest common divisor of the numerator and denominator. This generally requires multiple operations involving looping and branching and adds significant overhead. But even with it, we end up with less than 20 nanoseconds per operation.

But what about integer overflow?

The only downside is that we are still limited to the same fixed range as integer arithmetic, which can overflow if we are not careful. This poses the biggest issue when we need to perform many consecutive division or multiplication operations that make the numerator and denominator very unbalanced. This sounds bad, but in reality it is not easy to do as long as we correctly size the underlying integer type. To put this in perspective, if we use our Rational type to store USD currency values, then we can represent a maximum value of $21,474,836 using an Int32. For typical restaurant checks, that is completely fine. But if we think about the scale of long-term reporting or large stock trades, that is not going to cut it. We can easily change from an Int32 to an Int64, which can store a maximum value of $92,233,720,368,547,758. For perspective, this number is over 800x the GDP of the entire planet.

That sounds pretty great; what could possibly go wrong? Well, it turns out that some very common calculations can still lead to overflow even with int64 as the backing type. One example is the closed-form computation of a mortgage payment. The formula is deceptively simple, but it involves raising numbers to large exponents that will explode our humble int64 storage. But because of the power of generics and .NET's uniform numeric types, we can use bigint to cover this extreme case without any additional complexity. It all just works.

Refining the concept

So, as I worked on this article, I came to understand that a Rational type, while kind of great for intermediate calculations, poses a usability risk when it comes to output representations. The basic idea is that monetary values need to be exact, such as a list of line items on a restaurant check or the amount of money you owe on a monthly bill. At other times, it is necessary to perform sequences of calculations without rounding until the very end. So, to serve these two purposes, we have two types.

I use a traditional integer for my Money type and a rational number for my new ExactMoney type, which is suitable for chained computations without loss of precision. The two types interop with each other with ExactMoney.Round() yields a Money object, and division automatically widens Money values into ExactMoney.

In the end, the code grew a lot larger than I expected after I had to add all the arithmetic-operator overloads, utility functions, helpers, and performance optimizations. But I'm pleased with what I have made. It's fast, pretty clean, and hard to screw up.

Conclusion

I think I will stop here for now, this has gotten pretty long already. I have some examples lined up to show about this, I'll try to include them in a follow-up article. But so far, my testing has been promising. I want to iterate a little more on the API surface area, but I'm close to ready to adopt this into the core of our new payments platform just in time to implement proration logic. Maybe I'll talk about that system next, because it was a lot of fun to work on and optimize over the past few months.

If you made it this far, thanks for reading 😊.

Appendix

Appendix A: Well, actually...

But once again, the above statements about floating point bits isn't exactly true in the real world. It might surprise you a bit to hear that .NET doesn't provide a guarantee that floating point math will behave the same way on different platforms. That is to say that the math done on an ARM CPU might work differently than the math done on a x86 CPU. One of the biggest advantages of managed languages is the avoidance of Undefined Behavior that is a plague on C and C++. After a little more thought it might surprise your further because both ARM and x86/x64 processors implement the same floating point specification in hardware; the ever-present IEEE754. So how is it possible that there are differences? This is because the .NET specification allows for various performance optimizations as well as, perhaps surprisingly, flexibility on how floating points are computed; as long as the computation used is "at least" as precise as the bit width of the native type. Put another way, it is fine for the .NET runtime to perform floating point math using higher precious calculations than what the user asked for. And it fact, it does just that by taking advantage of something called extended precision floats in x86 processors, which uses 80-bit calculations instead of the more normal 64-bits. Well, depending on your exact CPU and the version on the runtime you are using. Because the JIT will emit different assembly depending on what it thinks is best.

If all that isn't bad enough, we can actually get .NET to disagree with itself within the same program running on a single machine in the same session. Without going into too much more painful detail, most of the time .NET's JIT will decide for us if it is best to use a CPU instruction like fadd instead of vaddss to add two floats, but we can force .NET to use very specific CPU instructions by using intrinsics. Here is a truncated example:

let bufferCount = 8
let loopIterations = 1
let entropy = Random 1
let vectorCount = Vector512<float32>.Count

let randomInts = Array.init (vectorCount * bufferCount) (fun i -> entropy.NextInt64(1, 10000))
let randomFloats = Array.map (fun x -> float32 x / 100.0f) randomInts

let mutable intSum = LanguagePrimitives.GenericZero
let mutable scalarSum = LanguagePrimitives.GenericZero
let mutable vectorSum = LanguagePrimitives.GenericZero

for loopCounter in 1 .. loopIterations do
    printfn $"Starting iteration {loopCounter} of {loopIterations}..."
    
    intSum <- intSum + Array.sum randomInts
    scalarSum <- scalarSum + Array.sum randomFloats
    
    for i in 0 .. vectorCount .. randomFloats.Length - 1 do 
        let bufferSpan  = randomFloats.AsSpan(i, vectorCount)
        let vector = Vector512.LoadUnsafe(&bufferSpan[0])
        vectorSum <- vectorSum + Vector512.Sum vector

let totalOperations = (int64 vectorCount) * (int64 bufferCount) * (int64 loopIterations)
printfn $"Operation Count: {totalOperations:N0}"
printfn $"Int Sum: {intSum:N0}"

let scalarBaselineDelta = (float intSum / 100.) - float scalarSum
let vectorBaselineDelta = (float intSum / 100.) - float vectorSum
printfn $"Scalar Sum: {scalarSum:N2}"
printfn $"    Scalar Detail : {scalarSum:N10} (Baseline Delta: {scalarBaselineDelta:N10})"
printfn $"Vector Sum: {vectorSum:N2}"
printfn $"    Vector Detail : {vectorSum:N10} (Baseline Delta: {vectorBaselineDelta:N10})"

if scalarSum <> vectorSum then
    printfn $"Difference in Sum: {scalarSum - vectorSum:N10}"
else
    printfn "Scalar and Vector sums are exactly equal."

In this code example, we generate an array of random integers, convert them to floats, and divide each by 100 to give them a decimal component. We first sum them using a normal scalar approach, Array.sum randomFloats. We then do something more complicated and use vector/SIMD instructions to sum them in batches. The output looks like this:

Operation Count: 128
Int Sum: 646,781
Scalar Sum: 6,467.81
    Scalar Detail : 6,467.8095703125 (Baseline Delta: 0.0004296875)
Vector Sum: 6,467.81
    Vector Detail : 6,467.8105468750 (Baseline Delta: -0.0005468750)
Scalar/Vector sum diff: -0.0009765625

The result is a slight difference, with the vector algorithm being slightly more accurate, but both sums have drifted from the baseline. At least on my computer. This might not seem like much, but it is already enough to cause an equality check to fail. Imagine check.Balance = 0 no longer being true. But if we increase the number of operations from 128 to 4,096 and then sum them, take a look at the results:

Operation Count: 4,096
Int Sum: 20,114,947
Scalar Sum: 201,149.61
    Scalar Detail : 201,149.6093750000 (Baseline Delta: -0.1393750000)
Vector Sum: 201,149.42
    Vector Detail : 201,149.4218750000 (Baseline Delta: 0.0481250000)
Scalar/Vector sum diff: 0.1875000000

The integer sum is the ground truth of $201,149.47. But both float results are noticeably wrong: the scalar version by around 14 cents and the vector version by about 5 cents. Ultimately, the two floating-point sums differ by almost 19 cents. Same program, same computer, same execution. I'm sure you can easily imagine a simple report needing more than 4,000 addition operations. This is a completely unacceptable level of instability.

The case is not the same with "normal" 64-bit floats (aka C# double). As bad luck would have it, I produced an equality discrepancy after only 32 addition operations, although it was tiny (0.0000000000002). If we want to induce an error large enough to directly affect a financial quantity, it takes about 500,000,000 operations, which is a lot.

Appendix B: Partial Payments and Proration

The other time we need something similar to division is with an advanced feature called tip-proration. When you submit an authorization request (a financial authorization, not a security authorization...), the payment processor can in some cases return a partial auth, which indicates that the account of the cardholder didn't have enough funds to cover the entire requested amount. A very common example is gift cards, where a consumer might try to pay a $50 check with a $20 gift card. The processor returns a result that says that we only get $20 out of the $50 we asked for. In these situations, we display a message to the consumer saying they need to provide a new payment instrument to pay off the remaining balance. But with a complication...

In these situations we offer configurable workflows on how to proceed with allocating the funds that were approved by the processor. You see, when the consumer runs their card, they indicate how much of a gratuity they want to leave along with the balance payment against the check. So to continue the previous example, if the authorization request is for $50, then a possible breakdown of that is $40 for the check balance and $10 for a gratuity. But in the event that only $20 is received from the bank, how do we allocate those funds?

In case you are wondering why we care so much about the tip on a check, it is because after we perform the auth with the bank, our software has to then inform the point-of-sale system about the details of the payment, including how much of it was the tip. This is because the point-of-sale is generally responsible for reporting tip allocations to the manager, which informs payroll. So we have to know.

We support several different options that our clients can configure such as:

• Prioritize Gratuity : Allocate money to the gratuity first, then to the check balance
• Prioritize Balance : Allocate money to the check balance first, then to the gratuity
• Prorate : Allocate to both check balance and gratuity based on the percentage the consumer indicated

If we choose proration, we determine the percentage of the payment that was allocated to the gratuity and scale it down to the amount actually authorized by the processor. So in our example, $10/$40 was a 25% gratuity (or 20% of the combined total), so prorated down to a $20 total amount, that would be a $4 gratuity allocation.

These are easy numbers, but you can imagine more realistic numbers that would not scale/divide cleanly using integer division. So we are going to need a plan on how to work around that. Our partitioning approach from above doesn't quite fit, since that is oriented around splitting values into roughly equal buckets. Instead we need a scaling operation, which is traditionally served by a multiplication such as x * 1.5, but in this case, we know that the amount authorized by the bank will always be less than the requested amount, which means the scaling factor will always be less than 1, e.g. x * 0.75 or something similar. This doesn't work in the integer world because we would have to round the scaling factor to the nearest integer, which would be either 1 or 0, both of which are very incorrect.

Looking at the whole problem we can lay out a general function like this:

let prorate balancePaymentAmount tipAmount authorizedAmount =
    let tipProportion = tipAmount / balancePaymentAmount
    let balancePaymentProportion = 1 - tipAmount

    let proratedTip = tipProportion * authorizedAmount
    let proratedBalancePayment = balancePaymentProportion * authorizedAmount

    (proratedBalancePayment, proratedTip)

If the values were floats, these formulas would work, but in the world of integers, they collapse to zero instantly. But we have seen that floats have precision issues with division. So what we are searching for is a data type that supports division cleanly, similar to a float, but also supports lossless operations similar to an integer. One potential answer is using Rational numbers.

So, about a week ago I made a post that talked about Satori, an exciting experimental garbage collector that showed pareto front advances of key metrics. Put another way, this GC seems to offer a new level of near minimal STW pause durations, minimal heap sizes and strong throughput performance in a number of synthetic benchmarks.

Initial benchmarking showed Satori as a shooting star of low latency with some modest give back on the throughput axis and great heap sizes, which seemed like a very attractive tradeoff for some classes of applications. But as more benchmarks have been run, we begin to see some of the places where Satori doesn’t shine as brightly. So, after a week of testing what have we learned so far? Read on below👇

Read more

Be sure to checkout my follow up post: A week with Satori, the experimental low-latency GC for .NET

Howdy folks, I wanted to bring your attention to a Github discussion over in the .NET runtime where an experimental Garbage Collector called Satori has emerged that is producing very exciting numbers for those of us in the .NET performance crowd.

Quick Links:

-          The discussion thread

-          The comment introducing the new GC

-          Benchmarks, Benchmarks, Benchmarks

TL;DR / Results

Compared to the traditional Server GC in interactive mode, Satori offers improvements in synthetic benchmarks in several key metrics that range from impressive to down right shocking. How shocking?

-          50x improvement to Median Pause Time

-          >100x improvement to 99^th percentile pause times

-          3x improvement to Heap Size

So yeah… it is really a stunning development.

I would encourage anyone interested in writing high-performance .NET code to try out Satori (instructions below) on your own workloads to see if it offers any benefits. This feedback can help the folks at Microsoft prioritize investment in this experiment.

👇 You can find instructions on how to get it at the end of this article 👇

Read more

Howdy! This is another chapter in my series about software testing. You don't have to have read any of the previous installments to understand this article, but "An Introduction to Testing the Impossible" covers some similar concepts and tools.

Today we are going to cover another advanced testing technique called Model-Based Testing that can help us find exotic bugs very quickly without a lot of code. It can also go places that other testing strategies cannot such as testing systems for bugs that only occur after a magic sequence of operations.

Read more

"What is the difference between a class and a struct in C#?". I like this as a lead-in interview question because most candidates can offer up a quick answer that can help them get some confidence rolling in case they are nervous (we are not generally looking to asses candidates for performance under duress 🙂). There is a spectrum of correct answers that can shed light on how the candidate thinks about this fundamental component of the .NET type system. I'm going to lay out some of the ways that I think about structs in .NET.

Read more