Displaying 3 results from an estimated 3 matches for "birthday_problem".
2013 Jun 19
0
[LLVMdev] How to deal with potentially unlimited count/length symbol names?
On Wed, Jun 19, 2013 at 1:04 AM, edA-qa mort-ora-y <eda-qa at disemia.com>wrote:
>
> The problem is that if I derive the name from what the type contains the
> length of that name is essential unbound. So how does one generate
> names? I'm thinking of just using a long hash and hoping I don't get
> accidental collisions. Surely there must be a better way?
>
Just
2013 Jun 19
2
[LLVMdev] How to deal with potentially unlimited count/length symbol names?
...collisions;
their goal is to make it super hard to produce a collision _on purpose_.
What you need is an algorithm designed for string inputs, with good
uniformity, and an adequate output size; there are many.
Accidental collisions are essentially the Birthday Problem:
http://en.wikipedia.org/wiki/Birthday_problem
See particularly the end of the "Square approximation" section, which
specifically discusses the application to hashes, relating probability
of collision to bit-width and number of inputs.
For example, I worked out that with a 128-bit hash you need around
2^50 inputs before you get a coll...
2013 Jun 19
4
[LLVMdev] How to deal with potentially unlimited count/length symbol names?
In my language I have anonymous types (essentially tuples), and I have
generated functions (like constructors) which are unique for these
types. If the same type occurs in multiple modules however it should end
up with only one definition being linked. Thus I need a way to give them
the same name.
The problem is that if I derive the name from what the type contains the
length of that name is