YOW Conference – #yow15

I had not been to YOW before myself. In my previous job I had sent my team there though; the timing works out perfectly for a business that tends to be quiet over Christmas and the new year.

I had been to TechEd before, and that was the closest benchmark I had.

YOW definitely wins on a broader scope of topics, and yet not so scattered that it was hard to find a relevant topic in each session timeslot. I have been to TechEd with timeslots reserved for walking the floor, because despite 5-6 sessions running in parallel there wasn’t one that I actually wanted to see.

TechEd wins on the catering front, hands-down. But then, in all the years I went, it never ceased to amaze me how well-oiled the Microsoft conference machine is, and the amount of effort they put into a great show.

Having said that, YOW wins hands-down on cost… it’s kinda the way they pitch their conference – focused on the technology and affordability at the expense of spectacle. I don’t think that’s a bad call, because TechEd was definitely never a trivial sell to management.

And yet… the one point I have a hard time qualifying specifically; YOW doesn’t feel as amenable to making new connections on the floor. During sessions the focus is on the speaker, and during breaks it is on getting some food and finding a place to eat it. Maybe it’s the TechEd lunch set-up around large tables that force you to sit down with strangers that helps? Maybe it’s the social evening of fun they put together (one year: go-kart-racing in the parking garage… yes… seriously) that makes friendly conversations easier to come by. I don’t have a clear answer, but YOW does feel stiffer than TechEd.

Having said that… if you’re just there to learn, the set-up is ideal.

Keynote 1 – It’s Complicated…
Adrian Cockcroft

To my shame, I barely remember the opening keynote.

I hadn’t had coffee yet.
I was trying to work out when I was going to be where.
And then I had 11 sessions and 3 more keynotes with memorable elements.

I think it just displaced (almost) all my memories.

The one thing I recall with clarity is the question how it can be that the most complex piece of technology in existence today is usable by kids as young as 2 years old in a meaningful way; the mobile phone. Something about it’s design is the pixie dust that hides the million things you don’t want to do right now.

Session 1 – Rethinking MVC with React Native & ReactiveCocoa
Ben Teese and Sam Ritchie

I was only superficially familiar with React before this talk, so it probably wasn’t aimed at me. But I still learned a lot about the way React uses it’s Virtual DOM to do delta-updates on-screen, and how that can be made to translate to native apps on mobile devices as well.

I believe Angular 2 is going down a similar path of supporting some kind of Native variant, although I may have just dreamed that. Either way; not quite relevant to me at the moment.

Great talk though, good speakers, especially the groan-worthy punny pictures.

Session 2 – 40 Agile Methods in 40 Minutes
Craig Smith

Spoiler: it’s actually 50+ minutes; the session ran a little too slow to make good on its titular promise. Having said that, it was a very enjoyable whirlwind through a lot of Agile Development approaches (some of which didn’t look anywhere near as Agile as they purported to be).

There were a few slides that specifically piqued my interest, but the pace prevented me from taking notes, so I look forward to the slides getting published. Especially the slide with a book that Craig recommended as providing a good underpinning of why Agile works.

Great talk, and more useful than the frivolous title might lead you to believe.

Keynote 2 – Using Formal Methods to Eliminate Exploitable Bugs
Kathleen Fisher

Oh yes.

Totally this.

It’s been only 17 years or-so since I graduated from University, and at long last the central pillar of the Computing Science program of Eindhoven University of Technology is actually becoming useful.

See ma, my degree has practical applications in the real world!

And apparently, Australia is one of the fore-runners in this field. I don’t want to say it’s because of me, but hey… I’ve been here 17 years now. Coincidence? I think not!

In all seriousness, it is great to see Formal Methods taking their rightful place as a central tool for the development of provably correct software.

Session 3 – Adaptive Security
Aaron Bedra

The key tenet of this talk was: exploit your logs; exploit them for all it’s worth.

Know what your messages mean, count them, and then look for patterns. And then act on those patterns. And start simple, because the business knowledge that produces will lead to requests for more of the same, and before you know it you’ll be tracking and measuring everything.

I couldn’t think of better real-world advice.

