An oddity if not a bug

[Harlan Grove]

A1:
=FACT(9)/FACT(6)/FACT(3) returns 84, as it should

A2:
=COMBIN(9,3) returns 84, as it should

A3:
=A1=A2 returns TRUE

A4:
=A1-A2 returns 0

A5:
=MOD(A4,1) returns 0

A6:
=MOD(A1,1) returns 0

A7:
=MOD(A2,1) returns -1.42109E-14

So the @#$% fudge factor strikes again, or does it? Shouldn't it affect
the evaluated value of cell A2 with the final result for A2 an integer?
This shouldn't be. If cell A4 is zero with no remainder in A5, why
should A7 have a remainder?

Same results in 2003 and 2007.

 

[Biff]

Don't know the reason but I've read posts by Jerry Lewis that cover this:

=A1-A2 = 0

But:

=(A1-A2)=0 returns FALSE

So you'd think that A5: =MOD(A4,1) should have a remainder. Or is that the
fudge factor in effect?

Biff

 

[Biff]

So you'd think that A5: =MOD(A4,1) should have a remainder. Or is that the

fudge factor in effect?

There it is:

=MOD((A1-A2),1)

1.4210854715202E-14

Biff

 

[Harlan Grove]

Biff wrote...

There it is:

=MOD((A1-A2),1)

1.4210854715202E-14

....

I hadn't thought of that, but this is still a bug. COMBIN should *only*
return integers or error values. If both its arguments are numbers,
it'll truncate them to integers, e.g., COMBIN(7.2,2.9) returns the same
result as COMBIN(5,2). If its arguments are integers, then numerically
it can only return integers.

If its result would be beyond Excel's capacity, e.g., COMBIN(1030,515),
no problem having it return #NUM!. If its result would take more than
15 decimal digits, no problem that it'd be only approximately correct
to 15 decimal digits (and it'd also be an integer). But when it could
easily be represented in 15 or fewer decimal digits, there's no excuse
for it not to be an integer.

FWIW, the standard approach when N gets large enough that FACT(N)
exceeds 15 decimal digits is to use
EXP(GAMMALN(N+1)-GAMMALN(k+1)-GAMMALN(N-k+1)), but in the case of N=9
and k=3, this returns 84.0000000106965, while (COMBIN(9,3)-84) is
negative. Leaves me wondering how Microsoft is calculating this.

 

[Biff]

this is still a bug. COMBIN should *only*

return integers or error values.

I agree and had always assumed as much. This little exercise proves
otherwise.

=MOD((COMBIN(9,3)-84),1)

Returns 1.

Biff

 

[Harlan Grove]

Biff wrote...

I agree and had always assumed as much. This little exercise proves
otherwise.

=MOD((COMBIN(9,3)-84),1)

Returns 1.

....

Actually, it returns 0.999999999999986. And don't get me started on
MOD.

With all boils in need of lancing in Excel, what does Microsoft do?
Give it a nose job.

 

[Biff]

With all boils in need of lancing in Excel, what does Microsoft do?

Enhance the charting "experience" ?

Did you see that post at http://blogs.msdn.com/excel/default.aspx ?

A "user experience designer" ? WTF is that?

That's what MS is interested in. Zen fluff!

Biff

 

[Guest]

But if A8 = COMBIN(9,3)-84 it appears to properly return 0
and if A9 = MOD(A8,1)

it also appears to properly return 0.

 

[Biff]

That's the "fudge factor" Harlan was talking about.

The result is not EXACTLY zero but the difference is so extremely small that
Excel "fudges" the result to be 0.

But if A8 = COMBIN(9,3)-84 it appears to properly return 0

Try this:

=(COMBIN(9,3)-84)=0

Jerry Lewis has explained that a test for true equality must be done this
way. Look for some of his posts where he gets into great detail about this.
It's really complex and quite educational.

Biff

 

[Guest]

Thanks for the suggestion, it is educational.

From one of Jerry's posts, it seems that excel may/may not apply a fudge
factor when nesting functions -or am I misunderstanding?

I was aware of the 15 digit limits and the binary fraction issue, but, as
Harlan stated, there's no apparent reason for Combin to apply the fudge
factor in this case.

 

[Dana DeLouis]

In your previous post on

=MOD((A1-A2),1)
1.4210854715202E-14

It appears that lone bit is a "large" error.

=POWER(2,-46)
1.4210854715202E-14
--
HTH. :>)
Dana DeLouis
Windows XP, Office 2003

That's the "fudge factor" Harlan was talking about.

<snip>

 

[Harlan Grove]

Dana DeLouis wrote...

In your previous post on

It appears that lone bit is a "large" error.

=POWER(2,-46)
1.4210854715202E-14

....

And 84 is between 2^6 (64) and 2^7 (128), so needs 7 bits for itself,
the -2^-46 uses another 46 bits, and 7 + 46 = 53, the number of
mantissa bits provided by double precision FP.

The problem is that Excel should be ensuring that functions like COMBIN
(and PERMUT) that should NEVER return noninteger numeric values
actually never do. And that stray final bit is enough to screw up
lookups, since Excel doesn't apply its fudge factor in lookups, and
there's no simple way to back fill it.

 

