time limit exceeded problem

[gourav1]

#include<stdio.h>

 unsigned long int call( unsigned long int);

int main()
{
    int t=0,i;
    unsigned long int n;
   // scanf("%d",&t);


    while(t==0){

          scanf("%lu",&n);
        printf("%lu\n",call(n));


    //t--;
  }


}


long unsigned int call(long unsigned  int n)
{
    long unsigned int a,b,c,x,y,z,m,l;
    a=n/2;
    b=n/3;
    c=n/4;
    m=a+b+c;
    if(m>n)
    {
               x=call(a);
               y=call(b);
               z=call(c);
               l=x+y+z;
               if(l>m)
               return (l);
               else
               return(m);
    }
    else
    {
        return n;
    }

}

this is code i have written. tell me any possible way to reduce the execution time of this code. i have used shorthand operators and everything i can do. please help. thanks

[Adak]

The biggest improvement in run-time is always found by choosing the right algorithm - the logical steps that will be used by the program, to find the answer.

Then there are optimizations beyond the algorithmic one's, which I'd call "machine and language" optimizations.

This program appears to need both of them. What is the program trying to do, exactly?
And what are your run-time requirements for it's time?

[rubberman]

The call() function is heavily recursive. This leads to simplicity, but can create a lot of processing overhead, especially with stack setup/teardown on each function call. Also, in your code, you initialize variables by dividing the argument by 2, 3, and 4. Since the components of the operation are integers, the divisions by 2 and 4 can be sped up significantly by using shift operators instead of division. IE:

a=n>>1;
c=n>>2;

This will work fine on Intel processors which won't wrap the bits around if a bit is shifted off the end. I think ARM processors will work the same way, but I'm not 100% sure of that.

[gourav1]

The call() function is heavily recursive. This leads to simplicity, but can create a lot of processing overhead, especially with stack setup/teardown on each function call. Also, in your code, you initialize variables by dividing the argument by 2, 3, and 4. Since the components of the operation are integers, the divisions by 2 and 4 can be sped up significantly by using shift operators instead of division. IE:

a=n>>1;
c=n>>2;

This will work fine on Intel processors which won't wrap the bits around if a bit is shifted off the end. I think ARM processors will work the same way, but I'm not 100% sure of that.

r u sure ?

[rubberman]

In your call() function, inside the branch if (m>n) you have three subsequent calls to call(), each of which potentially calls itself 3 more times. This can cause a lot of stack winding/unwinding, hence time. Also, each call() has these 3 divisions in setting up its automatic (stack) variables, and divisions are expensive, especially compared to simple shift operations. You can reference the Intel processor documentation on the Intel web site to find out how many cpu cycles are required for an integer divide, vs a shift operation.

[rubberman]

FWIW, I was Principal Software Engineer for a major software company for almost 20 years, and now am Senior Performance Engineer for one of the largest technology companies in the world. I do know something of this subject.

[gourav1]

FWIW, I was Principal Software Engineer for a major software company for almost 20 years, and now am Senior Performance Engineer for one of the largest technology companies in the world. I do know something of this subject.

really ? i am shocked!! it's really nice to meet u here!! wow!! what a resume!!