4. Länge einer Zahl in einer angegebenen Basis finden

Länge einer Zahl in einer angegebenen Basis finden

  • ?

    OK, Volkard, Ich glaube, ich verstehe langsam, was du da gemacht hast.

    Schlüssel ist die Konstante 11529215047 (260/108), welche das Verhältnis darstellt zwischen einer 9-stelligen Dezimalzahl und dem 60-Bit-Speicherraum, mit dem wir arbeiten wollen. Wir rechnen den Wert, den wir damit haben wollen, auf diesen Speicherraum hoch. Da wir uns auf 9-Stellige Dezimalwerte beschränken, vermeiden wir den Werteüberlauf - relativ knapp. Viel wichtiger ist aber, dass wir hierdurch die Zahl in ihrer Nibbledarstellung im Speicher haben - im ersten Nibble haben wir dann den gesuchten Wert in Dezimaldarstellung.

    Wir gehen also alle Nibble durch, multiplizieren immer mit 10, um die nächste Zehnerstelle zu bekommen, die im letzten Nibble steht, und schreiben diesen dezimalen Wert ohne weitere Konvertierung bis auf ASCII in den String. Und weil wir von Vorne nach Hinten alles durchgehen, brauchen wir nichts umdrehen, nichts dividieren.

    Bei vorwaerts_printMax9Digits haben wir eventuell nicht genug Nibbles mit Werten, die wir befüllen können. Deswegen schieben wir die Nibbles weiter, bis wir anfangen können mit dem Schreiben.

    Beeindruckender Code, das will ich sagen. Aber da stören mich noch ein paar Sachen ... darauf werde ich jetzt aber noch nicht eingehen, ich muss erst noch ein bisschen schlafen und dann ein paar Tests mit dem Code machen. Wenn ich was finales Abgeben kann, werde ich es posten.

    Vielen, vielen Dank für die Hilfe.

    0
  • V

    Wutz schrieb:

    |1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
function printUmdreh needs 732 ticks
function printAlt needs 1112 ticks
function printLog needs 800 ticks
function _ui64toa needs 564 ticks

    Die Win-CRT bietet seit (mind.) VC6 Zeiten auch "_ui64toa" an, und liefert brauchbare Ergebnisse, s.o.
    Den Quellcode kannst du dir ja mal zu Gemüte führen.

    Deine Messungen sind so … anders.
    Optimierungen waren alle an?

    0

  • Ich habe nur die Ersetzung

    #include <math.h>
#include <string.h>
...
uint64_t printSprintf(uint64_t n){
    //sprintf(theOutputBuffer,"%llu",n);
    _ui64toa(n,theOutputBuffer,10);
}

    und dann jeweils mit MinGW/gcc 4.7.1 + 4.8.1 32Bit und Win7 64Bit und -O1,-O2,-O3 im Release-Modus jeweils die gleichen relativen Ergebnisse auf zwei unterschiedlichen PC erreicht:
    mingw32-gcc.exe -Wall -std=c99 -O2 -c \GCC\utoa\main.c -o obj\Release\main.o

    |1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
