CODEWITHSUNDEEP
c++algorithmperformancesequencesquare
prolific
prolific

Reputation: 13

How to make the computation faster?

Here is short code which computes sum of all square numbers(not actually sum of squares) till n,where n can be upto 10 pow 20.

    long long res=0;
    long long sm=0;

    for (long long i = 1; res <=n; i=i+2)
    {
        res = (res+i);
        sm  = sm+(res*(n/res));

    }

How do we make the above code work faster? Here, the computation of sm is taking time for very large n like 10 pow 20.

Is there any way that the computation of sm can be made faster?

Here res computes all the square numbers like 1,4,9,16,25....

Lets say n=10, then the squares are 1,4,9 and then by the above code the sm is (1)(10/4)+(4)(10/4)+(9)(10/9)=27.

1*10+4*2+9*1=27.

Here the division is integer division.

edit1:

i need to compute sm mentioned in above code.

here sm is summation ( i2 * floor(n/(i2)) ) where i=1 to sqrt(n)

Upvotes: 0

Views: 433

Answers (2)

user11422223
user11422223

Reputation:

Is there any way that the computation of sm can be made faster?

If you notice the pattern plus apply some mathematics, yes.

The next perfect square after your very first perfect square (1 in all cases except for n==0) will be the square of ceil(sqrt(first number)).

In other words, the square root of say the nth number, in correspondence to your first number will be given by pow(ceil(sqrt(L)), n).

Now, notice the pattern between squares: 0 1 4 9 16 25...
Difference between 0 and 1 is 1
Difference between 1 and 4 is 3
Difference between 4 and 9 is 5
Difference between 9 and 16 is 7
Difference between 16 and 25 is 9, and so on.

This makes it clear that the difference between two perfect squares is always an odd number.

Proceeding with this knowledge, you'll need to know what must be added to get the next number, the answer to which is (sqrt(square) * 2) + 1).

i.e., current_square + (sqrt(current_square)*2+1) = next_square.

For instance and to prove this equation, consider the perfect square 25. Applying this logic, the next perfect square will be 25 + (sqrt(25) * 2 + 1) = 36, which is correct. Here 11 is added to 25, which is an odd number.

Similarly if you follow this trend, you'll observe all these numbers are odd, with a difference of +2. For finding the next square of 2, you'll need to add (sqrt(22)+1) = 5 to it (4+5=9); for finding the next square (i.e. for 3) you'll need to add (sqrt(32+1) = 7 to it (9+7=16). The difference is always +2.

Moreover, summing the odd number or applying addition is computationally less expensive than performing multiplication or finding square roots of every number, so your complexity should be fine.

Following that, do this:

  • Collect the first square. (which ideally should be 1, but if n>0 condition is not mentioned, apply the condition if(n!=0) to my logic)
  • Assign the next term's difference as first_square*2+1. You'll need to add the first square though, as this is not the next square, but the difference between next square and current square. Add the term in a loop like I did below.
  • Run a loop upto your required number. Collect your required sum given by (square*floor(n/square) in a variable within the loop.
  • Follow the approach I mentioned above, i.e. add the current square to the next term (difference between current and next square) and increment next square by 2.

A working example for the above logic:

#include <iostream>
#include <cmath>
#define ll long long 
int main() 
{ 
    ll int n; 
    std::cin>>n;

   // Start from 1: (add case for 0 if input is not >0)
   // you can also start from any other square or define a range.
    ll int first = 1; 

   // Square it:
    ll int first_square = first * first; 

   // Find next square:
    ll int next = (first_square * 2) + 1; 

   // Initialize variable to collect your required sum:
    ll int sum = 0;
    ll int square = first_square;

    while ((square >= 0 && square <= n)) 
    {  
        sum += (square *floor(n/square));

        // Add the perfect square: 
        square += next; 

        // Next odd number to be added:
        next += 2;      
    }     
    std::cout<<sum;  
    return 0; 
}

Upvotes: 2

backdoor
backdoor

Reputation: 901

we can find the sum of all square number till n using the formaula :

n * (n + 1) * (2*n + 1) / 6

long summation(long n) 
{ 
    return (n * (n + 1) *  
        (2 * n + 1)) / 6; 
}

Upvotes: 2

Related Questions