CODEWITHSUNDEEP
pythonmath
user6369958
user6369958

Reputation: 367

Predict the number of iterations required - iterated weighted average

Pardon me but I could find a better title. Please look at this super-simple Python program:

x = start = 1.0
target = 0.1

coeff = 0.999

for c in range(100000):

    print('{:5d} {:f}'.format(c, x))
    if abs(target - x) < abs((x - start) * 0.01):
        break

    x = x * coeff + target * (1 - coeff)

Brief explaination: this program moves x towards target calculating iteratively the weighted average of x and target with coeff as weight. It stops when x reaches the 1% of the initial difference.

The number of iterations remains the same no matter the initial value of x and target.

How can I set coeff in order to predict how many iterations will take place?

Thanks a lot.

Upvotes: 3

Views: 87

Answers (2)

Rory Daulton
Rory Daulton

Reputation: 22564

Your code reduces the distance between x and the target by a factor of coeff in each execution of the loop. Thus, if start is greater than target, we get the formula

target - x = (x - start) * coeff ** c

where c is the number of loops we have done.

Your ending criterion is (again, if start is greater than target),

x - target < (start - x) * 0.01

Solving for x by algebra we get

x > (target + 0.01 * s) / (1 + 0.01)

Substituting that into our first expression and simplifying a bit makes both start and target drop out of the inequality--now you see why those values did not matter--and we get

0.01 / (1 + 0.01) < coeff ** c

Solving for c we get

c > log(0.01 / (1 + 0.01), coeff)

So the final answer for the number of loops is

ceil(log(0.01 / (1 + 0.01), coeff))

or alternatively, if you do not like logarithms to an arbitrary base,

ceil(log(0.01 / (1 + 0.01)) / log(coeff))

You could replace that first logarithm in that last expression with its result, but I left it that way to see what different result you would get if you change the constant in your end criterion away from 0.01.

The result of that expression in your particular case is

4613

which is correct. Note that both the ceil and log function are in Python's math unit, so remember to import those functions before doing that calculation. Also note that Python's floating point calculations are not exact, so your actual number of loops may differ from that by one, if you change the values of coeff or of 0.01.

Upvotes: 2

Artyer
Artyer

Reputation: 40951

Let's make this a function, f.

f(0) is the initial value (start, in this case 1.0).

f(x) = f(x - 1) * c + T * (1 - c).

(So f(1) is the next value of x, f(2) is the one after that, and so on. We want to find the value of x where |T - f(x)| < 0.01 * |f(0) - f(x)|)

So let's rewrite f(x) to be linear:

f(x) = f(x - 1) * c + T * (1 - c)
     = (f(x - 2) * c + T * (1 - c)) * c + T * (1 - c)
     = (f(x - 2) * c ** 2 + T * c * (1 - c)) + T * (1 - c)
     = ((f(x - 3) * c + T * (1 - c)) * c ** 2 + T * c * (1 - c)) + T * (1 - c)
     = f(x - 3) * c ** 3 + T * c ** 2 * (1 - c) + T * c * (1 - c) + T * (1 - c)

     = f(0) * c ** x + T * c ** (x - 1) * (1 - c) + T * c ** (x - 2) * (1 - c) + ... + T * c * (1 - c) + T * (1 - c)

     = f(0) * c ** x + (T * (1 - c)) [(sum r = 0 to x - 1) (c ** r)]
  # Summation of a geometric series
     = f(0) * c ** x + (T * (1 - c)) ((1 - c ** x) / (1 - c))
     = f(0) * c ** x + T (1 - c ** x)

So, the nth value of x will be start * c ** n + target * (1 - c ** n).

We want:

|T - f(x)| < 0.01 * |f(0) - f(x)|
|T - f(0) * c ** x - T (1 - c ** x)| < 0.01 * |f(0) - f(0) * c ** x - T (1 - c ** x)|
|(c ** x) * T - (c ** x) f(0)| < 0.01 * |(1 - c ** x) * f(0) - (1 - c ** x) * T|
(c ** x) * |T - f(0)| < 0.01 * (1 - c ** x) * |T - f(0)|
c ** x < 0.01 * (1 - c ** x)
c ** x < 0.01 - 0.01 * c ** x
1.01 * c ** x < 0.01
c ** x < 1 / 101
x < log (1 / 101) / log c

(I somehow ended up with x < when it should be x >, but it gives the correct answer. With c = 0.999, x > 4612.8, and it terminates on step 4613).

In the end, it is independant of start and target.

Also, for a general percentage difference of p,

c ** x > p * (1 - c ** x)
c ** x > p - p c ** x
(1 + p) c ** x > p
c ** x > p / (1 + p)
x > log (p / (1 + p)) / log c

So for a coefficient of c, there will be log (1 / 101) / log c steps.

If you have the number of steps you want, call it I, you have

I = log_c(1 / 101)
c ** I = 1 / 101
c = (1 / 101) ** (1 / I)

So c should be set to the Ith root of 1 / 101.

Upvotes: 3

Related Questions