function printUmdreh needs 1953 ticks
function printAlt needs 2952 ticks
function printLog needs 2052 ticks
function printSprintf needs 1323 ticks

    Die Sourcen der WinCRT sind unauffällig, und entsprechen weitgehend dem <printUmdreh>.
    Wenn ich den Quelltext mit VStudio2013 übersetze, (rdtsc() muss durch __rdtsc() ersetzt werden), kommt der Unterschied nicht zustande, _ui64toa liegt immer auf Niveau von printUmdreh.
    Probiere selber:
    https://www.cubbyusercontent.com/pli/utoa.exe/_df8752037ade43559216f10da4198a9c
    https://www.cubbyusercontent.com/pli/main.c/_96390fbc63e9408c99f52126c6753bab
    https://www.cubbyusercontent.com/pli/main.s/_00aca2abfcfe4fd3b98b53999b60a616

    Das asm liefert nichts Überraschendes:

    _printSprintf:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$40, %esp
	movl	8(%ebp), %eax
	movl	%eax, -16(%ebp)
	movl	12(%ebp), %eax
	movl	%eax, -12(%ebp)
	movl	$10, 12(%esp)
	movl	$_theOutputBuffer, 8(%esp)
	movl	-16(%ebp), %eax
	movl	-12(%ebp), %edx
	movl	%eax, (%esp)
	movl	%edx, 4(%esp)
	call	__ui64toa
	leave
	ret

    Wen es interessiert, hier die WinCRT-Quelle: (den Secure+Unicode Müll habe ich mal entsorgt)

    /***
*xtoa.c - convert integers/longs to ASCII string
*
*       Copyright (c) Microsoft Corporation. All rights reserved.
*
*Purpose:
*       The module has code to convert integers/longs to ASCII strings.  See
*
*******************************************************************************/
static void __fastcall x64tox
        (/* stdcall is faster and smaller... Might as well use it for the helper. */
        unsigned __int64 val,
        char *buf,
        unsigned radix,
        int is_neg
        )
{
        char *p;                /* pointer to traverse string */
        char *firstdig;         /* pointer to first digit */
        char temp;              /* temp char */
        unsigned digval;         /* value of digit */

        p = buf;

        if ( is_neg )
        {
            *p++ = '-';         /* negative, so output '-' and negate */
            val = (unsigned __int64)(-(__int64)val);
        }

        firstdig = p;           /* save pointer to first digit */

        do {
            digval = (unsigned) (val % radix);
            val /= radix;       /* get next digit */

            /* convert to ascii and store */
            if (digval > 9)
                *p++ = (char) (digval - 10 + 'a');  /* a letter */
            else
                *p++ = (char) (digval + '0');       /* a digit */

        } while (val > 0);

        /* We now have the digit of the number in the buffer, but in reverse
           order.  Thus we reverse them now. */

        *p-- = '\0';            /* terminate string; p points to last digit */

        do {
            temp = *p;
            *p = *firstdig;
            *firstdig = temp;   /* swap *p and *firstdig */
            --p;
            ++firstdig;         /* advance to next two digits */
        } while (firstdig < p); /* repeat until halfway */

}

    Ist wie gesagt nichts Besonderes bei, irgendwas müssen die MinGW-Leute noch dazu gebacken haben, damit der Aufruf derselben CRT-Funktion merklich viel schneller abläuft, als beim 'Original' MS.

    0
  • ?

    OK, ich habe noch ein bisschen an dem Code rumgehackt:

    #include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

//geborgt von http://stackoverflow.com/questions/9887839/clock-cycle-count-wth-gcc
static __inline__ unsigned long long rdtsc(void)
{
	unsigned hi, lo;
	__asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
	return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}

//Die ganzen print-Funktionen und Messungen vom Speicherbesorgen befreien.
//Macht außerdem anscheinend genug OptimierMichNichtHanzWeg.
char theOutputBuffer[64];

typedef uint64_t LONGEST_SUPPORTED_INTEGER;

char*printUmdreh(LONGEST_SUPPORTED_INTEGER n)
{
	register char* out=theOutputBuffer;
	do
	{
		*out++=n%10+'0';
		n/=10;
	}
	while(n);
	*out='\0';

	//r soll mal in ein eigenes Register hüpfen wollen, mag out nicht mehr.
	register char*l,*r;
	for(l=theOutputBuffer,r=out-1;l<r;++l,--r){
		char tmp=*l;
		*l=*r;
		*r=tmp;
	}
}

/*Bisheriger naiver Ansatz*/
uint64_t get_number_length_base10(const LONGEST_SUPPORTED_INTEGER value)
{
	register uint64_t length=1;
	register LONGEST_SUPPORTED_INTEGER rvalue=value;

	while(rvalue>=10)
	{
		//rvalue-=rvalue%10;UNFUG!!!
		rvalue/=10;
		++length;
	}

	return length;
}

