Thread: make these functions more efficient

Hi everyone,

Is there a way i can make these functions more efficient?

Code:

int UlitmateCollapse (int num) {

	int ones, sum = 0;
	
	/* check if integer is one digit long */
	if (digitcount(num) == 1) {
		
		return num;
	}

	/* sum up all digits in the double */
	while (num != 0) {

		ones=num%10;	
		num=num/10; 
		sum = sum + ones;
	}

	return UlitmateCollapse(sum);	
}

int digitcount (int num) {

    int count, ones =0;
    
    while (num != 0) {

		ones=num%10;	
		num=num/10; 
		count = count + 1;
	}	

    return count;
}

Unfortunately, there is no way to avoid taking the modulus (which is expensive), because the base is 10. If you were talking hexadecimal, this would be easy.

The only real optimization that's possible is to replace the call to digitcount(num). It can be done by a simple check if(num < 10) Because obviously, any number less than 10 must be only a single digit, provided negative values are not possible.

If negative values ARE allowed, you're going to have some trouble anyway, because of the funky definition of modulus for negative values (it's not the same as the definition used in mathematics)

You can use div() to simultaneously compute the quotient and remainder. I don't know how the efficiency typically compares with doing it separately (I'd be interested in knowing if someone wants to enlighten me, since I've written some code that uses it).

http://www.cplusplus.com/reference/c...tdlib/div.html

ok, i heard off a friend that there was a way to avoid the recursive call by playing with the modules..

you see all the function needs to do is return the ultimate collapse, which is just a single digit - to get it you just keep adding the digits of the input number until the result is a single digit.

ie. assume the input number is 12345
= 1+2+3+4+5 = 15 = 1+5 = 6

Originally Posted by robatino

You can use div() to simultaneously compute the quotient and remainder. I don't know how the efficiency typically compares with doing it separately (I'd be interested in knowing if someone wants to enlighten me, since I've written some code that uses it).

On machines where the division operation results in both the quotient and a remainder (for instance, Intel chips), the compiler is usually able to take advantage of it. Especially in the case where you do one immediately followed by the other.

Originally Posted by waxydock

ok, i heard off a friend that there was a way to avoid the recursive call by playing with the modules..

Since the recursive call is the last thing that happens, it is known as "tail recursion." Many compilers are able to transform it into an iterative version, removing the recursion. But don't count on it.

You can do it manually, by just jumping back to the top of the function with goto, or even better, using an appropriate looping construct. Often, just wrapping the entire function with "while(1)" is sufficient.

Isn't *printf() doing essentially the quotient/modulus calculation internally when it prints an integer in decimal format?

if (digitcount(num) == 1) {

I prefer the slightly less over-engineered:

Code:

if (num < 10) {

I also don't use recursion at the drop of a hat...