Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Потеря значащих цифр

В табл. 1.35 даны шаги кодирования строки а^а^а^а^а^. Она похожа на табл. 1.34 и иллюстрирует проблему потери значащих разрядов. Переменные Low и High сближаются, и поскольку в этом примере Low всегда равна 0, переменная High теряет свои значащие цифры при приближении к Low.

Потеря значащих цифр происходит не только в этом случае, но всегда, когда Low и High должны близко сходиться. Из-за своего конечного размера переменные Low и High могут достигнуть значений, скажем 499996 и 500003, а затем, вместо того, чтобы получить значения с одинаковыми старшими цифрами, они станут равны 499999 и 500000. Поскольку самые значимые цифры остались разными, алгоритм ничего не даст на выход, не будет сдвигов, и следующая итерация только добавит цифры в младший разряд переменных. Старшие цифры будут потеряны, а первые 6 цифр не изменятся. Алгоритм будет работать, не производя выходных цифр, пока не достигнет eof.

Решить эту проблему можно, если заранее распознать эту ситуацию и поменять масштаб обеих переменных. В приведенном примере это следует сделать, когда обе переменные достигнут значений 49хххх и 50уууу. Необходимо удалить вторую значащую цифру, получить значения 4хххх0 и 5уууу9, а затем увеличить счетчик cntr. Возможно, смену масштаба придется делать несколько раз до тех пора, пока не сравняются самые значащие цифры. После этого самая значащая цифра (это будет 4 или 5) подается на выход, за которой следует cntr нулей (если переменные сходятся к 4) или девяток (если они стремятся к 5).

123 4 5

1

L=

ОН- (1 -0) хО.О

=

0.0

000000 0

000000


Н=

0 + (1-0) х 0.023162

=

0.023162

023162 0

231629

2

L=

0 + (0.0231629 - 0) х 0.0

=

0.0

00000 0

000000


Н=

0 + (0.0231629 - 0) х 0.023162

=

0.000536478244

005364 0

053649

3

L=

0 + (0.053649 - 0) х 0.0

=

0.0

000000 0

000000


Н=

0 + (0.053649 - 0) х 0.023162

=

0.00124261813

001242 0

012429

4

L=

0 + (0.012429 - 0) х 0.0

=

0.0

000000 0

000000


Н=

0 + (0.012429 - 0) х 0.023162

=

0.00028788049

000287 0

002879

5

L=

0 + (0.002879 - 0) х 0.0

=

0.0

000000 0

000000


Н=

0 + (0.002879 - 0) х 0.023162

=

0.00006668339

000066 0

000669

Табл. 1.35. Кодирование «азазазазаз» сдвигами.