{"id":523,"date":"2007-10-02T11:03:34","date_gmt":"2007-10-02T11:03:34","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/10\/02\/the-excel-65535100000-bug\/"},"modified":"2007-10-02T11:03:34","modified_gmt":"2007-10-02T11:03:34","slug":"the-excel-65535100000-bug","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/10\/02\/the-excel-65535100000-bug\/","title":{"rendered":"The Excel 65,535=100,000 Bug"},"content":{"rendered":"

I’ve been getting a lot of requests from people to talk about the recent Excel bug<\/a>. For those of
\nyou who haven’t heard about this, in Excel 2007, floating point calculations that should result in
\na number very, very<\/em> close to either 65,535 or 65,536 are displaying their result as 100,000.
\nIt’s only in the display though – the underlying number is actually represented correctly, so if you subtract 2 from 65,536, you’ll get the correct answer of 65,534 – not 99,998.<\/p>\n

I can’t give you the specifics – because without seeing the Excel code, I can’t tell exactly what they got wrong. But I’ve got some pretty good suspicions, so I’ll do my best to explain the background that leads to the problem, and what I think is probably going on. (Another excellent explanation if this
\nis in the Wolfram blog post<\/a> that I mentioned in my fast arithmetic fractals post<\/a> this weekend.)<\/p>\n

<\/p>\n

When you’re working with numbers on in a program like excel, you’re using something called floating point numbers. Floating point is annoying, seriously annoying. It’s an approximation<\/em> of real numbers using a finite precision in a way that allows arithmetic operations to be done reasonably quickly. (It’s still a whole lot slower than working with integers, but it’s usually pretty good.)<\/p>\n

\tWithout going into the gory details, what floating point means is that the number is represented by a fixed-precision number in a strange form of scientific notation. So, for example, in 4-digit base-10 floating point, the number 600 is actually represented as 0.6000×103<\/sup>; 31.4159 is represented as 0.3142×103<\/sup>. Notice what happened in that second case – we lost two digits, because the 4-digit float representation didn’t have enough precision to represent all of the digits.<\/p>\n

To make matters worse, floating point doesn’t using base-10. It’s binary: so numbers are really represented by a base-2 fraction and a base-2 exponent. So, for example, 1\/4 is really represented as
\n0.1×2-1<\/sup>.<\/p>\n

There are a couple of unfortunate side-effects of this:<\/p>\n

    \n
  1. The one which most people have seen in some form,
    \nis that almost every floating point computation accumulates errors: because of the finite precision,
    \nevery step performs a round-off, which can add a bit of error. The more you do, the larger the accumulated effects of roundoff errors can become. The typical example of this is on many calculators, if you do 2 – (sqrt(2)^2), you’ll get something odd like 0.00000000012.<\/li>\n
  2. The order in which you perform a computation can have a huge impact on the precision of the result.
    \nFor example, in base-10 4 digit floating point, with 1-digit exponents, if you have (0.1E-9)×(0.3E0)×(0.4E8), if you do the first pair of numbers first, it evaluates to
    \n0E0×0.4E8=0. If you do it in the second order, it evaluates to 0.1E-9×0.12E8=0.12E-2.<\/li>\n
  3. In order to display a value to a user, you need to convert it from base-2 scientific notation
    \nto a standard base-10 representation. There are a bunch of problems here: doing the conversion is
    \npotentially quite slow, involving multiple divisions (with the attendant round-off errors); and
    \nyou want to present the number to the user correctly; while the base-10 conversion might result in
    \n1.999999999999999999999999999999999999, you probably want to output that as 2. <\/li>\n<\/ol>\n

    The last is the problem in Excel. Converting to print format is very slow – so people devote enormous
    \namounts of effort to finding algorithms that make it faster. Every corner that can reasonably be cut
    \nin order to save a bit of time is cut. At the same time, you want to get the number out correctly – so along with doing your clever optimization, you’re always keeping your eyes open for one of the cases
    \nwhere the round-off errors should be corrected – like rounding 65,534.999999 to 65,535. <\/p>\n

    The problem with that is that floating point representation
    \nis very complicated, and there are an incredible number of different numbers that can be represented.
    \nIt’s very easy to write code which seems<\/em> correct, and which works perfectly on nearly every
    \nfloating point value, but which contains an error which will manifest on a dozen bit patterns.
    \nYou can test that code on billions of different values, and still miss the crucial couple that reveal
    \nthe problem.<\/p>\n

    It looks like the Excel bug is one of those cases. My suspicion is that there’s an unfortunate interaction between the code that tries to prevent generating numbers like 1.99999999999999999 instead of 2, and the code that does the optimized conversion. What it looks like is that the rounding-error correction is probably over-doing its job; it’s doing the roundoff and presenting its result back
    \nto the output code in what looks like it’s already base-10 format.<\/p>\n

    In general, I like ragging on Microsoft as much (if not more than) you average Mac user. But I can’t say that I really blame them too much for this one. Floating point arithmetic and conversion is a nightmare – it’s enormously complex, and the demand for speed is extraordinary. Slowing things down a tiny bit – taking an extra microsecond per conversion – can have a huge impact on the performance of the system. That kind of code is under constant pressure to squeeze out every last drop of performance. And errors like this are so<\/em> easy to miss, while catching them
    \nin testing is almost impossible. You can only reliably catch this kind of problem by doing a detailed analysis of the logic of the code, and all you need to do is miss one out of hundreds of different corner cases, and you’re hosed. It’s just so hard to get right that the only surprise is that they’ve made so few mistakes like this.<\/p>\n","protected":false},"excerpt":{"rendered":"

    I’ve been getting a lot of requests from people to talk about the recent Excel bug. For those of you who haven’t heard about this, in Excel 2007, floating point calculations that should result in a number very, very close to either 65,535 or 65,536 are displaying their result as 100,000. It’s only in the […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[7],"tags":[],"class_list":["post-523","post","type-post","status-publish","format-standard","hentry","category-bad-software"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-8r","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/523","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=523"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/523\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=523"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=523"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=523"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}