char* printAlt(LONGEST_SUPPORTED_INTEGER n)
{
	register char* out=theOutputBuffer+get_number_length_base10(n);
	*out='\0';
	do
	{
		*--out=n%10+'0';
		n/=10;
	}
	while(n);
}

char* printSprintf(uint64_t n)
{
	sprintf(theOutputBuffer,"%lu",n);
}

/*Immer vier. Einer weniger, und wir kriegen nicht mehr alle Ziffern im
**Dezimalsystem dargestellt.*/
#define BITS_RESERVED_FOR_LAST_DEC_POSITION (4)

/*Beinhaltet den Wert, mit dem man sämtliche Zahlen verrechnen muss, damit man
**eine rein binaere Representation des Wertes im Speicher erhaelt. Dieser ist:
**	2 ^ (sizeof(LONGEST_SUPPORTED_INTEGER) -
**	BITS_RESERVED_FOR_LAST_DEC_POSITION)
**	/ 10 ^ (Anzahl der Dezimalstellen, die man maximal mit dem Typen minus
**	BITS_RESERVED_FOR_LAST_DEC_POSITION schreiben kann). Dies muss
**zusätzlich noch aufgerundet werden.
***/

#define DEC_TO_BIN_REPRESENTATION(x) ((x)*11529215047)
#define GET_LAST_NIBBLE(x) ((x)>>sizeof(LONGEST_SUPPORTED_INTEGER)*8-BITS_RESERVED_FOR_LAST_DEC_POSITION)
#define GET_NEXT_DEC_POSITION(x) ((((x)<<BITS_RESERVED_FOR_LAST_DEC_POSITION)>>BITS_RESERVED_FOR_LAST_DEC_POSITION)*10)

char* vorwaerts_print9Digits(uint32_t n,char* pdst)
{
	/*register*/ LONGEST_SUPPORTED_INTEGER r=DEC_TO_BIN_REPRESENTATION(n);
	/*register*/ char*dst=pdst;

	/*Scheife ausgefahren.*/
	*dst++=GET_LAST_NIBBLE(r)+'0';
	r=GET_NEXT_DEC_POSITION(r);

	*dst++=GET_LAST_NIBBLE(r)+'0';
	r=GET_NEXT_DEC_POSITION(r);

	*dst++=GET_LAST_NIBBLE(r)+'0';
	r=GET_NEXT_DEC_POSITION(r);

	*dst++=GET_LAST_NIBBLE(r)+'0';
	r=GET_NEXT_DEC_POSITION(r);

	*dst++=GET_LAST_NIBBLE(r)+'0';
	r=GET_NEXT_DEC_POSITION(r);

	*dst++=GET_LAST_NIBBLE(r)+'0';
	r=GET_NEXT_DEC_POSITION(r);

	*dst++=GET_LAST_NIBBLE(r)+'0';
	r=GET_NEXT_DEC_POSITION(r);

	*dst++=GET_LAST_NIBBLE(r)+'0';
	r=GET_NEXT_DEC_POSITION(r);

	*dst++=GET_LAST_NIBBLE(r)+'0';

	return dst;
}

char* vorwaerts_printMax9Digits(uint32_t n,char* dst)
{
	register LONGEST_SUPPORTED_INTEGER r=DEC_TO_BIN_REPRESENTATION(n);
	register int i=0;

	/*Schleife koennen wir hier nicht ausfahren, weil wir die Anzahl der
	**bisherigen Iterationen benoetigen.*/
	while(i<9)
	{
		/*Sobald wir genug Stellen vorgeschoben haben, damit wir einen
		**Wert haben, konnen wir mit dem Schreiben anfangen.*/
		if(GET_LAST_NIBBLE(r))
			break;
		r=GET_NEXT_DEC_POSITION(r);
		++i;
	}
	while(i<9)
	{
		*dst++=GET_LAST_NIBBLE(r)+'0';
		r=GET_NEXT_DEC_POSITION(r);
		++i;
	}
	return dst;
}

