How to make my Collatz Conjecture code run a lot faster? (and even better, how do I implement it into multiple computers?) Python

Question

I have been writing this piece of code for a while now, and I was wondering, is it possible to run this code multiple times on my pc? For example could I make the code solve all the numbers from 1 to 1000 and all from 1001 to 2000 at the same time? And, if this is possible, could I use multiple computers to solve it in this way (just with bigger numbers)?

Heres the Code:

#(n*3)+1 = if odd
#else n/2 = if even
import time
import sys


def progress(count, total, status=''):
    bar_len = 60
    filled_len = int(round(bar_len * count / float(total)))

    percents = round(100.0 * count / float(total), 1)
    bar = '█' * filled_len + '-' * (bar_len - filled_len)

    sys.stdout.write('[%s] %s%s ...%s\r' % (bar, percents, '%', status))
    sys.stdout.flush()


one = "nothing"
while one != "n":
    if one == "n":
        break
    else:
        total = input("what is the limit number?:")
        total = int(total)
        total = total+1
        highest_step = 0
        highest_num = 0 
    
        for x in range(0,total):
            n = x
            steps = 0
            print(end="\r")
            progress(n, total, status='Doing very long job, current Num:'+str(n))# emulating long-playing job


       
               
            #print("----IMPOSSIBLE MATH SOLUTION------")
            #print()
            #print ("staring number is:(",n,")")
            #print()
    
            while n != 0:
                if n != 1:
                    if (n%2) == 0:
                        #print(
                        eval("n/2")
                        n = eval("n/2")
                        steps = steps+1
                    else:
                        #print (
                        eval("(n*3)+1")
                        n = eval("(n*3)+1")
                        steps = steps+1
            
                else:
                    #print ("amount of steps it took to solve:",steps)
                    if (highest_step <= steps):
                        highest_step = steps
                        highest_num = x
                        break
                    else:
                        break
    
        

    print()
    print()
    print ("the number with most steps",highest_num)
    print ("amount of steps:",highest_step)
    one = input("congrats!, do it again? (y/n)")


        
    
            
            
    
    

This would be a great help, thanks

(Also, I am still a beginner coder in python3.)

Answer 1

Not exactly sure what your goal is. If your primary goal is just getting the highest_step and highest_num a lot faster than your current code does, then you could achieve the goal without any of that. As an example, when I run the following code (basically your code that calculates to 99,999 without taking input or displaying the progress bar) on my machine,

from time import perf_counter_ns as ns


start = ns()
limit = 100_000
highest_step = 0
highest_num = 0 

for x in range(limit):
    n = x
    steps = 0

    while n != 0:
        if n != 1:
            if (n%2) == 0:
                n = eval("n/2")
                steps = steps+1
            else:
                n = eval("(n*3)+1")
                steps = steps+1
        else:
            if (highest_step <= steps):
                highest_step = steps
                highest_num = x
                break
            else:
                break
print("the number with most steps",highest_num)
print("amount of steps:",highest_step)
print(f'it took {(ns() - start)/1e6:,.0f}ms')

it prints this.

the number with most steps 77031
amount of steps: 350
it took 28,098ms

However, the same code without the useless eval() prints this (18x speed).

the number with most steps 77031
amount of steps: 350
it took 1,562ms

If I run the that code with pypy 3.8 instead of python 3.10, then this (49x speed).

the number with most steps 77031
amount of steps: 350
it took 569ms

And when I run the following code on the same machine with pypy3.8,

from time import perf_counter_ns as ns


start = ns()
limit  = 100_000
memo = {i: 0 for i in range(limit)}
for i in range(3):
    memo[i] = i
for i in range(3, limit):
    counter = 0
    cur = i
    while i > 1:
        if i < cur:
            memo[cur] = memo[i] + counter
            break
        if not i % 2:
            i /= 2
            counter += 1
        else:
            i *= 3
            i += 1
            counter += 1
print(f'the number with most steps: {max(memo, key=memo.get)}')
print(f'amount of steps: {max(memo.values()) - 1}')
print(f'it took {(ns() - start)/1e6:,.0f}ms')

it prints this (375x speed), even though this is probably not the most efficient way to do it, and Python usually take a considerably longer time to compute the same task, compare to many other languages like C++.

the number with most steps: 77031
amount of steps: 350
it took 75ms

EDIT: Added some more benchmark results (limit is now 1 million, instead of 100k shown above)

1. only removed two input()s from your original code (all four eval()s intact):

   • python3.10: 771,214ms

2. the 28 seconds code above (two eval()s remaining, progress bar removed):

   • python3.10: 344,444ms (2.2x speed)

3. without eval():

   • python3.10: 19,238ms (40x speed)
   • pypy3.8: 6,937ms (111x speed)

4. using dict memo:

   • python3.10: 1,078ms (715x speed)
   • pypy3.8: 732ms (1,054x speed)

5. using list memo (shown below):

   • python3.10: 805ms (950x speed)
   • pypy3.8: 50ms (15,424x speed)

from time import perf_counter_ns as ns


start = ns()
limit  = 1_000_000
memo = [0] * limit
memo[1], memo[2] = 1, 2
for i in range(3, limit):
    counter = 0
    cur = i
    while i > 1:
        if i < cur:
            memo[cur] = memo[i] + counter
            break
        if not i % 2:
            i //= 2
            counter += 1
        else:
            i *= 3
            i += 1
            counter += 1
print(f'the number with most steps: {memo.index((m := max(memo)))}')
print(f'amount of steps: {m - 1}')
print(f'it took {(ns() - start)/1e6:,.0f}ms')

6. list variant above vs C++ vector variant (1.96x over pypy, 30,231x speed overall)

pypy: 0.08s user 0.02s system 94% cpu 0.102 total (when it prints 51ms)
g++:  0.05s user 0.00s system 98% cpu 0.052 total