# Slower summation of a series in Julia than in Python

**URL:** <https://discourse.julialang.org/t/slower-summation-of-a-series-in-julia-than-in-python/77912>\
**Category:** Performance\
**Tags:** question\
**Created:** [March 15, 2022, 12:01pm UTC](https://discourse.julialang.org/t/slower-summation-of-a-series-in-julia-than-in-python/77912 "2022-03-15T12:01:57Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![RayleighLord](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rayleighlord/32/33592_2.png) [@RayleighLord](https://discourse.julialang.org/u/RayleighLord)\
**Post date:** [March 15, 2022, 12:01pm UTC](https://discourse.julialang.org/t/slower-summation-of-a-series-in-julia-than-in-python/77912/1 "2022-03-15T12:01:57Z")

</div>

Hello,

I was doing some tests in Julia and Python and I found that the following code was much slower in Julia and I do not see why this would be the case

```julia
harmonic(k) = (-1)^k / (k + 1)

function sₙ(an, n)
    S = 0.0
    for k in 0:n
        S += an(k)
    end
    return S
end

julia> @time sₙ(harmonic, 500_000)
   0.019135 seconds
0.6931481805570047

```

In Python I used the code

```julia
def harmonic(k):
    return (-1) ** k / (k + 1)

def sum_n(an, n):
    S = 0.0
    for k in range(n+1):
        S += an(k)
    return S

def main():
    start = timeit.timeit()
    sum_n(harmonic, 500000)
    end = timeit.timeit()
    print(abs(end - start))

>>> main()
0.000324424999738713

```

Any idea on why is this happening?

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [March 15, 2022, 12:15pm UTC](https://discourse.julialang.org/t/slower-summation-of-a-series-in-julia-than-in-python/77912/2 "2022-03-15T12:15:20Z")

</div>

Which julia version are you running? The way your microbenchmark is structured and the output you’re getting suggests you’re accidentally including compilation time of the julia code in your measurement. Try running it a second time in the same session.

Also, since you write `-1` in `harmonic` (a `Int` literal) instead of `-1.0` (a floating point literal) there may be some conversion cost as well.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [March 15, 2022, 12:19pm UTC](https://discourse.julialang.org/t/slower-summation-of-a-series-in-julia-than-in-python/77912/3 "2022-03-15T12:19:29Z")

</div>

> [@Sukera](#):
>
> Also, since you write `-1` in `harmonic` (a `Int` literal) instead of `-1.0` (a floating point literal) there may be some conversion cost as well.

Indeed, just changing `(-1)^k` to `(-1.0)^k` makes the code faster.

---

<div class="post-metadata">

**Author:** ![RayleighLord](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rayleighlord/32/33592_2.png) [@RayleighLord](https://discourse.julialang.org/u/RayleighLord)\
**Post date:** [March 15, 2022, 12:19pm UTC](https://discourse.julialang.org/t/slower-summation-of-a-series-in-julia-than-in-python/77912/4 "2022-03-15T12:19:37Z")

</div>

Im running Julia 1.7. The compilation time is not included since I executed @time a second time.

However, I just tried your second suggestion and you are absolutely right. I thought that there was no cost doing `(-1)^k` over `(-1.0)^k` but it seems I got that wrong.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [March 15, 2022, 12:23pm UTC](https://discourse.julialang.org/t/slower-summation-of-a-series-in-julia-than-in-python/77912/5 "2022-03-15T12:23:10Z")

</div>

Seem to be even faster if you use: `harmonic(k) = ifelse(isodd(k) , -1 , 1) / (k + 1)`

---

<div class="post-metadata">

**Author:** ![anowacki](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/anowacki/32/17375_2.png) [@anowacki](https://discourse.julialang.org/u/anowacki)\
**Post date:** [March 15, 2022, 12:31pm UTC](https://discourse.julialang.org/t/slower-summation-of-a-series-in-julia-than-in-python/77912/6 "2022-03-15T12:31:57Z")

</div>

> [@RayleighLord](#):
>
> ```julia
> def main():
> start = timeit.timeit()
> sum_n(harmonic, 500000)
> end = timeit.timeit()
> print(abs(end - start))
> 
> ```

`timeit.timeit` does not work this way. Each call to `timeit.timeit` returns the time taken to run the command given to `timeit.timeit`, which in your case with `timeit.timeit()` is no command. So your `main` simply returns the difference between two calls to `timeit.timeit`, each of which gives the time taken to run _no command at all_. This probably explains why sometimes the difference is negative and you have used `abs` to ignore that.

To correctly calculate the time taken to run `sum_n(harmonic, 500000)`, you need to do:

```python
import timeit

timeit.timeit("sum_n(harmonic, 500000)", setup="""
def harmonic(k):
   return (-1) ** k / (k + 1)

def sum_n(an, n):
   S = 0.0
   for k in range(n+1):
       S += an(k)
   return S
""", number=1)

```

Note however that `timeit.timeit` by default uses many evaluations (a million) of the expression you supply, so the above would take a _very_ long time to return. Use the `number` argument to `timeit.timeit` to get an answer in an acceptable time.

Doing that for me gives about 250 ms for the Python code above. So much slower than your original Julia.

---

<div class="post-metadata">

**Author:** ![rvasil](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rvasil/32/3821_2.png) [@rvasil](https://discourse.julialang.org/u/rvasil)\
**Post date:** [March 15, 2022, 12:43pm UTC](https://discourse.julialang.org/t/slower-summation-of-a-series-in-julia-than-in-python/77912/7 "2022-03-15T12:43:22Z")

</div>

Not a performance tip, but you can simplify sₙ function like this  
`sₙ(an, n) = sum(an(k) for k in 0:n)`

---

<div class="post-metadata">

**Author:** ![lawless-m](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lawless-m/32/30869_2.png) [@lawless-m](https://discourse.julialang.org/u/lawless-m)\
**Post date:** [March 15, 2022, 12:43pm UTC](https://discourse.julialang.org/t/slower-summation-of-a-series-in-julia-than-in-python/77912/8 "2022-03-15T12:43:28Z")

</div>

I can get the wrong answer even quicker !

```julia
julia> @btime sₙ(harmonic, 500_000)
  648.000 μs (0 allocations: 0 bytes)
0.6931481805570047

julia> function sₙ(an, n)
    S = 0.0
    for k in 0:n
        @fastmath S += an(k)
    end
    return S
end

julia> @btime sₙ(harmonic, 500_000)
  444.600 μs (0 allocations: 0 bytes)
0.6931481805569676

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [March 15, 2022, 4:18pm UTC](https://discourse.julialang.org/t/slower-summation-of-a-series-in-julia-than-in-python/77912/9 "2022-03-15T16:18:04Z")

</div>

> [@lmiq](#):
>
> Seem to be even fasYester if you use: `harmonic(k) = ifelse(isodd(k) , -1 , 1) / (k + 1)`

Yes, _definitely_ do this instead of `(-1.0)^k`, or `(-1)^k`. Repeatedly calculating a power for gradually increasing exponents is needlessly wasteful. It’s nothing to do with conversion cost, just that `(-1)^500_000` needs to do approximately `log2(500_000) = 19` multiplications, for each iteration. It doesn’t really make any sense to redo all of those calcualations over and over.

The same goes for Python, use some version of `isodd`, or keep track of the previous value of `(-1)^k` and get the next by just multiplying by -1.

This is a common performance pitfall. Too often you can find code that implements something like \sum\_{k=1}^N x^k/k! dutifully by

```julia
function slowsum(x, n)
    val = 0.0
    for i in 1:n
        val += x^i / factorial(i)
    end
    return val
end

```

instead of

```julia
function fastsum(x, n)
    val = 0.0
    part = 1.0
    for i in 1:n
        part *= x / i
        val += part
    end
    return val
end

```

with results like these:

```julia
1.7.2> @btime slowsum(x, 15) setup=(x=2+rand())
  377.451 ns (0 allocations: 0 bytes)
15.747545023566579

1.7.2> @btime fastsum(x, 15) setup=(x=2+rand())
  12.613 ns (0 allocations: 0 bytes)
10.771366140823954

```

Not to mention the overflow behaviour of `slowsum`.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [March 15, 2022, 4:36pm UTC](https://discourse.julialang.org/t/slower-summation-of-a-series-in-julia-than-in-python/77912/10 "2022-03-15T16:36:43Z")

</div>

> [@DNF](#):
>
> Yes, _definitely_ do this instead of `(-1.0)^k` , or `(-1)^k` . Repeatedly calculating a power for gradually increasing exponents is needlessly wasteful.

The [FastPow.jl package](https://github.com/JuliaMath/FastPow.jl) will do this transformation for you on `(-1)^k` if you just put `@fastpow` in front of your function.

Note that it’s generally even better to compute each term in a series by iteratively updating the previous term, like this:

```julia
S = 0.0
term = 1
for k = 0:n
    S += term / (k+1)
    term = -term
end

```

or you could even unroll:

```julia
S = 0.0
for k = 0:2:n
    S += inv(k+1) - inv(k+2)
end

```

These kinds of tricks become even more important for accumulating series where the terms are more complicated, e.g. `\sum\_{k=0}^n z^k / k!:

```julia
S = 0.0
term = one(z) / 1
for k = 0:n
    S += term
    term *= z / (k+1)
end

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [March 15, 2022, 4:44pm UTC](https://discourse.julialang.org/t/slower-summation-of-a-series-in-julia-than-in-python/77912/11 "2022-03-15T16:44:06Z")

</div>

> [@stevengj](#):
>
> These kinds of tricks become even more important for accumulating series where the terms are more complicated, e.g. `\sum\_{k=0}^n z^k / k! ∑nk=0zk/k!\sum\_{k=0}^n z^k / k! :

That’s some coincidence, you chose the _exact_ same example as I did, while we were simultaneously editing😁