21. září bude sraz! Od 18.00 v restauraci Tradice v Praze u Anděla
Autor Zpráva
janbarasek
Profil
Ahoj,
napadá někoho z vás nějaký dobrý algoritmus, jak zjistit periodu při dělení?

Naprosto každý zlomek, který je zadán jako A/B, přičemž A, B jsou celá čísla, má konečně velkou periodu.

Jak byste periodu zjišťovali automaticky vy? Nemám problém provést výpočet klidně na 100 (i více) desetinných míst a pak v tom nějak hledat. Potřebuji nicméně něco, co mi zaručí to, že nalezená perioda není jenom náhodná skupina čísel, která se sice nějaký čas opakuje, ale po nějaké chvíli přestane, tj. jak velkou oblast následujících čísel má smysl dále testovat?

Jde mi o to, že v současné době velice intenzivně pracuji na nové podobě matematického vyhledávače, který bude umět kvalitně pracovat s výpočty a součástí toho budou nejrůznější numerické nástroje na podrobnou analýzu všeho možného a právě periody mi vrtají hlavou.

Předem děkuji za jakékoli nápady.
Alphard
Profil
stackoverflow.com/questions/8946310/how-to-know-the-repeating-decimal-in-a-fraction
Hloupý algoritmus je hned nahoře (lépe hodnocený :-)), chytrý algoritmus je níže (snad to Daniel Fischer popisuje správně, teď nemám čas to blíže kontrolovat).
Chamurappi
Profil
Reaguji na janabaraska:
Možná bude existovat nějaká chytřejší finta, ale kdesi hluboko v paměti se mi vybavila základní škola a naučený postup, jakým se dají dvě dělit libovolně velká čísla na papíře… myslím takové to rozepisování stromečku ze zbytků pod dělence. Teď jsem našel nějakou stránku pro děti, kde si to jde zkoušet. Očekával bych, že když při tomto postupu narazíš podruhé na stejný zbytek, jsi v periodě.
Keeehi
Profil
janbarasek:
Nemám problém provést výpočet klidně na 100 (i více) desetinných míst
A to děláš jak? Jako na základní škole? Zbytek vynásobit deseti a dělit znovu? Pokud ano tak jakmile už dělíš nějaké číslo (zbytek) podruhé, už to je začátek periody.
Z toho mě teď napadl horní limit na délku periody. Maximální délka periody je rovna děliteli - 1, protože existuje N-1 různých zbytků různých od nuly při dělení číslem N.

Hezké čtení mathworld.wolfram.com/DecimalPeriod.html
janbarasek
Profil
Alphard:
Hloupý algoritmus je hned nahoře (lépe hodnocený :-))
Podobné algoritmy jsem zkoušel, ale jsou zrádné. Občas totiž dělení může vypadat třeba takto:

0.1234561212121212123456789

A asi si můžeš domyslet, že mi to chytne periodu hned na začátku a ignoruje to fakt, že se to po čase může změnit. A vůbec, co když bude vstupem do algoritmu třeba rozvoj čísla Pí? Pak to může najít nějaký opakující se kus a je problém.

Chamurappi:
kdesi hluboko v paměti se mi vybavila základní škola a naučený postup, jakým se dají dvě dělit libovolně velká čísla na papíře
Klasický školní algoritmus "dělení s ocáskem" je dobrý nápad. Vyzkouším to na vzorku pár příkladů a uvidím, jak se to bude chovat. Snad tam nebude nějaká nečekaná zrada.

Keeehi:
Maximální délka periody je rovna děliteli - 1
To je hezké. Až budu kontrolovat nějaké obří číslo, tak se server docela zapotí, když bude prohledávat například tisíc desetinných míst.

