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;
{X=zaklad, 1/N=exponent, ITER=pocet iteraci}
var h,d,v,k:real;
    i:integer;
begin
 h:=x;{Horni mez}
 d:=0;{Dolni mez}


 v:=x/2; {Polovina}
 k:=pow(v,n); {Kontrola}


 for i:=1 to iter do
  begin
   if (k>x) then
    begin
     h:=v; {Horni je v, dolni zustava}
     v:=v-((h-d)/2);
    end
   else
    begin
     d:=v; {Dolni je v, horni zustava}
     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í.