0

I've been working on the following code which sort of maximizes the number of unique (in lowest common denominator) p by q blocks with some constraints. It is working perfectly. For small inputs. E.g. input 50000, output 1898.

I need to run it on numbers greater than 10^18, and while I have a different solution that gets the job done, this particular version gets super slow (made my desktop reboot at one point), and this is what my question is about.

I'm trying to figure out what is causing the slowdown in the following code, and to figure out in what order of magnitude they are slow.

The candidates for slowness:

1) the (-1)**(i+1) term? Does Python do this efficiently, or is it literally multiplying out -1 by itself a ton of times? [EDIT: still looking for how operation.__pow__ works, but having tested setting j=-j: this is faster.]

2) set instantiation/size? Is the set getting too large? Obviously this would impact membership check if the set can't get built.

3) set membership check? This indicates O(1) behavior, although I suppose the constant continues to change.

Thanks in advance for insight into these processes.

import math
import time

a=10**18

ti=time.time()

setfrac=set([1])
x=1
y=1
k=2

while True:
    k+=1
    t=0
    for i in xrange(1,k):
        mo = math.ceil(k/2.0)+((-1)**(i+1))*(math.floor(i/2.0)
        if (mo/(k-mo) not in setfrac) and (x+(k-mo) <= a and y+mo <= a):
            setfrac.add(mo/(k-mo))
            x+=k-mo
            y+=mo
            t+=1
    if t==0:
        break

print len(setfrac)+1
print x
print y
to=time.time()-ti
print to
S C
  • 561
  • 1
  • 4
  • 5
  • 1
    `(-1)**(i+1)`: Why don't you check yourself? Use `j = -j` in the loop, initializing it the the correct value, and use `j` for your `(-1)**(i+1)` term? – AJNeufeld Jun 21 '17 at 17:52
  • great idea, thanks. still a newbish programmer here – S C Jun 21 '17 at 17:54
  • You can use `timeit` to answer all of your questions. – cs95 Jun 21 '17 at 17:55
  • 3
    `>>> timeit.timeit("(-1)**100"); 0.03868699073791504; >>> timeit.timeit("(-1)**1000000000"); 0.031023025512695312; >>> timeit.timeit("(-1)**1000000000000000000000000"); 0.037858009338378906;` – cs95 Jun 21 '17 at 17:56
  • Side remark: you might want to print intermediate times inside the outer loop to see how execution time of the inner loop is increasing with `k`. – Błotosmętek Jun 21 '17 at 17:56
  • Looking at the possible values of `k` and `t`: how do break the loop? – Klaus D. Jun 21 '17 at 17:57
  • @Coldspeed thanks for the tip. However, how does one find documentation on how ** actually works? My google-fu is totally failing me at this. – S C Jun 21 '17 at 17:59
  • @SC [Here ya go.](https://docs.python.org/2/library/timeit.html) – cs95 Jun 21 '17 at 18:00
  • @KlausD. If x+(k-mo) > a or y+mo > a for all k and mo, then the if commands never take place, t=0 and gets broken. If not, then t is positive and the for loop continues. – S C Jun 21 '17 at 18:01
  • Additionally, if you are concerned with performance, look for expressions you can move outside you inner loops. `math.ceil(k/2.0)` is a constant within the `for i ...` loop. Compute it once per `while` loop iteration. – AJNeufeld Jun 21 '17 at 18:02
  • @Coldspeed Thanks, I meant documentation on how the ** operator actually performs its job. – S C Jun 21 '17 at 18:04
  • @AJNeufeld thanks, good idea. – S C Jun 21 '17 at 18:05
  • 1
    @SC Sorry, misunderstood. Actually, ** internally calls the operator.__pow__ function. You can look up how that works. – cs95 Jun 21 '17 at 18:06
  • @AJNeufeld did a test, j=-j is faster (probably obviously, to you), still searching for how __pow__ works. – S C Jun 21 '17 at 18:14
  • See [How did Python implement the built-in function pow()?](https://stackoverflow.com/questions/5246856/how-did-python-implement-the-built-in-function-pow). That question is about `a ** b % c`, but it links to the cpython source. – AJNeufeld Jun 21 '17 at 19:12

0 Answers0