make these functions more efficient

This is a discussion on make these functions more efficient within the C Programming forums, part of the General Programming Boards category; Hi everyone, Is there a way i can make these functions more efficient? Code: int UlitmateCollapse (int num) { int ...

  1. #1
    Waxy-Dock
    Join Date
    Mar 2005
    Posts
    69

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

  2. #2
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,249
    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)

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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

  4. #4
    Waxy-Dock
    Join Date
    Mar 2005
    Posts
    69
    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

  5. #5
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,249
    Quote Originally Posted by robatino View Post
    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.

  6. #6
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,249
    Quote Originally Posted by waxydock View Post
    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.

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by brewbuck View Post
    Unfortunately, there is no way to avoid taking the modulus (which is expensive), because the base is 10.
    Code:
    int ucs( int num )
    {
        char buf[ BUFSIZ ] = { 0 };
        int sum = 0, count = 0;
        if( sprintf( buf, "%d", num ) == 1 )
        {
            while( buf[ count ] )
                sum += (buf[ count++ ] - '0');
        }
            
        return whateverthehellyourfunctionsaresupposedtobecounting;
    }
    Well you can get rid of the modulus, you just have to be creative.


    Quzah.
    Hope is the first step on the road to disappointment.

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Isn't *printf() doing essentially the quotient/modulus calculation internally when it prints an integer in decimal format?

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Possibly. You don't have to use modulus to get a remainder.


    Quzah.
    Hope is the first step on the road to disappointment.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. can any1 plz make this assignment
    By jean in forum C Programming
    Replies: 17
    Last Post: 05-13-2009, 09:19 PM
  2. Functions are Still Not Understood.
    By errigour in forum C Programming
    Replies: 6
    Last Post: 04-09-2009, 02:54 PM
  3. Where to put local auxiliary functions?
    By draugr in forum C++ Programming
    Replies: 10
    Last Post: 03-17-2009, 08:46 PM
  4. Win32 Common Controls in C++, how do i make and use them?
    By C+noob in forum Windows Programming
    Replies: 6
    Last Post: 01-09-2006, 10:53 AM
  5. Statements and Functions
    By GeekFreak in forum C++ Programming
    Replies: 5
    Last Post: 08-15-2002, 12:34 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21