A to děláš jak? Jako na základní škole?
V zásadě používám klasický školní algoritmus na dělení "s ocáskem", nicméně jsem ho opatřil mnoha vylepšeními, které zvyšují rychlost výpočtů (třeba tím, že mám k dispozici pole prvočísel a rychle vím, jestli se číslo dělitelné, nebo to nemá smysl). V současně používaném parseru jsem schopen provádět výpočet libovolného vstupu na libovolný počet desetinných míst - momentálně o rozsahu rozhoduje sám algoritmus na základě vytížení serveru, obvykle však počítám na 10 až 100 desetinných míst.
Alphard
Profil
janbarasek:
Podobné algoritmy jsem zkoušel, ale jsou zrádné.
To jsi je (přinejmenším tento) nepochopil. stackoverflow.com/a/8946506 popisuje totéž, co radí kolegové. Problém je ve výpočetní složitosti, pro větší čísla se procesor skutečně zapotí. Hledat opakující se sekvence v nějakém řetězci nikdo neradí, to ani není možné.
Více ti v této chvíli neporadím, touto oblastí teorie čísel jsem se více nezabýval. Jako dobrá vstupní stránka vypadá mathworld.wolfram.com/DecimalExpansion.html.

Mimochodem, trochu jsem na to podíval, protože mě matematické procesory docela zajímají, ale nepočítá ti to ani kvadratické rovnice. Když rovnici zadám ve tvaru x*x+x-1 = 0, ani to nepozná, že je kvadratiká. A když jsem zkusil zadat x^2 = -1, nějak se to odmlčeno. Jestli vše řešíš stylem brutal force v oboru reálných čísel, troufám si tvrdit, že to do použitelného stavu nikdy nedostaneš.
janbarasek
Profil
Alphard:
To jsi je (přinejmenším tento) nepochopil
Ok, už se na to dívám a vyzkouším ten klasický školní algoritmus na dělení.

Problém je ve výpočetní složitosti, pro větší čísla se procesor skutečně zapotí
To není problém, stejně většinu obsahu tahám ajaxově a zpomalení jednoho boxu neovlivní vůbec vyhledávání. Velice brzy totiž zátěž rozložím na několik fyzických strojů a jeden z nich bude jenom pro "náročnější" výpočty.

Mimochodem, trochu jsem na to podíval, protože mě matematické procesory docela zajímají, ale nepočítá ti to ani kvadratické rovnice. Když rovnici zadám ve tvaru x*x+x-1 = 0, ani to nepozná, že je kvadratiká. A když jsem zkusil zadat x^2 = -1, nějak se to odmlčeno. Jestli vše řešíš stylem brutal force v oboru reálných čísel, troufám si tvrdit, že to do použitelného stavu nikdy nedostaneš.
Je tam nahozený starý algoritmus a postupně všechno přepisuji do nového stylu symbolických výpočtů a všemožných rekurzí (ano, matematika je dokonale rekurzivní sama na sebe), zatím jsem se dostal k čistě numerickým výpočtům (už to výsledky vrací jako zlomky, příklad), rovnice budu řešit brzy paralelně s funkcemi (které na tom jsou už o něco lépe).

POZNÁMKA: Myslím, že se to vymyká tématu - nebude pro to lepší založit vlastní vlákno? Určitě existuje mnoho věcí, které by bylo dobré opravit nebo předělat.
Keeehi
Profil
janbarasek:
To je hezké. Až budu kontrolovat nějaké obří číslo, tak se server docela zapotí, když bude prohledávat například tisíc desetinných míst.
Jak psal Alphard, problém je v nepochopení algoritmu. Vstupem totiž není výsledek po dělení, v něm nikdy přesně periodu určit nemůžeš. Vstupem musejí být dělenec a dělitel. Tudíž to není vůbec závislé na počtu desetinných míst výsledku dělení ale na děliteli!
A další věc je, že horní mez délky přírody (dělitel -1) není žádná průměrná doba běhu. Jde o nejhorší scénář doby běhu hloupého algoritmu. Tudíž když budu dělit milionem tak teoreticky ten algoritmus bude muset provést milion cyklů ale ve skutečnosti se zastaví mnohem dříve protože perioda je prostě kratší. A když ten výjimečný případ nastane a při dělení milionem se provede milion cyklů než se najde perioda, tak to taky ale zároveň znamená, že perioda je dlouhá milion desetinných míst. A najít tak dlouhou periodu "jen" na milion průchodů cyklem není zase až tak špatné.
Pokud znáš faktorizaci dělitele tak podle toho odkazu na stackoverflow jde délka periody vypočítat s konstantní složitostí.
Jde tedy o to, zda zvládneš vypočítat faktirizaci dělitele dříve než hloupý algoritmus provede počet cyklů rovný délce periody.