Even beyond just security matters.

Session 4 – Production Haskell
Reid Draper

This was by far the greatest disappointment of the conference to me. Based on the excerpt I had hoped to see some samples of practical use of Haskell in a real-world production scenario.

In the end I walked out before the session was over, because I just couldn’t muster the will to look at further tool-chain scripts to build Haskell. That was so not the point I was coming to see.

I’m sure I could figure it out myself, but I wanted to come and be sold on the idea.

Session 5 – Pragmatic Microservices: Whether, When and How to Migrate
Randy Shoup

I slumped through this; not a bad talk, but after a full week of Udi Dahan, there wasn’t really a lot more anyone could tell me about big balls of mud and how to take bites out of them.

I had hoped those nice big open questions in the title would lead to new practical insights, but I think I just kinda zoned out and let my afternoon snack digest.

Not a bad talk, just nothing much in it for me.

Session 6 – Property Based Testing: Shrinking Risk in your Code
Amanda Laucher

This talk felt like a “missing link” between Formal Methods, Unit Testing and .NET Code Contracts. After listening to it all, I like the idea of higher-order tests, and I see how you could leverage them in procedural languages.

But it feels like perhaps it’d be easier to just go Functional, or use Theorem Provers instead of wasting this approach in its pure form on C#. Still, I like the ideas underpinning this way of testing, because as I’ve blogged previously, I’m very unsatisfied with the cost/benefit balance of most of the automated testing I have been exposed to in my working life.

Keynote 3 – Engineering and Exploring the Red Planet
Anita Sengupta and Kamal Oudrhiri

Anita is a great speaker. Kamal was clearly nervous.

Having said that, it’s hard to botch a topic as inherently interesting as trying to land complex and fragile technology on another planet within a very small target area. It’s hard to appreciate how awesome the stuff is that JPL and NASA do without someone explaining all the details that you’d never have thought of.

I secretly suspect there are still a lot of Waterfalls in these places to deal with the careful design required for a release that you don’t get a second chance at. Once it leaves the planet, it better work.

Also, it made me want to go and see The Martian again.

Session 7 – Building Microservice Architectures in Go
Matt Heath

This was actually a very fun Microservices talk. Not as much hands-on Go as I might have hoped, but some very salient points were made. It hadn’t occurred to me before that the combination of a language that statically links everything together with a very lightweight container is immensely powerful for Microservices / Service Oriented Architecture.

I guess he just made a very compelling case for dotnetcore without even realising it.

Also, he was an excellent and engaging speaker. He felt by far the most polished out of the speakers I saw. Having said that,… the thongs were visually incredibly distracting.

Session 8 – Agile is Dead (Long Live Agility)
Dave Thomas (Pragmatic)

And just as I thought thongs would be about as distracting as it could possibly get. Bare feet on stage.

After this talk I feel very self-conscious about my use of the term “Agile” as a short-hand for Agile Development Practices. A very well-put rant against the commercialisation and co-opting of common-sense to extremes where it just stops making sense altogether.

I suspect the fifth agile tenet that he can no longer remember might have been “Pizza over Steak”; that sounds like something a programmer would declare.

I guess the biggest lesson from this session is a cautionary tale; to keep an eye on the practices you follow and to make sure you don’t fall in the trap of trying to buy Silver Bullets. We all love them so much, and we know they don’t exist, but we still buy ’em.

Keynote 4 – Thriving in a Stochastic World
Don Reinertsen

And this one takes the title for “dullest yet most worth taking note of”.

The speaker reminded me of a professor with a slow drone. I’m glad I managed to barely keep my eyes from shutting, because the key thesis on how to exploit the asymmetry of the upside and downside of experimentation in an unpredictable environment is a great lesson for all start-ups. Heck, all technology businesses.

I would have hated to miss that nugget.

The lead-up to it, I could have done without I think. Maybe start closer to that point and then spend more time on concrete examples, and it’d be a much more relatable talk.

Session 9 – Making Hacking Child’s Play
Troy Hunt

This one was a lot of fun. Also terrifying.

