Блог

X_hat является приближением X. Оно задается X_t , усечением X с использованием t бит.

Найдите пределы X_t / X.

X_hat и X_t представлены в двоичном формате с плавающей запятой. Из моего понимания:

 If t = 3 and X_hat = 1, X_t = 1.01
 

1/1 = 1 — это верхний предел? Как насчет нижнего предела?

Следующее предполагает, что вопрос касается значащих битов (для примера в десятичном 3141592 формате будет усечено до 3 значащих цифр 3140000 , а усечено до 5 значащих цифр 3141500 ). Поскольку вопрос касается относительной ошибки, не имеет значения, есть ли или где десятичная точка, поэтому можно предположить без потери общности, что числа являются целыми числами.

Если X = 0 тогда X̂ = X = 0 и X̂ / X не определено.

В противном случае, если 0 < X < 2^(t-1) then X имеет не более t-1 значащих битов, а усечение остается X неизменным, поэтому X̂ = X и X̂ / X = 1 .

В противном случае if X >= 2^(t-1) then X может быть записан как X = 2^n q r where n >= 0 , 2^(t-1) <= q < 2^t и 0 <= r < 2^n . Крайние левые t биты X равны q , поэтому усечение X до t значащих битов равно X̂ = 2^n q .

Затем X̂ / X = 2^n q / (2^n q r) = 1 - 1 / (1 r / (2^n q)) . Выражение уменьшается r и увеличивается q , что в сочетании с r < 2^n и q >= 2^(t-1) дает нижнюю границу:

 X̂ / X  >  2^(n t-1) / (2^(n t-1)   2^n)
       =  1 - 1 / (1   2^(t-1))
 

Для фиксированного n > 0 точная нижняя граница, полученная из r <= 2^n - 1 и q >= 2^(t-1) , равна:

 X̂ / X  >=  2^(n t-1) / (2^(n t-1)   2^n - 1)
        =  1 - (2^n - 1) / (2^(n t-1)   2^n - 1)
        =  1 - 1 / (1   2^(n t-1) / (2^n - 1))
        =  1 - 1 / (1   2^(t-1) / (1 - 1 / 2^n))
 

Эта нижняя граница достигается для X = 2^(n t-1) 2^n - 1 соответствующего X̂ = 2^(n t-1) . В пределе n → ∞ оно сводится к нижней границе, независимой от n полученной на предыдущем шаге.