Já bych měl jinou otázku, proč znovu vynalézáš kolo? Nebo jsi nikdy neslyšel o wolframalpha.com?
janbarasek
Profil
Keeehi:
Já bych měl jinou otázku, proč znovu vynalézáš kolo? Nebo jsi nikdy neslyšel o wolframalpha.com?
Slyšel. Proč spolužáci chodí v neděli odpoledne hrát fotbal, když se na něj mohou dívat v televizi?

Wolfram neumí mnoho věcí, které zvládnu naprogramovat. Navíc je to celé v češtině a paralelně s tím "učím" základní "umělou inteligenci" pro další použití. Buď to pochopíš, nebo to nemá smysl dále vysvětlovat.
Keeehi
Profil
janbarasek:
Já to chápu, jen mě zajímala motivace.
bestik_63
Profil
ahoj,
zkus se podívat na internetu na zdroje jak vzniká perioda a jak ji najít. Možná najdeš něco lepšího (nemám moc času). Našel jsem toto : http://www.pf.ujep.cz/files/KMA_studium_AsD2material10.pdf.
Asi nejjednodušší řešení je opravdu dělit jak na základní škole a jakmile najdeš 2 stejné zbytky po dělení, jedná se o periodické číslo. Pak jen zbývá určit přesnost, se kterou to bude počítat (kolikrát se bude dělit, než prohlásíš číslo že je nemožné vypočítat jestli má periodu(snížení záteže, zamezení vzniku cyklů - např. u čísla pí, tam bys počítal asi 100 let a nedobral by ses výsledku).


Ještě mě docvakla jedna věc (jsem dost unavený tak sorry že mě to nedocvaklo hned).
Pokud stačí najít 2 stejné zbytky po dělení, tak ti stačí vždy max. 10x podělit 2 čísla, protože dostaneš 10 zbytků po dělení a mezi nimi vždy najdeš 2 stejné čísla. Takže k nějaké velké zátěži procesoru nikdy nedojde :-)
Keeehi
Profil
bestik_63:
janbarasek se ale zabývá výpočty v oboru racionálních čísel, ne reálných. A každé racionální číslo má buď konečný nebo nekonečný ale periodický desetinný rozvoj. Neexistuje racionální číslo s nekonečným neperiodickým desetinným rozvojem.
janbarasek
Profil
Ok, tak jsem vytvořil speciální box, kde se zobrazuje postup při dělení klasickým školním algoritmem "s ocáskem".

Podívejte se na živou ukázku.

Jak mám dále postupovat? Výstup z programu (pro 3/14) vypadá takto:
0.2142857
 2
  6
   4
    12
     8
      10
       2

Můžete se všimnout opakující se dvojky, nicméně perioda není od první cifry, nicméně až od druhé. Mám to tedy udělat tak, že se program vrátí zpět v řetězci s výsledkem na tuto hodnotu a jen vyznačí periodu? Jedná se takto o spolehlivé řešení?

Díky.
Keeehi
Profil
Vždyť je to správně. Jen ti tam chybí první zbytek což je číslo 3. Kdybys ji tam měl, tak pak je krásně vidět, jak to té periodě přesně odpovídá. A ano, je to spolehlivé řešení.

Vaše odpověď


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm:

0