[Dana DeLouis]

Thanks Harlan for that information. I see where I went wrong. The error is
within reason...so to speak.
Don't know if the following is interesting.
In math programs, Excel's Combin function is called "Binomial."

At the co-processor level, there appears to be a 7 in the 16th place.
Maybe Excel is doing something similar?

Binomial[9., 3.]//FullForm
84.00000000000007`

Other numbers return a value that's more of an integer...

Binomial[9., 4.]//FullForm
126.`

So with 3, I get similar results:

84 - Binomial[9., 3.]
-7.105427357601002*^-14

Mod[Binomial[9., 3.], 1]
7.105427357601002*^-14

I have to admit to being a little confused on the difference here though:

2.^(-47)
7.105427357601002*^-15

So, it looks like if we dig deep into the math co-processor, some values
will test Zero, and others will not.

Developer`ZeroQ[126 - Binomial[9., 4.]]

True

Developer`ZeroQ[84 - Binomial[9., 3.]]

False

Interesting...

 

[Harlan Grove]

Dana DeLouis wrote...
....

Don't know if the following is interesting.
In math programs, Excel's Combin function is called "Binomial."

In Mathematica. There's no equivalent in MathCAD. In GNU Octave, a
MatLab clone, the function is bincoeff, and

printf ("%.16g\n", bincoeff(9,3) - 84);

returns 0 while

printf ("%.16g\n", exp(gammaln(10) - gammaln(4) - gammaln(7)) - 84);

returns -1.4210854715202e-14.

But let's compare apples to apples. In OpenOffice Calc,

=(COMBIN(9;3)-INT(COMBIN(9;3)))

returns 0, while the comparable formula in Gnumeric returns 0, but it
returns the same fractional result as in Excel when used as a term in
longer formulas. The comparable formula in Lotus 123 returns 0.

It's all a matter of implementation.

At the co-processor level, there appears to be a 7 in the 16th place.
Maybe Excel is doing something similar?

Binomial[9., 3.]//FullForm
84.00000000000007`

....

Note that in Mathematica the result depends on the argument data types.

Binomial[9,3]//FullForn
84

So, it looks like if we dig deep into the math co-processor, some values
will test Zero, and others will not.

....

It's all a question of implementation. The algorithm used to calculate
general binomial coefficients may not return integer results, but
there's NOTHING to stop the implementor adding a lowest order bit and
truncating the result to an integer.

Note that in Mathematica, Binomial[9.,3.] is 2^-47 *greater* than 84
while in Excel COMBIN(9,3) is 2^-46 *less* then 84. Also note that
Mathematica's Binomial function accepts noninteger arguments, e.g.,
Binomial[9.5,3.] returns 100.937, which is the same result as given by

Exp[LogGamma[10.5]-LogGamma[4.]-LogGamma[7.5]]

Note also that after messing around for a while in Mathematica (playing
with N[..] calls), it now returns 84. as the result for
Binomial[9.,3.]//FullForm. Looks like Mathematica also has a fudge
factor for double precision evaluation.

I'll repeat: it's all a matter of implementation, and Excel's is
suboptimal.

 

[mwelinder]

But let's compare apples to apples. In OpenOffice Calc,

=(COMBIN(9;3)-INT(COMBIN(9;3)))

returns 0, while the comparable formula in Gnumeric returns 0, but it
returns the same fractional result as in Excel when used as a term in
longer formulas. The comparable formula in Lotus 123 returns 0.

OO's minus is special in that almost-equal values are deemed to have
a zero difference. Similarly for equality (which isn't transitive as a
result). That means that getting zero above does not tell you
anything about COMBIN's accuracy.

Gnumeric returns an integer COMBIN result because it seemed like
a good idea when mucking with logs. Note the floor(0.5 + ...) in this
fragment:

if (k < 0 || k > n)
return gnm_nan;
else if (n >= 15)
return gnm_floor (0.5 + gnm_exp (gnm_lgamma (n + 1) - gnm_lgamma (k +
1) - gnm_lgamma (n - k + 1)));
else
return fact (n) / fact (k) / fact (n - k);

And fact will return an exact (and thus integer) value for n<=15 and
probably more.

Morten

 

[Guest]

That is correct. Excel only artificially zeros a subtraction between numbers
(that are equal to 15 decimal digits) if that subtraction is the last
operation; even embedding the subtraction within parentheses will prevent it
from applying the fudge factor. You might also find my functions at
http://groups.google.com/group/microsoft.public.excel/msg/b106871cf92f8465
to be useful in determining the exact value that Excel is returning.

MS seems to have taken a "one size fits all" approach in selecting
algorithms for its functions, so I am not surprised that they do not have
special handling for COMBIN(n,x) where n<=17, which are the only instances
where the component factorials are exactly representable. However I am
surprised that this particular example is one bit away from returning an
integer, since most obvious implementations would have no floating point
error for this problem. Rounding the final result to an integer will usually
improve accuracy.

I don't know if there are representable values where the error in the
floating point operations within the COMBIN function would exceed 0.5, with
the result that rounding would reduce accuracy. Given the limitations of the
COMBIN algorithm, I somewhat doubt it. For instance, COMBIN(n,1) should
return n yet it returns #NUM! for n>=2^31-1.

Excel's implementation of GAMMALN is not terribly accurate, so you will take
a precision hit if you use it instead of COMBIN. Even if GAMMALN gave
machine accuracy, you would have some degree of catastrophic cancellation
with large n. You could do better by studying Ian Smith's coding around the
binomial distribution
http://members.aol.com/iandjmsmith/examples.xls

I must confess some agreement with Harlan's frustration that MS seems more
intrested in the glitz than the guts of this product.

Jerry

 

[Dana DeLouis]

Thanks Harlan. It's nice to get a feel from other systems.
Seems to me that taking the Mod of two positive numbers and returning a
negative number just isn't right.
But...you did say that Mod has problems! :>0
=MOD(COMBIN(9,3),1)
-1.42109E-14

Anyway, thanks for the hint on the size of the error. I should have known
better.
I know this is not related to Excel, but in Mathematica...

The machine error of this calculation is:

MachineError[Binomial[9., x], x -> 3.]
5.*Ulps

The machine error with Windows is 5 "Units in the last place, or Ulps"
And like you said, on my windows machine, a unit near 84 is

Ulp[84]
1.4210854715202004*^-14

Therefore, the machine error on my system for this calculation is:

5*Ulp[84]
7.105427357601002*^-14

which is the error I get...
Binomial[9., 3.] - 84
7.105427357601002*^-14

Mod[Binomial[9., 3.], 1]
7.105427357601002*^-14

As a side note, if I use the definition of Combin, I get much smaller
machine errors.
Even Excel returns True here.
=FACT(9)/(FACT(3)*FACT(9-3))-84=0

But this returns False as mentioned before:
=COMBIN(9,3)-84=0
Go figure???
--
Dana DeLouis

Dana DeLouis wrote...
...

Don't know if the following is interesting.
In math programs, Excel's Combin function is called "Binomial."

In Mathematica. There's no equivalent in MathCAD. In GNU Octave, a
MatLab clone, the function is bincoeff, and

printf ("%.16g\n", bincoeff(9,3) - 84);

returns 0 while

printf ("%.16g\n", exp(gammaln(10) - gammaln(4) - gammaln(7)) - 84);

returns -1.4210854715202e-14.

But let's compare apples to apples. In OpenOffice Calc,

=(COMBIN(9;3)-INT(COMBIN(9;3)))

returns 0, while the comparable formula in Gnumeric returns 0, but it
returns the same fractional result as in Excel when used as a term in
longer formulas. The comparable formula in Lotus 123 returns 0.

It's all a matter of implementation.

At the co-processor level, there appears to be a 7 in the 16th place.
Maybe Excel is doing something similar?

Binomial[9., 3.]//FullForm
84.00000000000007`

