(32S, 32SII) Birthday paradox, hash collision probability
05-04-2020, 05:56 PM
Post: #10
 Albert Chan Senior Member Posts: 1,676 Joined: Jul 2018
RE: (32S, 32SII) Birthday paradox, hash collision probability
(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
...
 « Next Oldest | Next Newest »

 Messages In This Thread (32S, 32SII) Birthday paradox, hash collision probability - Dave Britten - 04-25-2020, 04:49 PM RE: (32S, 32SII) Birthday paradox, hash collision probability - Albert Chan - 04-26-2020, 07:12 PM RE: (32S, 32SII) Birthday paradox, hash collision probability - Dave Britten - 04-26-2020, 07:58 PM RE: (32S, 32SII) Birthday paradox, hash collision probability - Albert Chan - 04-27-2020, 07:54 PM RE: (32S, 32SII) Birthday paradox, hash collision probability - Dave Britten - 04-27-2020, 09:16 PM RE: (32S, 32SII) Birthday paradox, hash collision probability - Albert Chan - 05-04-2020 05:56 PM RE: (32S, 32SII) Birthday paradox, hash collision probability - Albert Chan - 04-27-2020, 10:43 PM RE: (32S, 32SII) Birthday paradox, hash collision probability - Albert Chan - 04-28-2020, 03:23 PM RE: (32S, 32SII) Birthday paradox, hash collision probability - Albert Chan - 05-02-2020, 11:15 PM RE: (32S, 32SII) Birthday paradox, hash collision probability - Albert Chan - 05-03-2020, 01:00 PM RE: (32S, 32SII) Birthday paradox, hash collision probability - Werner - 05-05-2020, 01:46 PM

User(s) browsing this thread: 1 Guest(s)