 |
Een algoritme voor derdemachts wortels |  |
 |
Er is overeenkomst met de vierkantswortel. [ziehier].
Als N = root3 + rest, dan levert het programma de waarde root en de rest.
 |
 |
Theorie
Beschouw N als groepjes van 3 bits, geteld van rechts.[ab]2 = 2a + b
(2a+b)3 = 8a3 + 12a2 + 6ab2 + b3.
Bij de start is a=0 and "1" wordt afgetrokken van het rechter bit van het hoogste groepje (van 3) in N.
Dan a=1, N is verminderd met 8a3 = [1000]2.
Nu moet bit b gevonden worden: b=1 als 12a2b + 6ab2 + b3 van N kan worden afgetrokken.
Dat levert [a1]2 als (b=1) of [a0]2 als (b=0).
Dus, om het volgende bit (b) te vinden moet steeds 12a2b + 6ab2 + b3 van N worden afgetrokken.
omdat b=1 is deze aftrekker :
12a2 + 6a + 1 = [a0]([a0] + 1)*3 + 1.
Opmerking: [a0]2 = 2a.
Elke poging levert een nieuw bit op van a.
In geval van 30 bit getallen moeten bovenstaande stappen 10 keer worden herhaald.
De derdemachts wortel is maximaal 10 bits groot.
Opmerking: Derdemachts wortels kunnen ook uit negatieve getallen worden getrokken.
Het programma
function CubeRoot(N : longInt; var rem : longInt) : smallInt;
// -1,073,741,823 <= N <= 1,073,741,823
//return integer cube root of N and remainder rem
const max = 1073741824;
var NX,sub,r2 : longInt;
root : word;
p : shortInt;
neg : boolean;
begin
if (N <= -max) or (N >= max) then
begin
result := 0;
rem := N;
exit;
end;
if N < 0 then begin
N := -N;
neg := true;
end else neg := false;
p := 30;
root := 0;
repeat
r2 := root shl 1;
sub := r2*(r2+1)*3+1;
sub := sub shl p;
root := root shl 1;
NX := N - sub;
if NX >= 0 then
begin
N := NX;
root := root or 1;
end;
p := p - 3;
until p < 0;
if neg then begin
root := -root;
N := -N;
end;
result := root;
rem := N;
end;
procedure TForm1.GoBtnClick(Sender: TObject);
var N,rem : longInt;
root : smallInt;
begin
if length(numberEdit.Text) = 0 then numberEdit.Text := '0';
N := strtoInt(numberEdit.Text);
root := cubeRoot(N,rem);
rootLabel.Caption := inttostr(root);
remainderlabel.Caption := inttostr(rem);
end;
procedure TForm1.FormKeyPress(Sender: TObject; var Key: Char);
var OK,mt : boolean;
begin
OK := false;
with numberEdit do
begin
mt := length(text) = 0;
case key of
#8 : OK := true;
'1'..'9' : OK := true;
'0' : OK := not(mt);
'$' : OK := mt;
'a'..'f' : OK := text[1] = '$';
'-' : OK := mt;
end;
if OK = false then key := #0;
end;
end;
end.
download cube root program download cube root project
