Интернет-журнал "Домашняя лаборатория", 2007 №1

Журнал «Домашняя лаборатория»

Случай систематических дробей хорошо известен. При разложении числа в двоичную дробь длины m, т. е. при использовании m значащих бит для мантиссы погрешность приближения числа ? составит — (1/2)•2^{– m} = 2-^m-1. Поэтому для достижения потребной точности ? мы должны иметь

2^{– m-1} < ? => -m - 1 < log₂ ? => m > -log₂ ?
– 1 = log₂(1/?) - 1.

Таким образом для достижения точности ? мы должны затратить по меньшей мере

I₂(?) = log₂ (1/?) — 1 (1)

бит

информации.

2. Разложим теперь наше число ? в цепную дробь:

и возьмем в качестве представления числа ? последовательность {а₁, а₂…., а_n}, обрезая цепную дробь на n– м члене, т. е. беря n– ю подходящую дробь (поскольку ? € (0,1), то, очевидно, а₀ = 0).

Известно, что для записи числа ?_i, — требуется в среднем log₂ ?_i — бит, и значит для хранения последовательности {а₁, а₂…., а_n} этих бит потребуется по меньшей мере

I_с = ?ⁿ_i=1 log₂ a_i = log₂ Пⁿ_i=1a_i

(2)

Остается связать данное количество информации с потребной точностью представления числа ?. Этим мы и займемся.

Известно (см. [1], стр. 40, формула (30)), что подходящая дробь

построенная по числу а, приближает его с точностью 1/q²_n:

|? — (p_n/q_n)| < 1/q²_n

Поэтому для приближения ? с точностью ? достаточно соблюдения условия

1/q²_n < ? => q_n > 1/??

Остается получить оценку сверху для q_n, причем требуется оценить q_n величиной, связанной с I_c. Сделаем это.

Для знаменателей q_n подходящих дробей справедливо рекуррентное соотношение (см. [1], стр. 11, формула (7))

q_к = a_кq_к-1 + a_кq_к-2,

причем по определению полагается q_{– 1} = 0, q₀ = 1. Тогда q₁ = а₁, q₂ = a₂a₁ + 1, q₃ = a₃a₂a₁ + a₃ + a₁ и т. д.

Лемма. Для знаменателей q_n верна оценка q_n <= 2^n-1?_n,

где ?_n= Пⁿ _i=1= a_i.

Доказательство (методом мат. индукции). Для n = 1 утверждение верно, ибо q₁ = а₁. Предположим, что оценка верна для всех k и n. Тогда

поскольку выражение в круглых скобках не превосходит единицы ибо а_n >= 1, а_n+1 >= 1. Лемма доказана.

Опираясь теперь на лемму, заключаем, что для аппроксимации числа ? с точностью ? должно быть:

1/?? < q_n =< 2^n-1Пⁿ_i-1 a_i

Следовательно, используя (2), находим:

Таким образом, учитывая (1), получаем соотношение:

I_c(?) >= (1/2)•I₂(?) - n + 3/2

Впрочем, данная оценка довольно груба. Ее можно немного усилить.

С другой стороны, очевидно, q_n >= Пⁿ _i=1 a_i (доказывается тоже индукцией), поэтому если

1/q²_n < ? < 1/q²_n-1

то

q_n-1 < 1/?? < q_n

(5)

и, значит

Поэтому,

I_c(?) <= 1/2•I₂(?) + 1/2 + log₂ a_n

Если принять, что 1/q²_n < ?, то оценка упрощается:

I_c(?) <= 1/2•I₂(?) + 1/2

Таким образом видим, что теоретическая нижняя граница для I_c(?) — объема данных, потребных для хранения вещественного числа а, оценена нами как сверху (формулы (6) и (6’)), так и снизу (формула (4)). Поэтому в случае больших объемов информации (I_c(?) —> оо) представление числа в виде цепной дроби требует примерно вдвое меньшего количества бит, т. е. достигаемое сжатие — порядка 50 %.

3. Оценку (6) можно несколько улучшить. Для этого достаточно вместо (3) использовать более точную оценку приближения произвольного числа а подходящими дробями. Именно, ([1]. стр. 30) имеют место неравенства:

(7)

Поэтому если дробь p_n/q_n — первая из последовательности подходящих дробей, которая приближает число а с точностью ?, то, очевидно, имеют место неравенства: