[SOLVED] Why is one function of divisor >3000% faster than the other?

Issue

I was doing some simple Python exercises on https://www.practicepython.org/ when I did this task https://www.practicepython.org/exercise/2014/02/26/04-divisors.html.

I wanted to test different ways to code the answer, and I saw solutions in the comment field that piqued my interest; two codes looked similar, but one is almost 4000% faster than the other!

Code:

import time

start = time.time()

print("Fast code:")

#the slow code
def divisor(x):
    divisors = []
    for i in range(1, int(x)):
        if x % i == 0:
            divisors.append(i)
            divisors.sort()
    print(divisors)


divisor(50000000)
end = time.time()
print("Time elapsed: ")
print(end - start)

print("Fast code:")

start = time.time()

#the fast code!
def divisor2(x):
    divisors = []
    for i in range(1, int(x**.5)):
        if x % i == 0:
            divisors.append(i)
            divisors.append(x//i)
            divisors.sort()
    print(divisors)
divisor2(50000000)
end = time.time()
print("Time elapsed: ")
print(end - start)

Time elapsed (slow code):

3.1739981174468994

Time elapsed (fast code):

0.0010004043579101562

Can anyone please tell me how this is possible so perhaps anyone can take home some valuable faster coding skills for their toolbelt?

Solution

x**.5 is x to the power of a half, it’s a square root.

Both using x = 50,000,000, the first does:

for i in range(1, int(x)):

fifty million loops.

The second does:

for i in range(1, int(x**.5)):

seven thousand loops.

The reason you can do this when calculating divisors is because they form two sides of a rectangle:

 __
|  |
|  |
|__|

If you know the area (the goal, 50 million), and you know one side (the counter i) then you can work out the other side. Where both sides are the same is the square root, and it acts like a pivot, if one is shorter than that then the other must be longer, and balance it out. That is, 100/2 = 50 that gives you both 2 and 50.

So you can count up to the square root to find all the short answers, work out the other side (the counter-balance) for each one, and then you have all the answers. 100/10 = 10 that gives you 10 as a divisor, and tells you that if you keep counting up to get to 100/50 = 2 you’ve already seen that from the other side and got 50.

That’s why the second code has:

        divisors.append(i)
        divisors.append(x//i)

Adding two values to the list, after only testing one.

Answered By – TessellatingHeckler

Answer Checked By – Senaida (BugsFixing Volunteer)