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

Rastavljanje polinoma na faktore-treba mi pomoc

[es] :: Matematika :: Rastavljanje polinoma na faktore-treba mi pomoc

Strane: < .. 1 2 3

[ Pregleda: 30650 | Odgovora: 54 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dynamic.sbb.rs.



+2789 Profil

icon Re: Rastavljanje polinoma na faktore-treba mi pomoc14.04.2009. u 16:11 - pre 182 meseci
Da, pa? wikipedia nije savršena. Šts s tim?
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

holononi

Član broj: 163572
Poruke: 658
91.148.88.*



+5 Profil

icon Re: Rastavljanje polinoma na faktore-treba mi pomoc14.04.2009. u 17:27 - pre 182 meseci
Pukla mi je veza, dopunio sam prethodnu poruku.

 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dynamic.sbb.rs.



+2789 Profil

icon Re: Rastavljanje polinoma na faktore-treba mi pomoc15.04.2009. u 08:19 - pre 182 meseci
Trenutno nije poznat brži algoritam od algoritma Čudnovskog. Nije bio problem u tome, ali više ne uspevam da nađem taj iskaz. Izgleda da su ga makli.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dynamic.sbb.rs.



+2789 Profil

icon Re: Rastavljanje polinoma na faktore-treba mi pomoc15.04.2009. u 13:59 - pre 182 meseci
Ne mogu sa sigurnošću da tvrdim da li su dali složenost uopšteno u smislu najbržeg poznatog algoritma, ne specificirajući ga, ili su pomenuli i algoritam na koji se to odnosi, ali svakako danas nije poznat alhgoritam koji ima složenost koju su naveli.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

holononi

Član broj: 163572
Poruke: 658
91.148.88.*



+5 Profil

icon Re: Rastavljanje polinoma na faktore-treba mi pomoc15.04.2009. u 23:27 - pre 182 meseci
Citat:
ali svakako danas nije poznat alhgoritam koji ima složenost koju su naveli.

Naprotiv, Bailey, Borwein i Plouffe su konstruisali algoritma za izračunavanje broja Pi vremenske složenosti O( n ) i prostorne složenosti O( ln(n) ). U 25 koraka daje 45 miliona cifara broja Pi. Kad budem imao malo više slobodnog vremena proveriću (ako se dual pentijum ne zapali od tolikog računa).

 
Odgovor na temu

R A V E N
Mirza Beglerović Raven
Tuzla

Član broj: 36142
Poruke: 1629
91.191.8.45

Sajt: NietzscheSource.Org


+101 Profil

icon Re: Rastavljanje polinoma na faktore-treba mi pomoc16.04.2009. u 01:19 - pre 182 meseci
Ohoho,tema se pravo usijala.Uglavnom kako god,naučio sam par stvari.

Citat:
Nedeljko:Izgleda da su ga makli.


Ima u historiji članka.

Citat:
Nedeljko:5 - izvlačenje zaključaka


Često je suština ovakvih zadataka(sa zvjezdicom) primjeniti neki metod iz neke potpuno druge oblasti matematike u odnosu na oblast u koju posmatrani problem spada.

[Ovu poruku je menjao R A V E N dana 16.04.2009. u 02:32 GMT+1]
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dynamic.sbb.rs.



+2789 Profil

icon Re: Rastavljanje polinoma na faktore-treba mi pomoc16.04.2009. u 07:58 - pre 182 meseci
Citat:
holononi: Naprotiv, Bailey, Borwein i Plouffe su konstruisali algoritma za izračunavanje broja Pi vremenske složenosti O( n ) i prostorne složenosti O( ln(n) ). U 25 koraka daje 45 miliona cifara broja Pi. Kad budem imao malo više slobodnog vremena proveriću (ako se dual pentijum ne zapali od tolikog računa).


Ako misliš na ovako nešto



http://en.wikipedia.org/wiki/C...g_Pi#BBP_formula_.28base_16.29
http://en.wikipedia.org/wiki/B...orwein%E2%80%93Plouffe_formula

taj algoritam nema složenost koju pominješ za računanje prvih n decimala broja , već je na toj formuli zasnovan efikasan algoritam za računanje n-te decimale broja . Vidi

http://en.wikipedia.org/wiki/C...ng_pi#Digit_extraction_methods

Kako inače misliš da postigneš prostornu složenost koja je ispod linearne, kada rezultat zauzima linearno mnogo prostora? Izdvajanje jedne cifre je druga stvar.

Inače, najbrži programi za računanje broja za koje znam, a koje možeš naći za Windows su PiFast i QuickPi.

http://numbers.computation.fre...onstants/PiProgram/pifast.html
http://members.shaw.ca/francislyster/pi/pi.html
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

holononi

Član broj: 163572
Poruke: 658
91.148.93.*



+5 Profil

icon Re: Rastavljanje polinoma na faktore-treba mi pomoc16.04.2009. u 08:45 - pre 182 meseci

Drago mi je da se i ti pozivaš na Wikipedia.

To je upravo ono što sam imao na umu. JAVNOST je najveći autoritet. Veći od bilo kakvih doktorata i ko zna kakvih diploma i počasti uručenih u polumračnim kancelarijama. U tom smislu je Wikipedia autoritet koji se uvek mora respektovati. Jer stranice Wikipedia dnevno posećuje možda i na milione ljudi širom sveta. Pred tolikom navalom autor će teško doživeti jutro pišući gluposti. Uostalom i ovu našu prepisku prate mnogi sa strane, pozdrav @R A V E N i ostalima koji samo prate (za sada).

PS
Stavovi koje sam izneo u vezi algoritama za izračunavanje broja Pi zasnovani su na originalnim tekstovima autora od pre 10-tak godina a ne na Wikipedia materijalu.

 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dynamic.sbb.rs.



+2789 Profil

icon Re: Rastavljanje polinoma na faktore-treba mi pomoc16.04.2009. u 10:21 - pre 182 meseci
Čekaj, gde sam ja napisao da je vikipedija loša? Je li ovde

Citat:
Nedeljko: Wikipediju smatram odličnom enciklopedijom, ali svakako ne smatram da joj se može slepo verovati i da se sve sa nje može nekritički prihvatati. Člankena njoj pišu ljudi koji misle da nešto znaju. No, i pored toga ona je dosta kvalitetnija od konkurentskih, ali svakako da nijedan izvor ne pomaže protiv nerazumevanja.


Dakle, daleko od toga da je loša, ali nije za slepo prihvatanje, kao ni drugi izvori, a univerzitetski udžbenici i prava stručna literatura bi trebali da budu kredibilniji izvori od vikipedije.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dynamic.sbb.rs.



+2789 Profil

icon Re: Rastavljanje polinoma na faktore-treba mi pomoc16.04.2009. u 10:27 - pre 182 meseci
Citat:
holononi: Stavovi koje sam izneo u vezi algoritama za izračunavanje broja Pi zasnovani su na originalnim tekstovima autora od pre 10-tak godina a ne na Wikipedia materijalu.


Po svoj prilici ih nisi razumeo. Daj da ih pogledamo. Ne možeš na spektrumu da izračunaš milion decimala npr. broja e, kad spektrum ne može čak ni da memoriše toliki rezultat. Idvajanje jedne cifre je nešto drugo. Takođe, i u naučnim radovima ima grešaka, ali ne verujem da je to slučaj, jer bi to bila početnička greška (da bilo prostorna bilo vremenska složenost izračunavanja bude niža od prostorne složenosti rezultata). BBP je poznat algoritam u matematici po izdvajanju n-te cifre broja , pri čemu n može daleko da prevazilazi broj bajtova memorije računara.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

holononi

Član broj: 163572
Poruke: 658
91.148.80.*



+5 Profil

icon Re: Rastavljanje polinoma na faktore-treba mi pomoc17.04.2009. u 08:31 - pre 182 meseci
Citat:
Po svoj prilici ih nisi razumeo. Daj da ih pogledamo.

Kako @Nedeljko tvrdi da BBP algoritam računa n-tu cifru broj Pi, dok autori algoritma u svom tekstu tvrde da ne samo što njihov algoritam računa n-tu cifru broja Pi, već i da su izračunali broj Pi na 45 miliona cifara u 25 koraka, pokušao sam da proverim imali tu istine. Program sam napisao u JavaScript-u i rezultati su sledeći:

Broj iteracija 1, rezultat Pi = 3.1333333333333333
Broj iteracija 2, rezultat Pi = 3.1414224664224663
Broj iteracija 3, rezultat Pi = 3.1415873903465816
Broj iteracija 4, rezultat Pi = 3.1415924575674356

Da, autori se izgleda nisu šalili, ovo zaista liči na Pi. Nedostatak programa koji sam testirao je u tome što je sklepetan u par minuta pa verujem da bi mogao da proizvede i bolje rezultate, što prepuštam radoznalima.

Nisam to hteo da pominjem u prethodnim postovima, ali kad smo već razvukli diskusiju, za izračunavanje broja Pi postoje i FFT algoritmi. Poznato je da je složenost FFT algoritama reda O( n log(n) ) pa je moguće da su autori članka u Wikipedia, koju @Nedeljko kritikuje, upravo imali na umu takve algoritme.

 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
195.222.97.*



+2789 Profil

icon Re: Rastavljanje polinoma na faktore-treba mi pomoc17.04.2009. u 10:39 - pre 181 meseci
Svi članovi tog reda su pozitivni realni brojevi. Opšti član je

,

pri čemu k ide od nule. 26-ti član se dobija za k=25 i iznosi preko pa je samim tim i ostatak parcijalne sume prvih 25 članova veći od toliko (nije mnogo veći), što znači da je to dovoljno za dobijanje broja sa tačnošću od 33 decimale.

Ovaj red u svakoj iteraciji daje malo više od jedne dekadne cifre tačnosti, kao što tvoj račun i pokazuje. Za dobijanje 45000000 decimala ti treba nekih 37 miliona članova ovog reda.

Naravno, ova formula se pomoću algoritma binarnog preplitanja Čudnovskog (binary splitting algorithm) za sumiranje konačnih suma može iskoristiti za konstrukciju efikasnog algoritma složenosti . Tim algoritmom se prvih 37 miliona članova reda sumira u 25 iteracija algoritma binarnog preplitanja Čudnovskog. To je drugo.

http://en.wikipedia.org/wiki/Binary_splitting

Svi poznati algoritmi te složenosti koriste ili FFT ili njenog rođaka NTT (Number theoretical transform) za množenje sa složenošću , preko kojeg se realizuju delenje (i po potrebi korenovanje) sa složenošću .

Hajde ti lepo šibni tu referencu, pa da vidimo šta tačno piše. Članak nije dovoljno imati, već se mora i razumeti.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

holononi

Član broj: 163572
Poruke: 658
*.adsl.beotel.net.



+5 Profil

icon Re: Rastavljanje polinoma na faktore-treba mi pomoc17.04.2009. u 13:03 - pre 181 meseci
@Nedeljko
Opet menjaš priču. Tvrdio si da BBP algoritam ne izračunava broj Pi već

Citat:
na toj formuli zasnovan efikasan algoritam za računanje n-te decimale broja Pi


Ipak, izgleda da BBP može oboje.



 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
195.222.97.*



+2789 Profil

icon Re: Rastavljanje polinoma na faktore-treba mi pomoc18.04.2009. u 10:31 - pre 181 meseci
Da, na toj formuli jeste zasnovan efikasan algoritam za heksadekadnih cifara broja . Pa, gde sam ja to napisao da se na toj formuli ne može zasnovati algoritam za računanje prvih n cifara tog broja? Naravno, algoritmi koji daju različite izlaze su različiti.

Citat:
Nedeljko: taj algoritam nema složenost koju pominješ za računanje prvih n decimala broja , već je na toj formuli zasnovan efikasan algoritam za računanje n-te decimale broja .


Dakle, reč je o složenosti izračunavanja, tj o ovome

Citat:
holononi: Naprotiv, Bailey, Borwein i Plouffe su konstruisali algoritma za izračunavanje broja Pi vremenske složenosti O( n ) i prostorne složenosti O( ln(n) ). U 25 koraka daje 45 miliona cifara broja Pi. Kad budem imao malo više slobodnog vremena proveriću (ako se dual pentijum ne zapali od tolikog računa).


Daleko od toga da postoji ikakav algoritam za bilo šta čija je prostorna složenost manja od prostorne složenosti rezultata ili čija je vremenska složenost manja od prostorne.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
195.222.97.*



+2789 Profil

icon Re: Rastavljanje polinoma na faktore-treba mi pomoc20.04.2009. u 18:21 - pre 181 meseci
Evo još jednog propusta na Wikipedia-i: Na stranici o forsingu

http://en.wikipedia.org/wiki/Forcing_(set_theory)

nigde se ne pominje uslov cepanja, to jest da od svakog uslova p postoje jači uslovi q,r, koji su nekompatibilni, odnosno takvi da ne postoji uslov s koji je jači i od q i od r. Bez toga (tj. samo iz aksioma parcijalnog uređenja) se ne može dokazati da generički filter ne pripada modelu. Standardan dokaz ne prolaza jer skup ne mora biti gust, a ima i kontraprimer je bilo koje konačno uređenje i skup , gde je bilo koji minimalni element, G jeste generički filer jer svaki gust skup mora da sadrži p.

Sličan propust je načinjen na stranici o bulovsko-vrednosnim modelima, gde nema uslova bezatomičnosti Bulove algebre.

http://en.wikipedia.org/wiki/B...an-valued_models_of_set_theory

Pominje se slabiji i nedovoljan uslov da je Bulova algebra beskonačna.


Da se razumemo, wikipedija je odlična, ali nije idealna, niti za slapo verovanje, a izgleda i da "doktorati iz polumračnih prostorija" ipak vrede više.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

[es] :: Matematika :: Rastavljanje polinoma na faktore-treba mi pomoc

Strane: < .. 1 2 3

[ Pregleda: 30650 | Odgovora: 54 ] > FB > Twit

Postavi temu Odgovori

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