#define MY_NUMBER 0xFFFF000012341234ULL /* 123891380ULL*/ /*0xf100100010001fffULL*/

#define BIG_20 10000000000000000000ULL
#define BIG_19 1000000000000000000ULL
#define BIG_10 1000000000ULL

char* vorwaerts_printDigits(LONGEST_SUPPORTED_INTEGER pn,char* pdst)
{
	register LONGEST_SUPPORTED_INTEGER n=pn;
	register char*dst=pdst;

	/*Ganz grosse Zahl.*/
	if(n>=BIG_19)
	{
		/*GAAAAAAAAAAAAAANZ grosse Zahl. Bei dieser machen wir zweimal
		**die Konvertierung manuell sodass 18 Ziffern übrigbleiben,
		**und dann schreiben wir mit zwei Calls den String.*/
		if(n>=BIG_20)
		{
			*dst++='0'+n/BIG_20;
			n%=BIG_20;
		}
		*dst++='0'+n/BIG_19;
		n%=BIG_19;
		dst=vorwaerts_print9Digits(n/BIG_10,dst);
		dst=vorwaerts_print9Digits(n%BIG_10,dst);
		return dst;
	}
	/*Nicht ganz so große Zahl. Hier kann es sein, dass wir beim ersten
	**Mal nur 1 Stelle schreiben, daber danach schreiben wir wieder volle
	**9 Stellen.*/
	else if(n>=BIG_10)
	{
		dst=vorwaerts_printMax9Digits(n/BIG_10,dst);
		dst=vorwaerts_print9Digits(n%BIG_10,dst);
		return dst;
	}
	/*OK, kleine Zahl im Bereich von unter einer Millarde.*/
	else if(n)
	{
		dst=vorwaerts_printMax9Digits(n,dst);
		return dst;
	}
	/*Sonderfall 0*/
	dst[0]='0';
	return dst+1;
}

char* printVorwaerts(uint64_t n)
{
	*vorwaerts_printDigits(n,theOutputBuffer)='\0';
}

uint64_t measure(char const* fName,char* (*f)(LONGEST_SUPPORTED_INTEGER))
{
	//Nur der schnellste Laug zählt!
	int const maxLeft=1000000;
	int left=maxLeft;
	uint64_t minTime=(uint64_t)-1;
	while(left!=0)
	{
		uint64_t time=-rdtsc();
		f(MY_NUMBER);
		time+=rdtsc();
		if(time<minTime)
		{
			minTime=time;
			left=maxLeft;
		}
		--left;
	}
	printf("function %s needs %lu ticks\n",fName,minTime);
	return minTime;
}

#define MEASURE(f) measure(#f,f)

int main(void)
{
	memset(theOutputBuffer,0,64);
	printf("|%llu|\n",MY_NUMBER);

	memset(theOutputBuffer,0,64);
	printUmdreh(MY_NUMBER);
	printf("|%s|\n",theOutputBuffer);

	memset(theOutputBuffer,0,64);
	printAlt(MY_NUMBER);
	printf("|%s|\n",theOutputBuffer);

	memset(theOutputBuffer,0,64);
	printSprintf(MY_NUMBER);
	printf("|%s|\n",theOutputBuffer);

	memset(theOutputBuffer,0,64);
	printVorwaerts(MY_NUMBER);
	printf("|%s|\n",theOutputBuffer);

	MEASURE(printUmdreh);
	MEASURE(printAlt);
	MEASURE(printSprintf);
	MEASURE(printVorwaerts);

	return 0;
}

    Ausgabe:

    |18446462599038243380|
    |18446462599038243380|
    |18446462599038243380|
    |18446462599038243380|
    |18446462599038243380|
    function printUmdreh needs 78 ticks
    function printAlt needs 96 ticks
    function printSprintf needs 212 ticks
    function printVorwaerts needs 28 ticks //Buyakascha

    0
  • V

    dachschaden schrieb:

    OK, ich habe noch ein bisschen an dem Code rumgehackt:

    An ziemlich genau diese Tricks dachte ich auch.

    Aber bei mir bringen Deine Hacks leider 3 Ticks an Langsamkeit dazu. 😞

    function printVorwaerts needs 48 ticks //BOOM!
