czemu to mi zwraca zawsze 1? Zamiast randomowej liczby z przedziału 0-9?
int a[9][9] = {0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0};
a[0][0] = rand() % 10;
A zaseedowałeś rand?
Poza tym, ustalanie zakresu poprzez resztę z dzielenia zaburza równomierność losowanego ciągu (pomijam kwestię jakości samej funkcji rand, która jednak w 95% zastosowań jest wystarczająco dobra, ale w niektórych już nie bardzo). Ten sposób sprawdzi się tylko w przypadku, gdy zakres jest potęgą dwójki.
Lepiej coś takiego:
X = (((double)rand()/(double)(RAND_MAX)) * Range);
https://pl.wikibooks.org/wiki/C/srand
https://stackoverflow.com/questions/1202687/how-do-i-get-a-specific-range-of-numbers-from-rand
andrzejlisek napisał(a):
Ten sposób sprawdzi się tylko w przypadku, gdy zakres jest potęgą dwójki.
To nie prawda, nadal ostatni zakres będzie rzadszy pod warunkiem typowego RAND_MAX czyli 32767.
andrzejlisek napisał(a):
Poza tym, ustalanie zakresu poprzez resztę z dzielenia zaburza równomierność losowanego ciągu (pomijam kwestię jakości samej funkcji rand, która jednak w 95% zastosowań jest wystarczająco dobra, ale w niektórych już nie bardzo). Ten sposób sprawdzi się tylko w przypadku, gdy zakres jest potęgą dwójki.
Lepiej coś takiego:
X = (((double)rand()/(double)(RAND_MAX)) * Range);https://pl.wikibooks.org/wiki/C/srand
https://stackoverflow.com/questions/1202687/how-do-i-get-a-specific-range-of-numbers-from-rand
Czemu uważasz że przy losowaniu cyfr rzadsze trafienie cyfr 3, 6 jest lepszym rozwiązaniem niż rzadsze trafienie cyfr 7,8?
Ba czy wiesz o jaki procent tej różnicy się rozwodzisz?
W podanym przykładzie masz double a wylosować trzeba cyfrę, z prawdopodobieństwem 99% nie dasz rady poprawnie zastosować to co proponujesz dla cyfr.
_13th_Dragon napisał(a):
andrzejlisek napisał(a):
Ten sposób sprawdzi się tylko w przypadku, gdy zakres jest potęgą dwójki.
To nie prawda, nadal ostatni zakres będzie rzadszy pod warunkiem typowego RAND_MAX czyli 32767.
Załóżmy, ze RAND_MAX=32767
Wymyślimy sobie zakres od 0 do 127, czyli 128 możliwych liczb. Liczba 128 jest potęgą dwójki. Sama funkcja rand() zwraca losową wartość z zakresu od 0 do 32767. Zakładamy, że implementacja samej funkcji rand() nie budzi zastrzeżeń, a więc generuje każda liczbę z takim samym prawdopodobieństwem.
Idziemy dalej. Liczba 32767 przeliczona na binarnie to 15 jedynek, a każda liczba od 1 do 32766 to ciąg składający się z zer i jedynek, jeżeli on jest krótszy niż 15 bitów, to dopisujemy zera z przodu. Okazuje się, że liczbę od 0 do 32767 można otrzymać poprzez 15 losowań binarnych (np. rzucanie monetą) i spisanie wyników tych losowań jako kolejnych bitów. Ponieważ jednej liczbie odpowiada jedna kombinacja bitów, to jej prawdopodobieństwo to 50% pomnożone 15 razy, czyli 0,5^15=1/32768
Chcemy liczby z zakresu od 0 do 127, czyli robimy N % 128. W praktyce jest to to samo, co N & 127, a więc w obu przypadkach z wylosowanej liczby bierzemy 7 ostatnich bitów, resztę odrzucamy. W tym przypadku jednej wylosowanej liczbie po odrzuceniu odpowiada dokładnie 256 liczb przed odrzuceniem, bo odrzucamy 8 bitów, których wartość nie jest ważna. Z tego wynika, że prawdopodobieństwo każdej liczby od 0 do 127 jest takie samo i wynosi 256/32768=1/128.
Równie dobrze można obliczać N >> 8, bo odrzucamy 8 ostatnich bitów i zostaje 7 bitów, które były z przodu. Uogólniając, jeżeli dla każdego bitu wartość 1 uzyskuje się z prawdopodobieństwem 50%, to nie ma znaczenia, które bity będziemy odrzucać, a które zostawiać, ważne, żeby odrzucić 8 bitów i zostawić 7 bitów.
Czy moje rozumowanie jest poprawne?
andrzejlisek napisał(a):
Poza tym, ustalanie zakresu poprzez resztę z dzielenia zaburza równomierność losowanego ciągu (pomijam kwestię jakości samej funkcji rand, która jednak w 95% zastosowań jest wystarczająco dobra, ale w niektórych już nie bardzo). Ten sposób sprawdzi się tylko w przypadku, gdy zakres jest potęgą dwójki.
Lepiej coś takiego:
X = (((double)rand()/(double)(RAND_MAX)) * Range);https://pl.wikibooks.org/wiki/C/srand
https://stackoverflow.com/questions/1202687/how-do-i-get-a-specific-range-of-numbers-from-randCzemu uważasz że przy losowaniu cyfr rzadsze trafienie cyfr 3, 6 jest lepszym rozwiązaniem niż rzadsze trafienie cyfr 7,8?
Ba czy wiesz o jaki procent tej różnicy się rozwodzisz?
W podanym przykładzie maszdoublea wylosować trzeba cyfrę, z prawdopodobieństwem 99% nie dasz rady poprawnie zastosować to co proponujesz dla cyfr.
Niektóre samouczki podają wybór zakresu jako N % K, a inne, takie lepsze, podają, ze to nie jest dobry sposób, bo zakłóca równomierność. Prosty przykład, niech zakres wynosi 0-9999, czyli będzie N % 10000.
Ponieważ N może przyjąć zakres od 0 do 32767, wylosowaliśmy 2 liczby:
Liczba 2000, czyli N mógł mieć jedną z tych wartości {2000, 12000, 22000, 32000}
Liczba 3000, czyli N mógł mieć jedną z tych wartości {3000, 13000, 23000} - liczba 33000 już nie może być, bo przekracza zakres
Z powyższego wynika, że prawdopodobieństwo wylosowania 2000 wynosi 4/32768, a prawdopodobieństwo wylosowania 3000 wynosi 3/32768, czyli prawdopodobieństwa się różnią i już w tym momencie mamy potwierdzone, że N % 10000 zaburzyło równomierność i potrzebny jest inny sposób.
Nie napisałem, że uważam, że lepsze jest rzadsze lub częstsze trafienie konkretnych cyfr. Napisałem tylko, żeby odwieźć od wciąż podawanego w tutorialach N % K jako sposób na zakres. A to, jakie znaczenie ma to zaburzenie równomierności to już inny temat. W projekcikach studenckich to może nie ma, ale w poważniejszych to już może mieć.
A z tym double, to pierwszy lepszy przykład z Google, jak obsłużyć wskazany zakres losowania bez użycia modulo. Teraz jeżeli mamy liczbę ułamkową z zakresu od 0 do 32767/32768 z równomiernym prawdopodobieństwem, to prawdopodobieństwo nie zmieni się, jak pomnoży się to przez stałą liczbę ułamkową. Jedynym źródłem zaburzeń mogą być ograniczenia liczb zmiennoprzecinkowych i zaokrąglenia.
Czy dobrze rozumuję? A jeżeli uważasz, że zamiana na double i mnożenie przez stałą double również nie jest dobrym sposobem, to poproszę sposób, który jest dobry dla języka C, bo do C++ jest biblioteka <random>, która zastępuje rand() z C.
andrzejlisek napisał(a):
Niektóre samouczki podają wybór zakresu jako
N % K, a inne, takie lepsze, podają, ze to nie jest dobry sposób, bo zakłóca równomierność. Prosty przykład, niech zakres wynosi 0-9999, czyli będzieN % 10000.
Ponieważ N może przyjąć zakres od 0 do 32767, wylosowaliśmy 2 liczby:Liczba 2000, czyli N mógł mieć jedną z tych wartości {2000, 12000, 22000, 32000} Liczba 3000, czyli N mógł mieć jedną z tych wartości {3000, 13000, 23000} - liczba 33000 już nie może być, bo przekracza zakresZ powyższego wynika, że prawdopodobieństwo wylosowania 2000 wynosi 4/32768, a prawdopodobieństwo wylosowania 3000 wynosi 3/32768, czyli prawdopodobieństwa się różnią i już w tym momencie mamy potwierdzone, że
N % 10000zaburzyło równomierność i potrzebny jest inny sposób.
Czemu rozpatrujesz tylko N % K?
Rozpatrzmy też 10000*N/RAND_MAX czyli twoja "lepsza" propozycja.
Liczba 2005, czyli N mógł mieć jedną z tych wartości {6570, 6571, 6572, 6573}
Ponieważ:
10000*6569/32767 = 2004,76088747826
10000*6574/32767 = 2006,28681295206
Liczba 3000, czyli N mógł mieć jedną z tych wartości {9831, 9832, 9833}
Ponieważ:
10000*9830/32767 = 2999,96948149052
10000*9834/32767 = 3001,19022186956
Czyli to samo czyli 3/32768 w przypadku liczby 3000 oraz ponieważ twierdzisz że twoja metoda lepsza to z tego wynika że twierdzisz że wg ciebie liczba 2000 jest lepsza od 2005, dobrze rozumiem? Może wyjaśnisz czemu liczba 2000 jest lepsza od liczby 2005?
Nic nie powiedziałeś na temat procentu różnicy o który się rozwodzisz zobaczmy 100*(4/32768-3/32768) = 0,0031% o rzesz q-wa jak może program działać przy tak gigantycznej różnice? Przypominam że występuje w przypadku obu sposobów.
Nie napisałem, że uważam, że lepsze jest rzadsze lub częstsze trafienie konkretnych cyfr. Napisałem tylko, żeby odwieźć od wciąż podawanego w tutorialach
N % Kjako sposób na zakres. A to, jakie znaczenie ma to zaburzenie równomierności to już inny temat. W projekcikach studenckich to może nie ma, ale w poważniejszych to już może mieć.
Sposób N%K jest lepszy bo mniej błędogenny, zaś zaburzenie równomierności występuje w obu przypadkach jak pokazano wyżej. O jakich "poważniejszych" mówisz? Obstawiam że nawet nie znasz nazwy algorytmu w przypadku którego może to mieć istotne znaczenie.
A propos "mniej błędogenny" udowodnię ci to jak podasz kod losowania liczby całkowitej z zakresu.
Czyli twoja "lepsza" alternatywa do int rand_range(int range) { return rand()%range; }
Bo jak na razie ogólne powołałeś się na googla bez podania konkretnego kodu lub ewentualnie strony z kodem.
Czyżby nie byłeś w stanie zaadoptować podanego tobą wcześniej X = (((double)rand()/(double)(RAND_MAX)) * Range); do generacji liczby typu int?
A przy tym próbujesz dawać rady na forum?
Czemu rozpatrujesz tylko N % K?
Jest to najpopularniejszy sposób wśród początkujących, również zastosowany przez OP, moją intencją było uzasadnienie faktu, że jest to zawodny sposób, a nie analiza wszystkich możliwych sposobów.
Może wyjaśnisz czemu liczba 2000 jest lepsza od liczby 2005
Aby dostać liczbę 2000, trzeba uzyskać liczbę losową ze zbioru {6554, 6555, 6556}
Nic nie powiedziałeś na temat procentu różnicy o który się rozwodzisz
Napisałem, ze to bierze się z zaokrągleń, a w praktyce nie ma to istotnego znaczenia.
Bo jak na razie ogólne powołałeś się na googla bez podania konkretnego kodu
W poprzednim poście podałem te dwa linki, a zastosowanie liczb double to nie jest mój wymysł:
link
link
A że google nie boli, to znalazłem i podam jeszcze jeden link: link
link - tu jest propozycja jeszcze innego sposobu wykorzystującego pętlę.
A przy tym próbujesz dawać rady na forum?
Czy tylko ludzie nieomylni mają prawo udzielać odpowiedzi? Chyba, ze post jest skrajnie nie na temat, to wtedy wylatuje do kosza.
Ja uważam, że teraz wszystko jest wyjaśnione i proponuję zakończyć tą dyskusję.
andrzejlisek napisał(a):
Czemu rozpatrujesz tylko N % K?
Jest to najpopularniejszy sposób wśród początkujących, również zastosowany przez OP, moją intencją było uzasadnienie faktu, że jest to zawodny sposób, a nie analiza wszystkich możliwych sposobów.
Aby stwierdzić że coś jest lepsze od czegoś trzeba poddać jednakowemu badaniu oba obiekty.
Bo próbujesz udowodnić że kawa lepsza od herbaty za pomocą faktu że herbata jest płynna?
Może wyjaśnisz czemu liczba 2000 jest lepsza od liczby 2005
Aby dostać liczbę 2000, trzeba uzyskać liczbę losową ze zbioru {6554, 6555, 6556}
Owszem, ale aby dostać liczbę 2005, trzeba uzyskać liczbę losową ze zbioru {6570, 6571, 6572, 6573}
Czyli podtrzymujesz że 2000 jest lepszą liczbą niż 2005? Ponieważ wg ciebie przykład z 2005 jest gorszy niż przykład z 2000, dobrze rozumiem?
Nic nie powiedziałeś na temat procentu różnicy o który się rozwodzisz
Napisałem, ze to bierze się z zaokrągleń, a w praktyce nie ma to istotnego znaczenia.
Ok rozumiem, różnica pomiędzy 2005 a 3000 w przypadku twojej propozycji berze się z zaokrągleń, a w praktyce nie ma to istotnego znaczenia.
Natomiast różnica pomiędzy 2000 a 3000 w przypadku N%K jest istotna bo zakłóca równomierność?
Czy ty zastanawiasz się nad tym co piszesz?
Bo twierdzisz że kawa lepsza od herbaty ponieważ herbata jest płynna, zaś płynność kawy w praktyce nie ma to istotnego znaczenia?
Bo jak na razie ogólne powołałeś się na googla bez podania konkretnego kodu
W poprzednim poście podałem te dwa linki, a zastosowanie liczb double to nie jest mój wymysł:
link
link
W pierwszym nie ma nic o zakresie całkowitym - czyli może tobie google nie boli ale korzystać też nie umiesz.
W drugim znalazłem:
int random(int min, int max){
return min + rand() / (RAND_MAX / (max - min + 1) + 1);
}
Sprawdzamy:
#include <iostream>
#include <cstdlib>
using namespace std;
const int RND_MAX=32767;
int randomA(int rnd,int min, int max)
{
return min + rnd / (RND_MAX / (max - min + 1) + 1);
}
int randomB(int rnd,int min, int max)
{
return min + rnd%(max - min + 1);
}
int main()
{
int tb[2][10] = {{0}};
for(int rnd=0;rnd<=RND_MAX;++rnd)
{
++tb[0][randomA(rnd,0,9)];
++tb[1][randomB(rnd,0,9)];
}
for(int i=0;i<10;++i) cout<<i<<": "<<tb[0][i]<<" "<<tb[1][i]<<endl;
return 0;
}
https://wandbox.org/permlink/J9nhV3cVUYQyddG2
Proszę mi wyjaśnić czemu N%K (czyli ten niby gorszy) daje bardziej równomierny rozkład niż ten niby lepszy?
A że google nie boli, to znalazłem i podam jeszcze jeden link: link
Bez kodu? Czyli nie umiesz tego zastosować w praktyce a radzisz używać to nowicjuszom?
Pierwsza próba - 1:0 na rzecz N%K, poproszę o kolejną próbę.
Zamiast dalej dywagować, sprawdziłem, co podają u źródła:
Komentarz "Note: 1+rand()%6 is biased" jest chyba nie przez przypadek, natomiast w praktyce nie ma to istotnego znaczenia, bo różnica jest na 4 czy 5 miejscu po przecinku.
Wniosek jest jednoznaczny: Teoretycznie wydaje się, że ma znaczenie, w praktyce nie ma znaczenia. Sposób przeliczenia (module vs mnożenie) tak naprawdę zmienia sposób przyporządkowania liczb z podanego zakresu (czyli w linkowanym przykładzie 6 możliwości) do wszystkich możliwych wyników funkcji. W przypadku 6 możliwości i RAND_MAX=32767, zawsze dwie liczby będą faworyzowane, bo 32768%6 = 2, nie ma siły, żeby było inaczej, ale z drugiej strony to "faworyzowanie" nie ma tak istotnego wpływu, żeby zawracać sobie tym głowę.
_13th_Dragon napisał(a):
Czy ty zastanawiasz się nad tym co piszesz?> Bo twierdzisz że kawa lepsza od herbaty ponieważ herbata jest płynna, zaś płynność kawy w praktyce nie ma to istotnego znaczenia?
Dla mnie to jest wyraźny sygnał, że dalsza dyskusja na ten temat nie ma sensu i czas ją zakończyć.
andrzejlisek napisał(a):
Komentarz "Note: 1+rand()%6 is biased" jest chyba nie przez przypadek, natomiast w praktyce nie ma to istotnego znaczenia, bo różnica jest na 4 czy 5 miejscu po przecinku.
Stronniczy (biased)? Ten przez dzielenie jeszcze bardziej stronniczy, co pokazano w poprzednim poście.
No chyba że ktoś poprawnie to oprogramuje, nadal zachęcam do kolejnych prób poprawnej realizacji.
Nareszcie jakieś sensowne wnioski, nareszcie rozumiesz że nie warto bardziej skomplikowaną metodę radzić początkującym kiedy nie ma to istotnego znaczenia.
andrzejlisek napisał(a):
.... Sposób przeliczenia (module vs mnożenie) tak naprawdę zmienia sposób przyporządkowania liczb z podanego zakresu (czyli w linkowanym przykładzie 6 możliwości) do wszystkich możliwych wyników funkcji.
Lecz dla niektórych algorytmów jest to istotne, czy przyporządkowania są skupione w jednym miejscu czy rozrzucone po całym zakresie.
andrzejlisek napisał(a):
W przypadku 6 możliwości i RAND_MAX=32767, zawsze dwie liczby będą faworyzowane, bo 32768%6 = 2, nie ma siły, żeby było inaczej, ale z drugiej strony to "faworyzowanie" nie ma tak istotnego wpływu, żeby zawracać sobie tym głowę.
Zawsze 2? Nie ma siły? sprawdzamy!
#include <iostream>
#include <cstdlib>
using namespace std;
const int RND_MAX=32767;
int randomA(int rnd,int min, int max)
{
return min + rnd / (RND_MAX / (max - min + 1) + 1);
}
int randomB(int rnd,int min, int max)
{
return min + rnd%(max - min + 1);
}
int main()
{
int tb[2][6] = {{0}};
for(int rnd=0;rnd<=RND_MAX;++rnd)
{
++tb[0][randomA(rnd,0,5)];
++tb[1][randomB(rnd,0,5)];
}
for(int i=0;i<6;++i) cout<<i<<": "<<tb[0][i]<<" "<<tb[1][i]<<endl;
return 0;
}
Jak widać w przypadku N%K rzeczywiście 2 liczby faworyzowanie, zaś w przypadku mnożenia 5 liczb faworyzowanych, kosztem jednej mocno "dyskryminowej".
A to dla tego że prawie nikt nie umie zrobić poprawnego "rand range" poprzez proporcje rozkładu.
_13th_Dragon napisał(a):
Zawsze 2? Nie ma siły? sprawdzamy!
W ogólnym przypadku jest taka możliwość, miałem na myśli przypadek optymistyczny, czyli takim, w którym różnica maksymalnej i minimalnej liczby przypadków jest co najwyżej 1. Jeżeli ta różnica wynosi 4 (5462-5458), to oczywiście, że może być więcej liczb faworyzowanych. Jeżeli 32767/6=5461,1667, to ułożymy równanie (a*5461+b*5462)=32767 (zaokrąglenie 5461,1667 w górę i w dół), a liczby a i b mogą być całkowite. Ja widzę tylko jedno rozwiązanie, gdzie a=4 i b=2. Równanie ogólne to (a*floor(RAND_MAX/n) + b*ceil(RAND_MAX/n)) = RAND_MAX, gdzie a, b i n są całkowite.
andrzejlisek napisał(a):
_13th_Dragon napisał(a):
Zawsze 2? Nie ma siły? sprawdzamy!
W ogólnym przypadku jest taka możliwość ...
Nie, jest to w każdym przypadku N%K oraz w każdym przypadku poprawnej realizacji metody którą bezkrytycznie (a może bezmyślnie) faworyzujesz.
Problem w tym że napisać poprawny kod dla generacji zakresu liczb całkowitych ta metodą potrafi coś koło X=0,07% programistów (nie liczę tych co potrafią skorzystać z gotowca np. wbudowanego w C++).
Czyli w googlach procentowo znajdziesz X^2/π poprawnych rozwiązań.