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?

Answer 1

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?

Answer 2

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.

Answer 3

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.

Answer 4

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