[Tutor] Loop comparison

[Steven D'Aprano]

On Fri, 16 Apr 2010 06:29:40 pm Alan Gauld wrote:
> "Stefan Behnel" <stefan_ml at behnel.de> wrote
>
> >     import cython
> >
> >     @cython.locals(result=cython.longlong, i=cython.longlong)
> >     def add():
> >         result = 0
> >         for i in xrange(1000000000):
> >             result += i
> >         return result
> >
> >     print add()
[...]
> Or is cython doing the precalculation optimisations you mentioned?
> And if so when does it do them? Because surely, at some stage, it
> still has to crank the numbers?
>
> (We can of course do some fancy math to speed this particular
> sum up since the result for any power of ten has a common pattern,
> but I wouldn't expect the compiler optimiser to be that clever)

No fancy maths needed, although I'd be amazed (in a good way) to learn 
that compiler compiler optimizers recognised this case! Are optimizing 
compilers really that clever these days?

The sum of 1,2,3,4,...,N is given by a simple formula: 1/2*N*(N+1). An 
anecdote about the great mathematician Carl Gauss is that while still a 
very young child in primary school, his teacher assigned the class the 
problem of adding the numbers 1 through 100 in order to keep them 
occupied for an hour or so. To his astonishment, Gauss gave him the 
answer within seconds. He reasoned like this:

sum =   1 +  2 +  3 +  4 + ... + 99 + 100
sum = 100 + 99 + 98 + 97 + ... +  2 +   1
2*sum = 101 + 101 + 101 + ... 101
      = 100*101

so sum = 1/2 * 100 * 101 = 5050

While it is uncertain whether this specific story is actually true, it 
is certain that Gauss was a child prodigy and a genius of the first 
degree.


-- 
Steven D'Aprano