How to reduce time complexity of a program that loops huge number of times?

Question

I'm trying to code (whole day)number generation system, it starts with 3 and the value decreases by 1 until it reaches 1. Once it reaches 1, it resets its number to a new starting value 2x as that of the first number. And then with each new reset 2x as the first number of the earlier reset. Like shown in bellow,

3 2 1 6 5 4 3 2 1 12 11 10 9 8 7 6 5 4 3 2 1...

The program should return the value of the nth position that user request.

user can enter n < (10^12)

Tried skipping some steps if the target position is far away from the current position of the loop

# requesting position
tt = int(input())
# starting t 
t = 1
# starting value
sv = 3
# current value
cv = 3

while (True):

    # check if we have reached target time
    if (t == tt):
        # print the current value
        print("{}".format(cv))
        break

    # if there's a loong way to go, skip some 
    if (t + cv < tt):  # starting_t+current_value<target_t
        t += cv  
        sv = sv * 2  
        cv = sv  

        if cv % 2 == 0:
            if (t + cv // 2 < tt):
                t += cv // 2
                cv = cv // 2
                continue
        continue

    # check if value is 1 and double it
    if (cv == 1):
        # set new starting value
        sv = sv * 2
        # set new current value
        cv = sv
        # elapse time
        t += 1
        continue

    # elapsed time
    t += 1
    # changed value
    cv -= 1

Currently, this program takes more than 2 minutes to return the result for n>10^10. I need to reduce the time taken for the process as much as possible. What can I do to reduce the time taken for the process? (expect to reduce it to a couple of seconds) any reference may be helpful

Answer 1

The problem could be solved analytically without iterating through numbers and calculations as mentioned above. Finally able to solve the problem(of course with the help)

import math

def get_n_th(t):
    a=math.log((t/3)+1,2)   #if you input t,you need to get how many resets have done == integer value of log((t/3)+1, 2)
    # it always returns value > 0, even for the first reset (which is n need to be equal to zero) so we have to round number to least significant figures to get the correct reset value and substract 1 reset to get actual reset count

    # (3,2,1),   (6,5,4,3,2,1),  (12,11,10...)
    #    ^            ^               ^
    # 0th reset    1st reset       2nd reset
    #Bellow condition used to round number to least significant figures and sustract 1 reset. For further clarification please refer how log_2(n) return value and mentioned theory in the answer

    if(a%1 == 0):
        n = int(a-1)    # here n is equals to how many resets
        print("if")
    else:
        n = int(a)
    #here n gives how many resets occured
    #3*2**n will give the starting number of the last reset ---(1)
    #(t-3*(2**n-1))-1) will return how many steps remaining ---(2)
    # the difference between (1)-(2) will give the value in t position
    return (3*2**n)-((t-3*(2**n-1))-1)
    #or simplified equation
    #return 3 * 2 ** (n + 1) - t - 2


input = int(input())   #input the position
print(get_n_th(input))
print("[*] Ended in %.3f seconds." % (time.time() - start_time))

For understand this code you MUST refered this theory and answer. And also need to know the behaviour of log_2(n).

Answer 2

Summary

You can just do (indexing starts from 0, otherwise you need to replace n with n - 1):

def my_seq(n):
    k = int(math.log2(n / 3 + 1)) + 1
    return 3 * (2 ** k - 1) - n


print([my_seq(i) for i in range(2)])
# [3, 2, 1, 6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 24, 23, 22, 21]

which is basically a variation of a geometric series with step equal 2, as shown below.

---

Explanation

The first step is to notice that your underlying sequence of the "peaks" is a geometric progression:

x_k = a * r ** k

The sum of the first n terms of a geometric progression is the geometric series:

sum(x_k for k in 1 to n) = a * (1 - r ** n) / (1 - r)

The target sequence is basically obtained by subtracting the index from the largest term of the series not exceeding the index itself.

In code, this looks like:

# note that this uses integer division hence expects integer `r`
def geom_series_int(a, r, n):
    return a * (1 - r ** n) // (1 - r)


def my_seq_int(n, a=3, r=2): 
    i = 1
    cumsum = geom_series_int(a, r, i) 
    while cumsum < n + 1:
        i += 1
        cumsum = geom_series_int(a, r, i)
    return cumsum - n


print([my_seq_int(i) for i in range(25)])
# [3, 2, 1, 6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 24, 23, 22, 21]

---

One could also compute the geometric series iteratively, of course, and this would be computationally of similar efficiency as the above code, due to the fact that finding the minimum cumsum not exceeding the index n is done with a loop, but the code from above is faster:

def i_geom_progression(a, r): 
    i = 0 
    while True: 
        yield a * r ** i 
        i += 1


def i_geom_series(a, r):
    gp = i_geom_progression(a, r)
    result = next(gp)
    while True:
        yield result
        result += next(gp)


def my_seq(n, a=3, r=2): 
    gs = i_geom_series(a, r) 
    cumsum = next(gs) 
    while cumsum < n + 1:
        cumsum = next(gs)
    return cumsum - n


print([my_seq(i) for i in range(25)])
# [3, 2, 1, 6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 24, 23, 22, 21]

The computational complexity in both cases is log(n).

---

A more efficient approach is to do this analytically by solving for k the expression for the geometric series and using the index n as a proxy for the cumulative sum:

n = a * (r ** k - 1) / (r - 1)

becomes:

k = log_r(1 - n * (1 - r) / a)

and taking the integral part, this becomes:

import math


def my_seq_analytic(n, a=3, r=2):
    k = int(math.log2(1 - n * (1 - r) / a) / math.log2(r)) + 1
    return geom_series_int(a, r, k) - n


print([my_seq_analytic(i) for i in range(25)])
# [3, 2, 1, 6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 24, 23, 22, 21]

This is the fastest approach.

---

In general, the proposed methods are quite much faster than the method originally proposed, a simplification of which is reported in my_seq_loop() below:

def my_seq_loop(n, a=3, r=2):
    peak = a
    for i in range(1, n + 1):
        if a == 1:
            peak *= r
            a = peak
        else:
            a -= 1
    return a


print([my_seq_loop(i) for i in range(25)])
# [3, 2, 1, 6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 24, 23, 22, 21]

The give some idea of the timings, see the benchmarks below:

%timeit my_seq_loop(10 ** 8)
# 1 loop, best of 3: 6.65 s per loop
%timeit my_seq(10 ** 8)
# 100000 loops, best of 3: 14.1 µs per loop
%timeit my_seq_int(10 ** 8)
# 100000 loops, best of 3: 11.7 µs per loop
%timeit my_seq_analytic(10 ** 8)
# 1000000 loops, best of 3: 938 ns per loop

(EDITED to fix a bug in the code for analytics where integer division was used instead of regular division).

Answer 3

Simply you can do:

def get_n_th_number(x, n):
    if n <= x:
        return x - n + 1

    return get_n_th_number(2 * x, n - x)

x = 3

assert get_n_th_number(x, 1) == 3
assert get_n_th_number(x, 3) == 1
assert get_n_th_number(x, 4) == 6
assert get_n_th_number(x, 9) == 1
assert get_n_th_number(x, 10) == 12

Time Complexity: log2(n / x)

Space Complexity: log2(n / x) (Due to recursion.)

Answer 4

You can compute your answer without any loop :

After n resets, your number is 3*2^n. Therefore, you have done 3*(2^{n}-1) steps.

So, if the user inputs the number x, you need to find how many resets you have done so far (which is the integer value of log_2(x/3)), let's call R this number, and find how many more steps you have performed since this reset, let's call this number S.

Then your solution is 3*(2^{R}-1) - S.

Check on simple examples that this work, I may have made a mstake in my maths, but the method should be ok.