A test for the answer to http://stackoverflow.com/questions/20477424/efficient-way-to-find-the-sum-of-digits-of-an-8-digit-number Stackoverflow question: "Efficient way to find the sum of digits of an 8 digit number"

so20477424.c

#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include <time.h>


/*
	Compile this with /DBUILD_TABLES=1 to create the lookup tables.

	The output of that run needs to be named /temp/digit_sum_table.h
	before you can build this program without BUILD_TABLES defined
	to run the actual tests.

	So, assuming this file is named 'foo.c':

	    # on Windows
		cl /DBUILD_TABLES=1 foo.c
		foo > \temp\digit_sum_table.h
		cl /Ox foo.c
		foo

		# on Linux
		gcc -DBUILD_TABLES=1 foo.c -o foo
		./foo > /temp/digit_sum_table.h
		gcc -O2 foo.c -o foo
		./foo

*/



/*
// From C++98:
//      returns an iterator pointing to the
//      first element with key not less than k.
//
//      Finds the first position into which value can
//      be inserted without violating the ordering.
//
//      Returns: The furthermost iterator i in the range
//          [first, last] such that for any iterator j in the
//          range [first, i) the following corresponding conditions
//          hold: (*j < value) or (comp(*j, value) != false)
//

// from http://www.cplusplus.com/reference/algorithm/lower_bound/

template <class ForwardIterator, class T>
ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last, const T& value )
{
ForwardIterator it;
iterator_traits<ForwardIterator>::distance_type count, step;
count = distance(first,last);
while (count>0)
{
it = first; step=count/2; advance (it,step);
if (*it<value)                   // or: if (comp(*it,value)), for the comp version
{ first=++it; count-=step+1;  }
else count=step;
}
return first;
}

*/

void* bsearch_lbound(
	void const* key,
	void const* base,
	size_t nmemb,
	size_t size,
	int(*compar)(void const *, void const*))
{
	char* begin = (char*)base;

	while (nmemb) {
		size_t mid = nmemb / 2;
		char* cur = begin + (mid * size);

		if (compar(key, cur) > 0) {
			begin = cur + size;
			nmemb = nmemb - (mid + 1);
		}
		else {
			nmemb = mid;
		}
	}

	return begin;
}




/*
// From C++98:
//      returns an iterator pointing to the
//          first element with key greater than k.
//
//      Effects: Finds the furthermost position into which value
//          can be inserted without violating the ordering.
//
//      Returns: The furthermost iterator i in the range [first, last)
//          such that for any iterator j in the range [first, i) the
//          following corresponding conditions hold: !(value < *j) or
//          comp(value, *j) == false
//

// from http://www.cplusplus.com/reference/algorithm/upper_bound/

template <class ForwardIterator, class T>
ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last, const T& value )
{
ForwardIterator it;
iterator_traits<ForwardIterator>::distance_type count, step;
count = distance(first,last);
while (count>0)
{
it = first; step=count/2; advance (it,step);
if (!(value<*it))                 // or: if (!comp(value,*it)), for the comp version
{ first=++it; count-=step+1;  }
else count=step;
}
return first;
}
*/


void* bsearch_ubound(
	void const* key,
	void const* base,
	size_t nmemb,
	size_t size,
	int(*compar)(void const*, void const*))
{
	char* begin = (char*)base;

	while (nmemb) {
		size_t mid = nmemb / 2;
		char* cur = begin + (mid * size);

		if (compar(key, cur) >= 0) {
			begin = cur + size;
			nmemb = nmemb - (mid + 1);
		}
		else {
			nmemb = mid;
		}
	}

	return begin;
}



int sum_digits(int x)
{
	int sum = 0;

	while (x) {
		int dig = x % 10;
		x /= 10;

		sum += dig;
	}

	return sum;
}


struct digit_sum_rec {
	int num;
	int digit_sum;
};

extern struct digit_sum_rec digit_sum_lookup[10000];
extern struct digit_sum_rec digit_sum_lookup_reverse[10000];
extern int digit_sum_count[37];



