Länge einer Zahl in einer angegebenen Basis finden

dot schrieb:

Kannst auch mal probieren, mit dem ln oder ld (log zur Basis 2) zu arbeiten, ka welcher am schnellsten sein wird. Mit dem ld könnte es genügen, das höchstwertige Bit zu bestimmen, wofür es auf vielen CPUs eigene Instructions und entsprechende Compilerintrinsics gibt (http://en.wikipedia.org/wiki/Find_first_set) und du die int-float-Conversions loswerden könntest...

log2 ist ein wenig schneller (30000 Ticks), aber immer noch vollkommen übertrieben. Und da dachte ich heute mal, dass die Leute von der Standardbibliothek mich doch mal geschlagen haben ...
Natürlicher Logarithmus dauert 32000 Ticks.

Und mit Inlineassembler möchte ich erst einmal nichts zu tun haben - ich sehe es bereits als Schande an, dass ich den verwenden musste, um mir schnell die Ticks holen zu können.

dot

dachschaden schrieb:

Und mit Inlineassembler möchte ich erst einmal nichts zu tun haben [...]

Sollst du ja auch nicht, Stichwort Intrinsic. Unter GCC z.B. __builtin_clz()

Und das funktioniert, wenn ich den Code auch mit Krüppelcompilern wie Visual Studio kompiliere (muss halt auf beiden Systemen laufen)? Ich habe schon die Krise bekommen, als ich alloca durch ein Präprozessormakro ersetzen musste, weil VS nur _alloca kennt.

Oder anders: Ich werde es mir später anschauen, aber ich will mir jetzt nicht wieder zusätzliche Baustellen schaffen.

Außerdem hat es für den von dir beschriebenen Weg keine 64-Bit-Versionen, zumindest nicht für den GCC. Meh. Aber dennoch vielen Dank für den Hinweis - selbst, wenn es mich dem Ziel nicht näher bringt, lerne ich dennoch was.

Also, Frage vom ersten Post besteht weiterhin.

SeppJ

Kannst du mal ein Testprogramm geben? Ich habe selber ein bisschen rumgespielt und überrascht festgestellt, dass die Umdrehmethode von volkard tatsächlich langsamer ist, selbst als der Logarithmus aus der lm (Von ~100ns mit Logarithmus auf ~140 ns mit Umdrehen, bei kleinen Zahlen.) Das heißt, man könnte wohl wirklich was machen, wenn man diesen Teil optimiert. Aber ich habe keine Ahnung, wie deine Anforderungen sind (ich habe einmal mit nutzergegebenen, festen Arrays gearbeitet und einmal mit dynamischen. Hat zwar keinen Unterschied gemacht, aber wäre trotzdem gut zu wissen, was gewollt ist) oder wie genau du deine Ticks misst oder was ein Tick bei dir ist. Oder wie du überhaupt deine Umrechnungen vornimmst. Ich habe bloß die ganz naive Methode mit Schleife, Modulo und Division genommen, ohne Mikrooptimierungen.

SeppJ

dachschaden schrieb:

Und das funktioniert, wenn ich den Code auch mit Krüppelcompilern wie Visual Studio kompiliere (muss halt auf beiden Systemen laufen)? Ich habe schon die Krise bekommen, als ich alloca durch ein Präprozessormakro ersetzen musste, weil VS nur _alloca kennt.

_BitScanReverse, bzw. _BitScanReverse64 bei MSVC.
__builtin_clzl für unsigned long, bzw. __builtin_clzll für unsigned long long beim GCC.

Musst du eben weitere Präprozessormakros für definieren. Da es dir ja anscheinend auf jede noch so kleine Optimierung ankommt, ist das doch ein sehr kleiner Preis. Das ist doch noch relativ harmlos, was Mikrooptimierungen angeht.

ABER: Ist das überhaupt die richtige Lösung? Selbst wenn du den Logarithmus der Basis exakt berechnest (oder in einem Lookuptable nachguckst), so kann das Ergebnis doch um 1 ungenau sein:
1100011 -> MSB ist 7 -> Dezimaldarstellung hat 2 Stellen ("99")
1100100 -> MSB ist 7 -> Dezimaldarstellung hat 3 Stellen ("100")

Das kommt halt davon, wenn man bei einem der Zwischenergebnisse die Nachkommastellen abschneidet. Vermutlich wird es sogar irgendwo im Zahlenraum 0 bis 2^64 und im Basenraum 2 bis 36 sogar irgendeinen Fall geben, bei dem selbst long double Logarithmen einen of-by-1-Error ergeben werden. Ich fürchte fast, die einzig 100% zuverlässige Methode ist es, die Anzahl der benötigten Stellen im Nachhinein festzustellen (Umdrehmethode), oder durch eine "abgespeckte" Berechnung im Voraus (also so etwas wie deine erste Methode, aber das ist sicherlich langsamer als das Umdrehen im Nachhinein). Oder immer 1 Byte zur Sicherheit einfügen, wenn das Anwendungsszenario das hergibt.

PS: Mal so aus Neugierde: Ist das überhaupt ein realistisches Anwendungsszenario, an dem du gerade so viel Entwicklungszeit verbringst? Verschiedene Zahlendarstellungen klingen nicht unbedingt nach einem Thema, bei dem es auf Performance ankäme, erst recht nicht auf solche Mikrooptimierungen, wie du sie hier suchst. Einfach, da die Darstellung letztlich für eine Ausgabe bestimmt sein muss (warum sollte man sonst etwas darstellen wollen?) und bei IO ist normalerweise das Gerät der Flaschenhals, nicht die Programmlogik. Also: Bei welchem Anwendungsszenario meinst du, schnelle Zahlendarstellungen zu benötigen?

PPS: Hast du diese (oder eine sehr ähnliche) Frage hier schon einmal gestellt? Dein Thema und dein Stil kommen mir irgendwie bekannt vor, aber es ist schon ein paar Monate her, glaube ich.

Für das Messen der Ticks hab ich damals ein API geschrieben. welches auf Präprozessormarkos beruht, weil die Methode auf verschiedenen Architekturen halt anders ist.
Ich habe eine gute Stunde daran gearbeitet, den Code leserlich zu gestalten und dennoch die Grundstruktur beizubehalten:

/*Kompiliert mit:
**gcc -o geschw_test geschw_test.c -lm -m[32 oder 64]
**Laeuft mit:
**./geschw_test
*/

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

/*Generelles Objekt, welches einen Haufen Speicher beinhaltet.*/
struct my_heap
{
	size_t	my_max;	/*Wie viele Bytes wir reserviert haben*/
	char*	my_mem;	/*Zeiger zum eigentlichen Speicher*/
};

/*****************************************************************************
**Speicher ist gut und schoen, aber wir benoetigen auch etwas, das uns sichert,
**wie weit wir geschrieben haben. Dafuer haben wir einen Streamer.
*****************************************************************************/
struct my_streamer
{
	/*Basisobjekt*/
	struct my_heap my_ih;

	/*Und die Information wo im Heap definierte Werte anfangen und wo
	**aufhoeren.*/
	size_t my_begin;
	size_t my_end;
};

/*****************************************************************************
**Jetzt das Makro zum Sichern der Ticks. Auf 32-Bit-Systemen kann man ueber
**rdtsc die gegenwaertigen Ticks auslesen, indem man die Adresse einer
**64-Bit-Zahl angibt. Auf 64-Bit-Systemen muss man Adressen zu zwei
**32-Bit-Zahlen angeben.
*****************************************************************************/

#ifdef __x86_64__
#define SAVE_TICKS(x) \
	asm("rdtsc":	"=a"(*(uint32_t*)((my_cycle_counter_##x.my_ih.my_mem)+my_cycle_counter_##x.my_end)), \
			"=d"(*(uint32_t*)((my_cycle_counter_##x.my_ih.my_mem)+my_cycle_counter_##x.my_end+4)));
#else
#define SAVE_TICKS(x) \
	asm("rdtsc":	"=A"(*(uint64_t*)((my_cycle_counter_##x.my_ih.my_mem)+my_cycle_counter_##x.my_end)));
#endif

/*****************************************************************************
**Groesse eines Eintrages im Stream. Ein Eintrag sind immer 8-Byte fuer die
**Anzahl der Ticks selbst plus die Adresse des Strings, der im statischen
**Speicher der Anwendund steht, gross (auf 32-Bit Systemen 4 Byte, auf
**64-Bit-Systemen 8 Byte).
*****************************************************************************/
#define CYCLE_COUNTER_ENTRY_SIZE (sizeof(uint64_t)+sizeof(size_t))

/*Streamer deklarieren*/
#define CYCLE_COUNTER_INIT(x) struct my_streamer my_cycle_counter_##x

/*Makro zum Hinzufuegen eines Markers im Streamer.*/
#define CYCLE_COUNTER_ADD_MARKER(x,y) \
{ \
	SAVE_TICKS(x) \
	*(size_t*)(my_cycle_counter_##x.my_ih.my_mem+my_cycle_counter_##x.my_end+sizeof(uint64_t))=(size_t)&y; \
	my_cycle_counter_##x.my_end+=CYCLE_COUNTER_ENTRY_SIZE; \
}
/*Ende des Makros.*/

/*Streamer initialisieren.*/
#define CYCLE_COUNTER_ALLOC(x) \
{ \
	my_cycle_counter_##x.my_begin=0; \
	my_cycle_counter_##x.my_end=0; \
	\
	/*********************************************************************
	**Wir machen hier einfach eine statische Initialisierung, alles andere
	**wuerde den Rahmen des Programmes sprengen.
	**********************************************************************/ \
	my_cycle_counter_##x.my_ih.my_max=4096; \
	my_cycle_counter_##x.my_ih.my_mem=malloc(my_cycle_counter_##x.my_ih.my_max); \
	CYCLE_COUNTER_ADD_MARKER(x,"(Intern start)"); \
}
/*Ende des Makros.*/

/*Auf verschiedenen Systemen erwartet printf verschiedene Konstanten
**fuer einen size_t. Mit diesem Makro loesen wir das auf.*/
#ifdef __x86_64__
#define UINT64_T_PRINTF		"%lu"
#define HEX64_PRINTF		"%lx"
#else
#define UINT64_T_PRINTF		"%llu"
#define HEX64_PRINTF		"%llx"
#endif

/*Alle Marker im Streamer ausgeben.*/
#define CYCLE_COUNTER_PRINTOUT(x) \
{ \
	/*********************************************************************
	**"tmp" beinhaltet die Bytes bis zum gegenwaertigen Marker, "first"
	**die Ticks des ersten und "last" die Ticks des letzten Markers.
	**
	**Ausgabenformat ist folgendes:
	**[<Name des Objektes>|<Gegenwaertige Ticks in Hexdec>|<Gleiches in Dec>
	** |<Unterschied zum letzten Marker in Hexdec>|<Gleiches in Dec>
	** |Markerstring
	**********************************************************************/ \
	size_t tmp=0; \
	uint64_t first=*(uint64_t*)(my_cycle_counter_##x.my_ih.my_mem),last=0; \
	while(tmp<my_cycle_counter_##x.my_end) \
	{ \
		printf("[" #x "|" \
			"0x" HEX64_PRINTF "|" \
			UINT64_T_PRINTF "|" \
			"0x" HEX64_PRINTF "|" \
			UINT64_T_PRINTF "|" \
			 "\"%s\"" "]\n", \
			*(uint64_t*)(my_cycle_counter_##x.my_ih.my_mem+tmp), \
			*(uint64_t*)(my_cycle_counter_##x.my_ih.my_mem+tmp), \
			*(uint64_t*)(my_cycle_counter_##x.my_ih.my_mem+tmp)-last, \
			*(uint64_t*)(my_cycle_counter_##x.my_ih.my_mem+tmp)-last, \
			(char*)*(size_t*)(my_cycle_counter_##x.my_ih.my_mem+tmp+sizeof(uint64_t))); \
		last=*(size_t*)(my_cycle_counter_##x.my_ih.my_mem+tmp); \
		tmp+=CYCLE_COUNTER_ENTRY_SIZE; \
		\
	} \
	/*Finale Ausgabe mit der Anzahl der Ticks zwischen erstem und letzten
	**Marker.*/ \
	printf("[" #x "|" \
		"0x" HEX64_PRINTF "|" \
		UINT64_T_PRINTF "|" \
		"\"%s\"" "]\n", \
		last-first, \
		last-first, \
		"(Overall)"); \
}
/*Ende des Makros.*/

/*Streamer freigeben. Das heisst im Grunde, den Speicher von malloc wieder
**freigeben (duh).*/
#define CYCLE_COUNTER_FREE(x) free(my_cycle_counter_##x.my_ih.my_mem)

/*Ende des APIs. Jetzt koennen wir uns um richtigen Code kuemmern.*/

#include <math.h>

/*Bisheriger naiver Ansatz*/
uint64_t get_number_length(const uint64_t value,const uint8_t radix)
{
	register uint64_t length=1;
	register uint64_t rvalue=value;

	while(rvalue>=radix)
	{
		rvalue-=rvalue%radix;
		rvalue/=radix;
		++length;
	}

	return length;
}

/*Neuer Ansatz fuer Basis 16.
**Habe ich drin gelasen, damit man diese Funktionen gleich direkt mittesten
**kann.*/
uint64_t get_new_length_base16(const uint64_t value)
{
	register uint64_t rvalue=value,nibbles=sizeof(uint64_t)*2;
	do
	{
		--nibbles;
		if(rvalue&(0xFULL<<nibbles*4))return nibbles+1;
	}
	while(nibbles-1);
	return 1;

}

/*Neuer Ansatz fuer Basis 2.*/
uint64_t get_new_length_base2(const uint64_t value)
{
	register uint64_t rvalue=value,nibbles=sizeof(uint64_t)*2,temp;
	do
	{
		if(!(temp=(rvalue>>--nibbles*4)&0xFULL))
			continue;
		if(temp&8)return nibbles*4+4;
		if(temp&4)return nibbles*4+3;
		if(temp&2)return nibbles*4+2;
		return nibbles*4+1;
	}
	while(nibbles);
	return 1;
}

/*Neuer Ansatz mit Logarithmus.*/
uint64_t get_new_length_log2(const uint64_t value)
{
	return (uint64_t)(log2(value)/log2(10))+1;
}

/*Nummer, die fuer alle Calls verwendet werden soll, damit wir ja einheitliche
**Ergebnisse haben.*/
#define MY_NUMBER 0x1100100010001fffULL

int main(void)
{
	/*Streamer deklarieren.*/
	CYCLE_COUNTER_INIT(example_1);
	CYCLE_COUNTER_INIT(example_2);
	CYCLE_COUNTER_INIT(example_3);

	uint64_t first_length;
	uint64_t second_length;
	uint64_t third_length;

	printf("Wert fuer Berechnung: %llu\n",MY_NUMBER);

	/*Streamer alloziiieren.*/
	CYCLE_COUNTER_ALLOC(example_1);
	CYCLE_COUNTER_ALLOC(example_2);
	CYCLE_COUNTER_ALLOC(example_3);

	/*Erster Call, beinhaltet meinen damaligen "naiven" Ansatz.*/	
	CYCLE_COUNTER_ADD_MARKER(example_1,"get_number_length begin");
	first_length=get_number_length(MY_NUMBER,10);
	CYCLE_COUNTER_ADD_MARKER(example_1,"get_number_length end");

	/*Zweiter Call, beinhaltet die Berechnung mit log2, wird allerdings
	**- zumindest bei mir - vom Compiler weitestgehen optimiert.*/
	CYCLE_COUNTER_ADD_MARKER(example_2,"log2 begin");
	second_length=(uint64_t)(log2(MY_NUMBER)/log2(10))+1;
	CYCLE_COUNTER_ADD_MARKER(example_2,"log2 end");

	/*Dritter Call, wieder Logarithmus, aber diesmal in eine exportierte
	**Funktion, hier darf der Compiler nichts wegoptimieren.*/
	CYCLE_COUNTER_ADD_MARKER(example_3,"get_new_length_log2 begin");
	third_length=get_new_length_log2(MY_NUMBER);
	CYCLE_COUNTER_ADD_MARKER(example_3,"get_new_length_log2 end");

#define SEPARATOR "===========================================================================================\n"
	/*Ausgabe*/
	printf(SEPARATOR);
	CYCLE_COUNTER_PRINTOUT(example_1);
	printf(SEPARATOR);
	CYCLE_COUNTER_PRINTOUT(example_2);
	printf(SEPARATOR);
	CYCLE_COUNTER_PRINTOUT(example_3);
	printf(SEPARATOR);

	/*Aufraeumen*/
	CYCLE_COUNTER_FREE(example_1);
	CYCLE_COUNTER_FREE(example_2);
	CYCLE_COUNTER_FREE(example_3);

	/*Kontrolle, ob die Ergebnisse alle gleich sind.*/
	printf("Laengenergebnis: [" UINT64_T_PRINTF " == " UINT64_T_PRINTF " == " UINT64_T_PRINTF "]\n",first_length,second_length,third_length);

	/*Ende (duh).*/
	return 0;
}

Führt dann bei mir zur Ausgabe:

Wert fuer Berechnung: 1224996691099262975

[example_1|0x226724e4ee54c|605222335341900|0x226724e4ee54c|605222335341900|"(Intern start)"]
[example_1|0x226724e4efc98|605222335347864|0x174c|5964|"get_number_length begin"]
[example_1|0x226724e4f0290|605222335349392|0x5f8|1528|"get_number_length end"]
[example_1|0x1d44|7492|"(Overall)"]

[example_2|0x226724e4ef1f4|605222335345140|0x226724e4ef1f4|605222335345140|"(Intern start)"]
[example_2|0x226724e4f02ac|605222335349420|0x10b8|4280|"log2 begin"]
[example_2|0x226724e4f02c4|605222335349444|0x18|24|"log2 end"]
[example_2|0x10d0|4304|"(Overall)"]

[example_3|0x226724e4efc7c|605222335347836|0x226724e4efc7c|605222335347836|"(Intern start)"]
[example_3|0x226724e4f0370|605222335349616|0x6f4|1780|"get_new_length_log2 begin"]
[example_3|0x226724e4f7188|605222335377800|0x6e18|28184|"get_new_length_log2 end"]
[example_3|0x750c|29964|"(Overall)"]

Zu den Anforderungen: Das API soll zwei Funktionen exportieren. Einmal eine Version, wo der Nutzer nur einen Zeiger und eine Zahl angeben muss - hier bestimmt die Funktion dann, wie groß die Zahl ist, und übergibt diesen Wert zusammen mit Zeiger und Zahl an die zweite Funktion -> siehe weiter - und eine Version, die die Anzahl der zu schreibenden Zeichen (a.k.a. die Länge der Zahl oder Logarithmus) übernimmt und die Anzahl der Bytes schreibt. Aus Gründen der Performance (hast du ja schon selbst getestet, da brauche ich dann meinen Test nicht hochzuladen) schreibe ich die Werte so in das Array:

pstring[--pstring_length]='0'+pnumber_to_write%10;
pnumber_to_write/=10;

Also von hinten nach vorne. Wenn die Anzahl der zu schreibenden Zeichen nicht exakt passt, fehlen Zahlen am Ende. Deswegen muss ich die erst berechnen.

SeppJ schrieb:

PS: Mal so aus Neugierde: Ist das überhaupt ein realistisches Anwendungsszenario, an dem du gerade so viel Entwicklungszeit verbringst?

Soll ein API für hochskalierbare Systeme werden, bei denen die Programme CPU-bound sind und halt nicht I/O-bound. Und wir haben keine Lust, da immer wieder dran rumzuhacken, deswegen machen wir das einmal richtig und ändern höchstens was am API, nicht mehr an den Algorithmen.

SeppJ schrieb:

Verschiedene Zahlendarstellungen klingen nicht unbedingt nach einem Thema, bei dem es auf Performance ankäme, erst recht nicht auf solche Mikrooptimierungen, wie du sie hier suchst.

Verzeihung, dass ich mich nicht damit zufriedengebe, ein Problem zu lösen, dass ich auch in einem Dreißigstel der Zeit lösen könnte.

SeppJ schrieb:

PPS: Hast du diese (oder eine sehr ähnliche) Frage hier schon einmal gestellt? Dein Thema und dein Stil kommen mir irgendwie bekannt vor, aber es ist schon ein paar Monate her, glaube ich.

Tatsächlich habe ich das - naja, nicht exakt diese. Damals ging es um das schnelle Schreiben an sich. Dann haben wir in der Zwischenzit einen neuen HTTP-Stack geschrieben, der an Sicherheit (in der Übertragung) seinesgleichen sucht, aber wir wollen ganz sicher gehen und z.B. beim Lesen und Schreiben von Chunklängen kein Einfallstor hinterlassen. Deswegen habe ich dann das API angefasst, und währenddessen sind mir für unsere meisten anderen Anwendungsfälle (Binär und Hexadezimal) schnellere Lösungen eingefallen. Aber keinem von uns sind schnellere Lösungen für dekadische Logarithmen eingefallen.

SeppJ schrieb:

_BitScanReverse, bzw. _BitScanReverse64 bei MSVC.
__builtin_clzl für unsigned long, bzw. __builtin_clzll für unsigned long long beim GCC.

Ja, hatte ich nach 5 Minuten bereits gelesen. Aber dafür mache ich doch nicht extra einen weiteren Post.

SeppJ schrieb:

Musst du eben weitere Präprozessormakros für definieren. Da es dir ja anscheinend auf jede noch so kleine Optimierung ankommt, ist das doch ein sehr kleiner Preis. Das ist doch noch relativ harmlos, was Mikrooptimierungen angeht.

Hm, jetzt hast du mich neugierig gemacht. Welche anderen Mikrooptimierungen kennst du denn noch?

SeppJ schrieb:

ABER: Ist das überhaupt die richtige Lösung? Selbst wenn du den Logarithmus der Basis exakt berechnest (oder in einem Lookuptable nachguckst), so kann das Ergebnis doch um 1 ungenau sein:
1100011 -> MSB ist 7 -> Dezimaldarstellung hat 2 Stellen ("99")
1100100 -> MSB ist 7 -> Dezimaldarstellung hat 3 Stellen ("100")

Genau das ist das Problem, welchem ich begegnet bin, als ich versucht habe, die Anzahl der Stellen anhand des Bitmusters zu ermitteln. Und wie gesagt, bisher vertraue ich da eher meiner "naiven" Lösung.

Was eine Textwand ...

Und ein kleiner Fehler im Programm ist mir noch aufgefallen: in Zeile 122:

last=*(size_t*)(my_cycle_counter_##x.my_ih.my_mem+tmp); \

Sollte die Umwandlung in einen size_t* eigentlich uint64_t* sein.

volkard

SeppJ schrieb:

Kannst du mal ein Testprogramm geben?

Mal ein Entwurf:

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

/*****************************************************************************
**Jetzt das Makro zum Sichern der Ticks. Auf 32-Bit-Systemen kann man ueber
**rdtsc die gegenwaertigen Ticks auslesen, indem man die Adresse einer
**64-Bit-Zahl angibt. Auf 64-Bit-Systemen muss man Adressen zu zwei
**32-Bit-Zahlen angeben.
*****************************************************************************

#ifdef __x86_64__
#define SAVE_TICKS(x) \
    asm("rdtsc":    "=a"(*(uint32_t*)((my_cycle_counter_##x.my_ih.my_mem)+my_cycle_counter_##x.my_end)), \
            "=d"(*(uint32_t*)((my_cycle_counter_##x.my_ih.my_mem)+my_cycle_counter_##x.my_end+4)));
#else
#define SAVE_TICKS(x) \
    asm("rdtsc":    "=A"(*(uint64_t*)((my_cycle_counter_##x.my_ih.my_mem)+my_cycle_counter_##x.my_end)));
#endif*/

//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 );
}

#define MY_NUMBER 0x1100100010001fffULL
//#define MY_NUMBER 42ULL

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

uint64_t printUmdreh(uint64_t n){
	char* out=theOutputBuffer;
	do{
		*out++=n%10+'0';
		n/=10;
	}while(n!=0);
	*out='\0';
	//r soll mal in ein eigenes Register hüpfen wollen, mag out nicht mehr.
	for(char *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 uint64_t value)
{
    register uint64_t length=1;
    register uint64_t rvalue=value;

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

    return length;
}

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

/*Neuer Ansatz mit Logarithmus.*/
uint64_t get_new_length_log2(const uint64_t value)
{
    return (uint64_t)(log2(value)/log2(10))+1;
}

uint64_t printLog(uint64_t n){
	char* out=theOutputBuffer+get_new_length_log2(n);
	*out='\0';
	do{
		*--out=n%10+'0';
		n/=10;
	}while(n!=0);
}

uint64_t printSprintf(uint64_t n){
	sprintf(theOutputBuffer,"%llu",n);
}

uint64_t measure(char const* fName,uint64_t (*f)(uint64_t)){
	//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){
//			printf("%lld\n",time);
			minTime=time;
			left=maxLeft;
		}
		--left;
	}
	printf("function %s needs %lld ticks\n",fName,minTime);
	return minTime;
}

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

int main(void){
	memset(theOutputBuffer,0,64);
	printf("|%lld|\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);
	printLog(MY_NUMBER);
	printf("|%s|\n",theOutputBuffer);

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

	MEASURE(printUmdreh);
	MEASURE(printAlt);
	MEASURE(printLog);
	MEASURE(printSprintf);

    return 0;
}

|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
function printUmdreh needs 160 ticks
function printAlt needs 187 ticks
function printLog needs 202 ticks
function printSprintf needs 362 ticks

volkard

dachschaden schrieb:

Ich habe eine gute Stunde daran gearbeitet, den Code leserlich zu gestalten

function printUmdreh needs 62 ticks
function printAlt needs 64 ticks
function printLog needs 118 ticks
function printSprintf needs 210 ticks

Hm. Hm, hm, hm.

Vor allem habe ich das Gefühl, dass das Ergebnis des Logarithmus im Cache gehalten wird, da muss der das dann nicht berechnen.

Ich werd mir printUmdreh gleich noch mal genauer anschauen. Danke jedenfalls für den Code, der ist sehr aufschlussreich.

volkard schrieb:

dachschaden schrieb:

Ich habe eine gute Stunde daran gearbeitet, den Code leserlich zu gestalten

Das hört sich so böse an ...

Wutz

|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.

volkard

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.

Interessant.

Kannste den ASM-Code von _ui64toa mal zeigen?

Ich wollte ja schon immer mal die Ziffern vorwärts rauströpfeln lassen. Bin gerade dran und drauf und schau mir den ASM-Code erst an, wenn ich durch bin.

Hm, Volkard, ich glaube, damit wirst du nicht glücklich.
Ich habe mal hier Code von geborgt und das hier gebaut:

uint64_t _ui64toa(uint64_t n)
{
        char*__string=theOutputBuffer;
        uint64_t __value=n;
        char buf2[68] ;
        int len = 0, pos = 0 ;
        while (__value)
        {
                buf2[len++] = __value %10;
                __value /=10;
        }
        while (len)
        {
                int ch = buf2[--len] ;
                ch+= '0' ;
                __string[pos++] = ch ;
        }
        __string[pos] = 0 ;
}

Und dann ausgeführt:

|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
function printUmdreh needs 112 ticks
function printAlt needs 140 ticks
function printLog needs 248 ticks
function printSprintf needs 218 ticks
function _ui64toa needs 320 ticks

Auch mit -O2 ist es klar:

function printUmdreh needs 60 ticks
function printAlt needs 64 ticks
function printLog needs 118 ticks
function printSprintf needs 212 ticks
function _ui64toa needs 96 ticks

, dass deine Funktion für das unlimitierte Schreiben das schnellste ist, dicht gefolgt von meinem Code.
Allerdings stört mich da noch irgendwas ... ich kann auch nicht mit dem Finger daraufzeigen, aber etwas stört mich daran.

Nachtrag:
Habe jetzt auch noch einmal von WINE Code geborgt:

uint64_t wine_ui64toa(uint64_t value)
{
        char buffer[65];
        char *pos;
        int digit;
        pos = &buffer[64];
        *pos = '\0';
        do
        {
                digit = value % 10;
                value = value / 10;
                if (digit < 10)
                {
                        *--pos = '0' + digit;
                }
                else
                {
                        *--pos = 'a' + digit - 10;
                } /* if */
        } while (value != 0L);
        memcpy(theOutputBuffer, pos, &buffer[64] - pos + 1);
}

function printUmdreh needs 62 ticks
function printAlt needs 64 ticks
function printLog needs 118 ticks
function printSprintf needs 216 ticks
function _ui64toa needs 96 ticks
function wine_ui64toa needs 60 ticks

Aber das ist mit -O2. -O0 generiert:

function printUmdreh needs 114 ticks
function printAlt needs 140 ticks
function printLog needs 248 ticks
function printSprintf needs 216 ticks
function _ui64toa needs 320 ticks
function wine_ui64toa needs 218 ticks

volkard

dachschaden schrieb:

Hm, Volkard, ich glaube, damit wirst du nicht glücklich.
Ich habe mal hier Code von geborgt und das hier gebaut:

uint64_t _ui64toa(uint64_t n)
{
        char*__string=theOutputBuffer;
        uint64_t __value=n;
        char buf2[68] ;
        int len = 0, pos = 0 ;
        while (__value)
        {
                buf2[len++] = __value %10;
                __value /=10;
        }
        while (len)
        {
                int ch = buf2[--len] ;
                ch+= '0' ;
                __string[pos++] = ch ;
        }
        __string[pos] = 0 ;
}

Nee, wirklich nicht.
Der ganze Trick war, nicht inplace swappen zu müssen. Das passt auch fast zu den Messwerten von Wutz. So ebbes besser war es. Nee, nicht ganz!!! MS hat einen besseren Trick, denn wenn ich bei mir das Umdrehen ganz ausschalte, dann ist MS immernoch schneller (falls ich Eure Messwerte hochrechnen darf). Wir müssen den MS-Code anschauen, keine noch so gute Kopie. Jemand mit Windows möge sich erbarmen. Äh, Du natürlich, hast ja vorhin geschrieben. daß es auch auf Win drehen muss.

Mir scheint, "asm fbstp" führt zu keinem Sieg. Unglaublich lecker, klar. Aber dann den BCD-Code zu interpretieren? Ich weiß ja nicht…
Andererseits, 64Bit sind ne Menge Holz. Was kümmern einen da ein paar Konvertierungen, wenns danach flutscht? Evtl mit if(n>10000…) ne Sonderregel.

dachschaden schrieb:

Auch mit -O2 ist es klar:

Sorry, ich nehme nur -O3.

dachschaden schrieb:

, dass deine Funktion für das unlimitierte Schreiben das schnellste ist, dicht gefolgt von meinem Code.
Allerdings stört mich da noch irgendwas ... ich kann auch nicht mit dem Finger daraufzeigen, aber etwas stört mich daran.

Ich kanns ahnen. Du bist vielleicht auch im Geiste ein Progger, der triviale Hardware denkt. Ich hab mit nem ZX81 angefangen, 1k RAM und so. Es ist einfach voll unsinnig, zuerst voll viel Speicher zu schreiben und dann nochmal alles umzuwerfen. Ist halt nicht so, der Prozessor ist sowas von schnell, was ganz einfache Sachen angeht, aber Divisionen kosten endlos. Und die 64Byte sind im Prozessorcache, so schnell wie Register. Verrückte Welt.

Und nu kommt die Bescherung:

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

/*****************************************************************************
**Jetzt das Makro zum Sichern der Ticks. Auf 32-Bit-Systemen kann man ueber
**rdtsc die gegenwaertigen Ticks auslesen, indem man die Adresse einer
**64-Bit-Zahl angibt. Auf 64-Bit-Systemen muss man Adressen zu zwei
**32-Bit-Zahlen angeben.
*****************************************************************************

#ifdef __x86_64__
#define SAVE_TICKS(x) \
    asm("rdtsc":    "=a"(*(uint32_t*)((my_cycle_counter_##x.my_ih.my_mem)+my_cycle_counter_##x.my_end)), \
            "=d"(*(uint32_t*)((my_cycle_counter_##x.my_ih.my_mem)+my_cycle_counter_##x.my_end+4)));
#else
#define SAVE_TICKS(x) \
    asm("rdtsc":    "=A"(*(uint64_t*)((my_cycle_counter_##x.my_ih.my_mem)+my_cycle_counter_##x.my_end)));
#endif*/

//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 );
}

#define MY_NUMBER 0x1100100010001fffULL
//#define MY_NUMBER 42ULL

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

uint64_t tt=17;
uint64_t printUmdreh(uint64_t n){
	char* out=theOutputBuffer;
	do{
		tt*=17;
		*out++=n%10+'0';
		n/=10;
	}while(n!=0);
	*out='\0';
	//r soll mal in ein eigenes Register hüpfen wollen, mag out nicht mehr.
	for(char *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 uint64_t value)
{
    register uint64_t length=1;
    register uint64_t rvalue=value;

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

    return length;
}

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

/*Neuer Ansatz mit Logarithmus.*/
uint64_t get_new_length_log2(const uint64_t value)
{
    return (uint64_t)(log2(value)/log2(10))+1;
}

uint64_t printLog(uint64_t n){
	char* out=theOutputBuffer+get_new_length_log2(n);
	*out='\0';
	do{
		*--out=n%10+'0';
		n/=10;
	}while(n!=0);
}

uint64_t printSprintf(uint64_t n){
	sprintf(theOutputBuffer,"%llu",n);
}

char* vorwaerts_print9Digits(uint32_t n,char* dst){
	//assert(n<1000000000);//handles only 8 digits correctly
	uint64_t x=11529215046.06846976+1;//2^60/10^8
	uint64_t r=n*x;

	for(int i=0;i<9;++i){
		*dst++=((r)>>60)+'0';
		r&=0x0fffffffffffffff;
		r*=10;
	}
	return dst;
}

char* vorwaerts_printMax9Digits(uint32_t n,char* dst){
	//assert(n<1000000000);//handles only 8 digits correctly
	uint64_t x=11529215046.06846976+1;//2^60/10^8
	uint64_t r=n*x;

	int i=0;
	for(;i<9;++i){
		if(((r)>>60)!=0)
			break;
		r&=0x0fffffffffffffff;
		r*=10;
	}
	for(;i<9;++i){
		*dst++=((r)>>60)+'0';
		r&=0x0fffffffffffffff;
		r*=10;
	}
	return dst;
}

char* vorwaerts_printDigits(uint64_t n,char* dst){
	if(n>=10000000000000000000){
		*dst++='0'+n/10000000000000000000;
		n%=10000000000000000000;
		*dst++='0'+n/1000000000000000000;
		n%=1000000000000000000;
		dst=vorwaerts_print9Digits(n/1000000000,dst);
		dst=vorwaerts_print9Digits(n%1000000000,dst);
		return dst;
	}
	else if(n>=1000000000000000000){
		*dst++='0'+n/1000000000000000000;
		n%=1000000000000000000;
		dst=vorwaerts_print9Digits(n/1000000000,dst);
		dst=vorwaerts_print9Digits(n%1000000000,dst);
		return dst;
	}
	else if(n>=1000000000){
		dst=vorwaerts_printMax9Digits(n/1000000000,dst);
		dst=vorwaerts_print9Digits(n%1000000000,dst);
		return dst;
	}
	else{
		dst=vorwaerts_printMax9Digits(n,dst);
		return dst;
	}
}

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

uint64_t measure(char const* fName,uint64_t (*f)(uint64_t)){
	//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){
//			printf("%lld\n",time);
			minTime=time;
			left=maxLeft;
		}
		--left;
	}
	printf("function %s needs %lld ticks\n",fName,minTime);
	return minTime;
}

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

int main(void){
	memset(theOutputBuffer,0,64);
	printf("|%lld|\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);
	printLog(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(printLog);
	MEASURE(printSprintf);
	MEASURE(printVorwaerts);

    return 17;
}

|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
function printUmdreh needs 169 ticks
function printAlt needs 184 ticks
function printLog needs 199 ticks
function printSprintf needs 359 ticks
function printVorwaerts needs 48 ticks //BOOM!

Das hätte ich auch nicht gedacht. Uih!

Wie gesagt, ich wollte schon immer mal die Ziffern vorwärts rauströpfeln lassen; es war mir immer zu kompliziert und die alte Version war ja auch ganz gut. Irrelevant, weil die Ausgabe viel länger dauert. Dabei ist es gar nicht schwierig:
Man stellt die Zahl n=1234 einfach dar als Fixkommazahl r=1,234.
Aber binär! Trotzdem ist vor dem Komma binär die gesuchte Ziffer und dahinter der Rest.

Naja, ich freue mich so, daß ich's nochmal wiederholen muss:

function printVorwaerts needs 48 ticks //BOOM!

volkard

edit: ungetestet ob die 0 recht ausgegeben wird.

volkard schrieb:

Wir müssen den MS-Code anschauen, keine noch so gute Kopie. Jemand mit Windows möge sich erbarmen. Äh, Du natürlich, hast ja vorhin geschrieben. daß es auch auf Win drehen muss.

Jau. Kann aber ne Weile dauern. nm und objdump sehen da keine Symbole, aber ich kenne die DLL, die ich disassemblieren muss, Windows/System32/msvcrt.dll. Bumms. Und dann auch nur 64-Bit, also muss ich noch was anderes als IDA nehmen. Doppelbums.

volkard schrieb:

Mir scheint, "asm fbstp" führt zu keinem Sieg. Unglaublich lecker, klar. Aber dann den BCD-Code zu interpretieren? Ich weiß ja nicht…
Andererseits, 64Bit sind ne Menge Holz. Was kümmern einen da ein paar Konvertierungen, wenns danach flutscht? Evtl mit if(n>10000…) ne Sonderregel.

Dann kann ich genauso gut:

uint64_t printDumm(uint64_t n)
{
	register char* out=theOutputBuffer;
	register uint64_t pn=n;
	register uint64_t l=1;
	register char*r;
	if(pn>=10000000000000000000ULL)
		++l;
	if(pn>=1000000000000000000ULL)
		++l;
	if(pn>=100000000000000000ULL)
		++l;
	if(pn>=10000000000000000ULL)
		++l;
	if(pn>=1000000000000000ULL)
		++l;
	if(pn>=100000000000000ULL)
		++l;
	if(pn>=10000000000000ULL)
		++l;
	if(pn>=1000000000000ULL)
		++l;
	if(pn>=100000000000ULL)
		++l;
	if(pn>=10000000000ULL)
		++l;
	if(pn>=1000000000ULL)
		++l;
	if(pn>=100000000ULL)
		++l;
	if(pn>=10000000ULL)
		++l;
	if(pn>=1000000ULL)
		++l;
	if(pn>=100000ULL)
		++l;
	if(pn>=10000ULL)
		++l;
	if(pn>=1000ULL)
                ++l;
	if(pn>=100ULL)
                ++l;
	if(pn>=10ULL)
		++l;
	r=out+l;
	do
	{
		*--r=pn%10+'0';
		pn/=10;
	}
	while(pn);
}

machen ...

function printUmdreh needs 62 ticks
function printAlt needs 64 ticks
function printLog needs 118 ticks
function printSprintf needs 214 ticks
function _ui64toa needs 98 ticks
function wine_ui64toa needs 60 ticks
function printDumm needs 46 ticks //Ja klar, das ist überhaupt nicht bescheuert ... m(

volkard schrieb:

Ich kanns ahnen. Du bist vielleicht auch im Geiste ein Progger, der triviale Hardware denkt.

Exakt.

volkard schrieb:

Das hätte ich auch nicht gedacht. Uih!

Wie gesagt, ich wollte schon immer mal die Ziffern vorwärts rauströpfeln lassen; es war mir immer zu kompliziert und die alte Version war ja auch ganz gut. Irrelevant, weil die Ausgabe viel länger dauert. Dabei ist es gar nicht schwierig:
Man stellt die Zahl n=1234 einfach dar als Fixkommazahl r=1,234.
Aber binär! Trotzdem ist vor dem Komma binär die gesuchte Ziffer und dahinter der Rest.

Das muss ich mir noch mal in Ruhe anschauen - ist dann doch ein bisschen viel auf einmal.
Ich schau mir jetzt erst einmal den Maschinencode von _ui64toa an, vielleicht finde ich den Schlüssel.

@volkard:

Hier hast du das, was mir der DLL-Viewer rausgespuckt hat, bis zum ersten NOP. Allerdings ist mein Assembler zu eingerostet, um da effektiv was rauslesen zu können.

Einmal in AT&T-Syntax:

7ff756a4370:   48 8b c1                mov    %rcx,%rax
 7ff756a4373:   4c 8b da                mov    %rdx,%r11
 7ff756a4376:   4c 8b ca                mov    %rdx,%r9
 7ff756a4379:   41 8b c8                mov    %r8d,%ecx
 7ff756a437c:   4c 8b d2                mov    %rdx,%r10
 7ff756a437f:   33 d2                   xor    %edx,%edx
 7ff756a4381:   48 f7 f1                div    %rcx
 7ff756a4384:   83 fa 09                cmp    $0x9,%edx
 7ff756a4387:   77 2f                   ja     0x7ff756a43b8
 7ff756a4389:   80 c2 30                add    $0x30,%dl
 7ff756a438c:   41 88 11                mov    %dl,(%r9)
 7ff756a438f:   49 ff c1                inc    %r9
 7ff756a4392:   48 85 c0                test   %rax,%rax
 7ff756a4395:   75 e8                   jne    0x7ff756a437f
 7ff756a4397:   41 88 01                mov    %al,(%r9)
 7ff756a439a:   49 ff c9                dec    %r9
 7ff756a439d:   41 8a 02                mov    (%r10),%al
 7ff756a43a0:   41 8a 09                mov    (%r9),%cl
 7ff756a43a3:   41 88 01                mov    %al,(%r9)
 7ff756a43a6:   41 88 0a                mov    %cl,(%r10)
 7ff756a43a9:   49 ff c2                inc    %r10
 7ff756a43ac:   49 ff c9                dec    %r9
 7ff756a43af:   4d 3b d1                cmp    %r9,%r10
 7ff756a43b2:   72 e9                   jb     0x7ff756a439d
 7ff756a43b4:   49 8b c3                mov    %r11,%rax
 7ff756a43b7:   c3                      retq   
 7ff756a43b8:   80 c2 57                add    $0x57,%dl
 7ff756a43bb:   eb cf                   jmp    0x7ff756a438c

und einmal in Intel-Syntax

7ff756a4370:   48 8b c1                mov    rax,rcx
 7ff756a4373:   4c 8b da                mov    r11,rdx
 7ff756a4376:   4c 8b ca                mov    r9,rdx
 7ff756a4379:   41 8b c8                mov    ecx,r8d
 7ff756a437c:   4c 8b d2                mov    r10,rdx
 7ff756a437f:   33 d2                   xor    edx,edx
 7ff756a4381:   48 f7 f1                div    rcx
 7ff756a4384:   83 fa 09                cmp    edx,0x9
 7ff756a4387:   77 2f                   ja     0x7ff756a43b8
 7ff756a4389:   80 c2 30                add    dl,0x30
 7ff756a438c:   41 88 11                mov    BYTE PTR [r9],dl
 7ff756a438f:   49 ff c1                inc    r9
 7ff756a4392:   48 85 c0                test   rax,rax
 7ff756a4395:   75 e8                   jne    0x7ff756a437f
 7ff756a4397:   41 88 01                mov    BYTE PTR [r9],al
 7ff756a439a:   49 ff c9                dec    r9
 7ff756a439d:   41 8a 02                mov    al,BYTE PTR [r10]
 7ff756a43a0:   41 8a 09                mov    cl,BYTE PTR [r9]
 7ff756a43a3:   41 88 01                mov    BYTE PTR [r9],al
 7ff756a43a6:   41 88 0a                mov    BYTE PTR [r10],cl
 7ff756a43a9:   49 ff c2                inc    r10
 7ff756a43ac:   49 ff c9                dec    r9
 7ff756a43af:   4d 3b d1                cmp    r10,r9
 7ff756a43b2:   72 e9                   jb     0x7ff756a439d
 7ff756a43b4:   49 8b c3                mov    rax,r11
 7ff756a43b7:   c3                      ret    
 7ff756a43b8:   80 c2 57                add    dl,0x57
 7ff756a43bb:   eb cf                   jmp    0x7ff756a438c

Ich hoffe nur, ich habe jetzt nicht irgendein Copyright gebrochen oder so ...

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

Schlüssel ist die Konstante 11529215047 (2^60/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.

Länge einer Zahl in einer angegebenen Basis finden

Wert fuer Berechnung: 1224996691099262975

[example_1|0x226724e4ee54c|605222335341900|0x226724e4ee54c|605222335341900|"(Intern start)"]
[example_1|0x226724e4efc98|605222335347864|0x174c|5964|"get_number_length begin"]
[example_1|0x226724e4f0290|605222335349392|0x5f8|1528|"get_number_length end"]
[example_1|0x1d44|7492|"(Overall)"]

[example_2|0x226724e4ef1f4|605222335345140|0x226724e4ef1f4|605222335345140|"(Intern start)"]
[example_2|0x226724e4f02ac|605222335349420|0x10b8|4280|"log2 begin"]
[example_2|0x226724e4f02c4|605222335349444|0x18|24|"log2 end"]
[example_2|0x10d0|4304|"(Overall)"]

[example_3|0x226724e4efc7c|605222335347836|0x226724e4efc7c|605222335347836|"(Intern start)"]
[example_3|0x226724e4f0370|605222335349616|0x6f4|1780|"get_new_length_log2 begin"]
[example_3|0x226724e4f7188|605222335377800|0x6e18|28184|"get_new_length_log2 end"]
[example_3|0x750c|29964|"(Overall)"]

Länge einer Zahl in einer angegebenen Basis finden

Wert fuer Berechnung: 1224996691099262975

[example_1|0x226724e4ee54c|605222335341900|0x226724e4ee54c|605222335341900|"(Intern start)"] [example_1|0x226724e4efc98|605222335347864|0x174c|5964|"get_number_length begin"] [example_1|0x226724e4f0290|605222335349392|0x5f8|1528|"get_number_length end"] [example_1|0x1d44|7492|"(Overall)"]

[example_2|0x226724e4ef1f4|605222335345140|0x226724e4ef1f4|605222335345140|"(Intern start)"] [example_2|0x226724e4f02ac|605222335349420|0x10b8|4280|"log2 begin"] [example_2|0x226724e4f02c4|605222335349444|0x18|24|"log2 end"] [example_2|0x10d0|4304|"(Overall)"]

[example_3|0x226724e4efc7c|605222335347836|0x226724e4efc7c|605222335347836|"(Intern start)"] [example_3|0x226724e4f0370|605222335349616|0x6f4|1780|"get_new_length_log2 begin"] [example_3|0x226724e4f7188|605222335377800|0x6e18|28184|"get_new_length_log2 end"] [example_3|0x750c|29964|"(Overall)"]

[example_1|0x226724e4ee54c|605222335341900|0x226724e4ee54c|605222335341900|"(Intern start)"]
[example_1|0x226724e4efc98|605222335347864|0x174c|5964|"get_number_length begin"]
[example_1|0x226724e4f0290|605222335349392|0x5f8|1528|"get_number_length end"]
[example_1|0x1d44|7492|"(Overall)"]

[example_2|0x226724e4ef1f4|605222335345140|0x226724e4ef1f4|605222335345140|"(Intern start)"]
[example_2|0x226724e4f02ac|605222335349420|0x10b8|4280|"log2 begin"]
[example_2|0x226724e4f02c4|605222335349444|0x18|24|"log2 end"]
[example_2|0x10d0|4304|"(Overall)"]

[example_3|0x226724e4efc7c|605222335347836|0x226724e4efc7c|605222335347836|"(Intern start)"]
[example_3|0x226724e4f0370|605222335349616|0x6f4|1780|"get_new_length_log2 begin"]
[example_3|0x226724e4f7188|605222335377800|0x6e18|28184|"get_new_length_log2 end"]
[example_3|0x750c|29964|"(Overall)"]