function printVorwaerts needs 51 ticks //Buyakascha
    0
  • ?

    Verrückt. Wieder mit -O3 kompiliert?

    $ gcc -o volk_boom volk_boom.c -O2
$ ./volk_boom
|18446462599038243380|
|18446462599038243380|
|18446462599038243380|
|18446462599038243380|
|18446462599038243380|
function printUmdreh needs 78 ticks
function printAlt needs 96 ticks
function printSprintf needs 212 ticks
function printVorwaerts needs 32 ticks
$ gcc -o volk_boom volk_boom.c -O3
$ ./volk_boom
|18446462599038243380|
|18446462599038243380|
|18446462599038243380|
|18446462599038243380|
|18446462599038243380|
function printUmdreh needs 64 ticks
function printAlt needs 96 ticks
function printSprintf needs 212 ticks
function printVorwaerts needs 28 ticks

    Ansonsten wüsste ich jetzt auch nicht, was das Problem sein könnte - es ist exakt der gleiche Code wie gepostet. 😕

    0
  • V

    dachschaden schrieb:

    Verrückt. Wieder mit -O3 kompiliert?

    Klar.

    Aber um die Vergleichbarkeit zu alten Messungen zu bewahren, hab ich mit der alten Zahl gemessen.

    #define MY_NUMBER 0x1100100010001fffULL

    Mit der neuen Zahl sind bei mir beide Versionen gleich schnell.

    Hab nicht ins Compilat geschaut, vielleicht macht -O3 das Loop-Unrollig ja selber.

    0
  • ?

    volkard schrieb:

    Aber um die Vergleichbarkeit zu alten Messungen zu bewahren, hab ich mit der alten Zahl gemessen.
    Mit der neuen Zahl sind bei mir beide Versionen gleich schnell.

    Okee ... bei mir macht die alte Zahl gar keinen Unterschied. Sind immer noch die gleichen Werte bei -O2 und -O3.

    volkard schrieb:

    Hab nicht ins Compilat geschaut, vielleicht macht -O3 das Loop-Unrollig ja selber.

    Hättest das mal lieber gemacht. 🤡
    Die -O2-Variante hat gar keinen Unterschied in vorwaerts_print9Digits zu -O3. Unrolling passiert zwar bei vorwaerts_printMax9Digits - das erkenne ich trotz madigen Assemblerkenntnissen deutlich - aber bei so großen Zahlen wird vorwaerts_printMax9Digits gar nicht mehr ausgeführt.

    Ich gebe zu, ich bin mit meinem Latein ein wenig am Ende.

    0
  • V

    dachschaden schrieb:

    Ich gebe zu, ich bin mit meinem Latein ein wenig am Ende.

    Ich sehe das Problem nicht. Bei Dir ist die Version mit den Hacks um 4 Ticks schneller, wenn ich das richtig sehe. Ist doch ok.
    Bei mir ist sie um 3 Ticks langsamer. Ist auch voll ok. Kein Grund mehr, hier viel zu optimieren. Dreimal so schnell wie die alte Version.

    0
  • ?

    Gut, wenn du meinst.

    Vielen, vielen Dank für die Hilfestellung noch einmal, Leute. Besonders dir, Volkard. Durch diesen Thread habe ich einiges gelernt, was wir jetzt einbauen werden.

    0
Anmelden zum Antworten