34

My teacher who teaches "Logic" at the university told us a story about Intel processors, which goes: "In the 90s, Intel had a bug in the calculation of mathematical functions like sine or cosine encoded in the processor. This bug created inconsistencies in some bank accounts, bringing Intel to hire logicians in order to demonstrate the correctness of the code."

I tried to search this story around the web but I did not find anything. Does anyone know anything about it or can anyone give me some sources?

Improve this question
17
  • 42
    Such bugs do happen (see infamous FDIV bug mentioned by others), but this particular story appears to be a bit distorted. It's hard to imagine what use could a bank have for trigonometric functions, and the values of trigonometric functions have been tabulated for decades if not centuries to high precision - any discrepancy could be easily verified without hiring someone to examine algorithms. The FDIV bug is not a close match because Intel was indeed wrong on that one (and the error was not algorithmic but a missing column in a lookup table). Looking forward to a closer match.
    – Euro Micelli
    Commented Oct 12, 2020 at 16:55
  • 17
    Also every CPU has a tremendous bugs historically and now, google for "xxxx processor errata", e.g. ARM A77 errata is 59 pages: developer.arm.com/documentation/101992/0009
    – user3528438
    Commented Oct 12, 2020 at 21:43
  • 11
    Unfortunately, Intel has recently gotten rid of its validation team: danluu.com/cpu-bugs/#update
    – forest
    Commented Oct 13, 2020 at 2:53
  • 21
    @user3528438 So true about the errata. These can be really annoying when you run into them. A digital signal processor that we used on a project back over a decade ago - a product which we still manufacture to this day - had a couple of rather unfortunate silicon anomalies. One of them sometimes resulted in corruption of the DMA control registers when using the USB controller's DMA mode 0. The only listed workaround was to use mode 1. The other resulted in occasional corruption of the DMA control registers when using mode 1... with a listed workaround of using mode 0...
    – reirab
    Commented Oct 13, 2020 at 15:33
  • 11
    A joke I heard at the time was: "At Intel, quality is job 0.999999999."
    – Doug Warren
    Commented Oct 14, 2020 at 13:22

5 Answers 5

Reset to default
91

I suspect your teacher was referring to the FDIV Pentium bug, which led to a large outcry in the media at the time and for which Intel issued a recall.

This bug caused floating-point division to return incorrect results in some cases. It didn’t affect only FDIV, some related instructions were affected: the other division and remainder instructions, and FPTAN and FPATAN. Other trigonometric instructions were treated with suspicion, but ultimately cleared, including FSIN and FCOS.

It does however seem unlikely that this would cause problems in banks: financial applications typically avoid floating point representations, so errors in a floating-point instruction would be unlikely to affect them.

See also the Wikipedia entry on this bug. Another famous Pentium bug was the F00F bug. It didn’t cause calculation errors but it could lead to lock-ups, and was worked around by specific handling in operating systems.

