Performance on sum of many ints by Python

There is a such question  at codewars(http://www.codewars.com) site.

Write a function to do calculation according below formula:

mlbRlEm

for i from 1 to n, do i % m and return this sum

for example: f(n=10,m=5) //return 20 (1+2+3+5+0+1+2+3+4+0)

actually it is a quite simple algorithm, use python to do it like:

and it works very well when m and n are not very large.

But the performance will be very bad once n and m are very large, for example f(123939234234,249453949) and can not pass the test case of codewars.

We have to find out more clever algorithm.

There is a popular story that Gauss, mathematician extraordinaire, had a lazy teacher. The so-called educator wanted to keep the kids busy so he could take a nap; he asked the class to add the numbers 1 to 100.

Gauss approached with his answer: 5050. So soon? The teacher suspected a cheat, but no. Manual addition was for suckers, and Gauss found a formula to sidestep the problem:

\displaystyle{\text{Sum from 1 to n} = \frac{n(n+1)}{2}}

\displaystyle{\text{Sum from 1 to 100} = \frac{100(100+1)}{2} = (50)(101) = 5050}

It is said that Gauss was just 10 years old at that time.

We can use a illustrator to show the steps of the algorithm which we need to create.

gauss-sum

n can be divided by m into x parts, if n<m then x=0

Every sum of x can be calculated by m*(m-1)/2, there is a different with Gauss’ formula, m-1 instead of m+1, that because m % m=0.

Grown bar mean the value of n%m, just use normal Gauss formula to calculate it.

So our algorithm will be very simple.

First, get x=n/m, if n<m the x=0

Second, get c=n%m

At last sum them together: sum=x*(m*(m-1)/2) + (c+1)*c/2

 

The following two tabs change content below.
Wang Weiqiang is a senior web developer, and professional on ASP.NET, MVC, C#, Python, SQL Server, HTML5, Javascript, also interesting in machine learning and related algorithm.

Latest posts by Wang Weiqiang (王维强) (see all)

Wang Weiqiang is a senior web developer, and professional on ASP.NET, MVC, C#, Python, SQL Server, HTML5, Javascript, also interesting in machine learning and related algorithm.

Posted in Algorithm Tagged with: ,

Leave a Reply

Your email address will not be published. Required fields are marked *

*

Categories

Recent Posts

Related Posts