# Comparing Julia and Python for basic operations

Hi there Julia community!,

I’m quite new to the language and I’m falling in love more and more with it every day

In order to improve my knowledge, I’m revisiting Project Euler problems, which I’ve done in Python, with Julia and, so far, Julia code is waaay faster than Python (who knew! :D)
But I’m getting problems with the following problem that runs in 4.6 s while the Python version runs in 2.4 s. Both versions are almost identical

Julia version

``````function Problem12()
#=
The sequence of triangle numbers is generated by adding the natural
numbers. So the 7th triangle number would be:
1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred
divisors?
=#

function num_divisors(n)
res = floor(sqrt(n))
divs = []
for i in 1:res
if n%i == 0
append!(divs,i)
end
end
if res^2 == n
pop!(divs)
end
return 2*length(divs)
end

triangle = 0
for i in Iterators.countfrom(1)
triangle += i
if num_divisors(triangle) > 500
return string(triangle)
end
end
end
``````

Python version (for comparison)

``````import itertools
from math import sqrt, floor

# Returns the number of integers in the range [1, n] that divide n.
def num_divisors(n):
end = floor(sqrt(n))
divs = []
for i in range(1, end + 1):
if n % i == 0:
divs.append(i)
if end**2 == n:
divs.pop()
return 2*len(divs)

def compute():
triangle = 0
for i in itertools.count(1):
# This is the ith triangle number, i.e. num = 1 + 2 + ... + i =
# = i*(i+1)/2
triangle += i
if num_divisors(triangle) > 500:
return str(triangle)
``````
1 Like

One simple speed-up is to replace this line by `res = floor(Int, sqrt(n))`, as otherwise `floor` returns a `Float64`.

On a side note, I wonder if your `num_divisors` function is correct, as it returns `2` for `9` instead of `3` (unless I have the wrong definition of “divisors”). A fix could be to not `pop!` when `res^2 == n`, but instead to substract `1` to the returned result.

2 Likes

I’ve made a couple of changes (I’m not interested in the divisors themselves, just in the number of them) and now the code runs in 0.12 s

``````    function num_divisors(n)
#res = floor(sqrt(n))
res = floor(Int, sqrt(n))
divs = 0#[]
for i = 1:res
if n % i == 0
divs += 1
#append!(divs, i)
end
end
if res^2 == n
divs -= 1
#pop!(divs)
end
return 2 * divs #length(divs)
end
``````

Regarding the validity of the function, I guess that it’s correct as it gives the solution as good in Project Euler.

With the “validity” change I suggested, the answer to `Problem12` stays the same.

This creates an array with `Any` Type, analogue to a Python List. Operations on this list are very slow for the same reason as in Python - for every operation the element type must be detected dynamically.
The performance is much better if you specify the data type of the list in advance, e.g.
`divs = Int[]`.

6 Likes

Maybe not faster, but isn’t `isqrt(n)` more robust?

3 Likes

Yes, but I think the robustness issue applies to `n > maxintfloat()` which is about 9 000 000 000 000 000.

1 Like

You still have the same mistake in your code. You’re subtracting one from `divs`, where you should be subtracting it from the `2*divs` that is returned.
Here’s a shorter version, that’s even faster on my machine (using `isqrt`, as @DNF suggested):

``````function num_divisors2(n)
r = isqrt(n)
2 * count(n % i == 0 for i in 1:r) - (r^2 == n)
end
``````

not sure why this is faster than a straight loop.

1 Like

Thx a lot! As you said, it runs a bit faster and does less allocations