So today I was presented with a challenge that has multiple solutions but which is the fastest. So I set out to figure it out. The challenge was how can you compute the number of digits in an integer easily. There are 3 obvious solutions but which one is better. So I coded up a basic example of each and tested them out.

The four methods that I have tested are, using strings, log based methods, a loop and divide and a loop with multiplication instead. (See the code below)

To be honest the results were not really surprising, the loop method came out on top after running each method a million times and averaging the results.

Results:

Log Method:                     All Runs: 32 ms       perRun: 0.032 us
String Method:                All Runs: 146 ms     perRun: 0.146 us
Loop Method Div:          All Runs: 21 ms       perRun: 0.021 us
Loop Method No Div:   All Runs: 14 ms       perRun: 0.014 us

What was surprising from the results was how computationally expensive the string method was. From this it become blatantly obvious for the need to prevent casting things to strings when you can get any info you want from a mathematical approach. Furthermore, with a little analysis you can see that using multiplication is a lot faster than division taking about 2/3 of the time.

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <sys/time.h>

double time_to_ms(struct timeval tv) {
	return (tv.tv_sec) * 1000 + (tv.tv_usec) / 1000;
} 

int digitsLog(int num) {
	if (num == 0)
		return 1;

	return (int) floor(log10(num)) + 1;
}

int digitsStr(int num) {
	char tmp[15]; 
	sprintf(tmp, "%d",num);
	return (int) strlen(tmp);
}

int digitsDiv(int num) {
	int cnt = 0;

	while (num){
		num /= 10;
		cnt++;
	}

	return cnt;
}

int digitsNoDiv(const int number)
{
	int digits = 0;
	int step = 1;
	while (step <= number) {
		digits++;
		step *= 10;
	}
	return digits ? digits : 1;
}

int main()
{
	struct timeval tv1;
	struct timeval tv2;

	int i = 0;
	int j = 0;
	int cnt = 999999;

	double time1 =  time_to_ms(tv1);
	double time2 =  time_to_ms(tv2);

	gettimeofday(&tv1, NULL);

	for (i = 1; i <= cnt; i++){
		j = digitsLog(i);
	}

	gettimeofday(&tv2, NULL);

	time1 =  time_to_ms(tv1);
	time2 =  time_to_ms(tv2);

	printf("Log Method: All Runs: %lfms perRun: %lfus\n", time2 - time1, (1000*(time2 - time1)/i));

		gettimeofday(&tv1, NULL);

	for (i = 1; i <= cnt; i++){
		j = digitsStr(i);
	}

	gettimeofday(&tv2, NULL);

	time1 =  time_to_ms(tv1);
	time2 =  time_to_ms(tv2);

	printf("String Method: All Runs: %lfms perRun: %lfus\n", time2 - time1, (1000*(time2 - time1)/i));

	gettimeofday(&tv1, NULL);

	for (i = 1; i <= cnt; i++){
		j = digitsDiv(i);
	}

	gettimeofday(&tv2, NULL);

	time1 =  time_to_ms(tv1);
	time2 =  time_to_ms(tv2);

	printf("Loop Method Div: All Runs: %lfms perRun: %lfus\n", time2 - time1, (1000*(time2 - time1)/i));

	gettimeofday(&tv1, NULL);

	for (i = 1; i <= cnt; i++){
		j = digitsNoDiv(i);
	}

	gettimeofday(&tv2, NULL);

	time1 =  time_to_ms(tv1);
	time2 =  time_to_ms(tv2);

	printf("Loop Method No Div: All Runs: %lfms perRun: %lfus\n", time2 - time1, (1000*(time2 - time1)/i));
}