int21h
N-tá odmocnina z x
Nedávno se na PCsvětě řešila tato otázka. Je to celkem zajímavé téma, protože i když je to celkem užitečná funkce, tak jsem ještě nikde neviděl implementaci.
Nejlepší řešení je v jazyku Python, kde můžete použít funkci na mocninu a umocnit na realné číslo, takže x^(1/N).
Bohužel něco takového od Pascalu nemůžeme chtít, tak si to musíme napsat sami.
Trošku jsme nad tím doma popřemýšleli s bratrem (tzn: brácha to vymyslel, já se tím chlubím :) a zjistili jsme, že asi jediná metoda je půlení intervalu.
Algoritmus je asi takový:
Chceme zjistit N-tou odmocninu čísla X
Máme horní a dolní mez intervalu.
Střed S tohoto intervalu umocníme na N-tou do V a
pokud je výsledek větší než X, tak do horní hranice uložíme S a dolní necháme být a od V odečteme polovinu intervalu
pokud je výsledek menší než X, tak do dolní hranice uložíme S a horní necháme být a k V přičteme polovinu intervalu
Tohle děláme tolikrát, jaký je počtet iterací.
K tomu potřebujeme funkci mocniny. Ta je celkem jednoduchá, ale nevýhoda té mojí následující je rychlost:
function pow(x:real;n:integer):real;
var i:integer;
f:real;
begin
f:=1;
for i:=1 to n do
f:=f*x;
pow:=f;
end;
Pokud by šlo o rychlost, tak by možná šla přepsat do assembleru, ale pro běžné počty to stačí.
Tak a teď funkce:
function odm(x:real;n:integer;iter:integer):real;
var h,d,v,k:real;
i:integer;
begin
h:=x;
d:=0;
v:=x/2;
k:=pow(v,n);
for i:=1 to iter do
begin
if (k>x) then
begin
h:=v;
v:=v-((h-d)/2);
end
else
begin
d:=v;
v:=v+((h-d)/2);
end;
k:=pow(v,n);
end;
odm:=v;
end;
Nevýhoda této implementace je, že se každé číslo počítá stejně dlouho (pod stejným odmocnitelem), protože nemá žádný bailout.
To je jedna z věcí, které by se daly ošetřit.
Příkládám ještě takovou nic neříkající tabulku, kterou jsem naměřil na mojí 486DX/66Mhz:
1000^(1/3)
Kolikrat Cas Operace
10000x 44.37s 0.004437s
1000^(1/5)
Kolikrat Cas Operace
10000x 56.42s 0.005642s
1000^(1/15)
Kolikrat Cas Operace
10000x 109.08s 0.010908s
Tak to je vše. Doufám, že vám to někdy pomůže, nebo ušteří čas k vymýšlení důležitějších věcí.
2006-11-30 | BOby && Jasco
Datum: 6.7.2011 17:00
Od: m@rtlin
Titulek: :-D
Zdravim, nebylo by rychlejší použít (myslím, že se tomu tak říká) Newtonovu formuli?
Jaks psal, cheš spočítat toto: vysledek=zaklad^(1/exponent)
Po zlogaritmování a pár úpravách se dostaneš do tvaru:
vysledek=e^((1/exponent)*ln zaklad)
tedy
vysledek:=exp((1/exponent)*ln(zaklad));
GL, m@rtlin