Zjištění periody při dělení zlomku

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).

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ě.

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:
„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:
„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:
Já to chápu, jen mě zajímala motivace.

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 :-)

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.

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í.