int compare_digit_sum(void const* p1, void const* p2)
{
	struct digit_sum_rec const* r1 = (struct digit_sum_rec const*) p1;
	struct digit_sum_rec const* r2 = (struct digit_sum_rec const*) p2;

	if (r1->digit_sum < r2->digit_sum) return -1;
	if (r1->digit_sum > r2->digit_sum) return  1;

	// equal digit_sum values  
	if (r1->num < r2->num) return -1;
	if (r1->num > r2->num) return  1;

	return 0;
}



int get_matching_sum_count(int target_sum, int first, int last)
{
	struct digit_sum_rec* lb = digit_sum_lookup_reverse;
	struct digit_sum_rec* ub = digit_sum_lookup_reverse + 10000;

	struct digit_sum_rec key = { 0, target_sum };

	key.num = first;
	lb = (struct digit_sum_rec*) bsearch_lbound(&key, lb, ub-lb, sizeof(*lb), compare_digit_sum);

	key.num = last;
	ub = (struct digit_sum_rec*) bsearch_ubound(&key, lb, ub-lb, sizeof(*ub), compare_digit_sum);

	return (ub - lb);
}


int get_matching_sum_count_brute(int target_sum, int first, int last)
{
	int res = 0;
	int i = first;
	
	for (; i <= last; ++i) {
		res += (sum_digits(i) == target_sum);
	}
	
	return res;
}



#ifndef BUILD_TABLES

#include "/temp/digit_sum_table.h"

int alg1(int low, int high)
{
	int res = 0;
	int cnt = 0;

	for (cnt = low; cnt <= high; cnt++)
	{
		int first4 = cnt % 10000;
		int sum1 = first4 % 10 + (first4 / 10) % 10 + (first4 / 100) % 10 + (first4 / 1000) % 10;
		int second4 = cnt / 10000;
		int sum2 = second4 % 10 + (second4 / 10) % 10 + (second4 / 100) % 10 + (second4 / 1000) % 10;

		if (sum1 == sum2)
			res++;

	}

	return res;
}



int alg2(int first, int last)
{
	int i = 0;
	int res = 0;

	int mostsig_first = first / 10000;
	int leastsig_first = first % 10000;

	int mostsig_last = last / 10000;
	int leastsig_last = last % 10000;


	// handle singular partial range
	if (mostsig_first == mostsig_last) {
		int target = digit_sum_lookup[mostsig_first].digit_sum;

		for (i = leastsig_first; i <= leastsig_last; ++i) {
			res += (digit_sum_lookup[i].digit_sum == target);
		}
	}
	else {
		int j = 0;

		// get result from first partial range
		int target = 0;
		target = digit_sum_lookup[mostsig_first].digit_sum;
		for (i = leastsig_first; i <= 9999; ++i) {
			res += (digit_sum_lookup[i].digit_sum == target);
		}

		// get result from last partial range
		target = digit_sum_lookup[mostsig_last].digit_sum;
		for (i = 0; i <= leastsig_last; ++i) {
			res += (digit_sum_lookup[i].digit_sum == target);
		}

		// get results from any interior complete range
		for (j = mostsig_first + 1; j < mostsig_last; ++j) {
			target = digit_sum_lookup[j].digit_sum;
			for (i = 0; i <= 9999; ++i) {
				res += (digit_sum_lookup[i].digit_sum == target);
			}
		}
	}

	return res;
}


