2008-07-26 ден на админския махмурлук
by Vasil KolevСнощи в средно пияно състояние около един спор с Гунински (дължа му една бира) написах едно тестово програмче…
Въпросът беше следния – ако имаме две множества с 2^16 елемента, като всеки елемент може да е от 0 до 2^32, какъв е шансът сечението на двете множества да не е празното множество. Понеже количеството алкохол не предразполагаше към математика (а червото само ни препсува и отказа да го сметне), написах следното нещо, което да вади някаква статистика:
(да се отбележи, за пръв път успявам да използвам qsort() :) )
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/fcntl.h>
#include <stdlib.h>
#define LEN 65536
#define NTEST 100
static int compare(const void *a, const void *b)
{
if (*((int *) a) > *((int *) b)) return 1;
if (*((int *) a) < *((int *) b)) return -1;
return 0;
}
int do_whatever()
{
int s0[LEN],s1[LEN];
int i=0,j=0;
int rndsrc;
rndsrc=open("/dev/urandom",O_RDONLY);
read(rndsrc,s0,(sizeof(int)*LEN));
read(rndsrc,s1,(sizeof(int)*LEN));
close(rndsrc);
qsort (s0,LEN,sizeof(int),compare);
qsort (s1,LEN,sizeof(int),compare);
while ( (s0[i]!=s1[j]) && (i<LEN) && (j<LEN))
{
if (s0[i]<s1[j]) { if (!i<LEN) i++; }
else {if (!j<LEN) j++;};
}
if (s0[i]==s1[j]) return 1;
return 0;
}
int main()
{
int i,num=0;
for (i=0;i<NTEST;i++)
num+=do_whatever();
printf ("tests %d true %d false %d\n",NTEST,num,NTEST-num);
return 0;
}
Гунински твърдеше, че шансът клони към 1, и е прав – според програмката излиза над 1:2, което си клони към 1 :)
А, да, Шопов, как можа да ме черпиш две бири, след като бях пил толкова. Половината сутрин ми се искаше да съм умрял :).
Който помни повече от празнуването – да пише.
Tags: алкохолизъм
July 26th, 2008 at 17:20
Залагам на 2/3 :)
July 26th, 2008 at 17:47
Нека множествата са A и B. За всеки елемент x:
P(x in A) = P(x in B) = (2^16)/(2^32) = 1/(2^16)
P((x in A) and (x in B)) = P(x in A) * P(x in B) = 1/(2^32)
Шансът A и B да не се засекат в някое точно определено x е:
P(not((x in A) and (x in B))) = 1 – 1/(2^32) = 1 – 1/n
(означаваме n = 2^32)
Значи шансът A и B да не се засекат по нито едно x е:
(1 – 1/n) ^ n
ама как се доказваше, че това схожда към 2/3… ?
Ето и моят (много неефективен) емпиричен експеримент:
#!/usr/bin/env python
import sys
from random import *
def randset():
return frozenset([randint(0, 2 ** 32) for i in range(2 ** 16)])
n_tests = 100
n_intersects = 0
for i in range(n_tests):
if randset() & randset(): # it will become true if they intersect
n_intersects += 1
sys.stdout.write(‘%d out of %d pairs intersect\r’ % (n_intersects, i + 1))
sys.stdout.flush()
#EOF
July 26th, 2008 at 20:29
> ама как се доказваше, че това схожда към 2/3… ?
taz’ mila granica pri n->+int e 1/e
primordium 149% bc -l
n=2^32
n*l(1-1/n)
-1.00000000006927941632
e(n*l(1-1/n))
.36787944114595584863
1/e(1)
.36787944117144232159
primordium 150%
July 26th, 2008 at 21:15
Да, всъщност, тази граница трябва да е едно минус това което смятам, грубо 1/3. Мерси за помощта. Близко бях :) пия една бира в чест на всички нетрезвеници.
July 28th, 2008 at 13:53
С какви глупости се занимавате, докато Металика свирят бе, момчета???
July 28th, 2008 at 19:54
С DNS?
July 28th, 2008 at 21:57
Това е вариант на тема Birthday paradox
http://en.wikipedia.org/wiki/Birthday_paradox
Да приемем че числата са от 0 до 2^32-1 за опростяване на сметката. :)
Да приемем че елементите в А са различни един от друг и че елементите в B са различни един от друг. Иначе става страшно.
Да вземем първия елемент от А и да видим каква е вероятността той да е равен на кой да е от елементите в B. Елементарно – 2^16 * 1/2^32 = 1/2^16.
За втория и третия и 65536-тия елемент от A сметката е същата, от съображения за симетричност.
Сега остава да съберем вероятностите. Ако не сме чували че верояности не се събират с аритметично събиране ще кажем че вероятността да се засекат в поне едно елемент е е 2^16 * 1/2^16 или точно 1. Тъй като ме мързи (и не разбирам) да го разписвам като формула, драсвам 5 реда код, които казват че вероятността е около 63.2%, което съвпада с сметката на Атанас.
—————-
my $result=0;
for my $i (0..65535) {
$result+= (1-$result)/65536;
}
print “$result\n”;
0.632123365543794
—————-
July 28th, 2008 at 23:14
абе то всички ще свършим в лудница, ама важното е реда, т.е. някои ще ме изпреварят … което не е за успокоение де …
July 28th, 2008 at 23:43
tie: кво да се занимаваме, там работата е ясна от преди месец ;)
July 29th, 2008 at 09:43
ДЖБ:
http://cr.yp.to/djbdns/forgery.html
>As of November 2002, CERT is panicking because they didn’t realize how trivial this was, even though I spelled it out in a posting in July >2001
http://cr.yp.to/djbdns/forgery-cost.txt
>Randomizing the port number makes a huge difference in the cost
>of a forgery for blind attackers—i.e., most attackers on the Internet.
>Here’s the picture:
normal colliding sniffing
blind attack blind attack attack
———— ———— ——–
nothing 1 1 1
ID (BIND) 65536 256 1
ID+port (djbdns) 4227727360 65020 1
July 29th, 2008 at 14:17
gf: С DNS работата е мътна и кървава… Kaminsky разбърка курбана и едно черво изплува на повърхноста – но това далеч не е всичко в казана. Дори и със сорс порт рандомизация DNS остава много несигурен протокол. Дано хората не се подвеждат по “Not vulnerable” статусите за техните сървъри, в DNS няма такова положение. Там нещата са “Very vulnerable” и “Less vulnerable”.
August 4th, 2008 at 11:16
binom(2^32 + 1; 2^16) are the different ways you can choose 2^16 elements out of 2^32 + 1 set. If you choose two such sets, all possible combinations are given by binom(2^32 + 1; 2^16)*binom(2^32 + 1; 2^16). This is the denominator. Now, lets compute the numerator. Fix one particular combination of 2^16 numbers. We are interested in the remaining numbers, since if we choose another combination of 2^16 numbers out of the remaining, then the intersection of the two sets will be empty. We can choose 2^16 numbers out of 2^32 – 2^16 +1 set in binom(2^32 -2^16 + 1; 2^16) different ways. Now, lets sum over all possible ways of choosing 2^16 numbers out of 2^32 + 1 elements set, i.e. all good combinations are given by binom(2^32 + 1; 2^16)*binom(2^32 -2^16 + 1; 2^16). This gives us the possibility P = binom(2^32 + 1; 2^16)*binom(2^32 -2^16 + 1; 2^16) / binom(2^32 + 1; 2^16)*binom(2^32 + 1; 2^16) = binom(2^32 -2^16 + 1; 2^16) / binom(2^32 + 1; 2^16). а