Glaring FDIV bug in Pentium!
Dik T. Winter
> In article <1994Nov16.1...@vitsemi.com>,
> Tim Coe <c...@vitsemi.com> wrote:
> >(4195835 / 3145727) * 4195835
> >
> >The result was 4195579.
> >This represents an error of 256 or one part in ~16000.
>
I would say the error is much larger as the correct result is about 5596491.
I think you intended: (4195835 / 3145727) * 3145727. But in that case the
result tends to show 11 digits intermediate precision.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924098
home: bovenover 215, 1025 jn amsterdam, nederland; e-mail: d...@cwi.nl
Peter Gutmann
>In article <1994Nov16.1...@vitsemi.com>,
>Tim Coe <c...@vitsemi.com> wrote:
>>On a Packard Bell P90 PC I performed the following
>>calculation using Microsoft Windows Desk Calculator:
>>
>>(4195835 / 3145727) * 4195835
>>
>>The result was 4195579.
>>This represents an error of 256 or one part in ~16000.
>Are you definite that MS Windows and specifically the Desk Calculator
>takes advantage of a floating point unit and uses the FDIV instruction?
Actually, the desk calculator is somewhat buggy, as I pointed out in a
followup to the original post in comp.sys.intel - you can get it to produce
errors even without a Pentium.
Peter.
Herb Savage
>
>Not seen the original, but:
> > In article <1994Nov16.1...@vitsemi.com>,
> > Tim Coe <c...@vitsemi.com> wrote:
> > >(4195835 / 3145727) * 4195835
> > >
> > >The result was 4195579.
> > >This represents an error of 256 or one part in ~16000.
> >
>I would say the error is much larger as the correct result is about 5596491.
>I think you intended: (4195835 / 3145727) * 3145727. But in that case the
>result tends to show 11 digits intermediate precision.
On my Pentium 4195835 / 3145727 is 1.333739068902
on a 486 4195835 / 3145727 is 1.333820449136
It looks like a lot less than 11 digits of intermediate precision to me.
Herb Savage
e-mail: he...@perftech.com
Tim Coe
posted to comp.sys.intel. A more complete tentative
software model of the Pentium divider that explains
all divide errors that I am aware of is included with
this post.
On a Packard Bell P90 PC I performed the following
calculation using Microsoft Windows Desk Calculator:
(4195835 / 3145727) * 4195835
The result was 4195579.
This represents an error of 256 or one part in ~16000.
a...@ananke.s.bawue.de (Andreas Kaiser) writes
>Usually, the division is correct (what did you expect?). Just a few
>operands are divided wrong. My results (P90) with ~25.000.000.000
>random arguments (within 1..2^46), with even results divided by two
>until odd, to assure unique mantissa patterns (the binary exponent
>doesn't care, of course).
>
> 3221224323
> 12884897291
> 206158356633
> 824633702441
> 1443107810341
> 6597069619549
> 9895574626641
> 13194134824767
> 13194134826115
> 13194134827143
> 13194134827457
> 13194138356107
> 13194139238995
> 26388269649885
> 26388269650425
> 26388269651561
> 26388276711601
> 26388276712811
> 52776539295213
> 52776539301125
> 52776539301653
> 52776539307823
> 52776553426399
>
> Gruss, Andreas
>
>--------------------
>-- Andreas Kaiser -- internet: a...@ananke.s.bawue.de
>-------------------- fidonet: 2:246/8506.9
Analysis of these numbers reveals that all but 2 of them are of
the form:
3*(2^(K+30)) - 1149*(2^(K-(2*J))) - delta*(2^(K-(2*J)))
where J and K are integers greater than or equal to 0,
and delta is a real number that has varying ranges depending
on J but can generally be considered to be between 0 and 1.
The 2*J terms in the above equation leads to the conclusion
that the Pentium divider is an iterative divider that computes
2 bits of quotient per cycle. (This is in agreemnent with
the quoted 39 cycles per extended long division from the
Pentium data book. The technical name for this type of
divider is radix 4)
The extremely low probability of error (1 in 10^10) implies
that the remainder is being held in carry save format. (Carry
save format is where a number is represented as the sum of
two numbers. This format allows next remainder calculation
to occur without propagating carries. The reason that carry
save format is implied by the error probability is that
it is very difficult but not impossible to build up long
coincident sequences of ones in both the sum word and the
carry word.)
I assumed the digit set was -2, -1, 0, 1, and 2. (Having
5 possible digits in a radix 4 divider allows a necessarry
margin for error in next digit selection. When doing long
division by hand the radix 10 and 10 possible digits allow
no margin for error.)
Taking the above into consideration I wrote the tentative
model of Pentium divide hardware included below so that I
might watch what bit patterns developed in the remainder.
After running the numbers that were known to fail and numbers
near them that appeared not to fail I determined the
conditions for failure listed in the program.
Analysis of the precise erroneous results returned on the
bad divides indicates that a bit (or bits) is being subtracted
from the remainder at or near its most significant bit.
A modeling of this process is included in the program.
The program accurately explains all the published
errors and accurately predicted the error listed at the
beginning of the article.
The determination of the quotient from the sequence of digits
is left as an exercise for the reader ;-).
I would like to thank Dr. Nicely for providing this window
into the Pentium architecture.
-Tim Coe c...@vitsemi.com
An example run of the program (using the first reported
error):
---Enter dividend mantissa in hex: 8 <return>
---Enter divisor mantissa in hex: bfffffb829 <return>
---next digit 1
---1111000000000000000000000001000111110101101111111111111111111100
---0000000000000000000000000000000000000000000000000000000000000100
---11110000000000000000000000010001 iteration number 1
---.
---.
---.
---next digit -1
---0011111111100100101011110100110000010111010000000000000000000000
---1101111111111111111110110110010010010000000000000000000000000000
---00011111111001001010101010110000 iteration number 14
---next digit 2
---A bug condition has been detected.
---Enter 0 for correct result or 1 for incorrect result: 1 <return>
---0000000001101101010100001000000111110110011111111111111111111100
---1111111100100101010110100110010010010010000000000000000000000100
---11111111100100101010101011100101 iteration number 15
---next digit 0
---1111110100100000001010111001010110010001111111111111111111100000
---0000000100101010100000000000010010010000000000000000000000100000
---11111110010010101010101110011001 iteration number 16
---.
---.
---.
#include <stdio.h>
main()
{
unsigned r0, r1, r2, r3, r4, r5, r6, s0, s1;
unsigned t0, t1, t2, t3, cycle, f, incorrect;
unsigned thr_m2_m1, thr_m1_0, thr_0_1, thr_1_2, positive, errornum;
char line[30], *linepoint;
r0 = 0x0bffffc0;
r1 = 0;
r2 = 0x0800bf60;
r3 = 0;
printf("Enter dividend mantissa in hex: ");
scanf("%s", line);
linepoint = line;
while (*linepoint != '\0') linepoint++;
while (linepoint < line + 15) *linepoint++ = '0';
*(line+15) = '\0';
sscanf(line+7, "%x", &r3);
*(line+7) = '\0';
sscanf(line, "%x", &r2);
printf("Enter divisor mantissa in hex: ");
scanf("%s", line);
linepoint = line;
while (*linepoint != '\0') linepoint++;
while (linepoint < line + 15) *linepoint++ = '0';
*(line+15) = '\0';
sscanf(line+7, "%x", &r1);
*(line+7) = '\0';
sscanf(line, "%x", &r0);
r4 = 0;
r5 = 0;
/* These thresholds are VERY tentative. */
/* There may be bugs in them. */
t0 = r0 >> 22;
/* Next threshold is strongly indicated */
/* by the failure of 9895574626641 */
if (t0 < 36) thr_0_1 = 3;
/* Next threshold is strongly indicated */
/* by the failure of 824633702441 */
else if (t0 < 48) thr_0_1 = 4;
else if (t0 < 56) thr_0_1 = 5;
else thr_0_1 = 6;
thr_m1_0 = 254 - thr_0_1;
if (t0 < 33) thr_1_2 = 11;
else if (t0 < 34) {
printf("This model does not correctly handle\n");
printf("this divisor. The Pentium divider\n");
printf("undoubtly handles this divisor correctly\n");
printf("by some means that I have no evidence\n");
printf("upon which speculate.\n");
exit();
}
else if (t0 < 36) thr_1_2 = 12;
else if (t0 < 39) thr_1_2 = 13;
/* Next threshold is strongly indicated */
/* by the failure of 1443107810341 */
else if (t0 < 42) thr_1_2 = 14;
else if (t0 < 44) thr_1_2 = 15;
else if (t0 < 48) thr_1_2 = 16;
else if (t0 < 54) thr_1_2 = 18;
else if (t0 < 60) thr_1_2 = 20;
else thr_1_2 = 23;
thr_m2_m1 = 254 - thr_1_2;
/* Further error conditions may exist. */
/* I believe they could be accom- */
/* adated by adding conditions to the */
/* following clause. */
if (t0 == 35) errornum = 22;
else if (t0 == 41) errornum = 26;
else if (t0 == 47) errornum = 30;
else errornum = 128;
incorrect = 0;
cycle = 1;
/* The cycle count was chosen to keep */
/* the errors on my 60 line screen and */
/* would be 33 or 34 for extended long. */
while (cycle < 27) {
t0 = 255 & ((r2 >> 24) + (r4 >> 24));
if ((t0 > thr_m1_0) || (t0 < thr_0_1)) {
s0 = 0;
s1 = 0;
positive = 0;
printf("next digit 0\n");
}
else if (t0 > thr_m2_m1) {
s0 = r0;
s1 = r1;
positive = 0;
printf("next digit -1\n");
}
else if (t0 < thr_1_2) {
s0 = ~r0;
s1 = ~r1;
positive = 4;
printf("next digit 1\n");
}
else if (t0 & 128) {
s0 = (r0 << 1) | (r1 >> 31);
s1 = r1 << 1;
positive = 0;
printf("next digit -2\n");
}
else {
s0 = ~((r0 << 1) | (r1 >> 31));
s1 = ~(r1 << 1);
positive = 4;
printf("next digit 2\n");
if ((t0 == errornum) && (((r2 >> 21) & 7) == 7) && (((r4 >> 21) & 7) == 7)) {
printf("A bug condition has been detected.\n");
printf("Enter 0 for correct result or 1 for incorrect result: ");
scanf("%d", &incorrect);
if (incorrect) {
if (errornum == 22) s0 = s0 - (3 << 25);
else s0 = s0 - (4 << 25);
}
}
}
t0 = s0 ^ r2 ^ r4;
t1 = s1 ^ r3 ^ r5;
t2 = (s0 & r2) | (s0 & r4) | (r2 & r4);
t3 = (s1 & r3) | (s1 & r5) | (r3 & r5);
r2 = (t0 << 2) | (t1 >> 30);
r3 = t1 << 2;
r4 = (t2 << 3) | (t3 >> 29);
r5 = (t3 << 3) | positive;
t0 = r2;
f = 32;
while (f--) {
if (t0 & (1 << 31)) putchar('1');
else putchar('0');
t0 = t0 << 1;
}
t0 = r3;
f = 32;
while (f--) {
if (t0 & (1 << 31)) putchar('1');
else putchar('0');
t0 = t0 << 1;
}
putchar('\n');
t0 = r4;
f = 32;
while (f--) {
if (t0 & (1 << 31)) putchar('1');
else putchar('0');
t0 = t0 << 1;
}
t0 = r5;
f = 32;
while (f--) {
if (t0 & (1 << 31)) putchar('1');
else putchar('0');
t0 = t0 << 1;
}
putchar('\n');
t0 = r2 + r4;
f = 32;
while (f--) {
if (t0 & (1 << 31)) putchar('1');
else putchar('0');
t0 = t0 << 1;
}
printf(" iteration number %d\n", cycle++);
}
}
Trangdaithi Hoang
>On a Packard Bell P90 PC I performed the following
>calculation using Microsoft Windows Desk Calculator:
>
>(4195835 / 3145727) * 4195835
>
>The result was 4195579.
>This represents an error of 256 or one part in ~16000.
Are you definite that MS Windows and specifically the Desk Calculator
takes advantage of a floating point unit and uses the FDIV instruction?
There are MS Windows applications that do take advantage of a floating
point processor, but I don't think the Windows shell itself does.
Also, for those compiling source code (all languages except assembly)
to detect the FDIV bug. Are you sure your compiler is generating
floating point instructions and not emulating them?
android
>
>Much of the following explanation was previously
>posted to comp.sys.intel. A more complete tentative
>software model of the Pentium divider that explains
>all divide errors that I am aware of is included with
>this post.
[... Excellent analysis and program deleted to save space... ]
Tim,
Although this is not quite within the bounds of the FDIV Challenge, it is
a great factual analysis with actual data and a program which doesn't contain
any speculation.
Therefore, I will make you a "honorary" FDIV Challenge winner and buy you a
Texas Lottery ticket. Send me 6 numbers from 1 to 51.
Andy
Dennis Reinhardt
(Trangdaithi Hoang) writes:
This does not prove there is FDIV error in Pentium Processor. There is
no floating point involved in computing 3.11-3.1. The answer should be
01. Desk Calculator returns 0.0. Try and see. Fails on several
systems. Common element in all this is Windows Desk Calculator. BTW, I
hear above subtraction error fixed in Windows '95.
--
-----------------------------------------------------------
| Dennis | Den...@ix.netcom.com | Works for me, may |
| Reinhardt | den...@mipos3.intel.com | not work for you |
-----------------------------------------------------------
David desJardins
> On a Packard Bell P90 PC I performed the following
> calculation using Microsoft Windows Desk Calculator:
> (4195835 / 3145727) * 4195835
> The result was 4195579.
> This represents an error of 256 or one part in ~16000.
This clearly can't be right. The correct result is 5596490.52, so a
result of 4195579 would represent an error of about 25%.
David desJardins
--
Copyright 1994 David desJardins. Unlimited permission is granted to quote
from this posting for non-commercial use as long as attribution is given.
Tim Smith
>On a Packard Bell P90 PC I performed the following
>calculation using Microsoft Windows Desk Calculator:
The Windows calculator is not a good thing to use to show
hardware math problems. The Windows calculator manages to
botch things even on working processors. Try, for example,
2.01 - 2.
--Tim Smith
Tim Coe
>In article <1994Nov21.0...@vitsemi.com>, c...@vitsemi.com (Tim Coe)
>writes:
>
>>>Since then I performed the following calculations in Microsoft
>Windows Desk Calculator on a Pentium machine with the following
>results:
>
>(41.999999/35.9999999)*35.9999999 - 41.999999 ==> (-0.75)*(2^-13)
>(48.999999/41.9999999)*41.9999999 - 48.999999 ==> (-1.0)*(2^-13)
>(55.999999/47.9999999)*47.9999999 - 55.999999 ==> (-1.0)*(2^-13)
>(62.999999/53.9999999)*53.9999999 - 62.999999 ==> (-1.0)*(2^-13)
>(54.999999/59.9999999)*59.9999999 - 54.999999 ==> (-1.0)*(2^-13)
>>(5244795/3932159)*3932159 - 5244795 ==> (-1.0)*(2^8)
>
>I chose these calculations in anticipation of them exposing further
>Pentium FDIV failure modes. They did. The size of the erroneous results
>are exactly consistant with the final version of tentive Pentium
^^^^^^^
>divider model included below and in no way can be attributed to
>a Desk Calculator bug. The existance of these results pins
>most of the digit selection thresholds included in the model.<<
>
>
>Hello!!???!! Haven't you read anything about the Microsoft Windows
>calculator? It's just a tad buggy, in case you didn't know. If you are
>trying to find fpu bugs running that program then you would accuse any
>processor you ran it on. This has already been established here and
>elswhere.
>
>Scott W.
The Microsoft Desk Calculator may have bugs, but in order to produce
these erroneous results its SOFTWARE would have to exhibit exactly the same
behavior as my model of the buggy Pentium divider HARDWARE. Could it do
this by any means other than executing a FDIV instruction?
I don't think so!!!
I stand by my conclusions.
Tim Coe
Per Troelsen
:
: The Windows calculator is not a good thing to use to show
: hardware math problems. The Windows calculator manages to
: botch things even on working processors. Try, for example,
: 2.01 - 2.
:
: --Tim Smith
The calculator DOES know how to calculate, it just does not
want to show you the result :-)
Try (2.01-2.0)*100 and the result will be one.
============================================================================
Per Troelsen | Per.Tr...@Copenhagen.NCR.COM
AT&T GIS SE-Copenhagen | Tel: +45 38 15 75 00 (switch-board)
Svanevej 14 | +45 38 15 75 66 (direct call)
DK-2400 Copenhagen NV, Denmark | Fax: +45 31 10 23 62
============================================================================
Francesco Benvenuto
>From: c...@vitsemi.com (Tim Coe)
>Subject: Re: Glaring FDIV bug in Pentium!
>Date: Wed, 23 Nov 94 01:36:54 GMT
>Tim Coe
francesco Benvenuto
+---------------------------------------------------------------------------+
| "It's dark and eerie and it's really late, come on, kids, don't hesitate: |
| we are going down to the underground" "Let's Submerge" X-Ray Spex (1978) |
+---------------------------------------------------------------------------+
Francesco Benvenuto
bit too early... :-). I am unable (too lazy) to cancel it from here... if you
haven't see it don't worry!
Back to the main topic, a minor one I admit.
It has been mentioned that the Windows Desk Calculator is buggy (true) and the
calculations it performs should not be trusted (false). The bug in the
calculator is in the display function. If you compute:
2.11 - 2.1
the display shows you 0.00 (which is uncorrect), but the correct result is
held within the calculator, as anyone can easily proof by dividing 0.00 by two
and obtaining 0.005.
Just to be a little picky... (which I really shouldn't be, given my above
reported mistake).
Tim Coe
on a Pentium and post and/or email me the results. I do not
have easy access to any Pentium machines. My previously
reported calculations on Pentiums were performed at CompUSA
with my kid in one arm and my free hand on a mouse.
The program divides all 8 million single precision normalized
mantissas by the 1280 at risk single precision divisors. In
order to get it to compile right on a Sun IPC I used the
following command:
cc scansingle.c -fsingle -o scansingle
The -fsingle argument was required to keep it from expanding
everything into double precision. I would imagine that
x86 compilers have some similar requirement.
To run this program and watch the results do the following:
prompt> scansingle <return>
Enter 1 to have each divisor printed, 0 otherwise: 1 <return>
Error at xxx xxx xxx xxx xxx xxx
Finished divisor 15millionsomething
Error at xxx xxx xxx xxx xxx xxx
Error at xxx xxx xxx xxx xxx xxx
Finished divisor 15millionsomething-1
To run this program and pipe it to a file do the following:
prompt> scansingle >! single.errors <return>
Enter 1 to have each divisor printed, 0 otherwise: 0 <return>
^Z
prompt> bg <return>
On an IPC it was doing about 2 divisors per minute (and producing
no errors). On a P90 I estimate its run time to be about
2 hours. If you find bugs in the program send me email.
-Tim Coe c...@vitsemi.com
---- begin scansingle.c ----
#include <stdio.h>
main()
{
unsigned intdivisor, intdividend, hexdivisor, hexdividend;
unsigned printdivisor, c;
float divisor, dividend, atriskstep, errorterm;
float lowdividend, highdividend, lowdivisor, highdivisor;
fprintf(stderr, "Enter 1 to have each divisor printed, 0 otherwise: ");
scanf("%d", &printdivisor);
c = (1<<24) - 1;
highdividend = c;
c = 1<<23;
lowdividend = c;
c = (1<<24) - (1<<20) - 1;
highdivisor = c;
c = (1<<24) - (1<<20) - (1<<8);
lowdivisor = c;
c = 3<<19;
atriskstep = c;
while (highdivisor > lowdividend) {
divisor = highdivisor;
while (divisor >= lowdivisor) {
dividend = highdividend;
while (dividend >= lowdividend) {
errorterm = dividend - (dividend/divisor)*divisor;
if (errorterm > 1.0) {
hexdivisor = divisor;
hexdividend = dividend;
intdivisor = divisor;
while (!(intdivisor & 1)) intdivisor >>= 1;
intdividend = dividend;
while (!(intdividend & 1)) intdividend >>= 1;
printf("Error at %8.8g %8.8g %f %d %d %x %x\n",
dividend, divisor, errorterm, intdividend,
intdivisor, hexdividend, hexdivisor);
fflush(stdout);
}
dividend -= 1.0;
}
if (printdivisor) {
printf("Finished divisor %8.8g\n", divisor);
fflush(stdout);
}
divisor -= 1.0;
}
highdivisor -= atriskstep;
lowdivisor -= atriskstep;
}
}
Tim Coe
at the end of this message that accurately predicted
many of the stated failing divides, and accurately
confirms all failing divides of which I am aware.
I worked on an IEEE hardware FPU from 1989-1991.
As an FPU designer I am naturally interested in
algorithms for hardware arithmetic. I am currently
working on something completely different, but I
still occasionally support related development
tasks.
I saw the first post relating to the Pentium FDIV
bug in comp.sys.intel. When I saw the post from
Andreas Gruss (included), I saw a pattern and the
opportunity to completely reverse engineer Intel's
divider. I took to this task with great vigor, as
it is very rare that one gets visibility into the
details of someone else's leading edge design.
I decided to post my results when it appeared
to me that Intel was not coming clean with the
characteristics of the bug. The best characteristic
and only characteristic of the bug to come from
Intel is its 1 in 9 billion probability of occurring
with random operands. The worst characteristic
of the bug is that the specific operands that are most at
risk are integers +/- very small deltas. The
integers 3, 9, 15, 21, and 27 minus very small
deltas are THE at risk divisors. (In particular the
maximum expressible single precision, double precision,
and extended precision numbers less than 3, 9...27 are
all seriously at risk divisors.) The other bad
characteristic of this bug that I did not hear
from Intel is that the worst case error induced
by the bug was considerably greater than the 4 parts
per billion error observed by Professor Nicely.
It appeared to me that Intel was attempting to
minimize its exposure by focusing on the 1 in 9
billion probability of error that it publicized and
the 4 part per billion error observed by Professor
Nicely. I posted my conclusions so that the Intel
user community could be a peer to Intel when determining
what applications may be at risk due to this bug.
I think Intel does outstanding technical work. After
all, the only reason I was reading comp.sys.intel was
that I was considering the purchase of a P90 system.
After this brouhaha I will still buy a P90 system, though
when I do I will ask for a fixed chip and a guarantee
that if I find after receiving my system that it does
not contain said fixed chip that the seller will
replace the unfixed chip posthaste. I regard the
fact that the bug occurred as completely excusable,
for I have designed many chips and therefore designed
many bugs.
I posted an additional program not included here
that scanned single precision operands for errors
induced that were greater that one single precision
least significant bit. I received back a list of
1738 problem single precision divisions (out of 64
trillion). Herb Savage provided the list.
The following divisors and their binary scalings
(by this I mean different only in the binary exponent)
appear to account for >95% of the divide errors:
3.0 > divisor >= 3.0 - 36*(2^-22)
9.0 > divisor >= 9.0 - 36*(2^-20)
15.0 > divisor >= 15.0 - 36*(2^-20)
21.0 > divisor >= 21.0 - 36*(2^-19)
27.0 > divisor >= 27.0 - 36*(2^-19)
A divide with a divisor in one of the above ranges
has roughly a 1 in 200000 chance of suffering loss
of precision in double extended precision operations.
The other <5% of the divide errors can be accounted
for by changing the above 36 to 2048.
All dividends are somewhat at risk versus the above
divisors. The following formula identifies dividends
that are at particularly high risk for errors in
general and also for relatively large errors:
dividend = intdividend + deltadividend
or
dividend = intdividend - deltadividend
divisor = intdivisor - deltadivisor
intdivisor = 3, 9, 15, 21, 27
and one of the following must hold true, which one depends
on the exponent in the IEEE representation of the
dividend in question:
intdividend = intdivisor/3 mod intdivisor
intdividend = 2*intdivisor/3 mod intdivisor
The restrictions on the above deltadividend and deltadivisor
are somewhat complex, the details of which are left as
an exercise for the reader. ;-) I have not worked out
the restrictions in detail.
Here are the previous posts to comp.sys.intel. Read and
enjoy.
-Tim Coe c...@vitsemi.com
---- First and Second Post text ----
On a Packard Bell P90 PC I performed the following
calculation using Microsoft Windows Desk Calculator:
(4195835 / 3145727) * 3145727 [typo corrected from earlier posts]
The result was 4195579.
This represents an error of 256 or one part in ~16000.
a...@ananke.s.bawue.de (Andreas Kaiser) writes
---- Third Post ----
Since then I performed the following calculations in Microsoft
Windows Desk Calculator on a Pentium machine with the following
results:
(41.999999/35.9999999)*35.9999999 - 41.999999 ==> (-0.75)*(2^-13)
(48.999999/41.9999999)*41.9999999 - 48.999999 ==> (-1.0)*(2^-13)
(55.999999/47.9999999)*47.9999999 - 55.999999 ==> (-1.0)*(2^-13)
(62.999999/53.9999999)*53.9999999 - 62.999999 ==> (-1.0)*(2^-13)
(54.999999/59.9999999)*59.9999999 - 54.999999 ==> (-1.0)*(2^-13)
(5244795/3932159)*3932159 - 5244795 ==> (-1.0)*(2^8)
I chose these calculations in anticipation of them exposing further
Pentium FDIV failure modes. They did. The size of the erroneous results
are exactly consistant with the final version of tentive Pentium
divider model included below and in no way can be attributed to
a Desk Calculator bug. The existance of these results pins
most of the digit selection thresholds included in the model.
I also performed the following calculations that did NOT produce erroneous
results:
(38.499999/32.9999999)*32.9999999 - 38.499999 ==> 0
(45.499999/38.9999999)*38.9999999 - 45.499999 ==> 0
I have been following this thread with great interest. One misperception
that needs clearing is that this is an extended precision problem. This
bug hits between 50 and 2000 single precision dividend divisor pairs (out
of a total of 64 trillion.) Another misperception is related to the magnitude
of the relative error. I would propose the following table of probabilities
of getting the following relative errors when performing random double
extended precision divides:
relerror = (correct_result - Pentium_result)/correct_result
Error Range | Probability
-------------------------------------------
1e-4 < relerror | 0
1e-5 < relerror < 1e-4 | 0.3e-11
1e-6 < relerror < 1e-5 | 0.6e-11
1e-7 < relerror < 1e-6 | 0.6e-11
1e-8 < relerror < 1e-7 | 0.6e-11
.
.
1e-18 < relerror < 1e-17 | 0.6e-11
1e-19 < relerror < 1e-18 | 0.6e-11
Examination of the above divide failures reveals that both the dividend
and divisor are integers minus small deltas. Also notable is the induced
error is roughly delta^(2/3). The integers in the divisors are actually
restricted to those listed and their binary scalings. The integers in
the dividends may be much more freely chosen. This type of dividend
divisor pair actually occurs quite often when forward integrating
trajectories off metastable points. This is because metastable points
in systems often have certain exactly integral characteristics and as
a path diverges from the metastable point these characteristics slowly diverge
from their integral values. If the forward integration algorithm
happens to divide these characteristics, and they happen to be for
example 7 and 3, it will get nailed.
The divider model includes support for up to 60 bits of divisor and
up to 64 bits of dividend. The last four bits of dividend are kludged
in.
Here is a list of failing dividend divisor mantissas in hex. A dash
between two numbers indicates an inclusive failing range. Compile
the program and run these numbers through it and watch the bits dance:
800bf6 bffffc
a00ef6 effffc
a808d2 8fffe
e00bd2 bfffe
a7ffd2 8fffe
c3ffd2 a7ffe
dfffd2 bfffe
fbffd2 d7ffe
f9ffdc7 efffe
b9feab7-b9feabf 8fff
b9ffab0e-b9ffab7f 8fffc
-the following double extended pair fails 3 times!!!
c3ffd2eb0d2eb0d2 a7ffe
e00bd229315 bfffe
9fffef5-9fffeff effff4
9ffff21-9ffff3f effff8
9ffff4d-9ffff7f effffc
f008e35-f008e3f 8ffff4
f008e6d-f008e7f 8ffff6
f008ea1-f008ebf 8ffff8
f008ed9-f008eff 8ffffa
f008f0d-f008f3f 8ffffc
f008f45-f008f7f 8ffffe
f008f7e 8ffffff1
f0023e 8fffff8
effff0d 8ffffc
a808d1b-a808d3f 8fffe
a808d67-a808d7f 8fffe4
a808db3-a808dbf 8fffe8
a808dff 8fffec
-Tim Coe c...@vitsemi.com
#include <stdio.h>
main()
{
unsigned r0, r1, r2, r3, r4, r5, r6, s0, s1;
unsigned t0, t1, t2, t3, cycle, f, incorrect, spup;
unsigned thr_m2_m1, thr_m1_0, thr_0_1, thr_1_2, positive, errornum;
char line[30], *linepoint;
r0 = 0x0bffffc0;
r1 = 0;
r2 = 0x0800bf60;
r3 = 0;
printf("First digit of mantissas must be between 8 and f\n");
printf("Enter dividend mantissa in hex: ");
*(line+15) = '0';
scanf("%s", line);
linepoint = line;
while (*linepoint != '\0') linepoint++;
while (linepoint < line + 15) *linepoint++ = '0';
*(line+16) = '\0';
sscanf(line+15, "%x", &spup);
spup = (spup >> 2) | (12 & (spup << 2));
*(line+15) = '\0';
sscanf(line+7, "%x", &r3);
*(line+7) = '\0';
sscanf(line, "%x", &r2);
printf("Enter divisor mantissa in hex: ");
scanf("%s", line);
linepoint = line;
while (*linepoint != '\0') linepoint++;
while (linepoint < line + 15) *linepoint++ = '0';
*(line+15) = '\0';
sscanf(line+7, "%x", &r1);
*(line+7) = '\0';
sscanf(line, "%x", &r0);
r4 = 0;
r5 = 0;
t0 = r2;
while (!(t0 & 1)) t0 = t0 >> 1;
printf("%d\n", t0);
t0 = r0;
while (!(t0 & 1)) t0 = t0 >> 1;
printf("%d\n", t0);
/* These thresholds are VERY tentative. */
/* There may be bugs in them. */
t0 = r0 >> 22;
/* Next threshold is strongly indicated */
/* by the failure of 1/9895574626641 */
if (t0 < 36) thr_0_1 = 3;
/* Next threshold is strongly indicated */
/* by the failure of 1/824633702441 */
else if (t0 < 48) thr_0_1 = 4;
/* Next threshold is strongly indicated */
/* by the failure of 5244795/3932159 */
else if (t0 < 60) thr_0_1 = 5;
else thr_0_1 = 6;
thr_m1_0 = 254 - thr_0_1;
if (t0 < 33) thr_1_2 = 11;
else if (t0 < 34) {
printf("This model does not correctly handle\n");
printf("this divisor. The Pentium divider\n");
printf("undoubtly handles this divisor correctly\n");
printf("by some means that I have no evidence\n");
printf("upon which speculate.\n");
exit();
}
/* Next threshold is strongly indicated */
/* by the failure of 41.999999/35.9999999 */
else if (t0 < 36) thr_1_2 = 12;
else if (t0 < 39) thr_1_2 = 13;
/* Next threshold is strongly indicated */
/* by the failure of 1/1443107810341 and */
/* by the failure of 48.999999/41.9999999 */
else if (t0 < 42) thr_1_2 = 14;
else if (t0 < 44) thr_1_2 = 15;
/* Next threshold is strongly indicated */
/* by the failure of 55.999999/47.9999999 */
else if (t0 < 48) thr_1_2 = 16;
/* Next threshold is strongly indicated */
/* by the failure of 62.999999/53.9999999 */
else if (t0 < 54) thr_1_2 = 18;
/* Next threshold is strongly indicated */
/* by the failure of 54.999999/59.9999999 */
else if (t0 < 60) thr_1_2 = 20;
else thr_1_2 = 23;
thr_m2_m1 = 254 - thr_1_2;
if (t0 == 35) errornum = 22;
else if (t0 == 41) errornum = 26;
else if (t0 == 47) errornum = 30;
else if (t0 == 53) errornum = 34;
else if (t0 == 59) errornum = 38;
else errornum = 128;
incorrect = 0;
cycle = 1;
/* The cycle limit would be ~34 instead of */
/* 18 for double extended precision. */
while (cycle < 18) {
/* These amounts that are subtracted from the */
/* remainder have NOT been extensively verified. */
if (errornum == 22) s0 = s0 - (3 << 25);
else s0 = s0 - (4 << 25);
}
}
}
t0 = s0 ^ r2 ^ r4;
t1 = s1 ^ r3 ^ r5;
t2 = (s0 & r2) | (s0 & r4) | (r2 & r4);
t3 = (s1 & r3) | (s1 & r5) | (r3 & r5);
r2 = (t0 << 2) | (t1 >> 30);
r3 = t1 << 2;
r4 = (t2 << 3) | (t3 >> 29);
r5 = (t3 << 3) | positive | (spup & 3);
spup = spup >> 2;
Alan L. Cassel
: . . . The best characteristic
: and only characteristic of the bug to come from
: Intel is its 1 in 9 billion probability of occurring
: with random operands. The worst characteristic
: of the bug is that the specific operands that are most at
: risk are integers +/- very small deltas. The
: integers 3, 9, 15, 21, and 27 minus very small
: characteristic of this bug that I did not hear
: from Intel is that the worst case error induced
: by the bug was considerably greater than the 4 parts
: per billion error observed by Professor Nicely.
: It appeared to me that Intel was attempting to
: minimize its exposure by focusing on the 1 in 9
: billion probability of error that it publicized and
: the 4 part per billion error observed by Professor
: Nicely.
Than you very much.
*Your* information (including much of the detailed analysis that I
omitted from the quote above) is *MUCH* more useful in evaluating the
significance of the bug than the "once in 27,000 years" Intel press
releases.
The only thing that I would add to your statement above would be
something to clear away the confusion that exists in many quarters
between decimal places and significant figures. With the FDIV bug, it is
entirely possible to get answers only to four or five significant
figures, which could easily result in errors to the LEFT of the decimal
point. To use one of your example divisors above, try:
1048958.75 / 2.9999991,
which results in an error in the second digit to the left of the decimal
point -- i.e., where the error could conceivably cost someone dollars, not
just fractions of a cent.
Raul Deluth Miller
> Is there a site with a compiled Pentium tester available for download?
What kind of testing are you looking for? Investigation of the scope
of the problem, or identifying cpus with the problem?
If it's the latter, perhaps this C program will be simple enough for
you to compile:
/* make noise about pentium FDIV bug, if present */
/* compile with optimizations disabled */
#include <stdio.h>
main(){
double x= 4195835.0;
double y= 3145727.0;
if (256.0 == (x - y*(x/y))) {
printf("You have a pentium.\n");
exit(1);
}
exit(0);
}
--
Raul D. Miller N=:((*/pq)&|)@ NB. public e, y, n=:*/pq
<rock...@nova.umd.edu> P=:*N/@:# NB. */-.,e e.&factors t=:*/<:pq
1=t|e*d NB. (,-:<:)pq is four large primes, e medium
x-:d P,:y=:e P,:x NB. (d P,:y)-:D P*:N^:(i.#D)y [. D=:|.@#.d
Trangdaithi Hoang
John Lindsay <jlin...@byron.apana.org.au> wrote:
>Is there a site with a compiled Pentium tester available for download?
Information and programs to detect the Pentium division bug can be
found on the following ftp sites:
ftp.mathworks.com in //pub/tech-support/moler/Pentium
ucdmath.ucdavis.edu or math.ucdavis.edu in //pub/fdiv