Экспоненциальный откат - PullRequest
Новая
       28

Экспоненциальный откат

1 голос
/ 11 апреля 2019

Допустим, у меня было уравнение T = sum (A ** n) для n от 1 до M.

Теперь, допустим, я знал М и Т, но хотел А. Как бы я решил для А?

Я хочу сделать экспоненциальный откат в случае ошибки, но я не хочу, чтобы общее время, затрачиваемое на откат, было больше, чем T, и максимальное количество попыток не превышало бы M. Поэтому мне нужно найти А.

1 Ответ

2 голосов
/ 11 апреля 2019

Закрытое решение для суммы (A ** n) для n от 1 до M равно (A ^ (M + 1) - 1) / (A - 1) - 1. Чтобы увидеть эту работу, пусть M= 3 и A = 2. Тогда 2 ^ 1 + 2 ^ 2 + 2 ^ 3 = 14 и (2 ^ 4 - 1) / (2 - 1) - 1 = 15/1 - 1 = 14.

Итак, мы имеем выражение замкнутой формы T = (A ^ (M + 1) - 1) / (A - 1) - 1. Это трансцендентное уравнение и не имеет решения в замкнутой форме.Однако, поскольку RHS монотонно возрастает в A (большие значения A всегда дают большие значения выражения), тогда мы можем сделать то, что составляет двоичный поиск, чтобы найти ответ с произвольной точностью: 

L = 0
H = MAX(T, 2)
A = (L + H) / 2
while |(A ^ (M + 1) - 1) / (A - 1) - 1 - T| > precision
    if (A ^ (M + 1) - 1) / (A - 1) - 1 > T then
        H = A
    else then
        L = A
    end if
    A = (L + H) / 2
loop

Пример: Т = 14, М = 3, эпсилон = 0,25 

L = 0
H = MAX(15, 2) = 14
A = L + H / 2 = 7

|(A ^ (M + 1) - 1) / (A - 1) - 1 - T|
 = 385 > 0.25
H = A = 7
A = (L + H) / 2 = 3.5

|(A ^ (M + 1) - 1) / (A - 1) - 1 - T|
 = 44.625 > 0.25
H = A = 3.5
A = (L + H) / 2 = 1.75

|(A ^ (M + 1) - 1) / (A - 1) - 1 - T|
 = 3.828125 > 0.25
L = A = 1.75
A = (L + H) / 2 = 2.625

|(A ^ (M + 1) - 1) / (A - 1) - 1 - T|
 = 13.603515625 > 0.25
H = A = 2.625
A = (L + H) / 2 = 2.1875

|(A ^ (M + 1) - 1) / (A - 1) - 1 - T|
 = 3.440185546875 > 0.25
H = A = 2.1875
A = (L + H) / 2 = 1.96875

|(A ^ (M + 1) - 1) / (A - 1) - 1 - T|
 = 0.524444580078125 > 0.25
L = A = 1.96875
A = (L + H) / 2 = 2.078125

|(A ^ (M + 1) - 1) / (A - 1) - 1 - T|
 = 1.371326446533203125 > 0.25
H = A = 2.078125
A = (L + H) / 2 = 2.0234375

|(A ^ (M + 1) - 1) / (A - 1) - 1 - T|
 = 0.402295589447021484375 > 0.25
H = A = 2.0234375
A = (L + H) / 2 = 1.99609375

|(A ^ (M + 1) - 1) / (A - 1) - 1 - T|
 = 0.066299498081207275390625 < 0.25

Solution: 1.99609375
...