Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

ispitivanje slozenosti prirodnog broja

[es] :: Art of Programming :: ispitivanje slozenosti prirodnog broja

[ Pregleda: 4285 | Odgovora: 16 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

qzqzqz

Član broj: 66936
Poruke: 219
*.ptt.yu.



Profil

icon ispitivanje slozenosti prirodnog broja03.05.2006. u 12:46 - pre 217 meseci
Kao sto sam i rekao zanimaju me neki najbrzi algoritmi(ili kodovi u C++) koji ispituju slozenost proizvoljnog prirodnog broja.
 
Odgovor na temu

stf

Član broj: 51276
Poruke: 65
*.152.eunet.yu.



Profil

icon Re: ispitivanje slozenosti prirodnog broja03.05.2006. u 14:05 - pre 217 meseci
Pa, jednostavno ako je broj n deljiv sa nekim brojem u intervalu [2,round(sqrt(n))] onda je složen, a u suprotnom prost.
If you don't live for something, you will die for nothing.
 
Odgovor na temu

qzqzqz

Član broj: 66936
Poruke: 219
*.ptt.yu.



Profil

icon Re: ispitivanje slozenosti prirodnog broja03.05.2006. u 14:56 - pre 217 meseci
To se cak moze poboljsati tako sto se medju deliocima tog broja ne proveravaju svi prirodni brojevi u intervalu nego samo prosti, sto zahteva neku rekurziju. Ali mene zanima nesto brze, kao sto sam i rekao.
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: ispitivanje slozenosti prirodnog broja03.05.2006. u 16:08 - pre 217 meseci
Uvijek mozes precomputati tablicu prostih brojeva do nekih granica i uz pomoc nje provjeravati.
Ovo je ujedno i najbrze rijesenje.
 
Odgovor na temu

qzqzqz

Član broj: 66936
Poruke: 219
*.ptt.yu.



Profil

icon Re: ispitivanje slozenosti prirodnog broja03.05.2006. u 16:19 - pre 217 meseci
A zasto ne postoji brze resenje?
 
Odgovor na temu

emiraga

Član broj: 54285
Poruke: 32
217.199.142.*



Profil

icon Re: ispitivanje slozenosti prirodnog broja03.05.2006. u 17:11 - pre 217 meseci
http://en.wikipedia.org/wiki/Integer_factorization
nalazi se dosta linkova na razlicite algoritme, vrijedi pogledati.

http://en.wikipedia.org/wiki/Primality_test
mozda je ovo vise ono sto tebi treba,
pogledaj tamo recenicu i link sto pise o radu: "Manindra Agrawal, Nitin Saxena and Neeraj Kayal"

[Ovu poruku je menjao emiraga dana 03.05.2006. u 18:16 GMT+1]
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: ispitivanje slozenosti prirodnog broja03.05.2006. u 18:30 - pre 217 meseci
Citat:
qzqzqz: A zasto ne postoji brze resenje?

logicki nemoguce

koliku brzinu ti zelis???
 
Odgovor na temu

cynique
Ivan Štambuk
Zagreb@Croatia

Član broj: 93690
Poruke: 155
193.198.17.*

ICQ: 106979934
Sajt: istambuk.blogspot.com


Profil

icon Re: ispitivanje slozenosti prirodnog broja04.05.2006. u 02:15 - pre 217 meseci
Citat:
qzqzqz: A zasto ne postoji brze resenje?


Zato jer, da si pročitao članak na wikipediji, vidio bi da je faktorizacija integera jedan od onih bolesnijih problema za koje se ni ne zna da li su u P ili NP klasi (sl. npr problemu provjere da li su dva grafa izomorfna - brutforsanje svih bijekcija među skupovima vrhova jest jedini potpuno točan način).

Sve što možeš jest pronaći neki gotovi algo koji su smislili puno veći mozgovi od tebe a koji reducira prostor pretraživanja što je moguće više i nadati se da je dovoljno brz za tvoje potrebe. Gore su ti linkovi, počni kopati ;)
 
Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.12.*



+1 Profil

icon Re: ispitivanje slozenosti prirodnog broja04.05.2006. u 02:37 - pre 217 meseci
Najbrze ti je da ispitujes da li je deljiv prostim brojevima od 2 do koren iz n, a proste brojeve nadji preko eratostenovog sita.
Math is like love. A simple idea but it can get complicated.
 
Odgovor na temu

qzqzqz

Član broj: 66936
Poruke: 219
*.ptt.yu.



Profil

icon Re: ispitivanje slozenosti prirodnog broja04.05.2006. u 09:20 - pre 217 meseci
Citat:
NrmMyth: logicki nemoguce

koliku brzinu ti zelis???


ja hocu najmanju mogucu, ako postoji, ili dokaz da ona ne postoji. Kao sto je i rekao cynique to je jos otvoren problem.

Citat:
cynique:Sve što možeš jest pronaći neki gotovi algo koji su smislili puno veći mozgovi od tebe a koji reducira prostor pretraživanja što je moguće više i nadati se da je dovoljno brz za tvoje potrebe. Gore su ti linkovi, počni kopati ;)


Ma mene su i zanimali gotovi algoritmi koje sam i dobio. Zato vam se puno zahvaljujem.


Citat:
cassey: Najbrze ti je da ispitujes da li je deljiv prostim brojevima od 2 do koren iz n, a proste brojeve nadji preko eratostenovog sita.


