Find the value of f (T) for a large value of T

Question

I am trying to solve the problem described below

The specified value is f (0) and k, which are integers.

I need to find the value of f (T). where T <= 10 ¹⁰

Recursive function

 f(n) =  2*f(n-1)              ,  if  4*f(n-1) <=k 
         k - ( 2*f(n-1) )      ,  if 4*f(n-1) > k

My efforts

#include<iostream>

using namespace std;


int main(){

     long k,f0,i;
     cin>>k>>f0;
     long operation ; 
     cin>>operation;
     long answer=f0;
     for(i=1;i<=operation;i++){
         answer=(4*answer <= k )?(2*answer):(k-(2*answer));
     }
     cout<<answer;
     return 0;

}

My code gives me the correct answer. But in the worst case, the code will work 10 ¹⁰ which gives me Time Limit Exceed. I need a more effective solution to this problem. Please help me. I do not know the correct algorithm.

Answer 1

If 2f (0) k, then you can calculate this function in O (log n) time (using squaring modulo k).

r = f(0) * 2^n mod k
return 2 * r >= k ? k - r : r

. , 0 <= f (n) k/2 f (n).

Python, , (f) (g).

def f(n, k, z):
    r = z
    for _ in xrange(n):
        if 4*r <= k:
            r = 2 * r
        else:
            r = k - 2 * r
    return r

def g(n, k, z):
    r = (z * pow(2, n, k)) % k
    if 2 * r >= k:
        r = k - r
    return r

import random

errs = 0
while errs < 20:
    k = random.randrange(100, 10000000)
    n = random.randrange(100000)
    z = random.randrange(k//2)
    a1 = f(n, k, z)
    a2 = g(n, k, z)
    if a1 != a2:
        print n, k, z, a1, a2
        errs += 1
    print '.',

Answer 2

?

,
f (n) = f0 * 2 ^ (n-1), f (n-1) * 4 <= k      k - f0 * 2 ^ (n-1), f (n-1) * 4 > k

, :
condition = f0*pow(2, operation-2) answer = condition*4 =< k? condition*2: k - condition*2

Answer 3

; answer<<2 4*answer answer<<1 2*answer, , , . , - .

, @Shannon, , , . , , .

, Brent , .

def brent(f, x0):
    # main phase: search successive powers of two
    power = lam = 1
    tortoise = x0
    hare = f(x0)  # f(x0) is the element/node next to x0.
    while tortoise != hare:
        if power == lam:  # time to start a new power of two?
            tortoise = hare
            power *= 2
            lam = 0
        hare = f(hare)
        lam += 1

    # Find the position of the first repetition of length λ
    mu = 0
    tortoise = hare = x0
    for i in range(lam):
    # range(lam) produces a list with the values 0, 1, ... , lam-1
        hare = f(hare)
    # The distance between the hare and tortoise is now λ.

    # Next, the hare and tortoise move at same speed until they agree
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1

    return lam, mu



f0 = 2
k = 198779
t = 10000000000

def f(x):
    if 4 * x <= k:
        return 2 * x
    else:
        return k - 2 * x

lam, mu = brent(f, f0)

t2 = t
if t >= mu + lam:              # if T is past the cycle first loop,
    t2 = (t - mu) % lam + mu    # find the equivalent place in the first loop

x = f0
for i in range(t2):
    x = f(x)

print("Cycle start: %d; length: %d" % (mu, lam))
print("Equivalent result at index: %d" % t2)
print("Loop iterations skipped: %d" % (t - t2))
print("Result: %d" % x)

, memo , ( , brent), , , .

Answer 4

, , O (n). , , . ,

1. ( ,

2. O (Logn) ( - )

3. O (1)

. -

f(n) =  2*f(n-1)              ,  if  4*f(n-1) <=k
        k - ( 2*f(n-1) )      ,  if 4*f(n-1) > k

:

1: 4 * f (n-1) <= k (1) ( , )

a_n = 2 * a_n-1

,

Sn = 2 ^ (n-1) f (0) ----()

2: 4 * f (n-1) > k (2),

a_n = -2a_n-1 + k

, a_j - , (2)

an_1 ,

an = k -2k + 4k -8k... + (- 2) ^ (n-j) * a_j

k -2k 4k -8... -

Sn = k * (1-2 ^ (n-j))/(1-2) --- - k = -2

, a 2

an = k * (1-2 ^ (n-j))/(1-2) + (-2) ^ (n-j) * a_j ---- (**)

, , , aj, (1) (2)

, 1:

n, 4 * an = 4 * Sn = 4 * 2 ^ (n-1) * f (0) n: 4 * 2 ^ (n-1) * f (0) = k, n , n

, , 1 2. , .

, .

:

T, K f (0)

n, , (*), (**)

f (0) f (n), T - n

, T-n = 0 ( , T-n < 0, , )

Answer 5

Create a map that saves your results. Before finding f (n), check on this map if the solution already exists or not. If exists, use this solution. Otherwise, find it, save it for future use.

For C ++:

Definition:

map<long,long>result;

Insert:

result[key]=value

Access:

value=result[key];

Verification:

map<long,long>::iterator it=result.find(key);
if(it==result.end())
{
    //key was not found, find the solution and insert into result
}
else
{
    return result[key];
}

Use the above technique for a better solution.