addthis/stream-lib — pull request #56 by andrewbts (2013-12-09 19:12:51+00:00)
Title: Correct gamma values using high precision arithmetic in Mathematica

The previous values were computed solely using machine precision
arithmetic, and roundoff error resulted in many incorrect digits,
including incorrect leading digits for large values.

The values in this commit are computed with adaptive high precision
arithmetic in Mathematica to ensure all 14 significant figures are
correct, using the following code:

AccountingForm[
N[With[{m = 2^Range[0, 31]},
m (Gamma[-1/m]*(1 - 2^(1/m))/Log[2])^-m], 14]]

In the above:
- N[expr, n] is adaptive high precision ensuring n correct digits
- AccountingForm[num] prints all digits

These values can also be computed in WolframAlpha. For example, the
last value:

http://www.wolframalpha.com/input/?i=N%5B%282147483648+Log%5B2%5D%5E2147483648%29%2F%28%281+-+2%5E%281%2F2147483648%29%29%5E2147483648+Gamma%5B-%281%2F2147483648%29%5D%5E2147483648%29%2C+14%5D

The old incorrect values introduced the following biases to counts
for values of k from 1 to 30:

1	1.00000000
2	1.00000000
3	1.00000000
4	1.00000000
5	1.00000000
6	1.00000000
7	1.00000000
8	1.00000000
9	1.00000000
10	0.99999999
11	1.00000000
12	1.00000000
13	0.99999999
14	1.00000002
15	1.00000011
16	0.99999965
17	0.99999782
18	0.99999508
19	0.99995702
20	0.99992517
21	0.99986159
22	1.00255548
23	1.00796510
24	1.03042078
25	0.89915286
26	1.17605954
27	0.97801074
28	0.67635117
29	0.32346664
30	0.07398505

In the above:
- A bias of e.g. 0.89 means reported cardinality is 89% of true
best estimate given the data so far.
- The default value of 16 was not biased enough to notice.
- The 1.03 bias at k=24 is noticeable and was how this issue was
discovered.