For opening gambit: a dumb YouTube video showing a terminal with a clueless teenage voice-over explaining how to DDoS someone with a “ping -t” command, and how it’ll only work if “your network is powerful enough”.

A brilliant feint.

Later in the session, the most terrifying thing ever, an early-teen girl, in her early-teen bedroom, speaking into a laptop webcam selling DDoS services to knock your gaming competitors off the net. And completely serious and real.

We live in a world where the tools to disrupt services on the internet can be wielded by the completely clueless. It’s like a phaser; you just point and hit the button and stuff happens.

Very effective presentation.

And also, we’re all doomed.

Session 10 – DevOps @ Wotif: Making Easy = Right
Alexandra Spillane and Matt Callanan

Another talk that didn’t quite make good on its title, but nevertheless a talk with some interesting points.

Basically, Wotif ended up crawling out of the pit of despair by creating a better deployment story, but rather than using the hard-sell, they developed it alongside their existing deployment path and then let market economy take care of the rest.

“Do you want to go in the release queue, wait weeks, then have your code hit production; all safe and secure, or would you like to use this faster SLIPWay which can turn around your deployment in an hour, but you’ll have to change a few of your assumptions and processes?”

These were the only paired speakers that had put their talk together so that their perspectives complemented each other well. Not flawless, but definitely seamless.

Session 11 – Play in C#
Mads Torgersen

The biggest under-sell of YOW.

The title doesn’t do the content of this session justice by a long stretch.

For warm-up, we walked trough the history of C# (Mads leads the language team at Microsoft), with some miscellaneous barbs and snipes aimed at Georges Saab who did a Java talk before this session.

“C# 1.0, back in 2000, where we introduced value types”, /significant long silent glance to Georges/.

Poking fun was only the secondary purpose of this quick retrospective, because his real purpose was to show the language evolve to where it gained Roslyn. And then he went into a live demo.

He starts up Visual Studio.
He starts a language rule project.
He starts a nested Visual Studio within which the language rule he is developing lives.
He edits the language rule with code-and-resume.

And as he adds this new language rule and it incrementally applies squigglies in the nested VS, and then adds automatic correction options to apply fixes to the code; I want to play with Roslyn so desperately now. It is FxCop on steroids. It is magical. And also a little meta-insanity. But the good kind.

And then to finish he runs through some of the new language feature options on the table for C# 7. Note that hyperlink right there. That’s the GitHub repo where Microsoft keeps the live list of language feature discussions going on for the next version of C#. Microsoft are now not only open-sourcing their framework, but they have also opened up the design process. So have a look around and be part of the discussion!

It sounds like Pattern Matching by types, strong Tuples and non-nullability are strong contenders for features that might be in. But no promises just yet.

I could not have wished for a better closing session, because it sent me into the weekend very energised. I then proceeded not to play with Roslyn for lack of time after my other chores, but I think that flame will burn through a while longer.

My next goal: devise a talk worthy of YOW and get onto the speaker roster.
It is easy to criticise, but much harder to step up and do it.

Regular Like Clock-work

That is to say; with a whole bunch of wobbly and spinny bits that nobody quite understands the need of, but without which the mechanism just suddenly fails in spectacularly unpredictable ways.

You guessed it… Regular Expressions.

The greatest, most terrible tool, ever invented to do quick-and-dirty validation in web front-ends around the Interspaces.

I’ve been working to improve first-pass URL validation logic in the web front-end. I started by trying to read the existing regex, but it looked like a cat had just mashed some random symbol keys to a length of about 200 characters. And I knew it wasn’t allowing all the URLs we’d like to accept.

I decided to go back to first principles; RFC 3986 – URI Generic Syntax. The first shock was learning that the following is a perfectly legal URL:

http://jerryjvl:password@[FE80::0202:B3FF:FE1E:8329]:8080/
This:would/Be-Funny+(if);I-didn't/Have-to?parse=it#sadface

And I haven’t even used Unicode characters anywhere in that example yet.

First, the temptation is to go to the back of the RFC, and just translate the BNF notation into a Regex and be done with it. Alas, I didn’t think I could accurately transcribe that many permutations without slipping up… and regexes are hard enough when you have a clear idea of what exactly you are parsing.

