3 ms·

People tend to confuse the odds of two arbitrary strings colliding with the chances of a set of strings having a collision. 32bit space is not that big, and you

by tedivm 12y ago

People tend to confuse the odds of two arbitrary strings colliding with the chances of a set of strings having a collision. 32bit space is not that big, and you have to take into account the birthday problem. If you do out the math it turns out there's a 50% chance of collision after only 77,163 hashes. http://preshing.com/20110504/hash-collision-probabilities/ http://preshing.com/20110504/hash-collision-probabilities/

deleted 12y ago
[deleted]
- nitrogen 12y ago
  Of course, nobody will connect thousands of USB devices to their computer. No, but there are thousands of preset IDs in the hundreds of drivers already present on the computer. For this reason, isn't it safe to pick a random 32-bit identifier? Devices don't just collide with others on the same computer, but with other drivers on the same computer. Edit: Unfortunately sillysaurus3 deleted the parent comment. It had an interesting summary of a simulation of the collision problem.
  - deleted 12y ago
    [deleted]
- deleted 12y ago
  [deleted]
- FigBug 12y ago
  I believe the 32-bit id you select needs to be unique from all the ids your OS knows about or else it will install the wrong driver and may crash / encounter other issues. Of course the user could manually uninstall that driver and install a driver you provided. But randomly selecting an id doesn't make much sense. For example here are all the ids Linux knows about: http://www.linux-usb.org/usb.ids http://www.linux-usb.org/usb.ids. Obviously don't select Logitech, Microsoft, Canon, Samsung, etc. manufacture id. Either select an unused manufacture and then randomly select the device id. Or select a manufacturer id that is no longer used like US Robotics (I doubt they are making any new modems) and then randomly select a device id. As soon as make your device, connect it to a Windows machine which will try and find a driver -- if it doesn't, probably no conflict. If there is a conflict, it's with a product that distributes it's driver manually - so you don't have to worry. Or a product that doesn't exist yet, which could be an issue.
zellyn 12y ago
A good rough rule is to halve the power of two: so 2^16 = 65536, which is close enough to 77163.
- swimfar 12y ago
  That's really cool. I tried it with the birthday problem[1] (real answer 23) and got 16 if I used whole exponents[2] and 19 with fractional exponents[3]. They're a little off but it gives you an idea of the value. [1] https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem [2] 256 days=2^8, 16=2^4 [3] 365 days=2^8.51, 19=2^4.255
Pinckney 12y ago
That doesn't matter to an individual developer. Why should they care if the set of all in use USB PIDs has collisions? It's only becomes a problem for them if their PID suffers a collision.
Tinyyy 12y ago
The Birthday Problem is only relevant to find collisions between any 2 strings, but in this case the developer is only concerned about the probability of his own string clashing with someone else’s, thus the probability of a collision is only Number of taken strings / Number of total strings.

by tedivm 12y ago

deleted 12y ago

[deleted]

nitrogen 12y ago
Of course, nobody will connect thousands of USB devices to their computer. No, but there are thousands of preset IDs in the hundreds of drivers already present on the computer. For this reason, isn't it safe to pick a random 32-bit identifier? Devices don't just collide with others on the same computer, but with other drivers on the same computer. Edit: Unfortunately sillysaurus3 deleted the parent comment. It had an interesting summary of a simulation of the collision problem.
- deleted 12y ago
  [deleted]
deleted 12y ago
[deleted]
FigBug 12y ago
I believe the 32-bit id you select needs to be unique from all the ids your OS knows about or else it will install the wrong driver and may crash / encounter other issues. Of course the user could manually uninstall that driver and install a driver you provided. But randomly selecting an id doesn't make much sense. For example here are all the ids Linux knows about: http://www.linux-usb.org/usb.ids http://www.linux-usb.org/usb.ids. Obviously don't select Logitech, Microsoft, Canon, Samsung, etc. manufacture id. Either select an unused manufacture and then randomly select the device id. Or select a manufacturer id that is no longer used like US Robotics (I doubt they are making any new modems) and then randomly select a device id. As soon as make your device, connect it to a Windows machine which will try and find a driver -- if it doesn't, probably no conflict. If there is a conflict, it's with a product that distributes it's driver manually - so you don't have to worry. Or a product that doesn't exist yet, which could be an issue.

zellyn 12y ago

A good rough rule is to halve the power of two: so 2^16 = 65536, which is close enough to 77163.

swimfar 12y ago
That's really cool. I tried it with the birthday problem[1] (real answer 23) and got 16 if I used whole exponents[2] and 19 with fractional exponents[3]. They're a little off but it gives you an idea of the value. [1] https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem [2] 256 days=2^8, 16=2^4 [3] 365 days=2^8.51, 19=2^4.255

Pinckney 12y ago

That doesn't matter to an individual developer. Why should they care if the set of all in use USB PIDs has collisions? It's only becomes a problem for them if their PID suffers a collision.

Tinyyy 12y ago

The Birthday Problem is only relevant to find collisions between any 2 strings, but in this case the developer is only concerned about the probability of his own string clashing with someone else’s, thus the probability of a collision is only Number of taken strings / Number of total strings.