...

Note that in Mathematica the result depends on the argument data types.

Binomial[9,3]//FullForn
84

So, it looks like if we dig deep into the math co-processor, some values
will test Zero, and others will not.

...

It's all a question of implementation. The algorithm used to calculate
general binomial coefficients may not return integer results, but
there's NOTHING to stop the implementor adding a lowest order bit and
truncating the result to an integer.

Note that in Mathematica, Binomial[9.,3.] is 2^-47 *greater* than 84
while in Excel COMBIN(9,3) is 2^-46 *less* then 84. Also note that
Mathematica's Binomial function accepts noninteger arguments, e.g.,
Binomial[9.5,3.] returns 100.937, which is the same result as given by

Exp[LogGamma[10.5]-LogGamma[4.]-LogGamma[7.5]]

Note also that after messing around for a while in Mathematica (playing
with N[..] calls), it now returns 84. as the result for
Binomial[9.,3.]//FullForm. Looks like Mathematica also has a fudge
factor for double precision evaluation.

I'll repeat: it's all a matter of implementation, and Excel's is
suboptimal.

 

[Nick Hodge]

Harlan

That shows how marketing rules the roost... they'd rather have a nose job
than the boils lanced ;-) loved the analogy though

The devs would love to fix everything, it's just fixes don't sell <shrug>

--
HTH
Nick Hodge
Microsoft MVP - Excel
Southampton, England
www.nickhodge.co.uk
(e-mail address removed)

 

[Guest]

Thanks for the information Jerry, it is much appreciated.

 

[Harlan Grove]

(e-mail address removed) wrote...
....

Gnumeric returns an integer COMBIN result because it seemed like
a good idea when mucking with logs. Note the floor(0.5 + ...) in this
fragment: ....
And fact will return an exact (and thus integer) value for n<=15 and
probably more.

My appologies. I have created a test file in Excel, then loaded it into
OOo Calc and Gnumeric. Gnumeric didn't recalculate it automatically, so
it appeared that it gave the same results as Excel because it was still
displaying the Excel-calculated values.

Begs the question why Gnumeric didn't automatically recalc the file
when it opened.