Como posso implementar isso de forma mais eficiente

Question

Então, eu tenho uma função (estou escrevendo isso em uma linguagem pseudo-funcional, espero que o seu claro):

dampen (lr : Num, x : Num) = x + lr*(1-x)

E gostaria de aplicar esta n vezes para um valor x. Eu poderia implementá-lo de forma recursiva:

dampenN (0, lr, x) = dampen(lr, x)
dampenN (n, lr, x) = dampenN(n-1, lr, dampen(x))

Mas deve haver uma maneira que eu posso fazer isso matematicamente sem recorrer a um processo iterativo (recursivo, ou um loop).

Infelizmente minhas habilidades de álgebra estão enferrujadas crença além, alguém pode ajudar?

Answer 1

Podemos eliminar as séries de sua fórmula inteiramente.

Estamos atendendo:

x_(n+1) = x_n + lr(1-x_n)

Isso pode ser simplificado por reescrever a seguinte:

x_(n+1) = (1-lr)x_n + lr

Efetivamente, nós transformou isso em recursão de cauda. (Se você quer a perspectiva de ciência da computação.)

Isto significa que:

x_n = (1-lr)^n * x_0    +   ((1-lr)^(n-1) + (1-lr)^(n-2) + ... + 1)*lr 

A grande termo à direita é um geométrica série , de modo que pode ser recolhido como bem:

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

Editado devido a um pequeno erro nas expressões finais. +1 para comingstorm.

Answer 2

x + lr*(1-x) 
= x + lr - lr*x 
= x*(1-lr)+lr

aplicá-lo duas vezes dá

(x*(1-lr)+lr)*(1-lr)+lr 
= x*(1-lr)^2 + lr*(1-lr) + lr

e três vezes

(x*(1-lr)+lr)*(1-lr)^2 + lr*(1-lr) + lr 
= x*(1-lr)^3 + lr*(1-lr)^2 + lr*(1-lr) + lr

ou, em geral, n vezes dá

x*(1-lr)^n + lr * ( (1-lr)^n + (1-lr)^(n-1)...+(1-lr) +1)

Isso ajuda?

Answer 3

Na verdade, o post de MarkusQ tem um erro. A fórmula correta é:

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

Além disso, nota que "n" é o número de vezes que você aplicar a função. Em seu pseudocódigo funcional acima, o "n = 0" caso se aplica a função uma vez, não é zero vezes; para coincidir com a fórmula acima, ele teria que ir:

dampenN (0, lr, x) = x
dampenN (n, lr, x) = dampenN(n-1, lr, dampen(x))

Answer 4

Minha habilidade álgebra chupar também, mas eu decidi refazer a equação um pouco e começou a examinar alguns dos casos, d0 e 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

Basicamente, se você começar a ver o quadrática, você pode começar a ver a forma cúbica e assim por diante.

Em que ponto o x é usado apenas uma vez, e você só tem que lidar com a exponenciação de todos os sub termos da forma. (1 - lr) ^ n