(32S, 32SII) Birthday paradox, hash collision probability

[Albert Chan]

(04-27-2020 09:16 PM)Dave Britten Wrote:  Can't remember where it [ ln(1+x) = ln(x+1)*x/(1+x-1) ] came from exactly, but it was related to TVM calculations.
15C Advanced Functions handbook maybe?

You are right !
It was proved in Theorem 4, What Every Computer Scientist Should Know About Floating-Point Arithmetic

Quote:And yes, if x+1-1 returns 0, then you just return x, since ln(1+x) approaches x as x gets smaller.

I've noticed the formula failed for IEEE double with binary exponent of 53, and odd last bit.

It is impossible to represent odd 54-bits integer x with IEEE double (53-bits mantissa).
Let "⇒" represent round-to-even rules

If x last bit is 0: (x+1)-1 ⇒ (x)-1 ⇒ x
If x last bit is 1: (x+1)-1 ⇒ (x+2)-1 ⇒ x+2

lua> log = math.log
lua> log1p = require('mathx').log1p
lua> b = 2^53
lua> for i=1,1000 do x=b+2*i; print(i, log1p(x) , log(1+x)*x/(x+1-1)) end
1       36.7368005696771       36.736800569677094
2       36.7368005696771       36.7368005696771
3       36.7368005696771       36.73680056967709
4       36.7368005696771       36.7368005696771
5       36.7368005696771       36.736800569677094
...