Wurzel ziehen von Hand



  • Gibt es noch schnellere Methoden, die Wurzel auszurechnen als das Babylonische Wurzelziehen, basierend auf dem Newton-Näherungsverfahren? Es ist im Moment noch um den Faktor 90 langsamer als mit double-Werten.

    __int64 sqrt(__int64 x)
    {
    	__int64 a = x;
    	__int64 b = 0;
    
    	while (a != b)
    	{
    		b = a;
    		a = (b + x/b)/2;
    	}
    
    	return a;
    }
    


  • Also spontan fällt mir noch der Heron-Algorithmus ein.



  • Das scheint das selbe zu sein.



  • Wenn SSE unterstützt wird, kann man den Assemblercode dafür verwenden, so eine Wurzel auf float ist ca. 7 mal schneller als sqrtf.



  • Mis2com schrieb:

    Wenn SSE unterstützt wird, kann man den Assemblercode dafür verwenden, so eine Wurzel auf float ist ca. 7 mal schneller als sqrtf.

    Das halte ich für ein Gerücht. Je nach dem für welchen Prozessor der Compiler optimiert darf er sqrt auch durch Assembler-Befehle ersetzen.



  • Aber einer, den ich kenne, der hat mal sqrtss getestet und das war 7fach schneller als sqrtf!
    Aber probiert selbst, ich habe den Code mal rausgesucht:

    float 3DNow_Wurzel(float x){
    	float wurzel = 0.0f;
    	_asm
    	{
    
    _emit		0x0f
    		_emit		0x0e 
    		movd		mm0, x
    		pfrsqrt     	mm1,mm0
    		punpckldq	mm0, mm0
    		pfmul       	mm0,mm1
    		movd		wurzel, mm0
    		_emit		0x0f
    		_emit		0x0e
    
    }
    
    	return wurzel;
    }
    
    float SSE_Wurzel(float x){
    	float	wurzel = 0.0f;
    	_asm
    	{
    
    sqrtss		xmm0, x
    		movss		wurzel, xmm0
    
    }
    	return wurzel;
    }
    

    MfG MAV



  • @Mis2Com: Mag sein. Dann hat derjenige aber nicht für einen bestimmten Prozessor kompiliert sondern die Standardeinstellungen benutzt. Afaik darf der Compiler Standardfunktionen ersetzen wenn man explizit angegeben hat für welchen Prozessor er optimieren soll und er die Semantik dadurch nicht verändert.



  • Naja, dann stellt sich die Frage, wofür du so eine schnelle Wurzel brauchst. 😕



  • Also ich könnte mir vorstellen, dass Optimizer sie für eine Übung schreibt. Da erfindet man das Rad ständig neu.



  • Aber zählt für eine Übung die Performance?



  • Wenn in der Übung gefordert wird, einen möglichst schnellen Algorithmus zu schreiben, ja! 😉



  • die schnelligkeit des algorithmus hängt aber nicht davon ab welche befehle man nutzt - das ist eine frage der implementierung



  • ne schnelle wurzelfunktion ist vielleicht ganz nützlich wenn man oft abstände berechnen muss...

    bye

    tt



  • man ein Durchlauf sparen, wenn man a=x>>1; macht ;O)))



  • Wenn man die Größenordnung g von x im Zweiersystem kennt, kann man mit a = (1 << (g/2)) beginnen. Das spart einige Durchläufe.
    Bei __int64 (2^6 Bit) braucht man 6 Vergleiche, um g herauszufinden.


Log in to reply