int alg3(int first, int last)
{
	int res = 0;

	int mostsig_first = first / 10000;
	int leastsig_first = first % 10000;

	int mostsig_last = last / 10000;
	int leastsig_last = last % 10000;

	// handle singular partial range
	if (mostsig_first == mostsig_last) {

		res = get_matching_sum_count(digit_sum_lookup[mostsig_first].digit_sum, leastsig_first, leastsig_last);
	}
	else {
		int i = 0;

		// get result from first partial range
		//int tmp1 = get_matching_sum_count(sum_digits(mostsig_first), leastsig_first, 9999);
		//int tmp2 = alg1(mostsig_first * 10000 + leastsig_first, mostsig_first * 10000 + 9999);
		//assert(tmp1 == tmp2);

		res += get_matching_sum_count(digit_sum_lookup[mostsig_first].digit_sum, leastsig_first, 9999);

		// get result from last partial range
		//tmp1 = get_matching_sum_count(sum_digits(mostsig_last), 0, leastsig_last);
		//tmp2 = alg1(mostsig_last * 10000, mostsig_last * 10000 + leastsig_last);
		//assert(tmp1 == tmp2);

		res += get_matching_sum_count(digit_sum_lookup[mostsig_last].digit_sum, 0, leastsig_last);

		// get results from any interior complete range
		for (i = mostsig_first + 1; i < mostsig_last; ++i) {
			//tmp1 = get_matching_sum_count(sum_digits(i), 0, 9999);
			//tmp2 = alg1(i * 10000, i * 10000 + 9999);
			//assert(tmp1 == tmp2);

			res += get_matching_sum_count(digit_sum_lookup[i].digit_sum, 0, 9999);
		}
	}

	return res;
}


int alg4(int first, int last)
{
	// this is an algorithm based on the idea put forth by pepo in 
	// his answer here:
	//
	//	http://stackoverflow.com/a/20480515/12711
	//
	// Basically it uses a lookup table that tracks how many four
	//	digit numbers sum to a particular values
	//
	// There is some speical handling to deal with partial rances (as 
	//	usual)
	//
	
    int res = 0;
    
	int mostsig_first = first / 10000;
	int leastsig_first = first % 10000;

	int mostsig_last = last / 10000;
	int leastsig_last = last % 10000;

	// handle singular partial range
	if (mostsig_first == mostsig_last) {

		res = get_matching_sum_count(digit_sum_lookup[mostsig_first].digit_sum, leastsig_first, leastsig_last);
	}
	else {
		int i = 0;

		// get result from first partial range
		res += get_matching_sum_count(digit_sum_lookup[mostsig_first].digit_sum, leastsig_first, 9999);

		// get result from last partial range
		res += get_matching_sum_count(digit_sum_lookup[mostsig_last].digit_sum, 0, leastsig_last);

		// get results from any interior complete range
		for (i = mostsig_first + 1; i < mostsig_last; ++i) {

			res += digit_sum_count[digit_sum_lookup[i].digit_sum];
		}
	}

	return res;
}



int alg5(int first, int last)
{
	// alg5 is the same as alg4 except that instead of using alg3 to 
	//	determine the counts for partial ranges a brute force iteration
	//	over the partial ranges is done.
	// 
	// this works because there's a limit of 2 * 10000 partial range 
	//	values to check
	//
	// So with this algorithm, the only table necessary is the
	//	37 element digit_sum_count[] array that tracks how many 
	//	four digit numbers sum to a particular value.
	//
	// It seems that this algorithm hits the sweet spot between
	//	size and efficiency.  alg4 might be slightly faster, but
	//	not measurably so (by `clock()` anyway) and it requires
	//	a couple of 10000 element tables.
	//
	

    int res = 0;
    
	int mostsig_first = first / 10000;
	int leastsig_first = first % 10000;

	int mostsig_last = last / 10000;
	int leastsig_last = last % 10000;

	// handle singular partial range
	if (mostsig_first == mostsig_last) {

		res = get_matching_sum_count_brute(sum_digits(mostsig_first), leastsig_first, leastsig_last);
	}
	else {
		int i = 0;

		// get result from first partial range
		res += get_matching_sum_count_brute(sum_digits(mostsig_first), leastsig_first, 9999);

		// get result from last partial range
		res += get_matching_sum_count_brute(sum_digits(mostsig_last), 0, leastsig_last);

		// get results from any interior complete range
		for (i = mostsig_first + 1; i < mostsig_last; ++i) {

			res += digit_sum_count[sum_digits(i)];
		}
	}

	return res;
}




