Вход | Регистрация


Информационные технологии ::

Метки: 

Вероятности совпадения GUIDов (128-битовых чисел)

Я
   GANR
 
28.12.12 - 12:46
Дано:
128-битовое число (GUID), генерируемое по равномерному закону распределения случайной величины в интервале от 0 до 2^128-1.

Найти (2 обратные задачи):
1. Веротность P(N) генерации 2-х и более одинаковых GUID в группе из N элементов.
2. Количество GUIDов N, которое необходимо сгенерировать, чтобы вероятность совпадения 2-х и более элементов в группе была не ниже заданного числа P(N).
 
 
   GANR
 
1 - 28.12.12 - 12:49
Как считаете: стоит ли увеличивать длину идентификаторов до 256 бит? Если да - то для каких задач?
   acsent
 
2 - 28.12.12 - 12:49
С(2, n) / 2^128
   ЧеловекДуши
 
3 - 28.12.12 - 12:51
(0)Очень большая.
Ибо делается оно мего скоростным алгоритмом :)
   GANR
 
4 - 28.12.12 - 12:53
(3) Исходим из предположения, что величина равномерная случайная, а не псевдослучайная и генератор случайных чисел очень хороший и имеет период во много раз больше 2^128.
   acsent
 
5 - 28.12.12 - 12:56
(4) кстати атомов во вселенной меньше чем 2^128
   GANR
 
6 - 28.12.12 - 12:57
(5) примечательно
   ЧеловекДуши
 
7 - 28.12.12 - 13:04
(6)Вероятность всегда есть.
Я про то, что если его запустят одновременно из разных точек :)
...
А если ты сам его буш генерить, т.е. из одной программы.
То не волнуйся, не совпадет.
   1Сергей
 
8 - 28.12.12 - 13:04
(5) хорошо, что это невозможно проверить, правда? :)
   acsent
 
9 - 28.12.12 - 13:07
(8) много чего невозможно проверить.
   1Сергей
 
10 - 28.12.12 - 13:08
(9) значит можно с умным видом заявлять (5) :)
 
 Рекламное место пустует
   GANR
 
11 - 28.12.12 - 13:08
(7) Это да, если 2 генератора СВ генерируют одинаковую последовательность - хана.
   acsent
 
12 - 28.12.12 - 13:09
(10) Невозможно проверить расстояние до туманности андромеда, но как то же его вычисляют
   GANR
 
13 - 28.12.12 - 13:10
А 2-ю задачу (обратную 1) кто-нибудь знает?
   1Сергей
 
14 - 28.12.12 - 13:11
(12) >> Вот один способ, каким астрономы измеряют расстояние до звезды. Ученые наблюдают за звездой в двух положениях. Например, из двух точек, находящихся на противоположных сторонах Зем­ли. Или из одной и той же точки, но с разницей в полгода, когда Земля поворачивается к звезде противоположной стороной. При этом звезда так­же меняет свое положение. Это изменение ее по­ложения называется параллаксом. Измеряя парал­лакс звезды, астрономы могут вычислить расстоя­ние до нее.
   GANR
 
15 - 28.12.12 - 13:13
Сколько надо нагенерировать GUIDов, совпадения появились с вероятностью, скажем 1 / exp(1) ?
   1Сергей
 
16 - 28.12.12 - 13:15
(15) 2^128 / exp(1)
   Zubek
 
17 - 28.12.12 - 13:22
У меня разок генерились уникальные идентификаторы, когда время БИОС назад ушло. Правдв все крутилось под виртуалками
   Zubek
 
18 - 28.12.12 - 13:22
Веселуха была. Старые документы заменялись новыми )))
   DGorgoN
 
20 - 28.12.12 - 13:29
Это про кол-во атомов во вселенной. Так что гуида якобы должно хватить. Однако манагеры могут:
атом1, атом 1, атом адин, атом один, атом I etc
   DGorgoN
 
21 - 28.12.12 - 13:31
(5) их 3 в степени 1079
   DGorgoN
 
22 - 28.12.12 - 13:32
Хотя по гипотезе Дирака http://www.e3e5.com/article.php?id=18
10 в 80
   1Сергей
 
23 - 28.12.12 - 13:42
2^128 ~ 3.4 * 10^38



Список тем форума
Рекламное место пустует Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Тема не обновлялась длительное время, и была помечена как архивная. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.
Рекламное место пустует