Matematické Fórum

kexixex · 20. 07. 2013 21:13

Ahoj,
snazim se naprogramovat aritmetiku pro libovolne velka nezaporna cisla. Uz mam scitani, odcitani nasobeni, deleni se zbytkem a mocneni, ze zakladnich operaci mi zbyva akorat odmocneni (tedy presneji dolni cela cast odmocniny). Nikde na internetu jsem nenasel zadny zarucene rychly algoritmus a napada me jen toto:

Odhad: $x_{1}:=k^{floor(\frac{log_{k}N}{2})}\le \sqrt{N}\le k^{^{ceiling(\frac{log_{k}N}{2})}+1}=:x_{2}$ , kde k je zaklad soustavy v niz pocitam a N je odmocnovane cislo, floor je dolni cela cast;ceiling je horni cela cast. Logaritmus mam hned jako pocet cifer.

napadlo me postupne umocnit vsechna cisla mezi x1 a x2 na druhou a jakmile najdu takove x, ze $x^{2}\ge N$ , vratim x-1 a dostanu dolni celou cast odmocniny. Pripadne by se dala cisla mezi x1 a x2 prochazet pulenim intervalu, cimz bych vyrazne zlepsil cas. Take bych jiste mohl zrychlit nasobeni.

Problem je, ze se mi zda algoritmus stejne docela pomaly (pouzivam zaklad 2^16) - nevite nekdo, jestli existuje nejaky lepsi algoritmus? Napriklad nejak pouzit newtonovu metodu bez racionalnich cisel?

Diky za jakekoliv tipy...

Formol · 23. 07. 2013 15:06

První nástřel z hlavy: Předpočítaná tabulka (násobení máš) a následná interpolace několika bodů polynomem. To by ale asi při přímočaré implementaci nedávalo moc hezké výsledky, takže jsem se podíval na internet a našel jsem několik inspirací.

kexixex · 23. 07. 2013 18:26

↑ Formol:
Diky za odpoved.. Kdyz jsem cetl wikipedii pred zadanim dotazu, nenasel jsem tam ten spravny algoritmus. Ted uz ano. :)

Matematické Fórum

#1 20. 07. 2013 21:13

odmocnina

#2 23. 07. 2013 15:06

Re: odmocnina

#3 23. 07. 2013 18:26

Re: odmocnina

Zápatí