Improve this answer
20
  • 24
    To this day, the Linux kernel has code to detect if your processor has this bug: github.com/torvalds/linux/blob/v5.9/arch/x86/kernel/fpu/bugs.c
    – IMSoP
    Commented Oct 12, 2020 at 18:40
  • 20
    FWIW, the FSIN and FCOS instructions are rather useless except perhaps for size optimization in code where you don't care about the correct result. They're slower than library implementations (and always have been) and also have serious accuracy problems.
    – R.. GitHub STOP HELPING ICE
    Commented Oct 13, 2020 at 0:34
  • 14
    I was working on the (Silicon Graphics) IRIX kernel at the time, and had the privilege of writing code in the OS loader to detect the use of potentially buggy instructions and, if found, overwrite them with an invalid machine language instruction. This would invoke the fault handler at runtime, where another bit of code would determine if the arguments were likely to get invalid results and if so implement the division in a software "longhand." Pretty expensive fix!
    – Myk Willis
    Commented Oct 13, 2020 at 19:56
  • 12
    @ChrisH: In financial calculations, "never use (binary) floating-point" is a pretty well-known rule. (At least as an example for general audiences of where not to use FP, but it's probably actually true). Extended precision / fixed-point integer to make sure the fractional part (cents) isn't rounded, or possibly decimal floating-point (which x86 doesn't support in hardware, but PowerPC does). Note that binary (normal) floating point can't exactly represent a value such as 0.01 because the fractional part's denominator isn't a power of 2.
    – Peter Cordes
    Commented Oct 14, 2020 at 2:26
  • 12
    A lot of times it's stated as "financial applications should never use floating point," but what is really meant is "accounting applications should never use floating point." Many tasks in the realm of finance don't involve counting pennies, and many tasks outside of finance have similar problems with accurate number representation. That is why the libraries are described as "arbitrary precision math" and not "finance math."
    – fluffysheap
    Commented Oct 14, 2020 at 16:25
32

Stephen Kitt has already provided a good answer regarding the FDIV bug. I'll fill in some details about Intel employing logicians:

Because of this bug, Intel had to replace a lot of processors, which was very expensive. Not wanting to repeat this, they hired a number of computer scientists with background in formal logic to prove the correctness of algorithms to be implemented in successors of the pentium. If you want to know more about their research, check out the publications of two of these scientists: https://www.cl.cam.ac.uk/~jrh13/papers/index.html, https://scholar.google.com/citations?user=MACCA0cAAAAJ&hl=en

Improve this answer
1
  • 15
    The FDIV bug wasn't an algorithm bug, it was a wrong implementation of a lookup table such that 5 cells that should have been +2 read as 0. Possibly an algorithm bug in whatever generated that table, but the wikipedia description makes it sound like the storage cells were actually missing. This bug is also one of the major reasons why later Intel CPUs have a microcode-update interface. - future problems discovered in more complicated CPUs can be mitigated, sometimes with a performance cost.
    – Peter Cordes
    Commented Oct 14, 2020 at 2:48
26

Intel had a rather complex bunch of hardware to compute a floating-point quotient in a way that yielded two bits per iteration, which required having a rather large table listing all the combinations of bit patterns where part of the quotient should be 11 [rather than listing all patterns individually, the table would have had entries where each bit may be 0, 1, or X, such that e.g. a bit pattern of 100X01X would match 1000010, 1000011, 1001010, or 1001011, so the table didn't need an impossibly huge number of entries]. Unfortunately, part of the table got corrupted when it was being transferred from whatever tool was used to generate it, into the chip design.

I find this approach to division somewhat curious, since it would have been quick to examine the divisor and produce a value which, when multiplied by both the divisor (rounding up) and dividend (rounding down), would force the new divisor to have its upper bits equal to 0.1111 or 0.11111111, which would make it easy to extract 4 or 8 bits per iteration. The final quotient would likely be slightly less than the correct value [never greater, given the directions of rounding earlier], but it would be close enough that only two or three couple of successive-approximation steps should be needed at the end to clean things up.

In any case, the ultimate irony with the Intel FDIV bug is that, earlier, during the 386/387 era, there was a competing product by Weitek which could perform single-precision floating-point math much faster than Intel's chips, but didn't do double precision math at all. Some programs which would normally have used double-precision math shipped versions for the Weitek which used single-precision math and thus produced less accurate results. Intel's marketing team decided to exploit this (designed, and regarded as acceptable) lack of precision by producing an ad which showed a motherboard with a dime-store calculator decorated with clown graphics where the CPU should have been, and the caption "Ask for genuine Intel Math CoProcessors, or who knows what math you’ll have to count on".

Improve this answer
2
  • 9
    very informative answer. And the ad is so ironical in hindsight !
    – Olivier Dulac
    Commented Oct 13, 2020 at 23:11
  • Fairchild PDIP buffer circuits! Yeah what a joke, I wouldn't count on those :)
    – Lundin
    Commented Nov 6 at 15:25
4

I think this is probably referring to the Pentium FDIV bug (floating-point divide bug).

I don't recall any specific problems with trigonometry instructions.

Improve this answer
5
  • 1
    Trigonometry instructions are dependent on division. In early x87 FPUs it was explicit - there was a single trigonometric instruction and it gave 2 results. You had to divide one by the other to get tg / cotg (no, they were not sin and cos as one would initially think, FSINCOS instruction appeared later) and do even more (including divisions) in order to get sin/cos.
    – fraxinus
    Commented Oct 13, 2020 at 7:04
  • 1
    Intel wasn't the only manufacturer to have trouble with floating point arithmetic. The DEC PDP-6 also gave unfortunate results for some of its floating point ops. I'm saying unfortunate instead of erroneous, because a floating point operation sometimes requires roundoff to provide a representable result.
    – Walter Mitty
    Commented Oct 13, 2020 at 10:52
  • 1
    There is/was a documentation bug for the error bounds of fsin: randomascii.wordpress.com/2014/10/09/…. Intel used to claim 1ulp precision, but that's extremely far from true for some worst-case inputs near pi (e.g. less than 4 of 64 mantissa bits correct), and even worse for large-magnitude inputs. Because x87 uses its 64-bit-mantissa Pi value for range-reduction, not a higher precision value. But this doc bug was only discovered / corrected in 2014.
    – Peter Cordes
    Commented Oct 14, 2020 at 2:57
  • 1
    @PeterCordes: A better spec for intrinsics would be to specify that the result will be within a certain tolerance of the exact value for some value of input within a certain tolerance of the given input. There are very few non-contrived situations where a function that returns a value within one ulp of the sine of exactly x within 1ulp would be more useful than a function that was 1% faster and returned a value within 0.5ulp of the sine of some number within 0.5ulp of the specified value.
    – supercat
    Commented Oct 15, 2020 at 17:33
  • 1
    @PeterCordes: Actually, I suspect that for many purposes a function that returns the sine of 1.00000000000000003898x would be more useful than a function that returns the sine of exactly x, since accurately multiplying a floating-point number by 3.141592653589793115998 is a lot easier than accurately multiplying by π.
    – supercat
    Commented Oct 15, 2020 at 17:40
2

I suspect two stories get mixed up here. Much later than the fdiv bug, Intel did have a bad accuracy bug in sine and cosine of values close to pi as documented in Bruce Dawsons 2014 blog entry Intel Underestimates Error Bounds by 1.3 quintillion (see also in a reddit post) and this detailed analysis.

Quoting the reddit discussion, in one case the right sine was 1.188×10−20 but in fact, the value returned by the Intel x87 floating point unit is about: −3.407×10−3 .

At some later point in time AMD tried to break compatibility with intel's x86 and fix these implementations, but lots of software broke as a result and they gave up. Can't find a reference now, just remember something like that.

Improve this answer
7
  • Not really sure if that's a mix up, as the sine part never made much talk despite being known (back then people had different tolerance) at least until original 8087 (which AMD licenced until 486 times) if not all the way to AMD's original 9511 implementation, while the FDIV bug did make major news in every non-tech media around the planet. Would be nice if you could add sources and details for the claim in the last para.
    – Raffzahn
    Commented Nov 2 at 13:05
  • 1
    @Raffzahn The algorithms for the transcendental instructions (including the argument reduction) of the Am9511 are explained in detail in the "Floating Point Processor Manual Am9511A/Am9512", AMD 1986. They are based on Chebyshev polynomials, specifically C.W. Clenshaw, G.F. Miller and M. Woodger, "Algorithms for special functions I." Numerische Mathematik 4, 403-419 (1963). To my knowledge, nothing similar has ever been used in an x87 coprocessor or FPU.
    – njuffa
    Commented Nov 2 at 22:07
  • 2
    Re "AMD tried to break compatibility with intel's x86" The AMD K5 used a 256-bit representation of π/2: T. Lynch, et al., "The K5 Transcendental Functions." In Proceedings of the 12th Symposium on Computer Arithmetic, Jul. 1995, pp. 163-170. I don't recall that it "broke software", but that could plausibly have occurred. For the AMD Athlon processor (K7) I was in charge of compatibility with Intel's FPU and simply decided the safest way in a high-stakes game (AMD might have folded had the K7 flopped) was to stick with the same 66-bit value of π/2 that Intel had been using since the 80387.
    – njuffa
    Commented Nov 2 at 22:16
  • 1
    FWIW, Intel disclosed the exact 66-bit value of π/2 in the 387 User Manual (section 4.5 Transcendental Instructions), so it should not have come as a surprise to any programmers that read the documentation. The general problem of trig functions with a period of π⁺ instead of π due to limited-precision value of π⁺ in argument reduction was already discussed in Palmer/Morse, The 8087 Primer (1984).
    – njuffa
    Commented Nov 2 at 22:22
  • 1
    @Raffzahn I agree with that assessment. Maybe not that well-known, or possibly somewhat obscure. Enough so that it led to attention-garnering blog posts :-) The positive outcome of the hubbub some years back is that Intel improved their documentation. My vague memory is that the use of a limited precision machine PI was not perceived as an actionable issue early in the life of x87; it was noted in passing. A practical "proper" trig function argument reduction for use in software was not available until 1983 (Payne/Hanek), which would, however, have trouble fitting into a typical microcode ROM.
    – njuffa
    Commented Nov 3 at 19:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .