How can I implement this more efficiently
Question
So I have a function (I'm writing this in a pseudo-functional language, I hope its clear):
dampen (lr : Num, x : Num) = x + lr*(1-x)
And I wish to apply this n times to a value x. I could implement it recursively:
dampenN (0, lr, x) = dampen(lr, x)
dampenN (n, lr, x) = dampenN(n-1, lr, dampen(x))
But there must be a way I can do it mathematically without resorting to an iterative procedure (recursive, or a loop).
Unfortunately my algebra skills are rusty beyond belief, can anyone help?
Solution
We can eliminate the series from your formula entirely.
We are given:
x_(n+1) = x_n + lr(1-x_n)
This can be made simpler by rewriting as follows:
x_(n+1) = (1-lr)x_n + lr
Effectively, we've transformed this into tail recursion. (If you want the computer science perspective.)
This means that:
x_n = (1-lr)^n * x_0 + ((1-lr)^(n-1) + (1-lr)^(n-2) + ... + 1)*lr
The big term on the right is a geometric series, so that can be collapsed as well:
x_n = (1-lr)^n * x_0 + lr * (1 - (1-lr)^n) / (1- (1 -lr))
x_n = (1-lr)^n * x_0 + 1 - (1 - lr)^n
Edited due to a small error in the final expressions. +1 to comingstorm.
OTHER TIPS
x + lr*(1-x)
= x + lr - lr*x
= x*(1-lr)+lr
applying it twice gives
(x*(1-lr)+lr)*(1-lr)+lr
= x*(1-lr)^2 + lr*(1-lr) + lr
and three times
(x*(1-lr)+lr)*(1-lr)^2 + lr*(1-lr) + lr
= x*(1-lr)^3 + lr*(1-lr)^2 + lr*(1-lr) + lr
or in general, n times gives
x*(1-lr)^n + lr * ( (1-lr)^n + (1-lr)^(n-1)...+(1-lr) +1)
Does that help?
Actually, MarkusQ's post has an error. The correct formula is:
x * (1-lr)^n + lr * ( (1-lr)^(n-1) + (1-lr)^n-2 + ... + (1-lr) + 1 ) = x * (1-lr)^n + lr * ( 1 - (1-lr)^n )/(1 - (1-lr)) = x * (1-lr)^n + (lr/lr) * (1 - (1-lr)^n) = (x-1) * (1-lr)^n + 1
Also, note that "n" is the number of times you apply the function. In your functional pseudocode above, the "n=0" case applies the function once, not zero times; to match the above formula, it would have to go:
dampenN (0, lr, x) = x dampenN (n, lr, x) = dampenN(n-1, lr, dampen(x))
My algebra skill suck too, but I decided to refactor the equation a bit and started examining some of the cases, d0, and d1:
d0 = x + lr(1-x) => x + lr - lr*x => (1 - lr)x + lr
d1 = (1 - lr)[(1 - lr)x + lr] + lr => (1 - lr)^2 x + lr(1 - lr) + lr
Basically if you start seeing the quadratic, you can start seeing the cubic form and so on.
At which point the x is only used once, and you just have to deal with the exponentiation of all the sub terms of the form (1 - lr)^n.