Second, the important realisation that it doesn’t have to disallow everything that isn’t a valid URL. This is about helping the users by catching the most important mistakes they might make. If anyone decides to actually use an IPv6 literal as a host identifier, then it really isn’t important to check whether the exact right number of hex words were used.

So, when squinting just-right at the RFC, it is easy enough to come to the following right-to-almost-right rules:

  • The group [\w\$-\.!;=@~] is a great approximation for the permissible alphabet for most of the textual parts of a URL; in some places that might allow slightly too much, but it restricts all the characters that really do not belong.
  • “#” is only permitted exactly once, after which all further text is considered the fragment identifier.
  • “?” is not permitted until the query portion at the end of the URL, but can occur as many times after that as you want.
  • Allowing excess square brackets makes capturing the part between the “//” and the first following “/” easier. Making the expression more specific helps break down the results into more logical parts.

What I have landed on for now is the following (finessed so that the capturing groups try to catch the logical parts of a URL):

^
  (?:(https?|ftp):)? # URL Scheme Identifier: http, https, ftp
  (
    \/\/ # Literal //
    ([\w\$-\.!:;=~]*@)? # Followed by optional username:password@
    ([\w\$-\.!;=~]* # Followed by hostname
    |\[[a-fA-F0-9\:\.]*\]) # Or IPv6 address
    (\:\d*)? # Followed by optional :port

    |\/[\w\$-\.!;=@~]+ # Or literal / and a path segment

    |[\w\$-\.!;=@~]+ # Or no slashes and a path segment

    | # Or... nothing at all!
  )

  ((?:\/[\w\$-\.!:;=@~]*)*) # Rest of the URL path

  (\?[^#]*)? # Optional query: ?...

  (#.*)? # Optional fragment: #...
$

I’m a little sad that named groups are not available in Javascript; remove all comments, white space and line-breaks from the above, and you can expect the capturing groups to contain the following:

  1. The scheme: http, https or ftp
  2. Either “//” followed by a host (authority), or otherwise the first part of the path
  3. The username:password@ of the authority, or nothing if absent
  4. The hostname from the authority
  5. The :port of the authority
  6. All of the URL path if there was a host (authority), or otherwise the remainder of the path after the first level
  7. The ?query portion of the URL
  8. The #fragment portion of the URL

Clearly some more post-processing needed to extract the actual values if you want to. Although I strongly recommend using a proper Uri class if you really want to process the content, rather than just getting a quick yes/no whether a URL seems plausibly valid.

Next stop… email addresses – RFC 5322.

As agonising as all this sounds, even to me, I am actually having a great deal of fun right now.

Planning and Learning

This morning I successfully acquired the right SIM for my new phone. The transaction at Virgin Mobile Blacktown was quick and painless. I will need to spend a few more days making sure I get everything I care about across from the Galaxy Nexus to the Nexus 5, but then I can wipe the former and dispose of it.

In an hour I have a 30 minute cycle class to break up the day.
And then…

I’m going to start on a Web 2.0 adventure. I’ve meant to learn some new skills and build something for too long now. Time to bite the bullet.

I have the outline of an idea for a set of related problems I want to solve (scratching your own itch has been proven the best place to start). I have VS2013 Beta on my machine (so an upgrade will be in order first). And I have a list of compatible technologies to explore.

I guess this also means my personal GitHub account will finally get some love.

Wish me luck!

Floating Point One-Pager

Broadly speaking this post will go into increasing technical detail so that you may stop reading at the point where you either:

  1. Lose Interest
  2. Find the Answer you are After
  3. Lose the Ability to Follow My Garbled Writing

Note that regardless, this is by no means an exhaustive exploration of the topic. There is some significant glossing-over-details; I have merely tried to put “The Rules” into some context, and point the way to some problems you might want to delve deeper into by reading the references at the bottom for yourself.

After studying and digesting articles for a week, the only thing I can be certain of is that I have never fully comprehended all the dangers inherent in floating point numbers. And I never will. And neither, probably, will you.

All we’ll be able to do is take as much care as possible, and hope for the best.

Now, let’s go limit the damage we all might do.

Into the lair of IEEE 754 we go!

The Rules

If you don’t want to think, if you just want some rules-of-thumb to blindly follow, this is the section for you.

  • Multiplications and divisions are safe
  • Series of additions and subtractions should be ordered to operate on values of the closest magnitude first where possible
  • Do not compare floating point numbers directly
  • Do not use “Epsilon” to compare floating point numbers either
  • Use bankers rounding (round-to-even) whenever possible
  • Run code as 64-bit executables whenever possible
  • Never make any assumptions about how many decimal places are “good”, no, not even 2!

Comparing the Wrong Way

Most, if not all, programmers know that directly comparing two floating point numbers for equality does not work. If they are almost-but-not-quite-completely the same number, the code will fail.

0.1 x 10 != 1.0

Rounding errors along the way will kill any exact comparison.

The most common solution that gets suggested is to check if the absolute difference between two numbers is smaller than some tiny amount, and declare the numbers equal if that is the case:

if (Math.Abs(a - b) < 0.00001)
{
    ... NOTE: WRONG WAY TO DO IT! ...
}

if (Math.Abs(a - b) < Double.Epsilon)
{
    ... NOTE: WRONG WAY TO DO IT! ...
}

The former will work or not depending on the magnitude of “a” and “b”; if the two numbers are large relative to the “0.00001” bias it will work, but if they are smaller or even close to the bias itself, then the code will suddenly start failing.

The latter will probably never work; it is essentially the same as saying the two numbers need to be exactly equal, because “Double.Epsilon” is the smallest representable fraction in doubles, and the only thing that is smaller than the smallest representable fraction is equality.

Do not use either of these approaches.

Comparing using Relative Error

It is much better to do a comparison based on relative error, because the difference will scale with the inputs; the author of The Floating Point Guide recommends the following:

static bool RelativeCompare(double a, double b, double epsilon)
{
    // Compare NaNs and infinites
    if (a == b)
        return true;

    // Where relative error is meaningless use a direct epsilon
    double diff = Math.Abs(a - b);
    if ((a == 0) || (b == 0) || diff < double.MinValue)
        return diff < epsilon * double.MinValue;

    // Otherwise use relative error
    return diff / (Math.Abs(a) + Math.Abs(b)) < epsilon;
}

See The Floating Point Guide for a more detailed explanation and a link to an extensive test-suite for this code.

Comparing using ULPs

The most advanced solution to comparing floating point numbers is based on a key trick; when you re-interpret IEEE 754 floating point numbers as integers, the difference between two of those integers represents how many different floating point numbers exist between the two that were converted.

If you want a bit more explanation I suggest reading the 2012 edition of Comparing Floating Point Numbers by Bruce Dawson.

A .NET implementation of the relevant algorithms:

// Slow but safe version
static long DoubleToLong(double d)
{
    return BitConverter.ToInt64(BitConverter.GetBytes(d), 0);
}

// Fast but "unsafe" version
static unsafe long DoubleToLong(double d)
{
    return *((long*)&d);
}

static long UlpDistance(double a, double b)
{
    long intA = DoubleToLong(a);
    if (intA < 0)
        intA = Int64.MinValue - intA;

    long intB = DoubleToLong(b);
    if (intB < 0)
        intB = Int64.MinValue - intB;

    return Math.Abs(intA - intB);
}

static bool UlpCompare(double a, double b, long distance)
{
    return UlpDistance(a, b) <= distance;
}

The UlpDistance function returns the distance between two double precision floating point numbers. If this returns:

  • 0 – the floating point numbers are exactly identical
  • 1 – the floating point numbers are adjacent
  • 2 – there is one possible floating point representation between them
  • etc.

And by using the UlpCompare function you can indicate how close two floating point numbers must be to be considered equal, in a scale-independent way. In essence, the magnitude of the bias scales with the size of the values being compared.

A distance of about a million is enough to reasonably establish equality.

Problem Scenarios

Multiplication and Division

It may at first seem counter-intuitive that multiplication and division would not pose any problems. The reason for this is fairly simple though.

To illustrate, lets work in decimal and pretend we have 4 significant digits in our floating point representation:

(2.131 x 102) x (1.943 x 10-4)
= (non-rounded interim value) 4.140533 x 10-2
= 4.141 x 10-2

 
Even when two floating point numbers have wildly different exponents, the act of multiplying or dividing simply shifts the exponent of the result. And on either side of the calculation we have a full complement of significant digits.

Addition and Subtraction

For exactly the same reason, additions and subtractions can be problematic when dealing with big differences in exponents:

(2.131 x 102) + (1.943 x 10-4)
= 213.1 + 0.0001943
= (non-rounded interim value) 213.1001943
= 213.1
= 2.131 x 102

 
With a single addition or subtraction this loss of precision is unavoidable, because at the end of the calculation everything has to fit again into a finite amount of precision.

However, if you add a large series of numbers it suddenly becomes important to think about your additions:

(2.131 x 102) + (1.943 x 10-4) + … 999 times the same number
= 213.1 + 0.0001943 + … 999 more
= 213.1 + … 999 more
= 213.1 + 0.0001943 + … 998 more
= …
= 2.131 x 102

 
Every time an addition is performed in the CPU, the result needs to fit within our floating point representation and gets rounded to the original value. If we however perform the additions the other way around:

(2.131 x 102) + (1.943 x 10-5) + … 999 times the same number
= 213.1 + 0.0001943 + … 999 more
= 213.1 + 0.0003886 + … 998 more
= …
= 213.1 + 0.1943
= 213.2943
= 2.133 x 102

 
It’s not a big difference in this case, but depending on the number of additions involved and the relative magnitudes of the numbers it can make more or less of a difference. And all for the sake of re-ordering some additions.

If you were really keen you could probably develop some LINQ extensions in .NET that automatically re-order addition and subtraction sequences into the sequence in which the result is most accurate.

For now the point is: consider whether the values you are adding have wildly divergent magnitudes, and where possible try to order them to keep values with the same magnitude closer together to optimise for the most accurate result.

Rounding

Have you ever used Math.Round in .NET? Were you a little confused at first? So was I.

You see, it uses Bankers Rounding by default (overloads exist where a rounding algorithm can be specified). When rounding 2.5, you’d usually expect to end up with 3, but Bankers Rounding doesn’t round all .5s equally. It rounds towards even, so 1.5 becomes 2, but 2.5 also becomes 2, then 3.5 becomes 4, and so on.

This is actually a very sensible default, but it isn’t well explained. In most cases the default for IEEE 754 operations is the same for the same reasons.

The problem with “normal” rounding is that it rounds 4 values down (0.1 – 0.4) and it rounds 5 values up (0.5 – 0.9). For one rounding operation this isn’t too big a deal, but most calculations round multiple times along the way. The compounding effect of this rounding bias is that results can slowly creep upwards with every rounding.

Bankers Rounding however on average rounds just as much up as it does down. As a result repeating rounding along the path of a calculation will jitter up just as much as down and on average not introduce any bias.

If you have end-users that might be confused by Bankers Rounding, then try to restrict “normal” rounding only to the last operation before display and keep using Bankers Rounding internally.

Representational Error

Below in the technical bits there is an explanation why IEEE 754 floating point numbers cannot precisely represent the value 0.1; it results in an infinite binary expansion:

0.1 (decimal) = 1.1001100110011… (binary) × 2−4

As a consequence it is safe to say that most real-world values cannot be accurately represented in double precision floating point numbers; as soon as you parse a value from a text file or a NUMBER from a database into a double, it is no longer completely accurate.

Basically, any real-world value becomes inaccurate before you even perform any operations on it.

The only reason this isn’t patently obvious all over the place is because floating point numbers tend to get rounded again before display, and in most cases this rounds away the error that this parsing introduces.

0.1 (decimal) becomes 0.10000000000000000555111… once it is parsed. Display routines will never show that many decimal places for a double, but it’s only a matter of a few calculations before that error creeps into decimals that do show up. Nine additions of the same number is all it takes to turn this into a real error.

It is important to remember that errors are pervasive and unavoidable.

It’s all about strategically structuring code to limit the ways in which these errors can compound and inflate.

Loss of Scale Issues

This is a particularly insidious problem, because it tends to not be evident when a program is first written. It literally takes time for this problem to become evident, typically once a program is running in production, or long after a library is first written.

This problem exhibits itself when measuring elapsed time (since application start, or some fixed point in the past), or when data volumes might increase over time.

When the elapsed time is small, or calculated values operate on limited data, this means that the magnitude of values will also be small. As a result, a large amount of the precision of a float is still in the fractional part of the result.

As time passes, as data volumes grow, as the magnitude of results grows, less and less of the floating point precision is represented in the fractional part.

If you assume your values will always have 2, 3, 5, any number of accurate decimal places, you may one day be taken by surprise when that stops being true. A single-precision float has only 6-9 significant digits. Once the magnitude of your value goes into the millions, you cannot count on any accurate decimals. Doubles have a bit more headroom, but it is still not impossible to run out of headroom with 15 significant digits.

And your calculations will start showing visible inaccuracies in any decimal places well before you hit the limits on the result.

The Technical Bits

Double precision floating point numbers are 64-bit numbers, laid out as follows:

Double precision floating point bits

The meaning of these bits is expressed in the formula in the header of this post:

Double precision floating point interpretation

Meaning:

  • The sign-bit is set for negative numbers
  • The fraction is applied as the binary “decimal” places in: 1.xxxxx…
  • The exponent is used to multiply this fraction across 2-1022 to 21023

As a result, double precision can roughly express:

  • 15 significant decimal places of precision
  • Values as small as ±5.0 × 10−324
  • Values as large as ±1.7 × 10308

Magic with Integers – 1

Less obviously, but more remarkably: this carefully designed binary format means that if you re-interpret two doubles of the same sign as 64-bit integers and subtract these integers, the difference will tell you how many distinct double precision floating point numbers lie in between. (0 = equal, 1 = none in between, 2 = 1 in between, etc.)

Conversely, if you increment or decrement the integer representation of a floating point number, it will give you the very next larger or smaller floating point number that can be represented.

Magic with Integers – 2

Between using the fraction bits with a leading 1 and an exponent of 1075 (corresponding to 252), and the de-normalized values including 0, doubles can contain exact representations of all integers from -(253) up to +(253). Within these bounds all arithmetic with integer inputs and results will be exact at all times.

Because of the 52-bit fraction though, once you pass 253, you will only be able to exactly represent even numbers. And past 254 only multiples of 4, and so on.

The distance between representable integers doubles past each power of 2.

Floating Point Spacing

This is also true in the opposite direction, where up to 252 all halves can be exactly represented, and up to 251 all quarters, and so on.

If you were to plot marks of exactly representable integers in the double precision floating point domain you would have a ruler where towards the left, passing each power of two, the marks get twice as close together and to the right, passing each power of two, the marks get twice as distant.

Double Precision Floating Point Ruler
Double Precision Floating Point Ruler

Representation Difficulties

The biggest problem with binary floating point numbers is that we live in a decimal world. Our reality has a nasty habit of thinking in terms of tenths, or hundredths, or thousandths.

Per the formula for floating point representations, something simple can prove impossible to represent:

0.1 (decimal) = 1.1001100110011… (binary) × 2−4

To exactly represent a decimal 0.1, you need an infinitely recurring fraction in binary. As a result, the closest possible representation in binary that fits within a double translates to approximately 0.10000000000000000555111… in decimal.

And depending on how these tiny inaccuracies stack it might get better or worse.

If you multiply 0.1 by 10.0, you get an exactly represented 1 due to some fortuitous rounding. If you add 0.1 ten times however, you get something slightly above 1. The type and order of arithmetic operations can either make the problem worse, or purely coincidentally, as if it never existed.

Internal Representation Trouble

If all this wasn’t difficult enough yet, in a well-meaning effort to improve accuracy, the x87 floating point instructions have 80-bit internal registers available. Arguably use of this extra precision does not harm the accuracy of calculations, but depending on when they do or do not get used, two applications executing the exact same sequence of operations may provide different results with no easy way to determine which of the two is the more accurate result.

It goes something like this:

  • Calculations that remain in internal registers use 80-bits
  • Except when they get written to/from memory, in which case they are rounded to 64-bit. When and whether this happens depends on how good the optimizer of the compiler is, and it may alter from version to version of the compiler itself.
  • Or if the FPU is switched into a mode where it forces 64-bit precision internally. From what I have read it is highly likely the .NET runtime does this, but none of the sources are committing to saying so outright.
  • Also, 64-bit executables will be 64-bit only because they will be using SSE and not x87, which has never and will never have 80-bit registers.

All-in-all, it is best to try and force applications to use 64-bit internally to ensure repeatable behaviour. And while at it, switch to a 64-bit version of Excel, and hope that Microsoft does not decide to do anything clever internally.

These discrepancies are the most annoying in dev/test scenarios where developers and testers get different results. It can be very hard to be certain whether a difference is due to discrepancies in accuracy, or if either algorithm is incorrect.

Decimal To The Rescue!

Working in .NET, one possible solution is to use Decimal type wherever possible.

The reason this helps has less to do with the fact this type uses 96 bits for the representation of the digits. It has a lot more to do with the exponent. The formula for Decimal is as follows:

(-1)s × (96-bit integer number) × 10-e, where e = 0-28.

The exponent is applied to powers of 10, which means that commonly occurring real-world fractions can be exactly represented. If you deal with money, a decimal can contain 2 exact fractional digits.

The only down-side is performance; you pay for these awkward-for-computers-to-process powers of 10 with up to 20-fold reduction in performance for arithmetic operations. This is definitely a worst-case-scenario number, but regardless it is a steep price to pay.

References

If you want to investigate further yourself, consider the following sources:

  1. Wikipedia: Double-precision floating-point format
  2. The Floating-Point Guide
  3. What Every Computer Scientist Should Know About Floating-Point Arithmetic
  4. IEEE 754-2008

Back to Basics

For a while now I have been postponing writing a post about my progress regarding exceptions in software. I have informally formed an outline of an opinion, but I have been looking for a way to build a stronger foundation than “because I think that’s the right way to do it”.

Then, as I started straying further afield with my mind wandering over multi-threaded code, dependency injection, unit testing and mocking as well (and some others that I know I have forgotten), it occurred to me that I really should go back to basics with all this…

  • The most fundamental tool to reason about software correctness is still to think in terms of invariants over state-space and pre-conditions/post-conditions to method invocations.
  • Guides on “good coding practices” abound, but there are certain fundamental truths in most of them that are universal enough to almost be as good as “formal methods” to reason about “good code” beyond merely “correct code”.
  • Both the DRY principle (“don’t repeat yourself”) and a desire to produce self-documenting code further suggest that keeping as many perspectives on a single piece of code as close together as possible is the best way forward. The new .NET 4 Code Contracts already provide some unification between code, documentation and testing, but I think there is more possible that has not been exploited yet in this arena. Some tricks may be needed to keep aspects such as tests and documentation together with the code without overly burdening the generated assemblies with dead weight that does not participate in the execution of the code itself.

I strongly believe that C# as a language leaves us with too much flexibility in the general case. Every iteration of the language adds more interacting features, and opens up many useful possibilities as well as some that are dangerous or perhaps even plain wrong.

Some code patterns, although allowed by the compiler, just do not make any sense. There are usage patterns of exceptions that *will* compile, but really should be considered an error.

Tools like FxCop try to plug some of those holes by checking for such errors after-the-fact. Unfortunately, custom error conditions are not as easy to express in FxCop as I think they ought to be. But in principle this is definitely a path worth exploring to eliminate options that might be best avoided.

I think the rather nebulous state of this post reflects the fact that my mind hasn’t completely crystalised into a single vision of what combination of tools and paradigms I need to get to more ideal development practices. But I think I am starting to make some progress.