Algorithmensammlung: Zahlentheorie: Signum

Aus Wikibooks
Zur Navigation springen Zur Suche springen

Algorithmensammlung: Zahlentheorie

Die Signum-Funktion („ Vorzeichenfunktion“) ist definiert als

FreePascal[Bearbeiten]

FreePascal liefert in math.sign bereits eine Signumfunktion mit.

type
	signumCodomain = -1..1;
 
{**
	returns the sign of an integer
	
	\param x the integer to inspect
	\return 1 on positive integers, 0 on zero,
	        and -1 on negative integers
}
function signum({$ifndef CPUx86_64} const {$endif} x: longint): signumCodomain;
{$ifdef CPUx86_64}
assembler;
{$asmMode intel}
asm
	xor rax, rax         // ensure result is not wrong, because of residue
	
	test x, x            // x = 0 ?
	setnz al             // al := not ZF
	
	sar x, 63            // propagate sign-bit throughout register
	cmovs rax, x         // if SF then rax := -1
end;
{$else}
begin
	// This is what virtually math.sign does.
	// The compiled code requires _two_ cmp instructions, though. 
	if x > 0 then
	begin
		signum := 1;
	end
	else if x < 0 then
	begin
		signum := -1;
	end
	else
	begin
		signum := 0;
	end;
end;
{$endif}

Generell will man die test-Instruktion nutzen. Während die cmp-Instruktion tatsächlich rechnet, also einen Tucken länger braucht, ist die test-Instruktion ein banales and, anhanddessen Ergebnis die Flaggen gesetzt werden. Zudem kommt die asm-Implementation ohne Sprünge aus, was der BPU (“branch prediction unit”) zugute kommt.