int main(void)
{
	clock_t time_start, time_end;
	int res1 = 0;
	int res2 = 0;
	int res3 = 0;
	int res4 = 0;
	int res5 = 0;

    double duration_alg1 = 0;
    double duration_alg2 = 0;
    double duration_alg3 = 0;
    double duration_alg4 = 0;
    double duration_alg5 = 0;

	// make these numbers volatile to simulate reading them from an input file
	//	otherwise the compiler may optimize things so that `alg1()` call is 
	//	done when the `print()` call wants the results (therefore it's not timed).
	//	The `alg1()` still takes the same amount of time, it just doesn't show up 
	//	in the time calculated in `duration_alg1`.

	volatile int M = 10000000;
	volatile int N = 99999999;

	time_start = clock();
	res1 = alg1(M, N);
	time_end = clock();

	duration_alg1 = (double)time_end - (double)time_start;

	time_start = clock();
	res2 = alg2(M, N);
	time_end = clock();

	duration_alg2 = (double)time_end - (double)time_start;

	time_start = clock();
	res3 = alg3(M, N);
	time_end = clock();

	duration_alg3 = (double)time_end - (double)time_start;

	time_start = clock();
	res4 = alg4(M, N);
	time_end = clock();

	duration_alg4 = (double)time_end - (double)time_start;

	time_start = clock();
	res5 = alg5(M, N);
	time_end = clock();

	duration_alg5 = (double)time_end - (double)time_start;

	printf("alg1(%d, %d):     %d, %.6f seconds\n", M, N, res1, duration_alg1 / CLOCKS_PER_SEC);
	printf("alg2(%d, %d):     %d, %.6f seconds\n", M, N, res2, duration_alg2 / CLOCKS_PER_SEC);
	printf("alg3(%d, %d):     %d, %.6f seconds\n", M, N, res3, duration_alg3 / CLOCKS_PER_SEC);
	printf("alg4(%d, %d):     %d, %.6f seconds\n", M, N, res4, duration_alg4 / CLOCKS_PER_SEC);
	printf("alg5(%d, %d):     %d, %.6f seconds\n", M, N, res5, duration_alg5 / CLOCKS_PER_SEC);
	return 0;
}

#else

// build the various lookup tables

struct digit_sum_rec digit_sum_lookup[10000];
struct digit_sum_rec digit_sum_lookup_reverse[10000];
int digit_sum_count[37];

int compare_digit_sum(void const* p1, void const* p2);


int main(void)
{
	int i;

	for (i = 0; i<10000; ++i) {
		digit_sum_lookup[i].num = i;
		digit_sum_lookup[i].digit_sum = sum_digits(i);

		digit_sum_lookup_reverse[i].num = i;
		digit_sum_lookup_reverse[i].digit_sum = sum_digits(i);
	}

	qsort(digit_sum_lookup_reverse, 10000, sizeof(digit_sum_lookup_reverse[0]), compare_digit_sum);
	
	for (i = 0; i < 10000; ++i) {
		
	    digit_sum_count[sum_digits(i)] += 1;
	}

	// puts(
	// 	"struct digit_sum_rec {\n"
	// 	"    int num;\n"
	// 	"    int digit_sum;\n"
	// 	"};\n\n"
	// 	);


	puts("struct digit_sum_rec digit_sum_lookup[] = {");
	for (i = 0; i<10000; ++i) {
		printf("{ %d, %d },\n", digit_sum_lookup[i].num, digit_sum_lookup[i].digit_sum);
	}
	puts("};");

	puts("");
	puts("");

	puts("struct digit_sum_rec digit_sum_lookup_reverse[] = {");
	for (i = 0; i<10000; ++i) {
		printf("{ %d, %d },\n", digit_sum_lookup_reverse[i].num, digit_sum_lookup_reverse[i].digit_sum);
	}
	puts("};");

	puts("");
	puts("");

	puts("int  digit_sum_count[] = {");
	for (i = 0; i<37; ++i) {
		printf("%d,\n", digit_sum_count[i]);
	}
	puts("};");

	return 0;
}
#endif /* BUILD_TABLES */