sum of sequares

[LOGIC]

Hi

 

I have tried to write program to calculate the sum of squares of number from 1 to n without using multiplication and it is supposed to be the efficient.

 

I end up with this function that calculate the square of a number recursively and I made iterative function to calculate the sum of the squares but when it come to write the sum function recursively I could not do it.

Take a look.

 

c code for find the square

int sqr(int n)
{
   if(n>1)
   {

          return sqr(n-1)+n+n-1;
   }
   else
   return 1;
}

 

c code for the itritive sum square function

int sumSqr(int n)
{
   int i,j,f;    
   for(i=1;i<=n;i++)
   {
          if(i==1)
          {
                  j=1;
                  f=j;
          }
          else
          { 
                 j=j+i+i-1;
                 f=f+j;
          }
   }   
   return f;    
} 

 

HOW TO WRITE SIMILER FUNCTION RECURSEVLY?

[RyanJ]

HOW TO WRITE SIMILER FUNCTION RECURSEVLY?

 

One question, why would you want too? Multiplication is basically addition to a computer so there is really no difference in the method but recursive funcitons put some strain on the computer when they run for long periods

 

Cheers,

 

Ryan Jones

[timo]

I´ll assume that n are natural numbers:

 

Recursively it would look something like:

int sumSqr(int n)  {  if (n<=0) {return 0;} else {return n*n + sumSqr(n-1);} }

 

But as already mentioned by RyanJ, iterative method are usually preferable over recursive one when it comes to efficiency of the code (recursive looks nicer on the source-lvl though):

1) Calling functions takes processing time.

2) Calling functions takes up memory.

 

A way to get rid of the multiplication is realizing that the distance between two squares of two ajdecent natural numbers increases by two with each step. Consider (0², 1², 2², 3²,4²,5²,...) = (0,1,4,9,16,25). The difference beween two ajecent squares is (1, 3, 5, 7, 9) and as you see increases by two in each step. A code using this would look something like this:

int sumSqr(int n)
{ int result =0;
 int delta = 3;
 int nSquared = 1;
 for (; n>0; n--)  {
   result += nSquared;
   nSquared += delta;
   delta += 2;
 }
 return result;
}

 

On modern machines (pentium and up) it´s probably not worth getting rid of the multiplication, it´s as fast as an addition if I remember correctly.

[RyanJ]

On modern machines (pentium and up) it´s probably not worth getting rid of the multiplication' date=' it´s as fast as an addition if I remember correctly.[/quote']

 

Yes you are correct. A compute basically works with bits so to it addition and multiplication are (basically anyway) one and the same thing

As I remember everything is one in terms of addition to a computer, division etc.

 

On a side note: its a bit different with division but its not enough to warent any sort of change to a code to account for, it just makes things more complicated!

 

Cheers,

 

Ryan Jones

[LOGIC]

thank you very much guys.

I forgot to mention that I am practicing writing algorithms by induction and that was one question the instructor gave us .

 

After some tries I relied that the best way to write it recursively is to save the returned value and add the next returned to it by using a variable defined out side the function, but the problem was How could I make the first call for the function returns the value in that variable and make other calls return the square?

 

I got some help from a friend and end up with this function

 

int i,z,f;
bool m=false;

int sqr(int n)
{
   int i,j=0;
   if(n>1)
   {
          if(!m)
          {
          z=n;
          m=true;
          }
          i=sqr(n-1)+n+n-1;
          f=f+i;
          if(n==z)
          return f;
          else
          return i; 
   }
   else
   return f=1;
}

 

thank you very much, your posts were very helpful