An oddity if not a bug

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


"Biff" wrote in message
...
That's the "fudge factor" Harlan was talking about.

snip

Dana DeLouis wrote...
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
....

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.

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...
--
Dana DeLouis

"Harlan Grove" wrote in message
oups.com...
Dana DeLouis wrote...
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
...

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 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.

Harlan Grove wrote:

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

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/micro...06871cf92f8465
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

"JMB" wrote:

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.



"Biff" wrote:

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

"JMB" wrote in message
...
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.

"Harlan Grove" wrote:

Biff wrote...
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.
....

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.

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 befo
=COMBIN(9,3)-84=0
Go figure???
--
Dana DeLouis

"Harlan Grove" wrote in message
ups.com...
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.

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
HIS


"Harlan Grove" wrote in message
ups.com...
Biff wrote...
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.
...

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.

Thanks for the information Jerry, it is much appreciated.

"Jerry W. Lewis" wrote:

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/micro...06871cf92f8465
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

"JMB" wrote:

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.



"Biff" wrote:

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

"JMB" wrote in message
...
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.

"Harlan Grove" wrote:

Biff wrote...
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.
....

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.

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.