Algorithmensammlung: Zahlentheorie: Signum

Algorithmensammlung: Zahlentheorie

• Euklidischer Algorithmus
• Sieb des Eratosthenes
• Primfaktorisierung
• Fibonacci-Folge
• Quadratwurzel mit Rest
• Goldener Schnitt
• Signum

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

${\text{sgn}}(x)={\begin{cases}1&{\text{falls }}x>0\\0&{\text{falls }}x=0\\-1&{\text{falls }}x<0\end{cases}}$

C

Der GCC 10.1 erzeugt ab Intel Core2 / AMD K8 (Athlon 64) und eingeschalteter Optimierung (außer -Os) aus folgender Funktion Code ohne Sprünge (branchless code):

int sign(int num)
{
  if(num > 0){
    return 1;
  } 
  else if(num < 0){
    return -1;
  }
  else{
    return 0;
  }
}

FreePascal

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.