algoritmi.1ppekovic,
Ova tema je namenjena za sve one programerske probleme, predloge, ideje,...
koje nisu vezani ni za jedan programski jezik.
Paya
algoritmi.2janko,
Skoro sam dobio pismo čije delove citiram, jer mislim da mogu
još nekog zanimati i pitanje i odgovor...
> Nedavno sam radio neki install za neki program čiji je autor
> poodavno u inostranstvu i u okviru toga mi je trebalo prilagođavanje
> poruka rasporedu koji je instaliran na ciljnom računaru. Prvo
> sam mislio da upotrebim već gotove programe za konverziju, ali
> pošto je tu bilo i nekih uslovnih konverzija, napisao sam kod
> koji to vrši. Pri tom sam primenio princip koji sam video u
> tvom juk100.cpp, s tim što sam samu konverziju uradio u
> asembleru kao inline assembly (ostatak programa je urađen u
> C-u). Stvar radi dosta brzo, i kad je ceo install bio gotov,
> izdvojio sam samo taj deo za konverziju jer me zanimalo kako
> se po pitanju brzine odnosi sa programima kakvi su cconv i
> yuras (poskok tad još nije bio javno publikovan). Rezultat je
> bio da je moj program za konverziju između 2-4 puta sporiji od
> Zakovog cconv-a. Ništa čudno, obzirom da je u pitanju C
> program, ali me zanimalo da li se ipak stvar može ubrzati.
> Zato sam program preveo sa MSC-om sa max. optimizacijom i bio
> je za 7-8% brži nego kad je preveden sa BCC. E, sad, tu sam
> stao jer pretpostavljam da kad bi se ceo program napisao u
> asembleru da bi se jako približio cconv-u, ali nemam mnogo ni
> vremena ni živaca da se previše petljam sa asemblerom pa sam
> stao na ovom. Install rutina radi dovoljno brzo, a za lične
> potrebe ionako koristim poskok i cconv.
>
>
> P.S. Planiram i da prepravim taj program za koji sam radio
> install (kad se dokopam celog source-a) tako da radi u skladu
> sa UKRAS-om, pa onaj Install više neće ni biti potreban.
Krenuo si na pogrešnu stranu u ubrzavanju. Konkretno, da bi
znao šta treba da ubrzavaš, moraš da znaš šta je 'usko grlo'
programa. To bi trebalo, kao, da mere profajleri, ali oni koje
sam ja probao, i koliko sam uspeo da ih iskoristim, su dosta
nesavršeni kada se mere perfomanse programa koji imaju
intenzivan I/O.
Ukratko, očigledno da u tvom slučaju sama rutina za konverziju
NIJE usko grlo u programu.
Takođe, ako si slučajno pomislio suprotno, ni Yuras ni Poskok
nisu pisani u asembleru. I jedan i drugi su Turbo Paskal
programi, ni jednog ni drugog NISAM ja pisao, (drugom, čak, nisam
ni video sors) ali sam za oba napisao kratke rutinice koje JESU
u asembleru -- i koje bi trebalo da ubrzaju ono što bi trebalo
da je njima usko grlo -- samu konverziju. Primeti da ni u
jednom ni u drugom I/O operacije NISU pisane u asembleru.
Ovo sve, naravno, NE znači da je moguće napisati brži program
na Turbo Paksalu nego na C-u. Turbo Paskal ima interno
memorijski model koji je po brzini ekvivalentan 'compact'
(a zavisi od konfiguracije TP-a, nekad i 'large') memorijskom
modelu u C-u. Dakle, ako koristiš 'small' ili 'medium'
memorijski model, trebalo bi da ti je ekvivalentan program brži
u C-u. S druge strane, Turbo Paskal koristi interni format
brojeva u pokretnom zarezu, dok C programi (ako se ne varam,
možda može nekako da se promeni emulacioni kod?) uvek rade
unekoliko okrnjenu emulaciju IEEE standarda, pa je moguće da u
aplikacijama koje rade sa takvim brojevima, ako nemaš numerički
koprocesor, TP varijanta radi brže?
Dakle ti si uradio u svom programu, ako sam dobro razumeo
(pomenuo si neke inline assembly rutine) isto ono što sam i ja
u programima koje pominješ.
Međutim, sporije rezultate si dobio verovatno jer su rutine za
rad I/O operacija očigledno sporije od onih koje su primenjene
u pomenutim programima.
Na primer, pošto pominješ C, već sam svojevremno pisao da je
scanf ili fscanf
na primer, naredba koja SVAKI PUT kada se pozove INTERPRETIRA
svoj format string. Naravno, u petlji to može traje primetno...
Ali ni to nije sve. Verovatno u svom programu nisi podešavao
veličnu bafera, što se može učiniti naredbom setvbuf u C-u,
kojom ćeš (potencijalno, SAMO na Dosu) primetno ubrzati svoj
program čak iako koristiš fscanf (koji je ponekad nezamenljiv).
I na kraju, žao mi je što do sada nisam video da je iko
iskoristio pomenute Ukras rutine za C i C++. Možda neko nije
shvatio da te rutine rade i na svakom ANSI C kompajleru, (iako
u zahlavljima to piše?) i nisu isključivo C++ programi iako im
je ekstenzija .cpp?
algoritmi.3dzakic,
Treba mi par funkcija koje ostvaruju 1-1 preslikavanje između skupa
datuma (oblika dd, mm, yyyy) i skupa celih brojeva. žini mi se da je
tako nešto dejanr ostavio u starom pc.prog-u, čini mi se da je se to čak
našlo i u bajtovima lične prirode, ali nikako ne uspevam da pronađem ni
jedno ni drugo (a nisam baš raspoložen da pronalazim toplu vodu). Help!
algoritmi.4bojanp,
-> #3, dzakic> Treba mi par funkcija koje ostvaruju 1-1 preslikavanje između skupa
> datuma (oblika dd, mm, yyyy) i skupa celih brojeva. žini mi se da je
Pogledaj sledeće poruke u ORKA.1 konferenciji: 14.184, 14.186, 14.206.
Pozdrav, Bojan
algoritmi.5dejanr,
-> #3, dzakicprogram datumi;
{
KONVERZIJE DATUM<--->JULIAN DAY NO
Copyright (C) 1980-1988 Dejan Ristanovic
}
var d,m,g: integer;
function cj (d,m,g: integer): longint;
var gp,izlaz: real;
begin
gp:=g+(m-2.85)/12.0;
izlaz:=int(367*gp)-int(gp)-0.75*int(gp)+d;
izlaz:=int(izlaz)-0.75*int(gp/100);
izlaz:=int(izlaz)+1721115;
cj:=trunc(izlaz);
end;
function day(d,m,g: integer): integer;
begin
day:=(cj(d,m,g)+1) mod 7
end;
procedure jc(jdn: longint; var d,m,y: integer);
var n,c,np,yp,npp,mp: longint;
begin
n:=jdn-1721119;
c:=trunc((n-0.2)/36524.25);
np:=n+c-trunc(c/4);
yp:=trunc((np-0.2)/365.25);
npp:=np-trunc(365.25*yp);
mp:=trunc((npp-0.5)/30.6);
d:=trunc(npp-30.6*mp+0.5);
if mp<=9 then begin m:=mp+3; y:=yp end
else begin y:=yp+1; m:=mp-9 end
end;
begin
repeat
write ('Datum (DD): ');
readln (d);
write ('Mesec (MM): ');
readln (m);
write ('Godina (YYYY): ');
readln (g);
writeln('Julian day = ', cj(d,m,g));
jc(cj(d,m,g),d,m,g);
writeln(d,' ',m,' ',g);
writeln('Dan (0=nedelja): ',day(d,m,g));
until false;
end.
algoritmi.7dzakic,
-> #4, bojanpZnam da se ovo neće svideti mjogiju, ali...
Hvala i tebi i dejanu.
cu
algoritmi.8janko,
Pogledajte ovaj deo teksta iz PGP 2.0 paketa:
> When I was in college in the early seventies, I devised what I
> believed was a brilliant encryption scheme. A simple
> pseudorandom number stream was added to the plaintext stream to
> create ciphertext. This would seemingly thwart any frequency
> analysis of the ciphertext, and would be uncrackable even to the
> most resourceful Government intelligence agencies. I felt so
> smug about my achievement. So cock-sure.
>
> Years later, I discovered this same scheme in several
> introductory cryptography texts and tutorial papers. How nice.
> Other cryptographers had thought of the same scheme.
> Unfortunately, the scheme was presented as a simple homework
> assignment on how to use elementary cryptanalytic techniques to
> trivially crack it. So much for my brilliant scheme.
>
> From this humbling experience I learned how easy it is to fall
> into a false sense of security when devising an encryption
> algorithm.
Zna li neko kako se 'elementarnim tehnikama trivijalno
razbijaju' tako kriptovane datoteke? (MNOGI komercijalni
programi upravo ovako kriptuju datoteke!)
algoritmi.9zormi,
-> #8, janko* > A simple pseudorandom number stream was added to the plaintext
* > stream to create ciphertext.
*
* Zna li neko kako se 'elementarnim tehnikama trivijalno
* razbijaju' tako kriptovane datoteke?
Odmah da kažem: ne znam i nisam se time bavio. Možda samo da dam
poneku laičku ideju.
Npr. ako je pseudorandom niz kraći (mnogo puta?) od teksta onda se
ponavlja, pa na odredjenom rastojanju (dužine niza) se dodaju isti
brojevi na slova. Kada se ovo rastojanje ulovi (naravno računarom)
može da se napravi statistika i dovede u korelaciju sa učestanošću
pojavljivanja slova u jeziku ili sl. tj. može da se izvuče na koja
su najverovatnija slova dodati pojedini članovi pseudo slučajnog
niza, što je elementarna tehnika.
Kada je niz mnogo kraći od teksta, ne "ispuca" se ceo pa je statistika
neujednačena i sigurno može nešto da se izvuče.
U svakom slučaju, kakve su sve šifre razbijane ovo mi ne "miriše" na
nešto mnogo sigurno.
algoritmi.10dusanp,
-> #8, janko=> Zna li neko kako se 'elementarnim tehnikama trivijalno
=> razbijaju' tako kriptovane datoteke? (MNOGI komercijalni
=> programi upravo ovako kriptuju datoteke!)
Jedino meni logično objašnjenje je da se mogu dekriptovati
fajlovi koji imaju bar neki deo koji standardno izgleda - na
primer kriptovani WP5 tekstovi, koji imaju identične hedere...
Ima li nekog ko nije i sam "smislio" ovaj sistem ??? Ja
svojevremeno jesam, i dalje ga smatram jako pouzdanim.
algoritmi.11dejanr,
-> #10, dusanp>> > Zna li neko kako se 'elementarnim tehnikama trivijalno
>> > razbijaju' tako kriptovane datoteke?
>>
>> Jedino meni logično objašnjenje je da se mogu dekriptovati
>> fajlovi koji imaju bar neki deo koji standardno izgleda - na
>> primer kriptovani WP5 tekstovi, koji imaju identične hedere...
>>
>> Ima li nekog ko nije i sam "smislio" ovaj sistem ??? Ja
>> svojevremeno jesam, i dalje ga smatram jako pouzdanim.
Nisi u pravu. To jest u pravu si za WP tekstove, ali nisi u pravu
ako misliš da probijanje šifra slovo:=(slovo+rnd) mod xxx predstavlja
pomena vredan problem. Ja sam na toj šifri jednom zaradio 100 dem a
jednom izgubio 10,000 dinara (ili tako nešto).
Što se tiče zarade, davno je to bilo, imali neki moji drugari neki
programčić za šifrovanje (tad nije bilo PKZIP-a, PGP-a i tako dalje,
sve se to dešava na nekakvom PDP-ju 11) koji radi otprilike ovako
(ovo nije nikakav konkretan programski jezik ali verujem da će svi
razumeti):
input seed
randomize(seed)
repeat
input txt
for i=1 to length(txt)
print chr((ord(txt(i))+rnd(128)) mod 128); ((())) <-- ovo su
zagrade, dodajte kolko
treba da bude ok izraz
next i
print
until false
Program za dešifrovanje je otprilike isti takav, samo što je umesto
plusa minus i tako to. Elem, genije koji je smislio taj program je
bio silno ubeđen u njegovu sigurnost, i tako su se oni mesecima
"dobacivali" šifrovanim porukama. Ja sam ih duže vreme ubeđivao da
je ta šifra golo go*no i najzad se opkladimo u 100 dem da ću im
probiti šifru za 24 sata (to je u srećno vreme kad sam bio dokon
pa sam mogao da se majem sa takvim glupostima... mada 100 maraka
za sat-dva posla... hmmm... možda bi se i sad našlo vremena ;).
Pokupim ja sve šifrovane poruke koje su stajale po disku, i krenem
otprilike ovako:
1. razne poruke su šifrovane istim ključem (nisu valjda dogovarali
nov ključ za svaku poruku ;)
2. ispišem prva slova iz 100 poruka jedno do drugog
3. svih tih 100 slova je šifrovano istim slučajnim brojem. Recimo ako
je taj broj 15, onda je svako slovo pomereno za 15 mesta u odnosu
na originalnu poziciju.
4. prebrojim koliko među tim prvim slovima ima A, koliko B, itd.
Ispostavi se da najviše ima slova M (recimo!), negde 10 od 100.
Dakle M je verovatno zamena za A, onda je N zamena za B, O zamena
sa C i tako dalje. Malo probam da li to važi (ako se ispostavi da
je drugo slovo po učestanosti č, onda pretpostavka da M menja A nije
dobra, nego je M zamena za neko drugo često slovo, recimo I ili O)
i ispadne da važi, dakle znam da dešifrujem prvo slovo svih poruka
5. Ponovim 2, 3, 4 za drugo, treće, četvrto, peto itd slovo iz 100
poruka i eto dešifrovanih poruka. Naravno da se to 2-4 ne ponavlja
ručno nego pomoću programčeta, ali programče se napiše za cca sat.
Na metod koji sam izmislio sam bio strrrrrašno ponosan, ali sam posle
saznao da je isti još hiljadu osamsto i neke predložio Kerkhofs, a pre
toga nešto slično i Bazeri, Valerio... i da je sve to deo nečega što
se zove "opšti metod za sve polialfabetske kriptograme". Šta da se radi,
nije lako na ovaj svet doneti nešto novo, ali 100 DEM sam uredno inkasirao ;)
Inače, kad sam kod tih kriptografskih metoda, na mene je najjači utisak
ostavila Kerkohofsova ideja kako se određuje dužina ključa kod Vižnerove,
de la Portine, Belazove i sličnih tablica za polialfabetsko šifrovanje.
Tako to komplikovano i neprobojno izgleda a štos je tako prost i tako
genijalan da nemam reči. Koga zanima... Pitalice, januar 1993 :)
Što se tiče gubitka, pre par godina sam u "Galaksiji" objavio jedan
program koji šifruje baš opisanim algoritmom i uz njega sam dao JEDAN
malo duži kriptogram. Dakle, ništa 100 kriptograma šifrovanih istom
šifrom. Ponudio sam 10,000 dinara (ili je možda bilo 1,000, 100,000
ili tako nešto, ko će se razabrati sa tim parama, tek nije bila neka
silna lova) prvome ko reši... rešilo njih 7 ;)
Metod da se razbije takva šifra je za nijansu složeniji (mada je na
sličnu foru) pa me mrzi da ga sad opisujem, možda nekom drugom
prilikom.
Uzgred, kad bih ja hteo da nešto šifrujem a ne bi imao neki stvarno
neprobojan alat kao što je RSA (to dal' je stvarno neprobojan ne
znam(o), ali u našim uslovima garant jeste ;), ja se nikako ne bih
opredelio za neki od polialfabetskih metoda poput opisanog jer isti,
ma koliko da zvuče zaguljeno, jako lako padaju i jer se pri rešavanju
može sjajno primeniti računar. Obavezno bih uzeo neku metodu zamenjivanja
poligrama, makar najobičniju Plejferovu šifru, ili ako me ne bi mrzelo
da se više bakćem sa šifrovanjem onda Delastelovu trifidnu šifru, a onda
bih je nečim sasvim jednostavnim nadšifrovao. Tako bih dobio šifru
koja se, nema sumnje, može probiti i to na način koji je više ili
manje poznat, ali bih bio siguran da "napadač" ima da se naradi k'o
crnac da to probije, da mu trebaju silni ljudski resursi (kod probijanja
tako nadšifrovanih poligramskih šifri računar mu je lepa alatka, ali da
vidi vajdu od njegove brzine... slabo) i dosta vremena. Pa ako baš voli...
algoritmi.12dusanp,
-> #11, dejanr=> Nisi u pravu.
Majkumubožjuimperijalističku! Baš mi se sistem činio
elegantnim :(
algoritmi.13janko,
-> #11, dejanr> Metod da se razbije takva šifra je za nijansu složeniji
> (mada je na sličnu foru) pa me mrzi da ga sad opisujem,
> možda nekom drugom prilikom.
Mene zanima...
algoritmi.14vili,
U knjizi: "C: The Complete Reference", na strani 474 se nalazi
algoritam za Quick sort. Taj algoritam kod mene ne radi, tj. za
vrlo mali broj slucajeva radi, a za ostale daje cudne rezultate.
Da l' je u pitanju greska u knjizi ili sta?
Vili
void quick(item,left,right)
char *item;
int left,right;
{
register int i,j;
char x,y;
i=left;
j=right;
x=item[(left+right)/2];
do {
while (item[i]<x && j<right) i++;
while (x<item[j] && j>left) j--;
if (i<=j){
y=item[i];
item[i]=item[j];
item[j]=y;
i++;
j--;
}
} while (i<=j);
if (left < j ) quick(item,left ,j);
if (i < right) quick(item,i,right);
}
#include <stdio.h>
main(){
char s[80];
printf("enter a string:");
gets(s);
quick(s,0,strlen(s)-1);
printf("the sorted string is: %s\n",s);
}
algoritmi.15prvul,
-> #14, viliŮ while (item[i]<x && j<right) i++;
Ů while (x<item[j] && j>left) j--;
Ů▄▄
Mislim da u prvom od ovih redova treba (item[i]<x && i<right)
Ovako se na početku promenljiva i nikada ne pomeri nagore, pa
se sortiranje ubrlja.
algoritmi.16isekulovic,
Da li postoji neki opštepoznati algoritam (da se ne mučim da otkrivam
Ameriku, pa da je još ne otkrijem :) za najkraći put između dve tačke
koje su povezane mrežom različitih puteva. Npr. najkraći put od Zelenog
Venca do Krsta ali da ne idem kroz zgrade ili preko Banovog Brda. Kapirate
šta pitam? Meni je palo napamet za sada jedino prava linija između te dve
tačke pa pratiti puteve koji idu najbliže toj pravoj.
algoritmi.17jtitov,
-> #16, isekulovic> Da li postoji neki opstepoznati algoritam (da se ne mucim
> da otkrivam
Uh, malo mi pitanje nije jasno. Inace Operaciona istrazivanja (pitaj
FON-ovce o tom predmetu) resavaju taj problem 'najkraceg puta'. Naravno i
programska podrska postoji.
algoritmi.18kenza,
-> #16, isekulovic [;> Da li postoji neki opstepoznati algoritam (da se ne mucim da otkrivam
[;> Ameriku, pa da je jos ne otkrijem :) za najkraci put izmedu dve tacke
[;> koje su povezane mrezom razlicitih puteva. Npr. najkraci put od Zelenog
Mislim da se zove Dijkstra,potrazi pod tim imenom ;)
algoritmi.19zolika,
Elem, kada se već priča o algoritmima: zna li neko neki dobar algo-
ritam (i po mogućnosti jednostavan, tj. neki kongruencioni fazon) kojim bi se
dobijali pseudoslučajni brojevi od 0 do N, gde to N može da bude proizvoljno
veliko? Drugim rečima, da li se može napraviti (tj. da li već postoji) način
generisanja pseudoslučajnih brojeva, ali CELIH pseudoslučajnih brojeva proiz-
voljne tačnosti?
Reći će neko: "Imaš algoritam objavljen u 'Galaksiji' broj 186 ili
tu negde, prepiši ga i rešio si stvar". Da, ali taj algoritam daje slučajne
brojeve između 0 i 1, a ja od svega imam samo CELOBROJNU aritmetiku više-
struke preciznosti, tj. ne mogu da množim MALI realan broj VELIKIM (više
od 100 cifara) celim brojem i da tu onda 'kao nešto dobijem'.
Reći će neko drugi: "Imaš algoritam u DejanRovom fajlu IZAZOV.TXT,
pa analiziraj njega". Jeste, analizirao sam i to, ali kako god da ga prila-
godim, brojevi koje dobijam nisu mi dovoljno pseudoslučajni.
Reći će neko treći: "Šta si toliko zapeo za tu aritmetiku višestruke
preciznosti i slučajne brojeve?" Pa, programiram Miler-Rabinov test za
prostotu brojeva, a tu se radi I sa velikim I sa slučajnim brojevima. Taj
program mi dođe za seminarski...
žekajući pomoć,
Zolika
algoritmi.20spantic,
-> #19, zolika> Elem, kada se već priča o algoritmima: zna li neko neki
> dobar algo- ritam (i po mogućnosti jednostavan, tj. neki
> kongruencioni fazon) kojim bi se
Najlakše bi bilo da ti dostavim Knutovu rvu knjigu iz serije "The Art Of
Computer Programming" ili bar skripte sa PJMPa 2 na ETF Beograd. Ako niko
ne bude dobar uradićemo tako :)
Ali evo za prvu pomoć, ovo je za praktičnu primenu. Ako ti treba teorija
javljaj da šaljem literaturu.
Mašinski zavistan ( linearno kongrulentni ) generator:
N(i+1) = ( a * N(i) + c ) mod M, 0 <= N(i) < M
M je sekvenca maksimalne dužine.
Za binarnu mašinu je M = 2**B
pa za B = 16 ( šesnaestobitni ) imamo:
a = 31413
c = 13849
B = 32
a = 314159269
c = 907633409
gde su i A i B dobijeni Knutovim postupkom.
algoritmi.21dejanr,
-> #19, zolika>> Elem, kada se već priča o algoritmima: zna li neko neki dobar algo-
>> ritam (i po mogućnosti jednostavan, tj. neki kongruencioni fazon)
>> kojim bi se dobijali pseudoslučajni brojevi od 0 do N, gde to N
>> može da bude proizvoljno veliko? Drugim rečima, da li se može
>> napraviti (tj. da li već postoji) način generisanja pseudoslučajnih
>> brojeva, ali CELIH pseudoslučajnih brojeva proizvoljne tačnosti?
Problem teorijske prirode je to "proizvoljno veliko". Naime, prilikom
projektovanja kongruencionog generatora slučajnih brojeva koristi se
formula Xn+1=(A*Xn+B) mod N pri čemu najpre treba usvojiti N (najčešće
prema dužini mašinske reči) a onda "računati" A i B. Potom, kada se te
vrednosti usvoje, čitav generator treba testirati nizom testova, pa
prihvatiti ili odbaciti. Dakle, ako se naknadno ukaže potreba za
brojevima *većim* od N, moraš početi sve iz početka.
Kao što vidiš, kongruencioni metod generiše cele brojeve, racionalni
brojevi iz intervala (0,1) dobijaju se kada izračunaš Y=X/N. Tek ti
tu treba floating point.
>> Reći će neko drugi: "Imaš algoritam u DejanRovom fajlu IZAZOV.TXT,
>> pa analiziraj njega". Jeste, analizirao sam i to, ali kako god da
>> ga prilagodim, brojevi koje dobijam nisu mi dovoljno pseudoslučajni.
Taj algoritam sam "pokupio" na predavanjima prof. Joze Dujmovića iz
"Metoda programiranja" (ETF, nekad bilo na petoj godini, sada je
mislim pomereno na neku raniju). Obzirom da se prof. Dujmović godinama
bavi simulacijama a, u okviru njih, i generatorima slučajnih brojeva,
i obzirom da je u okviru istog tog kursa veoma detaljno predavao o
tome kako se neki kongruencioni generator testira, sklon sam da mu
poverujem kada kaže da je taj generator detaljno testirao i da su
mu karakteristike optimalne. Naravno, ako su "lagali" mene onda i
ja "lažem" vas, lično ga nisam testirao.
Jedina stvar koju sam primetio a koju prof. Dujmović nije pomenuo
(ili sam ja taj čas prespavao ;) jeste da se, ako ti ne treba broj
između 1 i N nego recimo između 1 i M pri čemu je M<N, uzimanjem
tih par potrebnih bitova sa *kraja* broja dobija veoma ne-slučajna
sekvenca - brojevi se, ako ništa drugo, smenjuju paran-neparan-paran
-neparan što ne liči mnogo na slučajnost (da nisi ti tako radio?).
Prelistao sam Knutha i tamo je zbilja pomenut takav problem, i
izričito se kaže da te potrebne bitove treba uzimati sa *početka*
(leve strane) psuedoslučajnog broja. Tako je i urađeno u IZAZOV.TXT.
>> Pa, programiram Miler-Rabinov test za prostotu brojeva, a tu se
>> radi I sa velikim I sa slučajnim brojevima. Taj program mi dođe
>> za seminarski...
Obzirom da je to verovatno ozbiljnije od nekog igranja sa programima,
bojim se da ti nema druge nego da prelistaš literaturu. A mesto od
koga možeš lepo da počneš je D.E.Knuth, "The Art of Computer Programming",
druga knjiga. Veliki prostor je posvećen generatorima slučajnih brojeva,
tekst je na prvi pogled malo "težak" ali se u stvari sasvim lepo može
čitati (kada naučiš da mnogo komplikovane delove preskočiš ;). Svakako
je i kasnije bilo mnogo radova na ovu temu, ali verujem da je bilo koji
od njih teško mogao da prođe bez referenciranja Knutha kao nekakve
osnove. Uzgred, kongruencioni generatori nisu jedini na svetu, možda
ćeš se odlučiti da probaš sa nekim drugim metodom.
Kada smo već kod ove tematike, da pomenem i ja dva problema koji me
zanimaju, premda ne verujem da će neko biti raspoložen da ih reši ;)
1. Recimo da imamo kongruencioni generator pseudoslučajnih brojeva
Xn+1=(AXn+B) mod N i da nam je N poznato a A, B i X0 nisu. Ali,
dato nam je "nekoliko" slučajnih brojeva iz tog niza, naravno
ne u punoj dužini nego svedeni na neki interval, recimo ako je
N=2^32 data su nam po dva najviša bita svakog od prvih 200 elemenata
niza. Na osnovu toga treba odrediti A, B i X0. Zanimljivo je da
Knuth pominje ovaj problem u okviru zadataka za rešavanje na kraju
poglavlja uz "koeficijent složenosti" koji odgovara semestralnom
radu (eto ideje! :) No, kada okrenete rešenje ;) tamo piše "to se
može uraditi relativno lako, 150 brojeva je dosta za "razbijanje"
32-bitnog generatora, pogledajte moj rad "taj i taj" koji će
uskoro biti objavljen". Slično sam i ja prošao kada sam isto pitanje
postavio ovde, neko od matematičara kaže "može to da se uradi" ali
ne reče KAKO :)
2. Projektovati generator (teško da će biti kongruencioni) koji generiše
uniformno raspoređeni pseudoslučajan broj iz intervala [0,+beskonačno).
Neka radi koliko treba (ako je nužno i milion godina, dakle pitanje
je teorijsko a ne praktično), i neka mi generiše takav broj. Da li
je to uopšte moguće?
algoritmi.22bradenkovic,
-> #20, spantic>Masinski zavistan ( linearno kongrulentni ) generator:
> N(i+1) = ( a * N(i) + c ) mod M, 0 <= N(i) < M
> M je sekvenca maksimalne duzine.
> Za binarnu masinu je M = 2**B
> pa za B = 16 ( sesnaestobitni ) imamo:
> a = 31413
> c = 13849
> B = 32
> a = 314159269
> c = 907633409
> gde su i A i B dobijeni Knutovim postupkom.
Ima malih ispravki, najpre u nazivu. Navedeni generator se zove mesani
kongruentni.
Najverovatnije da ce siri auditorijum interesovati da procita malo vise
detalja o generatorima pseudoslucajnih brojeva, pa pre nego sto napisem
nesto o najsire koriscenom multiplikativnom linearnom kongruentnom
generatoru, nije lose da najpre definisemo osnovne pojmove o
kongruentnim brojevima:
Brojevi Z(i-1) i Z(i) su kongruentni po modulu m ako je njihova
razlika deljiva sa m bez ostatka, sto se zapisuje sa: Z(i)=Z(i-1) mod m ;
Prema tome multiplikativni kongruentni generator je definisan izrazom:
Z(i)=(a*Z(i-1)) mod M
gde je: a - multiplikator i odredjuje se po obrascu 8j+-3 (j=1,2,3,4...)
Z(0)=1,3,5,7.... - seme generatora (seed);
Maksimalna moguca duzina niza bez ponavljanja je: Nmax = m - 1;
Zato se kod binarnih masina uzima m=2^(b-1)
gde je: b - duzina masinske reci u bitovima (najvisi bit predstavlja znak)
Pri takvim uslovima u zavisnosti od izabranog multiplikatora dobija
se najduza sekvenca bez ponavljanja u intervalu m/4 <= Nmax <=m-1
Duzina niza i kvalitet generatora zavise iskljucivo od duzine masinske
reci i multiplikatora. S obzirom da je duzina masinske reci obicno
fiksirana na 4 bajta, kvalitet generatora iskljucivo zavisi od izabranog
multiplikatora. I dan danas se pojavljuju radovi gde autori tvrde da su
pronasli multiplikator koji obezbedjuje bolju statistiku od poznatih u
literaturi. Navedene reference (Knut) su odavno popljuvane (jos dok sam
ja bio djak) i navedene kao primer dokle moze da nas dovede (ne ova
visoka hiperinflacija) nego siroka primena nepouzdanih generatora.
Takodje je popljuvan i IBM-ov generator iz SSP-a i to jos crnje i gore.
Na osnovu prakse od nekoliko godina ratovanja sa generatorima slucajnih
brojeva, mogu da kao najednostavnije ali sigurno resenje preporucim
portabilni generator sa uniformnom raspodelom (poznat kao UNIRAN) koji
se pojavio 1980 godine. Ako ima zainteresovanih mogu da obezbedim kopiju
rada iz casopisa Simulation.
Inace kod kongruentnih generatora najveci problem je kako realizovati
modulo deljenje sa sto manje masinskih operacija. Jos pedesetih godina
bistri programeri su se dosetili kako da iskoriste neprijavljivanje
greske za integer overflow i naprave vrlo jednostavan emulator za modulo
delenje.
Napomena: rezultat modulo delenja je ostatak od celobrojnog delenja dva broja
Program SlucajanBroj;
Var Z,m : longint;
Procedure Uniform(var Randu: longint);
Begin
Randu := Randu * m; If Randu < 0 then Randu:= Randu + m + 1;
End;
Begin
Z := 1; m := 1220703125;
Uniform(Z); Writeln(Z)
end.
Ukoliko je prilikom mnozenja Randu * m rezultat pozitivan, tada se taj
pozitivan broj uzima kao ostatak celobrojnog delenja sa m, u suprotnom
je doslo do prekoracenja pa je bit znaka setovan. Rezultat modulo
delenja je sada zbog setovanog bita znaka negativan. Da bi ga
konvertovali u pozitivan, u skladu sa zapisom celog broja u obliku
dvostrukog komplementa, dobijenom negativnom broju dodajemo m + 1.
Kao sto vidite vrlo kvalitetan generator slucajnih brojeva moze se
napisati iz dve naredbe koje staju u jedan programski red. To nije
nikakva nauka. Najveca nauka je kako odabrati multiplikator.
Takodje se zbog razlicitog nacina predstavljanja celih i realnih brojeva
u racunaru kao problem javlja i nacin preslikavanja slucajnog broja iz
celobrojnog domena (integer) u domen racionalnih brojeva (real) tako da
se gustina iz jednog domena ekvivalentno preslika na drugi bez
nagomilavanja na granicama ili unutar intervala za koji generisemo
slucajan broj npr: [0,1).
Pozdrav Boza.
algoritmi.23bradenkovic,
-> #22, bradenkovicDaklem dosao sam do zakljucka da ne valja u sitne sate pisati duge poruke.
Mogu mangupi posle da zajebavaju. Evo svecano se obavezujem da vise necu.
U poruci 1.22 ima jedna greska. Zaboravio sam da metnem multiplikator.
To sam primetio tek kad sam procitao poruku. Ovde je ispravljen pseudo kod.
Program SlucajanBroj;
Var a,Z,m : longint;
Procedure Uniform(var Randu: longint);
Begin
Randu := Randu * a; If Randu < 0 then Randu:= Randu + m + 1;
End;
Begin
Z := 1; a := 1220703125; m:= 2147483647;
Uniform(Z); Writeln(Z)
end.
algoritmi.24janko,
-> #22, bradenkovic> Duzina niza i kvalitet generatora zavise iskljucivo od
> duzine masinske reci i multiplikatora. S obzirom da je
> duzina masinske reci obicno fiksirana na 4 bajta, kvalitet
> generatora iskljucivo zavisi od izabranog multiplikatora.
> I dan danas se pojavljuju radovi gde autori tvrde da su
> pronasli multiplikator koji obezbedjuje bolju statistiku
> od poznatih u literaturi. Navedene reference (Knut) su
> odavno popljuvane (jos dok sam ja bio djak) i navedene kao
> primer dokle moze da nas dovede (ne ova visoka
> hiperinflacija) nego siroka primena nepouzdanih
> generatora.
Ti si takođe bacio ljudima prašinu u oči. Prvo, pošto je čisto
multiplikativan, tvoj generator se jako lepo ZAKUCA u nulu, u
prvom pogodnom trenutku. ;)
Drugo, to što je neko pronašao neku zgodnu konstantu za 32 bita
ne znači da Knut nije bio u pravu. žovek je dao razne metode i
načine KAKO napraviti generator. Nije rekao: 'moja konstanta za
32 bita je najbolja.' On je matematičar. :)
Treće, ono što Zoliki treba je upravo NAžIN kako da napravi
generator koji će da radi sa znatno VIŠE od 32 bita!
Ja (napamet, možda ima i nešto bolje) Zoliki preporučujem neki
aditivni generator slučajnih brojeva, za koje mu ne treba
određivanje egzotičnih konstanti, i, usto, ne zavise od broja
bita broja -- lako će napraviti neki za broj bita koji njemu
treba.
Referenca: Knut, druga knjiga The Art...
algoritmi.25janko,
-> #21, dejanr
> Taj algoritam sam "pokupio" na predavanjima prof. Joze
> Dujmovića iz "Metoda programiranja" (ETF, nekad bilo na
> petoj godini, sada je
> Jedina stvar koju sam primetio a koju prof. Dujmović nije
> pomenuo (ili sam ja taj čas prespavao ;) jeste da se, ako
> ti ne treba broj između 1 i N nego recimo između 1 i M pri
> čemu je M<N, uzimanjem tih par potrebnih bitova sa *kraja*
> broja dobija veoma ne-slučajna sekvenca - brojevi se, ako
> ništa drugo, smenjuju paran-neparan-paran -neparan što ne
> liči mnogo na slučajnost (da nisi ti tako radio?).
Osim što to lepo pominje Knut u knjizi, kod nas je to pominjao
i Laslo na vežbama, a Laslo to zna odavno, jer je to ilustrovao
pomoću printauta koje je napravio još na PDP-11. Verovatno
nisi išao na vežbe, već samo na predavanja. ;))
> 2. Projektovati generator (teško da će biti kongruencioni)
> koji generiše uniformno raspoređeni pseudoslučajan broj iz
> intervala Š0,+beskonačno). Neka radi koliko treba (ako je
> nužno i milion godina, dakle pitanje je teorijsko a ne
> praktično), i neka mi generiše takav broj. Da li je to
> uopšte moguće?
Odgovoriću ti rečenicom iz tvoje poruke ;)
> Problem teorijske prirode je to "proizvoljno veliko".
Hoću da kažem, +beskonačno se može predstaviti na računaru, ali
se opseg 0.. +beskonačno NE MOčE raspodeliti uniformno na
računaru, sve dok nemamo beskonačno veliku mantisu i beskonačno
veliki eksponent na raspolaganju. Problem si zadao kao da nisi
familijaran sa računarskom reprezentacijom brojeva ili nikada
nisi slušao numeričku analizu. :(
algoritmi.26zkehler,
-> #20, spanticŔ> Elem, kada se već priča o algoritmima: zna li neko neki
Ŕ> dobar algo- ritam (i po mogućnosti jednostavan, tj. neki
Ŕ> kongruencioni fazon) kojim bi se
Ŕ
Ŕ Najlakše bi bilo da ti dostavim Knutovu rvu knjigu iz serije
Ŕ "The Art Of Computer Programming" ili bar skripte sa PJMPa 2 na
Ŕ ETF Beograd. Ako niko ne bude dobar uradićemo tako :)
čiveo J. Dujmović, koji je imao i dobrih strana :) spanticu, zar ne
stoji još uvek na ETF-u u Oglasima fajl sa nekoliko generatora slučajnih
brojeva?
Zolika, imam "The Art of..." od Knutha i "The Art of Numerical
Computing" od tri autora. Možeš da kopiraš, ako želiš.
ZK
algoritmi.27bradenkovic,
-> #24, janko> Ti si takode bacio ljudima prasinu u oci. Prvo, posto je cisto
> multiplikativan, tvoj generator se jako lepo ZAKUCA u nulu, u
> prvom pogodnom trenutku. ;)
Polako mladi gospodine,
nije bas tako kako ti se cini. Da si malo ozbiljnije pogledao formule
>>Z(i)=(a*Z(i-1)) mod M
>>gde je: a - multiplikator i odredjuje se po obrascu 8j+-3 (j=1,2,3,4...)
>> Z(0)=1,3,5,7.... - seme generatora (seed);
>>
>>Maksimalna moguca duzina niza bez ponavljanja je: Nmax = m - 1;
>>Zato se kod binarnih masina uzima m=2^(b-1)
>>gde je: b - duzina masinske reci u bitovima (najvisi bit predstavlja znak)
Video bi da su seme (i dobijena sekvenca slucajnih brojeva) pozitivni
neparni brojevi. Multiplikator je takodje pozitivan neparan broj. Da bi
se generator "zakucao" potrebno je da je rezultat celobrojnog delenja
modula sa multiplikatorom pozitivan neparan broj. Pogodnim izborom
multiplikatora (8j+-3) j=1,2,3,4.. obezbedjuje se da se takav slucaj
nikada ne desi.
Prema tome, nema nikakvog bacanja prasine u oci. Sve funkcionise
besprekorno.
>Drugo, to sto je neko pronasao neku zgodnu konstantu za 32 bita
>ne znaci da Knut nije bio u pravu. Covek je dao razne metode i
>nacine KAKO napraviti generator. Nije rekao: 'moja konstanta za
>32 bita je najbolja.' On je matematicar. :)
Coveku niko ne spori da je lepo sto je dao pregled nacina kako napraviti
generator, cak stavise to je sa obrazovne strane vrlo korisno. Medjutim
kad neko proba da u profesionalne svrhe (recimo simulacija sistema sa
vise mesta opsluzivanja sa duzim redovima cekanja) koristi takav
generator, tada njegove statisticke nesavrsenosti obicno dovode do toga
da se redovi cekanja znatno produze. S vremena na vreme se na
simpozijumima i casopisima pojavi neko ko neoprezno kao referencu za
multiplikator navodi Knut-a. Onda ga drustvo sa zadovoljstvom slozno
popljuje. Ja sam eto sa svoje strane hteo da ukazem na tu pojavu.
> Trece, ono sto Zoliki treba je upravo NACIN kako da napravi
> generator koji ce da radi sa znatno VISE od 32 bita!
Da bi napravio generator sa vise od 32 bita potrebno je da zna kako
funkcionise generator sa 32 bita. Ako je mangup, ona dva reda programa
ce prosirii sa jos dva reda i par promenljivih i napraviti generator od
64 bita. Pretpostavljam da je Zoliki za njegov rad generator sa 4 bajta
dovoljan. Pri generisanju slucajnog broja glavni problem je postizanje
odgovarajuce rezolucija generatora kao i odgovarajuci statisticki
kvalitet. U svakom slucaju da bi Zoliki pomogli, on mora da kaze u kojim
granicama hoce slucajan broj, sa kojom rezolucijom i kakvim statistickim
kvalitetom. E onda cemo da prekopamo ormane da vidimo sta su drugi
radili da ne izmisljamo toplu vodu.
>Ja (napamet, mozda ima i nesto bolje) Zoliki preporucujem neki
>aditivni generator slucajnih brojeva, za koje mu ne treba
>odredivanje egzoticnih konstanti, i, usto ne zavise od broja
>bita broja -- lako ce napraviti neki za broj bita koji njemu
>treba.
U strucnim krugovima na osnovu teorijskih i empirijskih istrazivanja
vlada misljenje da aditivni generatori imaju vrlo lose statisticke
performanse. Zato se jos jedino koriste u obrazovanju da deca vide da i
tako moze. A odredjivanje parametara za aditivni generator je vece
bajanje nego kod multiplikativnog generatora ali sa neizvesnijim
posledicama po statisticki kvalitet. E sad ako Zoliki treba neki
generator da bi testom dokazao da nije bas najbolji, onda je aditivni
generator za njega bas po meri.
Pozdrav
Boza.
algoritmi.28dejanr,
-> #25, janko>> Hoću da kažem, +beskonačno se može predstaviti na računaru, ali
>> se opseg 0.. +beskonačno NE MOčE raspodeliti uniformno na
>> računaru, sve dok nemamo beskonačno veliku mantisu i beskonačno
>> veliki eksponent na raspolaganju. Problem si zadao kao da nisi
>> familijaran sa računarskom reprezentacijom brojeva ili nikada
>> nisi slušao numeričku analizu. :(
Zašto ne bi mogao? Naime, slučajan broj iz intervala [0,+beskonačno)
je konačan broj, može da ima 10^10^10^10 itd cifara, ali je i dalje
konačan broj. Dakle, može se predstaviti u okviru memorije koja
je dovoljno velika. Najzad, nek se štampa na papiru, cifru po cifru.
Evo jednog programa koji generiše pseudoslučajan broj iz intervala
[0,+beskonačno). Samo je mali problem što raspodela nije uniformna,
ali broj svejedno može da ispadne proizvoljno veliki:
repeat
print rnd(10);
until rnd(1000)<>1
Nema to veze sa računarskom reprezentacijom brojeva, to je pitanje
imaginacije :)
algoritmi.29dejanr,
-> #26, zkehler>> zar ne stoji još uvek na ETF-u u Oglasima fajl sa
>> nekoliko generatora slučajnih brojeva?
Ne da ne stoji nekoliko generatora slučajnih brojeva,
nego ne stoje ni sami OGLASI ;) Ukinuto "zbog zloupotreba".
algoritmi.30zolika,
-> #24, janko>> Treće, ono što Zoliki treba je upravo NAžIN kako da napravi
>> generator koji će da radi sa znatno VIŠE od 32 bita!
Tačno, Janko, TO je ono što mi ne da mira... :-)))))
>> Ja (napamet, možda ima i nešto bolje) Zoliki preporučujem neki
>> aditivni generator slučajnih brojeva, za koje mu ne treba
>> određivanje egzotičnih konstanti, i, usto, ne zavise od broja
>> bita broja -- lako će napraviti neki za broj bita koji njemu
>> treba.
>> Referenca: Knut, druga knjiga The Art...
Kod nas na faksu nabaviše SAMO treću knjigu, gledali smo bibliotekarka
i ja zajedno sve signature...
algoritmi.31zolika,
-> #21, dejanr>> Kao što vidiš, kongruencioni metod generiše cele brojeve, racionalni
>> brojevi iz intervala (0,1) dobijaju se kada izračunaš Y=X/N. Tek ti
>> tu treba floating point.
Odustajem, jer nemam floating-point aritmetiku (a i ne treba mi).
>> sekvenca - brojevi se, ako ništa drugo, smenjuju paran-neparan-paran
>>- neparan što ne liči mnogo na slučajnost (da nisi ti tako radio?).
Nisam tako radio, nešto sam muvao sa onim tvojim generatorom, ali
bez ozbiljnijih rezultata... :-(((
>> Obzirom da je to verovatno ozbiljnije od nekog igranja sa programima,
>> bojim se da ti nema druge nego da prelistaš literaturu. A mesto od
>> koga možeš lepo da počneš je D.E.Knuth, "The Art of Computer
>> Programming", druga knjiga. Veliki prostor je posvećen generatorima
>> slučajnih brojeva,
OK, OK, ubedili ste me svi: počeću od Knuth-a i njegove "Umetnosti...",
drugi tom. Je l' TAKO TREBA???? :-))))
algoritmi.32robert,
-> #26, zkehler<:> stoji još uvek na ETF-u u Oglasima fajl sa nekoliko generatora
Oglasna tabla je već poooduže ukinuta!
algoritmi.33spantic,
-> #26, zkehler> čiveo J. Dujmović, koji je imao i dobrih strana :)
> spanticu, zar ne stoji još uvek na ETF-u u Oglasima fajl
> sa nekoliko generatora slučajnih brojeva?
Kao što Dejan lepo reče nema OGLASa. A pošto ne želim da i mene ukinu
nema ni tih listinga pošto je Joza to zabranio :)
Zbilju na stranu, veoma bih voleo da se dokopam tih listinga. Ili još
bolje ako neko ima generator pseudoslučajnih brojeva na ADA :) Nije
problem ali ako je neko već bio dobar :) Simuliram vreme odziva
telefonske centrale sa njim. Mislim da kao granice ipak neću staviti
vreme odziva NAŠIH centrala ;)
algoritmi.34spantic,
-> #22, bradenkovic> literaturi. Navedene reference (Knut) su odavno popljuvane
Pa ni sam Knut nigde ne tvrdi da su sjajni. Reč je o teoriji algoritama
pseudoslučajnih brojeva. E sad, ako neko pogreši pa se prevari... :) Ali
koliko sam razumeo Zoliku on je tražio nešto ovako, a pošto sam žurio,
dao sam osnovu bez teorije, mada sam verovatno trebao i više :)
algoritmi.35janko,
-> #27, bradenkovic> nije bas tako kako ti se cini. Da si malo ozbiljnije
> pogledao formule
>>> Z(i)=(a*Z(i-1)) mod M
>>> gde je: a - multiplikator i odredjuje se po obrascu
>>> 8j+-3 (j=1,2,3,4...) Z(0)=1,3,5,7.... - seme
>>> generatora (seed);
> Video bi da su seme (i dobijena sekvenca slucajnih
> brojeva) pozitivni neparni brojevi. Multiplikator je
> takodje pozitivan neparan broj. Da bi se generator
> "zakucao" potrebno je da je rezultat celobrojnog delenja
> modula sa multiplikatorom pozitivan neparan broj. Pogodnim
> izborom multiplikatora (8j+-3) j=1,2,3,4.. obezbedjuje se
> da se takav slucaj nikada ne desi.
>
> Prema tome, nema nikakvog bacanja prasine u oci. Sve
> funkcionise besprekorno.
Hvala na objašnjenju. Izvinjavam se na iskazanim sumnjama, ali
drugačije ne bih saznao ove detalje, jer ih nisi napisao u
svojoj prvoj poruci. Imam još pitanja:
DA LI SVAKI MULTIPLIKATOR oblika 8j+-3 ima dobre osobine?
Ako ne, kojim postupkom odrediti neki drugi multiplikator, osim
onog koji si ti dao? (Ovo pitam jer si istakao da su oni Knutovi
postupci pogrešni, a postupak nam je ipak bitniji od jedne
konstante. A ako znamo postupak, lako ćemo i Zoliki isporučiti
jedan primerak dobrog generatora.)
I, da, koje su glavne slabosti mešovitih LK generatora
dobijenih Knutovim postupkom (konkretno, onakvog kakvog je
prikazao spantic) u odnosu na generator koji si nam prikazao?
algoritmi.36janko,
-> #28, dejanr> 2. Projektovati generator (teško da će biti kongruencioni)
> koji generiše uniformno raspoređeni pseudoslučajan broj iz
> intervala Š0,+beskonačno). Neka radi koliko treba (ako je
> nužno i milion godina, dakle pitanje je teorijsko a ne
> praktično), i neka mi generiše takav broj. Da li je to
> uopšte moguće?
>>> Hoću da kažem, +beskonačno se može predstaviti na
>>> računaru, ali se opseg 0.. +beskonačno NE MOčE
>>> raspodeliti uniformno na računaru, sve dok nemamo
>>> beskonačno veliku mantisu i beskonačno veliki eksponent
>>> na raspolaganju. Problem si zadao kao da nisi
> Zašto ne bi mogao? Naime, slučajan broj iz intervala
> Š0,+beskonačno) je konačan broj, može da ima 10ž10ž10ž10
> itd cifara, ali je i dalje konačan broj. Dakle, može se
> predstaviti u okviru memorije koja je dovoljno velika.
> Najzad, nek se štampa na papiru, cifru po cifru.
>
> Evo jednog programa koji generiše pseudoslučajan broj iz
> intervala Š0,+beskonačno). Samo je mali problem što
> raspodela nije uniformna, ali broj svejedno može da
> ispadne proizvoljno veliki:
>
> repeat
> print rnd(10);
> until rnd(1000)<>1
>
> Nema to veze sa računarskom reprezentacijom brojeva, to je
> pitanje imaginacije :)
žekao sam nekog matematičara da se javi, ali, izgleda da ću
morati sam da pišem o stvarima koje mi nisu uža specijalnost (i
rizikujem da ne budem u pravu).
Malo sam razmišljao o tvojoj i svojoj poruci. Prvo, moj zahtev
za beskonačnom mantisom NE stoji. Mantisa sasvim mirno može
biti i VRLO konačna. S druge strane, imam utisak da je
beskonačni eksponent neophodan. (I to ne u tom smislu da se
ne može ispisati. Neka i pretpostvimo da imamo printer sa
beskonačnim papirom. Nije u tome problem.)
Pogledaj opet svoj program:
> repeat
> print rnd(10);
> until rnd(1000)<>1
Svaki nama poznati generator RND ima svoju periodu. Posle te
periode se brojevi ponavljaju. U gornjem primeru, maksimalna
veličina broja je određena periodom generatora. Tako da ti
NIKAD ne dobijaš brojeve iz (.0..+oo .) već iz daleko užeg
(daleko užeg od beskonačnosti ;) opsega (koji zavisi od
generatora koga koristiš).
(Da napomenem onima koji nisu razumeli: Dejan ovde koristi
rnd(n) kao oznaku generatora koji daje cele slučajne brojeve u
opsegu 0..n-1)
Sad zamisli da si, umesto da generišeš samo cifre broja, ovakav
postupak primenio na eksponent (za koji smo zaključili da je
bitniji). Opet, i tako ćeš dobijati brojeve iz daleko užeg
opsega od onog beskonačnog. (Beskonačnost je tako velika ;)
Kako bi tvoj program davao dobre rezultate? Ovako:
> repeat
> print rnd(10);
> until rnd(+oo)<>1
I šta sad? Da bismo dobili generator koji daje brojeve iz
opsega 0..+oo moramo da imamo generator koji daje brojeve iz
opsega 0..+oo. ;)
algoritmi.37zolika,
-> #27, bradenkovic Vidim da se Zolika intenzivno pominje u vašim porukama (toliko me nisu
pominjali ni kada sam prodavao XT računar :-)) ), pa da obrazložim:
>> Trece, ono sto Zoliki treba je upravo NACIN kako da napravi
>> generator koji ce da radi sa znatno VISE od 32 bita!
Tačno, interesuje me KAKO da napravim (ili da iskoristim neki od
postojećih) generator slučajnih brojeva koji će davati slučajne prirodne
brojeve od 0 do N, gde to N može biti proizvoljno veliko. Ajd' da ne kaže-
te "A koliko je to veliko VELIKO?", neka bude na pr. 2^1000.
>> 64 bita. Pretpostavljam da je Zoliki za njegov rad generator sa 4 bajta
>> dovoljan.
Ne, Zoliki nije dovoljan generator sa 4 bajta. Treba mu neki generator
koji će davati brojeve čija reprezentacija ima više bajtova od 4.
>> U svakom slucaju da bi Zoliki pomogli, on mora da kaze u kojim
>> granicama hoce slucajan broj, sa kojom rezolucijom i kakvim statistickim
>> kvalitetom. E onda cemo da prekopamo ormane da vidimo sta su drugi
>> radili da ne izmisljamo toplu vodu.
Zolika je rekao granice generatora, i hteo bi da su brojevi što
ravnomernije raspoređeni u tom intervalu. Beše li to uniformna raspodela
(još nisam polagao Verovatnoću i statistiku, pa mi nemojte zameriti).
>> posledicama po statisticki kvalitet. E sad ako Zoliki treba neki
>> generator da bi testom dokazao da nije bas najbolji, onda je aditivni
>> generator za njega bas po meri.
Zolika uopšte neće da se upušta u ocenjivanje generatora slučajnih broje-
va i njihovih karakteristika. Njemu generator treba samo kao SREDSTVO, tj.
ALAT za problem koji treba da reši. Naime, kao što je poznato, za Miler-
Rabinov test prostote nekog broja treba izabrati SLUžAJAN broj u intervalu
od 0 do N-1, gde je N uneti broj.
Dakle, bilo bi dobro kada bi neko predložio takav generator slučajnih
brojeva koji bi se "automatski" (koliko je to moguće) prilagođavao intervalu
brojeva, koji je poznat kada korisnik unese broj N čiju prostotu treba pro-
veriti. Zolika će (bar koliko ga poznajem) isprogramirati takav generator,
ako sazna postoji li fazon da se generator prilagodi gornjoj granici. To zna-
či da N može da bude 13, 98457694856749501, 84787, 2674537, sve zavisi od
toga šta korisnik unese.
Nadam se da je Zolika bio dovoljno jasan. Ako nije, slobodno pitajte,
objasniće koliko to bude bilo u njegovoj moći.
algoritmi.38bradenkovic,
-> #35, janko> DA LI SVAKI MULTIPLIKATOR oblika 8j+-3 ima dobre osobine?
Jok. To se uglavnom odredjuje empirijski i tu je najveci problem. Izbor
8j+-3 je stavljen da se generator nikako ne zaglupi. U opstem slucaju
dozvoljen je izbor bilo kog multiplikatora koji pomnozen bilo kojim
neparnim brojem daje proizvod razlicit od modula. Postoji neka tanana
teorija koja se oslanja na preslikavanja definisana operacijom modulo
delenja i morfizme prilikom mnozenja nenegativnih celih brojeva, koja
daje odgovor u kojim oblastima treba traziti dobar multiplikator ali su
rezultati dosta siroki tako da su u praksi neupotrebljivi. Ceo posao se
svodi na sac bod metod. Osacuje se multiplikator (Na osnovu neke
kvaziteorije), urade se statisticki testovi i uporede sa poznatim
rezultatima, pa ako je bolje onda se objavljuje da i drugi mogu da
koriste. Dosta se na tom polju radilo tako da postoje testirani dosta
dobri multiplikatori. Prilicno dobar multiplikator dat je u [3],
a=630360016.
>Ako ne, kojim postupkom odrediti neki drugi multiplikator, osim
>onog koji si ti dao? (Ovo pitam jer si istakao da su oni Knutovi
>postupci pogresni, a postupak nam je ipak bitniji od jedne
>konstante. A ako znamo postupak, lako cemo i Zoliki isporuciti
>jedan primerak dobrog generatora.)
Nisu postupci pogresni nego su rezultati tih postupaka losiji od nekih
novijih koji su dobijeni empirijskim istrazivanjima. E ako je neko
empirijski odredio da nesto bolje funkcionise, ne postoji razlog da se
to ne koristi.
>I, da, koje su glavne slabosti mesovitih LK generatora
>dobijenih Knutovim postupkom (konkretno, onakvog kakvog je
>prikazao spantic) u odnosu na generator koji si nam prikazao?
Problem je u neujednacenim statistickim performansama za razlicite
opsege generisanih slucajnih brojeva. Vise detalja mogu se naci u
navedenoj literaturi. Ako nekoga interesuje, moze dobiti radove da
kopira, najbolje subotom kad svrati u klub (preko ppekovica).
LITERATURA:
1. Fishman G.S and Moroe L.R,
"A statistical evaluation of multiplicative congruential generators
with modulus 2^31 -1", Tehnical report 78-11, University of North
Carolina at Chapel Hill, (1980).
2. Fishman G.S and Moroe L.R,
"In search of correlation in multiplicative congruential generators
with modulus 2^31 -1", Tehnical report 80-5, University of North
Carolina at Chapel Hill, (1980).
3. Ken Marse and Stephen D. Roberts,
"Implementing a portable FORTRAN Uniform (0,1) generator"
Simulation, october, (1983).
P.S. Generator slucajnih brojeva UNIRAN opisan u referenci 3 je masinski
nezavisan i stvarno dobar. Kad proradi fakultet (pocnu da greju) uzecu fajlu
i proslediti ovde.
algoritmi.39bradenkovic,
-> #37, zolika> Zolika uopste nece da se upusta u ocenjivanje generatora slucajnih broje-
>va i njihovih karakteristika. Njemu generator treba samo kao SREDSTVO, tj.
>ALAT za problem koji treba da resi. Naime, kao sto je poznato, za Miler-
>Rabinov test prostote nekog broja treba izabrati SLUCAJAN broj u intervalu
>od 0 do N-1, gde je N uneti broj.
Ako hoces da ti test bude dobar, slucajan broj mora da ima rezoluciju 1,
t.j. da je verovatnoca da se izvuce neki broj u intervalu [0,N-1)
podjednaka za sve brojeve. Posledica toga je da slucajan broj mora da
ima odgovarajuci broj znacajnih cifara pa su sva petljanja sa mantisama
necelishodna.
> Dakle, bilo bi dobro kada bi neko predlozio takav generator slucajnih
> brojeva koji bi se "automatski" (koliko je to moguce) prilagodavao intervalu
> brojeva, koji je poznat kada korisnik unese broj N ciju prostotu treba pro-
> veriti. Zolika ce (bar koliko ga poznajem) isprogramirati takav generator,
> ako sazna postoji li fazon da se generator prilagodi gornjoj granici. To
zna-
> ci da N moze da bude 13, 98457694856749501, 84787, 2674537, sve zavisi od
> toga sta korisnik unese.
Da bi resio problem postoji vise nacina. Jedan od jednostavnijih je da
koristis neki gotov paket koji podrzava beskonacne integere, cija je
duzina ogranicena memorijom (ja sam koristio pre par godina REDUCE) i da
u njemu realizujes neki od algoritama koji je predlozen u predhodnim
porukama.
Drugi postupak je da algoritam realizujes tako sto ces da umesto jedne
promenljive Z, napravis niz od 250 longint promenljivih. Mnozenje mozes
da realizujes na isti nacin kako se radi u procesoru, uzmes zadnji
pomnozis sa multiplikatorom i ako postoji prenos na sledeci broj dodas
jedan i mnozis. Ispitivanje da li postoji promena znaka vrsis samo na
prvom elementu niza. Mozda je malo glupo ali moze da se realizuje. Pri
tome je zgodno da multiplikator bude u okviru 4 bajta.
Pozdrav Boza.
algoritmi.40dejanr,
-> #36, janko>> I šta sad? Da bismo dobili generator koji daje brojeve iz
>> opsega 0..+oo moramo da imamo generator koji daje brojeve iz
>> opsega 0..+oo. ;)
Pa, ja i nisam rekao da je to što sam napisao generator koji
zadovoljava uslove, zato i postavljam problem. Šta znam, i "luđe"
stvari su na kraju ispadale moguće.
Šteta što Alexa nije tu, sa njim sam na ovu temu svojevremeno imao
poduži razgovor i svašta smo smislili... ali problem rešili nismo ;)
algoritmi.41sirius,
Da li neko zna algoritam pomocu kojeg bi se ugrubo, ali prilicno brzo
iscrtavali TTF ili naki vektorski fontovi?
algoritmi.42zolika,
-> #39, bradenkovic>> Da bi resio problem postoji vise nacina. Jedan od jednostavnijih je da
>> koristis neki gotov paket koji podrzava beskonacne integere, cija je
>> duzina ogranicena memorijom (ja sam koristio pre par godina REDUCE) i da
>> u njemu realizujes neki od algoritama koji je predlozen u predhodnim
>> porukama.
Pa TO i hoću. Programe za supertačnu celobrojnu aritmetiku imam, samo
mi još algoritmi fale. Elem, da rezimiramo:
MOLIM SVE ONE KOJI SU SE U DISKUSIJI OKO SLUžAJNIH BROJEVA I NJIHOVOG
GENERISANJA JAVLJALI U OVOJ TEMI, A IMAJU NEKE ALGORITME KOJI BI MI KORIS-
TILI - AKO SU VOLJNI DA TE ALGORITME DAJU (POZAJME, POKLONE), NEKA DOĐU
DONOSEĆI ISTE U SUBOTU, 16. JANUARA 1993. NA SASTANAK KLUBA U "SLAVIJU".
Dolazim u BG, pa da spojimo lepo s korisnim... Ako nekome nešto nije
jasno, molim da sva prepiska ide preko privatne pošte, da ne gnjavimo cenjeni
auditorijum.
Unapred zahvalan,
Zolika
algoritmi.43kareem,
>>
>> Onima koji traze genetator slucajnih brojeva od 0..+beskonacno
>>
E sad ovako..Prvo i Prvo Nisam matematicar iako idem u mat.gim.
Dakle onako ,ovo je nesto najbolje sto sam smislio
randseed:=??????..................??????????????????
for i:= 1 to randseed
begin
rastavimo randseed u niz od po n cifara
od clanova tog niza napravimo brojeve
for j:= 1 to koliko vec ima tih brojeva
begin
randseed:= trunc(randseed (onda neka random operacija koju izaberemo
uz pomoc nekog malog i prostog generatora slucajnih brojeva)
a[j]);
end;
end;
e sad Da nadjem matematicara koji ce potvrditi da je kodomen ove funkcije
ceo N i na konju sam..
E da jos i ovo. Ako sam nesto pogrijesio pazite nisam matematicar.
a nisam ni provjeravao. Dakle Ak vam posluzi posluzi ak ne Oprostite za
izgubljeno vrijeme.(ipak sam se potrudio,da me ne pece savest)
algoritmi.44djelovic,
Povodom diskusije o slučajnim brojevima koja se ovde vodila
proteklih nedelja, evo diskusije dejanr-ovog problema i rešenja zolikinog:
█ Für dejanr: Problem je bio da li je moguće naći generator
slučajnih brojeva od nule do beskonačnosti, uniformne raspodele. Ja
mislim da nije, a evo i zašto:
Matematika se, barem do sada, razvijala manje-više iz potrebe
(2 ovce + 2 ovce = 4 ovce :)). Još važnije od toga, svo matematičko
znanje koje mi imamo su stvorili *ljudi*. Prema tome, ono je i
ograničeno našim poimanjem sveta. Linija kao matematički pojam nije
nastala sve dok ljudi nisu počeli da prave noževe (kuće, sekire, ili šta ti
ja znam drugo) pravih ivica.
Elem, naći ću ti generator kakav želiš ako mi smisliš i
jedan događaj iz prirode koji ima uniformnu verovatnoću od 0 do
beskonačno. Bez toga, nema generatora.
Već vidim kako se ljutiš: "Pa zar matematika nije apstraktna
nauka koja nema veze sa prirodom? Mi je čisto primenjujemo na prirodu
kada nam to odgovara. Možemo recimo na osnovu našeg znanja algebre da
stvorimo matematičku strukturu koja ne bi imala nikakve veze sa stvarnim
svetom." Naravno, naravno da možemo. Ali nećemo znati da je koristimo
zbog toga što smo ograničeni ovim našim svetom...
Nadam se da smo se razumeli. Ovo gore nije naravno nikakav dokaz,
već je samo moj kratki pokušaj da objasnim zašto mislim da sa našim
matematičkim alatkama nećemo nikada moći da napravimo generator
slučajnih brojeva kakav si ti naveo. Isto kao što ne bi uopšte stigli do
integrala da smo ostali na rimskim brojevima umesto što koristimo
arapske.
█ Für zolika: Za razliku od ove "mekane" diskusije dejanr-ovog
problema, za tebe imam konkretan algoritam. Da se podsetimo, traži se
algoritam koji bi davao slučajan broj iz opsega 0 do N, gde je N
proizvoljno. Rešenje je banalno:
Ako je N broj od K cifara, jednostavno uzmeš i složiš
proizvoljnu kombinaciju od K cifara. Recimo:
A$ = ""
FOR I = 1 TO N
A$ = A$+CHR$ (ODR ('0') + RND (9))
NEXT I
Sada proveriš da li je broj koji si tako dobio veći od N, i ako
jeste, samo zatražiš sledeći slučajan broj od generatora. Ako nije, to
je tvoj broj. žudno kao što to možda izgleda, raspodela je uniformna, a
slučajan broj može biti iz proizvoljnog opsega. Sve što ti treba jeste
generator slučajnih brojeva od 0 do 9.
BTW, ne postoji *savršen* generator slučajnih brojeva, tj. svaki
od njih ima neku periodu posle koje počinje da se ponavlja. Ukoliko ćeš
ovaj svoj generator koristiti za statističku analizu a ne za neku igricu
koja mora svaki put da se drugačije ponaša, idealan način da dobiješ niz
stvarno slučajnih cifara jeste da "vadiš" cifre iz nekog iracionalnog
broja, kao što je pi, sqrt 2, sqrt 3, itd.
algoritmi.45dejanr,
-> #44, djelovic>> Elem, naći ću ti generator kakav želiš ako mi smisliš i
>> jedan događaj iz prirode koji ima uniformnu verovatnoću od 0 do
>> beskonačno. Bez toga, nema generatora.
To je lako, svet je pun takvih događaja. Recimo, trenutak rođenja
DJelovića :)
algoritmi.46djelovic,
-> #45, dejanr> To je lako, svet je pun takvih događaja. Recimo, trenutak rođenja
> DJelovića :)
Not so. Dobar matematičar bi, na osnovu znanja o mestu i vektorima
brzina svih čestica ovoga univerzuma mogao da izračuna stanje univerzuma
u bilo kom trenutku. Prema tome, slučajna verovatnoća rađanja moj e (a
bogami i tvoje) malenkosti zapravo i nije slučajna. Radi se pre o tome
da su babice imale nepotpune informacije :).
algoritmi.47dejanr,
-> #46, djelovic>> Not so. Dobar matematičar bi, na osnovu znanja o mestu i vektorima
>> brzina svih čestica ovoga univerzuma mogao da izračuna stanje univerzuma
>> u bilo kom trenutku.
Ako je tako, onda se i svaka druga stvar može tačno predvideti pa uopšte
ne postoji slučaj a samim tim ni slučajan događaj/slučajan broj. Dakle,
svet je potpuno determinisan. Ovo je već filozofsko pitanje.
Za mene je slučajan događaj nešto na šta utiče toliko stvari da se ishod
ne može predvideti (recimo, ako bi dva puta bacio novčić identičnim
vektorom brzine, u uslovima istih vazdušnih strujanja itd, novčić bi uvek
isto pao, pa se opet to bacanje novčića uzima kao "školski primer"
slučajnog događaja).
Dakle, da je neko pre samo 5-6 hiljada godina opisao tebe i pitao kada
ćeš se roditi, jedini odgovor koji se mogao dati je "između sada i
plus beskonačno"... naravno, ako se uzme da će vasiona postojati do
"plus beskonačno".
algoritmi.48djelovic,
-> #47, dejanr> Dakle, da je neko pre samo 5-6 hiljada godina opisao tebe i pi
> ćeš se roditi, jedini odgovor koji se mogao dati je "između sa
> plus beskonačno"... naravno, ako se uzme da će vasiona postoja
> "plus beskonačno".
Ajmo ovako: Vasiona ima početak i vasiona ima kraj (Big Beng). S obzirom na
to, verovatnoća događaja nije uniformna od nula do beskonačno, nego od nula do
vremena Big Benga.
No, ukoliko ostanemo na tvojim premisama, onda bi tvoj algoritam bio
sledeći:
1. Uključi štopericu.
2. Proveri da li se rodilo dete po imenu Slafirtblatfast Ristanović.
3. Ukoliko jeste, tj. ukoliko si ti to uspeo da otkriješ, zaustavi
štopericu. Broj proteklih sekundi je naš slučajan broj.
4. Ukoliko se nije rodilo takvo dete, idi na 2.
Naravno, ovakav algoritam bi morao da radi na specifičnom hardveru
(kompjuter bi morao da bude sposoban da pretrči svet tražeći dete, a bogami
trebalo bi mu i dosta memorije da upamti broj sekundi od danas do Big Benga),
ali bi radio to što ti želiš.
Kao događaj, opet, ne moraš da upotrebiš ime deteta, dovoljno je recimo da
na kompjuter priključiš kameru, da na ekranu iscrtaš neku sliku, i da čekaš da
se ulaz sa kamere potrefi sa slikom. Ili, da čekaš da neki elektron izleti iz
orbite, ili bilo šta slično.
algoritmi.49inesic,
-> #46, djelovic> bogami i tvoje) malenkosti zapravo i nije slučajna. Radi
> se pre o tome
Sve, sve... ali reći za Dejana njegova malenkost...
algoritmi.50bradenkovic,
-> #44, djelovic> Ako je N broj od K cifara, jednostavno uzmes i slozis
> proizvoljnu kombinaciju od K cifara. Recimo:
>
> A$ = ""
> FOR I = 1 TO N
> A$ = A$+CHR$ (ODR ('0') + RND (9))
> NEXT I
>
> Sada proveris da li je broj koji si tako dobio veci od N, i ako
> jeste, samo zatrazis sledeci slucajan broj od generatora. Ako nije, to
> je tvoj broj. Cudno kao sto to mozda izgleda, raspodela je uniformna, a
> slucajan broj moze biti iz proizvoljnog opsega. Sve sto ti treba jeste
> generator slucajnih brojeva od 0 do 9.
Bilo bi lepo kad bi bilo tako jednostavno.
Najpre rezolucija od 1/10 je vrlo mala za bilo kakav ozbiljan generator.
Dalje na osnovu osobina centralne granicne teoreme moze se predpostaviti
da tvoj generator generise neki slucajan broj koji verovatno "lici" na
normalnu raspodelu. U svakom slucaju taj broj nije sa uniformnom raspodelom.
U slobodnoj (prilagodjenoj za ovaj auditorijum) interpretaciji centralna
granicna teorema glasi: Zbir n slucajnih brojeva sa uniformnom raspodelom
predstavlja jednu realizaciju slucajne promenljive sa normalnom raspodelom,
kada n tezi beskonacno. U praksi je dovoljno da n bude 12.
Na osnovu centralne granicne teoreme moguce je napraviti skoro savrsen
generator slucajnih brojeva sa normalnom raspodelom tako sto u petlji
saberete 12 slucajnih brojeva sa uniformnom raspodelom i dobijeni zbir
proglasite za jednu realizaciju slucajne promenljive sa normalnom raspodelom.
Pozdrav Boza
algoritmi.51djelovic,
-> #50, bradenkovic> Najpre rezolucija od 1/10 je vrlo mala za bilo kakav ozbiljan generator.
Nisam siguran na šta misliš kada kažeš rezolucija, ali ukoliko misliš na
broj ponavljanja pre nego što se generator vrati u početno stanje, tj. ukoliko
misliš da posle deset slučajnih brojeva generator počinje da se ponavlja, onda
se slažem s tobom. No, sama funkcija RND ne mora da radi po modulu 10, već može
da bude i recimo dvadesetobajtna, mi je samo svodimo na opseg 0-9.
E sad, ovaj generator koji sam ja izneo, iako je daleko od savršenog, radi
zoliki posao ko bog, prema tome što dalje teoretisati?
BTW, Evo na šta se algoritam svodi:
1. uzmi par slučajnih brojeva.
2. Provuci ih kroz HASH funkciju (ono slepljivanje cifara se na to svodi!),
i time im povećaj rezoluciju.
algoritmi.52vpetrovic,
-> #46, djelovic>> Not so. Dobar matematičar bi, na osnovu znanja o mestu i vektorima
>> brzina svih čestica ovoga univerzuma mogao da izračuna stanje univerzuma
>> u bilo kom trenutku. Prema tome, slučajna verovatnoća rađanja moj e (a
>> bogami i tvoje) malenkosti zapravo i nije slučajna. Radi se pre o tome
>> da su babice imale nepotpune informacije :).
Ali nikad ne bi mogao da dođe do tih podataka zbog principa neodređenosti,
pa bi jedino mogao da izračuna verovatnoću ;))
Vlada
algoritmi.53bradenkovic,
-> #51, djelovic> Nisam siguran na sta mislis kada kazes rezolucija, ali ukoliko mislis na
>broj ponavljanja pre nego sto se generator vrati u pocetno stanje, tj. ukoliko
>mislis da posle deset slucajnih brojeva generator pocinje da se ponavlja, onda
>se slazem s tobom. No, sama funkcija RND ne mora da radi po modulu 10, vec
moze
>da bude i recimo dvadesetobajtna, mi je samo svodimo na opseg 0-9.
Rezolucija generatora je najmanja distanca izmedju dva razlicita slucajna
broja.
U tvom slucaju uzeo si celobrojnu vrednost od rnd(9) i time ukinuo sve brojeve
izmedju cifara. Najmanja distanca izmedju tako generisana dva broja je 1. Ako
normalizujes na interval [0-1) dobijes 1/10. Funkcija gustine raspodele takve
promenljive bice stepenice sa 10 stepenika umesto fine gladke funkcije.
Kakva ce se raspodela promenjive dobiti kad se takav broj sa kilavom uniformnom
raspodelom pomnozi sa istim takvim brojem pomnozenim sa 10, Bog sveti zna.
Ako se zanemare raznorazne autokorelacije koje su u ovom slucaju moguce,
trebala bi da bude nesto sto pomalo lici na normalnu raspodelu a malo vise
na studentovu za odgovarajuci broj stepeni slobode. No ovo vec prelazi u
bajanje tako da dalja diskusija po ovom pitanju bez detaljnijeg uvida u
literaturu ili nekog dodatnog istrazivanja nema smisla.
Pozdrav Boza.
algoritmi.54nenadb.,
-> #46, djelovic>> Not so. Dobar matematicar bi, na osnovu znanja o mestu i vektorima
>> brzina svih cestica ovoga univerzuma mogao da izracuna stanje univerzuma
>> u bilo kom trenutku.
Konacni odgovor u svakom slucaju je '42'.
algoritmi.55janko,
-> #44, djelovic> █ Für zolika: Za razliku od ove "mekane" diskusije
> dejanr-ovog problema, za tebe imam konkretan algoritam. Da
> se podsetimo, traži se algoritam koji bi davao slučajan
> broj iz opsega 0 do N, gde je N proizvoljno. Rešenje je
> banalno: Ako je N broj od K cifara, jednostavno uzmeš i
> složiš proizvoljnu kombinaciju od K cifara. Recimo:
>
> A$ = ""
> FOR I = 1 TO N
> A$ = A$+CHR$ (ODR ('0') + RND (9))
> NEXT I
>
> Sada proveriš da li je broj koji si tako dobio veći od N,
> i ako jeste, samo zatražiš sledeći slučajan broj od
> generatora. Ako nije, to je tvoj broj. žudno kao što to
> možda izgleda, raspodela je uniformna, a slučajan broj
> može biti iz proizvoljnog opsega. Sve što ti treba jeste
> generator slučajnih brojeva od 0 do 9.
:( Ovako bi se onda svi generatori pravili... a ne prave se.
Kao dalja varijacija tvoje ideje: napraviš RND generator u
opsegu 0..1 pa praviš proizvoljno velike RND generatore.
To se ne radi. Zašto? Piše u nekim knjigama...
> BTW, ne postoji *savršen* generator slučajnih brojeva, tj.
> svaki od njih ima neku periodu posle koje počinje da se
> ponavlja. Ukoliko ćeš ovaj svoj generator koristiti za
> statističku analizu a ne za neku igricu koja mora svaki
> put da se drugačije ponaša, idealan način da dobiješ niz
> stvarno slučajnih cifara jeste da "vadiš" cifre iz nekog
> iracionalnog broja, kao što je pi, sqrt 2, sqrt 3, itd.
I ovo se ne koristi. ;) To što ne znamo kako se ponašaju cifre
iracionalnih brojeva ne znači da njihovo pojavljivanje ima
uniformnu raspodelu.
algoritmi.56zzile,
-> #21, dejanr Razmisljao sam malo na temu beskonacnog slucajnog broja. Cinimi se
da ne stoji da je broj RND(ý) (za uniformnu raspodelu) konacniji od
broja ý, sto cu pokusati da obrazlozim:
Ako je raspodela uniformna onda ce matematicko ocekivanje te
raspodele opet da bude beskonacan broj, a ako razmatramo bilo koji
ogranicen interval u kome bi se nasao generisani broj, verovatnoca
da broj bude van tog intervala tezi sigurnom dogadjaju. Znaci da
ako generator da konacan broj, skoro sigurno raspodela nije uniformna!
U skladu s tim meni se cini da nema razlike u koriscenju oznaka
RND(ý) i ý, tj. sumnjam u primenjivost broja RND(ý), a da se ona
razlikuje od primenjivosti broja ý. Na primer: ako integral sa
nekom granicom ý tezi konacnom broju onda ce i integral sa granicom
RND(ý) takoce da tezi tom broju, sa verovatnocom koja tezi jedinici,
takodje verovatno vazi sa verovatnocom koja tezi jedinici:
abs(RND(ý)-RND(ý)) = ý, itd.
Za matematicke primene je verovatno RND(ý) = ý, a za programerske
bi bilo dovoljno naci algoritam za bilo koji unapred zadati interval,
ili generator koji do kraja svog postojanja izbacuje cifre, ili
generator za neku raspodelu koja nije uniformna (kao sto u prirodi
uglavnom nije) npr. za gausovu raspodelu na intervalu do +ý, sto je
lakse napraviti (potrebno je da imamo generator slucajnog broja izmedju
0 i 1, kao i samu raspodelu sa proizvoljnom tacnoscu).
algoritmi.57nenadp,
-> #46, djelovic>> Not so. Dobar matematicar bi, na osnovu znanja o mestu i
>> vektorima brzina svih cestica ovoga univerzuma mogao da
>> izracuna stanje univerzuma u bilo kom trenutku.
Eh bas bi voleo da vidim tog dobrog matematicara kada pocne da se bavi
kvantnom fizikom da li bi i dalje tvrdio ovo gore.
Pozdrav, Nenad
P.S. Da potsetim na poznatu relacija neodredjenosti po kojoj sto je
tacnije poznat polozaj cestice to netacnije poznajemo impuls cestice.
algoritmi.58zzile,
-> #21, dejanr Sva ova diskusija kao problem ima sustinu pojma beskonacno.
Ako za primer primene ovog generatora uzmemo ipak ograniceno
trajanje vasione i jedan proizvoljan trenutak onda je to problem
odgovarajuceg hardvera, a o pravoj beskonacnosti mi je tesko
diskutovati. Ako je vasiona beskonacna onda u njoj ima susednih
cestica samo zato sto i njih mora da ima beskonacno mnogo?!
Neka neko za pocetak predlozi generator realnihbrojeva u opsegu
0 do 1, ali sa beskonacno velikim brojem decim
algoritmi.59dejanr,
-> #58, zzile>> Neka neko za pocetak predlozi generator realnihbrojeva u opsegu
>> 0 do 1, ali sa beskonacno velikim brojem decim
Pa, to je isto - ako bi imao onaj "moj" generator, generišeš ceo
slučajan broj između 1 i beskonačno (recimo, broj M) i izračunaš
1/M.
algoritmi.60zsiz,
-> #48, djelovic> Ajmo ovako: Vasiona ima početak i vasiona ima kraj (Big Beng). S obzirom
na
> to, verovatnoća događaja nije uniformna od nula do beskonačno, nego od nula
do
> vremena Big Benga.
žitao sam u jednom kompjuterskom listu da za pravljenje programa
software-ske firme sve više angažuju diplomirane filozofe kao
konsultante. Ako ovako nastaviš neka od tih firmi ima garantovano
da te angažuje ;)).
Pozdrav.
zsiz
algoritmi.61darone,
-> #56, zzile>> da ne stoji da je broj RND(ý) (za uniformnu
>> raspodelu) konacniji od broja ý, sto cu pokusati
>> da obrazlozim:
Šta konkretno, na primeru, znači konačniji? To je
kao crnji. Ako je već crn, kako može da bude crnji?
darone
algoritmi.62dejanr,
-> #48, djelovic>> Ajmo ovako: Vasiona ima početak i vasiona ima kraj (Big Beng).
Hmmm... valjda je Big Beng početak, a za kraj se još naučnici nisu
"dogovorili", 'oćel' ga biti il' neće.
>> S obzirom na to, verovatnoća događaja nije uniformna od nula do
>> beskonačno, nego od nula do vremena Big Benga.
Ako se uzme da će vasiona "zauvek" postojati, onda je to uniformno
raspoređen broj između trenutka nastanja ljudi u današnjem obliku
i plus beskonačno. Šanse da će se neko nalik na čoveka roditi
u prvih pola sata posle Big Banga su, recimo, nikakve ;)
U tom smislu, mislim da bi se sve to moglo uzeti kao generator
slučajnog broja u intervalu [0, +beskonačno) E još da napravimo
nešto slično za računar...
Uzgred, neki ljudi na BIX-u sa kojima sam diskutovao o istom problemu
su me uputili na neki rad (premda još nemam tačnu referencu) u kome
su neki treći ljudi navodno (k'o što se vidi, sve same sigurne
informacije ;) dokazali da bi se takav generator mogao konstruisati
(eto, ispade da nisam izmislio problem, ništa novo na ovome svetu :( )
ali izgleda da još niko nije uspeo da ga konstruiše. Jedna faca sa nekog
manjeg USA univerziteta (za koji nikad nisam čuo :) kaže da bi čak i
najugledniji časopis rado objavio rad u kome se opisuje takav generator
(ja dodajem "po skidanju sankcija" ;)
algoritmi.63zzile,
-> #59, dejanr>Pa, to je isto - ako bi imao onaj "moj" generator, generises
>ceo slucajan broj izmedu 1 i beskonacno (recimo, broj M) i
>izracunas 1/M.
Problem je naravno slicne tezine ali se navedenom transformacijom
raspodela drasticno menja.
algoritmi.64inesic,
-> #62, dejanr> Hmmm... valjda je Big Beng početak, a za kraj se još
> naučnici nisu "dogovorili", 'oćel' ga biti il' neće.
Grešiš! Sve se zna. Kraj se zove Gneb Gib i ako u neku od
intergalaktičkih banaka uložiš paru, od kamata ćeš moći dooobro
da se najedeš posmatrajući to čudo. U retoranu na kraju
univerzuma.
algoritmi.65zzile,
-> #61, darone> Sta konkretno, na primeru, znaci konacniji? To je
> kao crnji. Ako je vec crn, kako moze da bude crnji?
More, bice nam sve crnje i crnje :)). Salu na stranu pridev konacan
stvarno ne vredi porediti.
algoritmi.66tomae,
-> #57, nenadp> P.S. Da potsetim na poznatu relacija neodredjenosti po kojoj sto je
> tacnije poznat polozaj cestice to netacnije poznajemo impuls
Da dodamo i koeficijent eta (potreban za određivanje momenta rođenja
određene osobe) koji karakteriše položaj mama<->tata :)
on ona eta
======================
G D 0.2
D G 0.21
B B 0.03
NZ NP 0.18
. . .
legenda
-------
G - gore D - dole
B - bok NZ - nazad ...
Tabela se može smatrati PD. "Dobri matematičari", napred! :)))))
algoritmi.67ndragan,
-> #61, darone/>> da ne stoji da je broj RND(ý) (za uniformnu
/ Šta konkretno, na primeru, znači konačniji? To je
Pa RND(ý) bi morao da daje slučajne brojeve u intervalu od 0 do ý;
vrednosti koje daje bi mogle da budu konačne ili ne. Ja sam 'konačniji'
shvatio kao 'više puta ispadne konačan' ili 'ima više osobina konačnog
broja nego beskonačnog', sasvim u duhu matematičarskog jezika.
algoritmi.68ndragan,
-> #52, vpetrovic/>> bogami i tvoje) malenkosti zapravo i nije slučajna. Radi se pre o
/>> tome da su babice imale nepotpune informacije :).
/ Ali nikad ne bi mogao da dođe do tih podataka zbog principa
/ neodređenosti,
A bogami, da su se babice malo pozabavile očitavanjem relevantnih
činjenica, ne bi se rodio do dana današnjeg... one bi još čitale
preliminarna opšta mesta.
algoritmi.69janko,
Pitanje:
Koji brojevi od onih koje često nalazimo kod nas u praksi imaju
osobinu da može da im se proveri ispravnost pri ukucavanju i
koji su odgovarajući algoritmi za odgovarajuće brojeve? Drugim
rečima, koji brojevi imaju u sebi ugrađene kontrolne sume?
Npr: ako neko otkuca neispravan matični broj, ili broj tekućeg
računam ili... može li to program da detektuje, i ako može
kako?
(Dobio sam inspiraciju za pitanje kada su mom tati na nekom
dokumentu koji su generisali kompjuterom zeznuli njegov MB, pa
je morao još jedan dan da ide da se zeza po šalterima)
algoritmi.70ppekovic,
-> #69, janko>> Koji brojevi od onih koje često nalazimo kod nas u praksi imaju
>> osobinu da može da im se proveri ispravnost pri ukucavanju i
>> koji su odgovarajući algoritmi za odgovarajuće brojeve? Drugim
>> rečima, koji brojevi imaju u sebi ugrađene kontrolne sume?
Uvek sam se pitao što u metičnom broju predstavljaju
poslednjih 6 cifara. Početak je naravno dan, mesec i godina (bez
hiljada) rođenja.
Paya
algoritmi.71djelovic,
-> #70, ppekovic> Uvek sam se pitao što u metičnom broju predstavl
> poslednjih 6 cifara.
Šifru mesta rođenja, bolnice i valjda informacija koje si dete na bolničkom
spisku. Ni za jedan zvanični podatak ne postoji CRC-32 :).
algoritmi.72wizard,
-> #70, ppekovic> Uvek sam se pitao što u metičnom broju predstavljaju
> poslednjih 6 cifara.
Od tih 6, prve dve predstavljaju opštinu, sledeća označava pol, 0 i još
jedan (ne sećam se koji) za muškarce i 5 i još jedan (opet se ne sećam
koji) za žene, a poslednje 3 cifre su i meni neobjašnjive i za sada
smatram da i ne znače ništa osim što učestvuju u kontrolnoj sumi.
Inače - odgovor na Jankovo pitanje: postoji kontrolna suma, verovatno se
poslednje tri cifre "nameštaju" tako da kontolna suma bude svima ista.
algoritmi.73dejanr,
-> #69, janko>> Koji brojevi od onih koje često nalazimo kod nas u praksi imaju
>> osobinu da može da im se proveri ispravnost pri ukucavanju i
>> koji su odgovarajući algoritmi za odgovarajuće brojeve? Drugim
>> rečima, koji brojevi imaju u sebi ugrađene kontrolne sume?
Bojim se da je takvih jako malo, ako ih uopšte ima. Neki od brojeva
koji sigurno *nemaju* checksum su: matični broj firme, šifra delatnosti,
šifra oblika udruživanja (termin iz drugog vremena ;), žiro račun...
Kažu da matični broj građanina ima zadnju cifru koja predstavlja kontrolu
tačnosti, ali izgleda da niko nije baš siguran da je stvarno tako niti
zna kako se šifra određuje.
Od prošle godine svi brojevi faktura imaju poslednju cifru kojom se
utvrđuje tačnost. Algoritam je poznat i ima ga negde na Sezamu iz
vremena kada je to bilo aktuelno (prošle godine su svi Clipper programi
morali da se prepravljaju tim povodom, kad će nešto novo pa da opet
naplaćujemo? :)).
Taj algoritam je otprilike ovakav:
function checksum (broj: longint): longint;
var brojs: string;
suma,i: longint;
begin
str(broj, brojs);
suma:=0;
for i:=1 to length(brojs) do
begin
suma:=suma+(ord(brojs[i])-ord('0'))*(length(brojs)+2-i)
end;
suma:=suma mod 11;
if suma<>0 then suma:=(11-suma) mod 10;
checksum:=broj*10+suma;
end;
algoritmi.74ivanna,
-> #70, ppekovic> Uvek sam se pitao sto u meticnom broju predstavljaju
> poslednjih 6 cifara. Pocetak je naravno dan, mesec i godina
10-ta cifra je za pol
0 - muski
5 - zenski
algoritmi.75mladenp,
-> #70, ppekovic> Uvek sam se pitao što u metičnom broju
> predstavljaju poslednjih 6 cifara. Početak je naravno dan,
> mesec i godina (bez hiljada) rođenja.
Posle godine idu dve cifre koje označavaju mesto rođenja.
Za Beograd - 71. Neko reče da je to oznaka opštine. Ne bih
rekao. Mogao bi neko rođen u Zemunu da nam kaže šta kod
njega piše.
Sledeće tri cifre su redni broj bebe (od 0 do 499 za muške
i 500 do 999 za ženske). Tako su mi svojevremeno rekli u
gradskom zavodu za statistiku. Ne znam da li se sortiraju po
vremenu rođenja (sumnjam) ili po redosledu prijavljivanja.
Poslednja cifra je kontrolni broj.
algoritmi.76bulaja,
-> #70, ppekovic│Uvek sam se pitao sto u meticnom broju predstavljaju poslednjih
│6 cifara. Pocetak je naravno dan, mesec i godina (bez hiljada) rodenja.
└───
Neke od cifara su i sifra grada (za beograd su valjda 7. i 8. cifra 71)
i pol. Ima jos i neka random cifra i that's all. Nisam siguran da li
postoji kontrolna cifra. U brojevima ziro i tekucih racuna uvek postoji
kontrolna cifra, bilo je negde u staroj PC.PROG temi diskusije oko toga.
algoritmi.77dtadic,
-> #75, mladenp>> Posle godine idu dve cifre koje oznacavaju mesto rodenja.
>> Za Beograd - 71. Neko rece da je to oznaka opstine. Ne bih
>> rekao. Mogao bi neko roden u Zemunu da nam kaze sta kod
>> njega pise.
Za Zemun je takodje 71.
DT
algoritmi.78dejanr,
-> #76, bulaja>> U brojevima ziro i tekucih racuna uvek postoji kontrolna cifra, bilo
>> je negde u staroj PC.PROG temi diskusije oko toga.
Ne znam za broj tekućeg, ali za broj žiro računa veoma sumnjam da ima
kontrolnu sumu. čiro računi za firme su obično rrxxx-mmm-n gde je rr
Republika/Pokrajina (još od exYU je bilo Bosna, CG, Hrv, Mak, Slo
redom 10,20,30,40,50, Srbija 60-64, Vojvodina 65-66 i Kosovo 68.
xxx označava banku, mmm je tip žiro računa (firme su obično 601, 603,
ali ima i raznih internih banki, siz-ova itd sa 664 i raznim drugim
brojevima) a N je redni broj, i to ti brojevi N idu redom, dakle recimo
postoje žiro računi tipa 60811-601-10, pa onda 60811-601-11 i tako dalje,
"rupe" uglavnom dolaze od firmi koje su vremenom propadale, integrisale
se itd.
U svemu ovome nema mesta za kontrolnu sumu. Jedina mala kontrola je da
žiro nije ispravan ako počinje na 67 ili 69, ali od toga slaba vajda.
algoritmi.79milan,
-> #73, dejanr> Kažu da matični broj građanina ima zadnju cifru koja predstavlja kontrolu
> tačnosti, ali izgleda da niko nije baš siguran da je stvarno tako niti
> zna kako se šifra određuje.
Zaboravio sam modul, ali je checksum po sredi. žini mi se da je to
zbir prethodnih cifara modulo 11 ili 13.
Pl poz M
algoritmi.80jtitov,
-> #70, ppekovic>>> Koji brojevi od onih koje cesto nalazimo kod nas u
>>> praksi imaju osobinu da moze da im se proveri ispravnost
>>> pri ukucavanju i
> Uvek sam se pitao sto u meticnom broju
> predstavljaju
U maticnom broju radnih ljudi i gradjana, postoji kontrola po modulu 11 i
to je ona zadnja cifra.
algoritmi.81djelovic,
-> #80, jtitov> U maticnom broju radnih ljudi i gradjana, postoji kontrola po modulu 11 i
> to je ona zadnja cifra.
Jok. Probao sam - kod mene radi, kod moje babe ne :).
algoritmi.82robert,
-> #75, mladenp>> Sledeće tri cifre su redni broj bebe (od 0 do 499 za muške
>> i 500 do 999 za ženske). Tako su mi svojevremeno rekli u
Sve je to lepo ali kako se određuju brojevi onima rođeni u
inostranstvu? Teško da imaju onda taj 'broj bebe'.
algoritmi.83dragisak,
-> #76, bulaja║ Neke od cifara su i sifra grada (za beograd su valjda 7. i 8. cifra
║ 71) i pol. Ima jos i neka random cifra i that's all. Nisam siguran
║ da li postoji kontrolna cifra. ...
Evo ga algoritam za izračunavanje kontrolne cifre kod matičnog broja građana :
MBG = a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13
sum = a1 * 7 +
a2 * 6 +
a3 * 5 +
a4 * 4 +
a5 * 3 +
a6 * 2 +
a7 * 7 +
a8 * 6 +
a9 * 5 +
a10* 4 +
a11* 3 +
a12* 2;
ctrl = 11 - mod( sum, 11 );
if ( ctrl < 10 )
a13 = ctrl;
else
a13 = 0;
algoritmi.84vitez.koja,
-> #82, robert#=> Sve je to lepo ali kako se određuju brojevi onima rođeni
#=> u inostranstvu? Teško da imaju onda taj 'broj bebe'.
Onda im daju 666 ;)
algoritmi.85mjova,
-> #83, dragisak> Evo ga algoritam za izračunavanje kontrolne cifre kod
> matičnog broja građana :
probah, moj broj paše ;)
algoritmi.86mladenp,
-> #82, robert> Sve je to lepo ali kako se određuju brojevi onima rođeni u
> inostranstvu? Teško da imaju onda taj 'broj bebe'.
Odmah da kažem: ne znam. Ako ide po redosledu prijavljivanja
(upisivanja u matične knjige), nema problema.
Mnogo zanimljivije pitanje u vezi sa bebama rođenim
u inostranstvu: koja je oznaka mesta rođenja? :)
algoritmi.87dnikolic,
-> #73, dejanr>> suma:=suma+(ord(brojs[i])-ord('0'))*(length(brojs)+2-i)
Ne razumem se bas u Pascal, sta radi funkcija ORD? Inace, ovo je veoma
interesantan programcic, to mi zaista treba!
dn
algoritmi.88darone,
-> #83, dragisak>> MBG = a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13
Samo još da neko kaže šta je *tačno* koja od
cifara...
darone
algoritmi.89zolika,
-> #70, ppekovic>> Uvek sam se pitao što u metičnom broju predstavljaju
>> poslednjih 6 cifara. Početak je naravno dan, mesec i godina (bez
>> hiljada) rođenja.
Zar nije poslednja cifra ostatak po modulu 11 ili 13 ?
algoritmi.90ladislavs,
-> #75, mladenp> Posle godine idu dve cifre koje označavaju mesto rođenja.
> Za Beograd - 71. Neko reče da je to oznaka opštine. Ne bih
Izgleda da to nije baš to. Po ovome bi Novi Sad bio deo Beograda,
a čini mi se da (još uvek ;) nije.
Možda su pretpostavili da ću o'ma da se preselim u BG ;))).
ciLa.
algoritmi.91smiloradovic,
-> #86, mladenp)>> Sve je to lepo ali kako se određuju brojevi onima rođeni u
)>> inostranstvu? Teško da imaju onda taj 'broj bebe'.
)>
)> Odmah da kažem: ne znam. Ako ide po redosledu prijavljivanja
)> (upisivanja u matične knjige), nema problema.
Znam par ljudi koji nisu rođeni u Beogradu, ali pošto im je lična
karta izdata ovde, u MB imaju 71 kao oznaku mesta. Znači, biće da nema
baš puno veze sa bebama :)
algoritmi.92mbole,
-> #91, smiloradovicJa sam rođen u Kragujevcu a u matičnom broju imam 71. Možda to ide na
osnovu mesta izdavanja lične karte.
algoritmi.93janko,
-> #83, dragisak> Evo ga algoritam za izračunavanje kontrolne cifre kod
> matičnog broja građana :
Super! Samo još da ga probam... nadam se da oni koji su
izmišljali broj za svakog čoveka nisu davali peške službenicima
da ga računaju. ;)
Izuzetno mi je drago što smo došli do nekih rezultata! Idemo
dalje! Hajde da nađemo još 'bezbednih' brojeva!
A već smo načeli i drugu temu:
Očigledno postoji i dosta brojeva koji u sebi, osim što imaju
osobinu ključa, sadrže još neke korisne podatke. Videli smo i
par primera. Npr. u pomenutom matičnom broju se krije
informacija o datumu rođenja osobe i njenom polu. Zne li neko
još neke brojeve, koje do sada nismo pomenuli, a koji u sebi
sadrže dodatne korisne informacije?
algoritmi.94mladenp,
-> #92, mbole> Ja sam rođen u Kragujevcu a u matičnom broju imam 71.
> Možda to ide na osnovu mesta izdavanja lične karte.
Sve što mogu da zaključim na temu JMBG (jedinstveni
matični broj građana) je JBMG ('bem li ga ;)).
Matični brojevi su uvedeni relativno skoro (petnaestak
godina) a svi mi smo rođeni ranije. Trebalo bi videti
kakav broj imaju oni koji će ličnu kartu prvi put dobiti
za dve-tri godine. :)
algoritmi.95wizard,
-> #92, mbole> Ja sam rođen u Kragujevcu a u matičnom broju imam 71. Možda to ide na
> osnovu mesta izdavanja lične karte.
Ma naravno, nema veze gde si rođen. :) Ja sam nejasan bio kad sam
rekao da je to broj za opštinu (mislio sam na prebivalište - uostalom,
samo u Srbiji ima preko 100 opština), pre će biti da su u pitanju malo
veće enklave. ;)
algoritmi.96bulaja,
-> #87, dnikolic│Ne razumem se bas u Pascal, sta radi funkcija ORD?
└───
Da ne bi mnogo objasnjavao :), evo Wirthove definicije - Ord(x) je redna
funkcija koja vraca redni broj (celobrojnu vrednost) rednog parametra x
u skupu vrednosti definisanih tipom podataka od x.
Npr. ako je x tipa char, onda bi Ord(x) vratio ascii kod od x.
algoritmi.97mbole,
-> #94, mladenp> kakav broj imaju oni koji će ličnu kartu prvi put dobiti
> za dve-tri godine. :)
Matični broj se dobija pri rođenju, a ne pri izdavanju lične karte. Ne
znam koji je sistem bio za nas koji smo već bili rođeni kada su ga uveli.
Izgleda da tu dolazi do zbrke.
algoritmi.98dejanr,
-> #95, wizard>> Ja sam nejasan bio kad sam rekao da je to broj za opštinu (mislio sam
>> na prebivalište - uostalom, samo u Srbiji ima preko 100 opština), pre
>> će biti da su u pitanju malo veće enklave. ;)
Garant su te enklave tzv. "bivši srezovi". Ti srezovi su ukinuti još
Bog-zna-pre-koliko-godina ali što se administracije tiče i dan danas
funkcionišu. Svaki izgleda ima neki svoj računski centar (sa svojim
rasporedom YU slova :( ) i onda se to samo sliva u neki centar.
algoritmi.99mbacic,
Da li neko zna neki algoritam za crtanje kruga sem Bresham's algorithm i
trigonometrijskog nacina.
algoritmi.100pedjak,
-> #83, dragisak> ctrl = 11 - mod( sum, 11 );
A kako bi izgledala ova funkcija mod ? Pojam modula mi je nepoznat,
pa bih bio vrlo zahvalan da mi ga neko objasni.
pedja
algoritmi.101ppekovic,
-> #100, pedjak>> A kako bi izgledala ova funkcija mod ? Pojam modula mi je nepoznat,
>> pa bih bio vrlo zahvalan da mi ga neko objasni.
Modul/moduo je ostatak deljenja dva broja.
Paya