2
\$\begingroup\$

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.)

\$\endgroup\$
3
  • 6
    \$\begingroup\$ Your existing code is fine to review, but this site isn't really well suited to tell you how to rewrite this from scratch in a distributed manner. \$\endgroup\$
    – Reinderien
    Oct 27, 2021 at 23:20
  • \$\begingroup\$ 1 to 1000 [/] 1001 to 2000 Given the relation between argument and run time, that division of labour may need to be refined. There is Python concurrency with modules/packages like concurrent, threading, multiprocessing \$\endgroup\$
    – greybeard
    Oct 28, 2021 at 3:19
  • \$\begingroup\$ I'm not sure that distributing the calculation on multiple computers would be faster than running the code with memoization of the previous results. Especially checking for powers of 2 should speed up the calculation. As is you're redoing at least the 8 - 4 - 2 -1 sequence for every number >4. Ideally you'd run it on multiple processes with a shared dictionnary [num] -> steps. \$\endgroup\$
    – kubatucka
    Oct 28, 2021 at 10:11

1 Answer 1

6
\$\begingroup\$

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')
  1. 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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.