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)
i = 1
while True:
if factors(i * (i+1) * 0.5) > 500:
print(int(i * (i+1) * 0.5))
break
i += 1
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 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?
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
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.
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
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..
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With