[es] - Least denominator

Farenhajt
Goran Kapetanović
Beograd

Član broj: 78132
Poruke: 449
*.tehnicom.net.

+6 Profil

^{08.01.2006. u 12:31 - pre 224 meseci}

Dodatak 3

Na sugestije cenjenog uraniuma, formulišem nekoliko specijalnih slučajeva u kojima treba modifikovati kriterijume upoređivanja verižnih razlomaka, budući da inicijalni zadatak zahteva stroge nejednakosti. Svi slučajevi opisuju završne karike verižnih razvoja i podrazumeva se da pre njih nisu nađene nejednake karike.

Ovde se oba razvoja proširuju kao

, gde je

ceo broj ili verižni razlomak

Slično kao gore, prvi razvoj se proširuje pa imamo

, gde je

ceo broj ili verižni razlomak

Prvi razvoj se proširuje, pa imamo

. Ako je

ceo broj, ovo se za

svodi na

, a za

ne postavlja problem. Ukoliko je

verižni razlomak, prvi razvoj može biti neophodno dodatno proširiti kao

ukoliko prvobitnim proširenjem dobijamo neki od već obrađenih slučajeva.

@Bojan

Od algoritma koji pominješ upravo smo i pošli:

Citat:

Farenhajt:
...zaključujem da bi traženo

trebalo da bude rešenje sistema

(Naravno, uz neophodne modifikacije zbog zahtevanih strogih nejednakosti.) Međutim, od onda se stvar razvila.

_{[Ovu poruku je menjao Farenhajt dana 08.01.2006. u 13:33 GMT+1]}

Odgovor na temu

Bojan Basic
Novi Sad

SuperModerator
Član broj: 6578
Poruke: 3996
*.smin.sezampro.yu.

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253

+605 Profil

Re: Least denominator

^{08.01.2006. u 15:05 - pre 224 meseci}

Pratio sam temu od početka, nikad ne volim da upadam kao s Marsa. Ono što sam pokušao da pitam u prošloj poruci (verovatno se nisam najbolje izrazio), je na osnovu čega znamo da je taj razvijeni algoritam efikasniji od onog trivijalnog i da li bi se možda mogao konstruisati primer gde trivijalni algoritam brže stiže do rešenja od razvijenog?

Ljubičice crvena, što si plava kô zelena trava.

Odgovor na temu

Farenhajt
Goran Kapetanović
Beograd

Član broj: 78132
Poruke: 449
*.tehnicom.net.

+6 Profil

Re: Least denominator

^{08.01.2006. u 16:10 - pre 224 meseci}

Zavisi i šta podrazumevaš pod brzinom. U trivijalnom algoritmu u svakom koraku imaš dve operacije sabiranja i dve operacije poređenja - "dodaj jedno

levo i jedno

desno, pa vidi da li je leva strana strogo manja od celog dela desne strane i desna strana strogo veća od svog celog dela" - ali zato brojčano više koraka (čini mi se), dok u izvedenom algoritmu imaš manje koraka ali više računskih radnji. Sa stanovišta procesorskog vremena, nisam siguran koji je brži.

Međutim, izvedeni je doveo do rezultata s verižnim razlomcima, a taj mi se čini teorijski bitan i verovatno bi se moglo dokazati da je zapravo i najbrži.

_{[Ovu poruku je menjao Farenhajt dana 08.01.2006. u 17:12 GMT+1]}

Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Re: Least denominator

^{08.01.2006. u 19:22 - pre 224 meseci}

Evo da opišem i ja jedan algoritam (koji je verovatno sporiji od svih navedenih).

Neka je

.
Neka nam predikat

označava da li je slučaj problematičan ili ne, tj.

.

Evo ukratko u čemu je ideja - pa ću onda to i formalizovati.

Ako nije

, stvar je gotova - upotrebimo Farenhajtovu formulu.
Ako jeste

, onda uzmimo da je

, pa mora da važi:

. Brojevi,

su susedni članovi Farey-evog niza

. Sada generišemo jedan međučlan

ako je on upao u interval

našli smo broj koji smo tražili, a ako nije postupak nastavljamo sa međučlanom i jednim od prethodnih (zavisno od toga da li je

ili je

. Jasno je da se algoritam kad tad zaustavlja.

Evo sad isto to samo dosadnije

Radi lakšeg izražavanja posmatrajmo i funkciju

, pri čemu je

.

Neka je

. Stavimo da je

. Pretpostavimo da su već definisani svi brojevi

onda:

1. Ako je

tu stajemo - jer je

upravo ono što smo tražili.

2. Ako je

, onda stavimo da je

.

3. Ako je

, onda stavimo da je

.

Jasno je da će postupak u najgorem slučaju trajati dok se ne desi da

Ključna stvar je u tome da za susedne članove Farey-evog niza, pomoću f-je

uvek dobijamo novi (njima susedni) član koji se nalazi između njih a ima najmanji mogući imenilac.

_{[Ovu poruku je menjao uranium dana 08.01.2006. u 21:06 GMT+1]}

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Odgovor na temu

Farenhajt
Goran Kapetanović
Beograd

Član broj: 78132
Poruke: 449
*.tehnicom.net.

+6 Profil

Re: Least denominator

^{09.01.2006. u 03:24 - pre 224 meseci}

Ne deluje sporiji od onog s reciprociranjem, bar na prvi pogled. A računski je daleko jednostavniji

Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Re: Least denominator

^{09.01.2006. u 11:04 - pre 224 meseci}

Samo na prvi pogled izgleda jednostavniji - jer ona f-ja

u stvari krije u sebi f-ju

(verovatno sam loše objasnio, ali sam mislio da se njen output uvek dovede u sveden oblik - a za to bih potrošio jedno

i dva deljenja), a zavisno od načina predstavljanja brojeva

ni ono nalaženje brojioca i imenioca ne mora biti zanemarljivo

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Odgovor na temu