Matematické Fórum

Ahoj,

co myslíš tím odmocňováním? Odmocňováním bych chápal algoritmus, který zjistí odmocninu daného čísla. Jenže to je přesně to, co ty chceš.

Pro odmocňování se používá často algoritmus, kterému je jedno, jestli máš číslo, které je druhou mocninou přirozeného čísla, nebo jiné číslo. Chceš teda najít nějaký efektivnější algoritmus, který využije té znalosti?

ako uz povedal ↑ Pavel Brožek: je dost nejasne co je vlastne zakazane pouzit.

Najlepsie vyuzije znalost toho ze je to druha mocnina "tabulkova metoda". Ulozis si do tabulky vsetky druhe mocniny max. 15 cifernych cisel a potom ked dostanes cislo, kt. chces odmocnit, tak ho iba hladas v tabulke. Kedze v nej su cisla ulozene podla velkosti, tak ju vies prehladavat v logaritmickom case.
Toto ale moze byt dost narocne na pamat, hlavne ak by si neskor chcel odmocnovat aj viacciferne cisla.

- ale aj takato metoda je de facto odmocnovanie a s istymi trikmi sa takto da odmocnovat aj necelociselne

Este viac "odmocnovacia" by bola metoda "celociselneho odmocnovania" t.j. funkcia . Ocividne plati takze by to robilo to co chces.

Algoritmus na Newtonovu metodu pre nu je napr. takyto: (Nie tak uplne - vid EDIT2)
------------------------------------------------
N # cislo co chceme odmocnit
x=radovy_odhad_odmocniny(N)

repeat
y=N div x
x=(x+y) div 2
until x=y

return x
------------------------------------------------
tato metoda je dost rychla. Ak a pociatocny odhad je niekde v tak potrebujes maximalne zhruba iteracii, co je v tvojom pripade najviac 6. Ak by si mal prvy odhad velmy zly, povedzme zoberies , tak to zo zaciatku bude to cislo polit, kym sa nedostane zhruba do toho intervalu co by bolo max. nejakych 50 iteracii naviac. Nechce sa mi ten odhad moc spresnovat, lebo tvrdis, ze radovo tu odmocninu vies - co ani nie je take tazke, staci sa pozriet na pocet cifier a ten predelit dvomi a to uz viac menej staci.

Celkovo by som tym chcel povedat to, ze ak vymyslis nieco trikove co viac vyuziva celociselnost vysledku, tak by to malo byt rychlejsie ako toto. Ta metoda co som uviedol ako prvu rychklejsia je, ale je to na ukor pamate, tak treba presnejsie stanovit ake vlastne mas obmedzenia.

Ak by si chcel nejak seriozne optimalizovat strojovy cas (nie len algoritmicku zlozitost) tak s tym bohuzial nepomozem, lebo ako ma jadro implementovane jednotlive funkcie neviem a teda ani neviem ake su rychle.

EDIT: trochu som zneistel. Je mozne, ze ten algoritmus by mohol zlyhat ak by nebola druha mocnina nejakeho cisla, t.j. ze by nenasiel dolnu celu cast odmocniny, lebo by to tam okolo nej oscilovalo. Ale myslim, ze za predpokladu, ze sa jedna naozaj o druhu mocninu cohosi, by to nemalo nastat.

EDIT2: predsa som bol prilis skoro nadseny, ked som v tom algoritme pouzil celociselne delenie. Tak sa to moc neda - blblo by to. Treba to obabrat bud tym, ze sa pouzije presne delenie v racionalnych cislach, alebo delenie s dostatocnou presnostou - ak sa nemylim, tak zhruba na tolko desatinnych miest s kolko cifernymi cislami robis. A potom zastavovacia podmienka bude . Ale kedze neviem, ci taketo nieco je to co hladas, tak to uz necham tak.