Why is using a generator function twice as fast in this case?

Question

The code which is common for both the implementations:

from math import sqrt

def factors(x):
    num = 2
    sq = int(sqrt(x))
    for i in range(2, sq):
        if (x % i) == 0:
            num += 2
    return num + ((1 if sq == sqrt(x) else 2) if x % sq == 0 else 0)

1. Implementation which doesn't make use of a generator function:

i = 1
while True:
    if factors(i * (i+1) * 0.5) > 500:
        print(int(i * (i+1) * 0.5))
        break
    i += 1

2. Implementation which makes use of a generator function:

def triangle():
    i = 1
    while True:
        yield int(0.5 * i * (i + 1))
        i += 1

t = triangle()

while True:
    num = t.__next__()
    if factors(num) > 500:
        print(num)
        break

The Question:

The first implementation takes about 4 seconds while the second one takes approximately 8.2 seconds. Why is there such a big difference between the run times of the two implementations?

Answer 1

temp1():

def temp1():
        i = 1
        while True:
            if factors(i * (i+1) * 0.5) > 500:
                print(int(i * (i+1) * 0.5))
                break
            i += 1

temp2():

def temp2():
    def triangle():
        i = 1
        while True:
            yield int(0.5 * i * (i + 1))
            i += 1

    t = triangle()

    while True:
        num = t.next()
        if factors(num) > 500:
            print(num)
            break

cProfile for both:

After changing the factors call in temp1() to factors(int(...)), It turns out that temp1() takes the similar time

Modified temp1 to pass int rather than float:

def temp1():
    i = 1
    while True:
        if factors(int(i * (i+1) * 0.5)) > 500:
            print(int(i * (i+1) * 0.5))
            break
        i += 1

So it turns out that in your first implementation you are passing float to the factors() and floating point arithmetic is complex than integer arithmetic

Why Floating point operations are complex??

Because the way floats are represented internally is different from ints, they are represented in 3 parts as sign , mantissa and exponent (IEEE 754) whereas representation of integer is much simple and so are operations like addition and subtraction on integers, even multiplication and division are performed using a combination of addition,subtraction and shift operations internally . since integer addition and subtraction are simple, so are their division/multiplications and hence floating point operations are some what expensive

Why Floating point modulo is expensive than Integer?

The answer is same as above , A modulo operation is nothing but combination of primitive operations mentioned above as follows:

a mod n = a - (n*int(a/n))

Since primitive operations for floats are more expensive, so is modulo for floats

Answer 2

In the explicit case you're not taking the int of the expression before calling factors and therefore the value passed will be a floating-point number.

In the generator case you're instead yielding int(...), calling factors passing an integer number.

Answer 3

You can remove factors() of the code, make 500 much larger.

# implementation 1
i = 1
while True:
    if (i * (i + 1) * 0.5) > n: # n=100000
        # print int(i * (i + 1) * 0.5),
        break
    i += 1

and %timeit, to compare with implementation 2:

def triangle():
    i = 1
    while True:
        yield i * (i + 1) * 0.5
        i += 1

t = triangle()

while True:
    num = t.next()
    if num > n:
        # print num,
        break

Answer 4

The only difference as far as I know is that you do the calculation i * (i+1) * 0.5 twice in the first example. It is not a expensive computation, but it might make a big difference since it is such a big portion of the program..