Opet isto ako kazes da je nesto najbrze onda postoji i dokaz za to. Jeste da to logicki izgleda ok, ali sta mislis da se nadje relativno jednostavna formula koja generise proste brojeva, sa kojom bi to islo brze.
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: ispitivanje slozenosti prirodnog broja04.05.2006. u 10:31 - pre 217 meseci
Citat:
qzqzqz: Opet isto ako kazes da je nesto najbrze onda postoji i dokaz za to. Jeste da to logicki izgleda ok, ali sta mislis da se nadje relativno jednostavna formula koja generise proste brojeva, sa kojom bi to islo brze.

Ako imas tabelu prostih brojeva od [0, 100] onda mozes u kratkom vremenu provjeriti dali je tvoj broj koji je iz [0, sqr(100)] slozen ili ne.
A tabelu ces samo jednom generirati i imati precomputanu na koristenje tvom programu.

I ako postoji takva neka funkcija, ako vec ne postoji, tesko da cemo je mi izvesti i dokazati...
 
Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*



+1 Profil

icon Re: ispitivanje slozenosti prirodnog broja04.05.2006. u 12:29 - pre 217 meseci
Razumem ja sa ti hoces da pitas ali sta ce to tebi. Da imas dokaz sigurno, kao sto imas i dokaz da sort ne moze przeod NlogN ali to da bi razumeo treba ti dosta teorije...
Math is like love. A simple idea but it can get complicated.
 
Odgovor na temu

qzqzqz

Član broj: 66936
Poruke: 219
*.ptt.yu.



Profil

icon Re: ispitivanje slozenosti prirodnog broja04.05.2006. u 12:38 - pre 217 meseci
Takav mi je odgovor trebao. Znaci do sad je najbrzi ovaj sa eratostenovim sitom, jel da?
 
Odgovor na temu

ntojzan
Sandor II Tojzan
Becej

Član broj: 36657
Poruke: 168
*.bbtec.net.



Profil

icon Re: ispitivanje slozenosti prirodnog broja05.05.2006. u 02:16 - pre 217 meseci
Nije. Ja sam skontao jednu foru da se dosta ubrza stvar.

Radi se o tome da se sa jednim deljenjem moze eliminisati veliki postotak brojeva. Recimo da je broj koji izucavamo X. Imamo jednu konstantu, koju cemo nazvati Y. :-) Y mozes sam definisati, sto je veci, veca je efikasnost, ali se takodje i povecava lookup-tabela koju ces koristiti. Y se racuna na sledeci nacin:

Y = 2 * 3 * 5 * 7 ....

Dakle mnozimo proste brojeve.

E sad. Ukoliko X podelimo sa Y, i ostatak je 0 ili deljiv sa nekim od sastavnih brojeva Y (brojeva koje smo pomnozili), broj koji izucavamo nije prost broj, posto je i on deljiv sa istim sastavnim brojem.

Mozda nisam bas jasan, pa evo mali primer:

Y = 2 * 3 = 6

N = X mod Y = X mod 6

ako je N = 0, 2, 3 ili 4, onda broj nije prost. Dakle jednim deljenjem smo eliminisali 66.67% brojeva.

Sledeci slucaj:

Y = 2 * 3 * 5 = 30

N = X mod Y

ako je N = 0, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27 ili 28, onda X nije prost broj.
U ovom slucaju smo eliminisali 73.33% brojeva sa jednim deljenjem.

Vrednosti koje oznacavaju slozene brojeve mozemo pamtiti kao bit array, dakle table ce zauzeti Y / 8 bajtova.

Na primer ako uzmemo proste vrednosti do 23, Y ce biti 223092870, dakle velicina tabele je nesto vise od 26 megabajta. Naravno ovo nece puno znaciti ako je broj zaista prost, ali ce pomoci za eliminaciju slozenih brojeva. A mogu se koristiti i dva (ili vise) deljenja, da bi se ustedelo na memoriji, u tom slucaju bi bilo:

Y1 = 2 * 5 * 11 * ...
Y2 = 3 * 7 * 13 * ...
 
Odgovor na temu

qzqzqz

Član broj: 66936
Poruke: 219
*.ptt.yu.



Profil

icon Re: ispitivanje slozenosti prirodnog broja05.05.2006. u 13:49 - pre 217 meseci
moze i da se proverava da li je . Ako jeste onda je prost, u suprotnom je slozen. Mada ne znam koliko je ovo efikasno za velike .



[Ovu poruku je menjao qzqzqz dana 05.05.2006. u 14:57 GMT+1]
 
Odgovor na temu

emiraga

Član broj: 54285
Poruke: 32
217.199.142.*



Profil

icon Re: ispitivanje slozenosti prirodnog broja05.05.2006. u 22:10 - pre 217 meseci
Informaciju da li je neki broj prost ili nije (bez faktorisanja)
moguce je dobiti u polinomijalnom vremenu
http://en.wikipedia.org/wiki/AKS_primality_test

(nadam se da se ne ljutite na mene sto samo lijepim samo linkove od wikipedije)

Evo i nekih implementacija [nije wikipedia]
http://fatphil.org/maths/AKS/#Implementations
 
Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.11.*



+1 Profil

icon Re: ispitivanje slozenosti prirodnog broja11.05.2006. u 01:34 - pre 217 meseci
Da (izvinjavam se zbog predjasnjeg odgovora - nisam procitao da tebe bas zanima najbrzi algoritam). Da postoje neki algoritmi koji imaju plimijalnu slozenost ali se vecina njih zasniva na verovatnoci. O toe mozes da njadje dosta u neki knjigama o RSA i tome slicno. A evo i ja sam zaheftao jedan mali pdf....
Math is like love. A simple idea but it can get complicated.
Prikačeni fajlovi
 
Odgovor na temu

[es] :: Art of Programming :: ispitivanje slozenosti prirodnog broja

[ Pregleda: 4285 | Odgovora: 16 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.