Длинная арифметика с фиксированной точкой

[s-andriano]

Спасибо, правда в 12 номере статья не поместилась и пришлось искать следующий.
А пока он качается, замечание к уже прочитанному:

Строка устроена так, что в нее относительно
легко можно добавить символы в конец, но никак
не в начало строки (то есть операция такая
конечно имеется, но вот скорость ее выполнения
в большинстве случаев оставляет желать
лучшего).

Вот на этом ошибочном (!) утверждении и основана вся дальнейшая стратегия и тактика работы.

Почему неверном?
Давайте посчитаем сами (в данном случае строка - просто массив байтов, причем, заданный указателем на него):

Вариант А. Добавляем байт в конец массива длиной N:
1. Выделяем массив длиной N+1, используя временный указатель.
2. Копируем N байтов из старого массива в новый.
3. Дописываем на N+1 место добавляемый байт.
4. Освобождаем память старого массива.
5. Переписываем в старый указатель значение временного указателя.

Вариант Б. Добавляем байт в начало массива длиной N:
1. Выделяем массив длиной N+1, используя временный указатель.
2. Копируем N байтов из старого массива в новый со смещением на 1 в сторону конца (т.е. [i] -> [i+1]).
3. Дописываем на 1 место добавляемый байт.
4. Освобождаем память старого массива.
5. Переписываем в старый указатель значение временного указателя.

Как видим, не только по сложности, но и по количеству операций эти действия полностью эквивалентны.

А иллюзия автора основана, видимо, на убеждении, что процедура SetLength имеет сложность O(1), тогда как ее реализация полностью включает шаги 1, 2, 4, 5 Варианта А.

К слову сказать, в процессе реализации автор не мог обойти случай, когда, скажем, нужно удалить байт слева, а левая последовательность уже пуста, и тогда приходится удалять байт из начала правой последовательности. Реализация посредством двух массивов оказывается громоздкой и неэффективной.

Ладно, загрузился 13 номер - пошел читать продолжение...

[Utkin]

Если Вы желаете самовыразиться, или же действительно улучшить код - просто создайте нвую тему. Не надо засирать данную

[s-andriano]

Любопытный момент:

Плавающая точка имеет
одно очень нехорошее свойство – числа,
близкие по значению, но разные числа в
различных операциях могут считаться
одинаковыми (равными, эквивалентными) и
различными числами, все это вызывает
погрешность и справедливое удивление
начинающих программистов.

Давайте вспомним:
Для записи чисел с фиксированной точкой хранятся только цифры самогочисла,
Для записи чисел с плавающей точкой хранятся как цифры самого числа (мантисса), так и цифры, описывающие положение точки (порядок).
Автором используются числа, содержащие запись порядка, т.е. по сути - числа с плавающей точкой. Только в общем случае ненормализованные.

...следует помнить, что
время работы операции сравнения различно в
зависимости от числа разрядов и самих чисел.
Это еще одна причина гасить незначащие
разряды в числах.

В принципе, вроде, все верно.
Только не учитывается тот факт, что операция "гашения" незначащих разрядов выполняется существенно дольше операции сравнения.

С
учетом количества памяти в современных
компьютерах, я считаю, что ста разрядов в
целой части (и ста разрядов в дробной, для
точности) вполне достаточно.

Очень странное решение, учитывая, что под порядок отводится число типа Integer, которое в Delphi (а на ТурбоПаскале операции SerLength нет) занимает 32 разряда и позволяет задать диапазон в пределах плюс-минус два миллиарда вместо плюс-минус сотни.

Автор на протяженни половины страницы сетует на проблемы, возникающие при поиске очередной цифры при делени в столбик, заявляя даже:

...не
всегда представляется возможным (иногда,
даже решая на листочке, приходится
проводить дополнительные промежуточные
деления либо и вовсе жульничать с помощью
калькулятора). Здесь мы займемся самым
настоящим гаданием.

А между тем, причина проблемы - выбранная автором десятичная система счисления, т.к. в двоичной системе эта проблема отсутствует полностью: "если фрагмент делителя больше делимого - единица, иначе - ноль". И никакого гадания с попытками умножения на разные цифры.

Но в целом хочу отметить:
- любопытен сам подход,
- интересная статья (с удовольствием прочитал),
- несмотря на некоторые (в том числе и серьезные) недостатки - это неплохая основа для создания вариантов арифметики длинных чисел,
- в частности, можно заменить реализацию байтовых последовательностей своими, вроде, на работоспособность основного модуля длинной арифметики это повлиять не должно.

[s-andriano]

Сообщение от Utkin

Если Вы желаете самовыразиться, или же действительно улучшить код - просто создайте нвую тему. Не надо засирать данную

Не понял.
Разве данная тема называется не "Длинная арифметика с фиксированной точкой"?
И разве не по теме я пишу?

[glabz]

Доброго времени суток ув. Уткин, нашел пару жучков в вашем коде

Первый, при делении нуля на число, программа зависает

GetBigNum('0', x);
GetBigNum('2', y);
DivBigNumE(x, y,f,4);

Второй, при делении числа на 1, программа снова зависает

GetBigNum('0', x);
GetBigNum('2', y);
DivBigNumE(x, y,f,4);

Могли бы, пожалуйста подсказать, как быстро залатать дырку ?.
Просто лучше вашего модуля, я пока что ничего не находил в интернете. Очень уж хочется протестировать его "в полевых условиях".

[glabz]

@s-andriano
Вот в принципе есть, еще один модуль, Реализован на динамических строках, если Вам интересно.

http://delphiworld.narod.ru/base/big_numbers.html

В нем тоже есть пару жучко, припустим
1,0001 - 2,0054 выдаст, как ответ -1,
и при сложении чисел с разной мантиссой, тоже возникает не точность.
В остальном, все довольно таки нормально работает. К сожжению, автор данного кода погиб в авто катастрофе несколько лет назад..

Я просто первый рас стыкаюсь с подобной задачей, и пока что не очень в ней ориентируюсь, поэтому прошу простить меня, за возможные глупости с моей стороны.

[Utkin]

Беглый анализ указывает на функцию Increasing...

ЗЫ. Я давно не занимаюсь Дельфи, поэтому мне требуется время чтобы найти ошибки.

[glabz]

Я Вас понимаю, спасибо большое за ответ.
Вы сможете, если что залатать дырку, или направить в нужное русло?.

[Utkin]

Если поступать по мелкософтовски - навскидку можно поставить заплатку на

procedure DivBig (Op1, Op2: TBigNum; var Res: TBigNum; Quan: Integer; F: Boolean);

заменив

while Increasing(Op2, Dif)=True do
     begin
                    
          // Äîáàâëÿåì ðàçðÿäû è íóëè
          Mul10(Dif, 1);

          // Íóëü
          Inc(x);
     end;

на

while Increasing(Op2, Dif)=True do
     begin

          // ×àñòíûé ñëó÷àé íóëü
          if (Length(Dif.Category.Left)=0) and (Length(Dif.Category.Rigth)=0) then break;
          
          // Äîáàâëÿåì ðàçðÿäû è íóëè
          Mul10(Dif, 1);

          // Íóëü
          Inc(x);
     end;

Однако я код не тестировал и не знаю как он повлияет на решение других чисел... По идее здесь идет низкоуровневая проверка второго операнда на нуль и только в операции деления, но без полного тестирования я не могу быть увереным на 100 процентов.

Давайте посчитаем сами (в данном случае строка - просто массив байтов, причем, заданный указателем на него):

Причем здесь Ваш случай? Не надо Ваши абстрактные случаи натягивать на реальный пример из жизни. Если бы Вы знали что такое паскалевские строки, то не писали бы такое .

Только не учитывается тот факт, что операция "гашения" незначащих разрядов выполняется существенно дольше операции сравнения.

Это учитывается в том плане, что по замыслу либа должна глотать строки вида '0000000007.000000000', но делать так медленно.
Учитывая что это не ООП, то в данную структуру можно напихать любую последовательность цифр, и количество нулей там ограничено фантазией.

Автором используются числа, содержащие запись порядка, т.е. по сути - числа с плавающей точкой.

Наглая ложь. Там указана позиция разделителя целой и дробной части, а не запись порядка. Именно попытка натянуть традиционные представления на данную модель числа и есть грубейшая ошибка. Читатйте статью внимательно.

Очень странное решение

Прежде чем дальше писать всякий бред внимательно читаем. Сравнивать две абсолютно разные категории (типа разряды под реализацию Интерджер и разряды десятичного числа в естественной для человека записи) это весьма неожиданно для Вашего уровня. Дальше комментить не стал ибо и так ясно, что человек ставит личные эмоции выше желания навести порядок в статье и коде.

[s-andriano]

Сообщение от Utkin

Причем здесь Ваш случай? Не надо Ваши абстрактные случаи натягивать на реальный пример из жизни. Если бы Вы знали что такое паскалевские строки, то не писали бы такое .

Это хорошо, что Вы написали, что "давно не занимаетесь", иначе я бы не знал, что и подумать на Ваше утверждение.
Тогда напоминаю написанную Вами реализацию:

type
    TByteSpace=record

        Left: Array of Byte;      // Левая часть последовательности
        Rigth: Array of Byte;     // Правая часть последовательности
    end;

Как не сложно видеть, у Вас не "паскалевские строки", а именно массивы байтов.

Наглая ложь. Там указана позиция разделителя целой и дробной части, а не запись порядка.

Эта позиция есть не что иное как количество разрядов, на которое смещена точка в записи числа относительно ее реального расположения.
Именно эту величину в записи дробного числа и принято называть порядком.

Именно попытка натянуть традиционные представления на данную модель числа и есть грубейшая ошибка. Читатйте статью внимательно.

Есть два традиционных представления - числа с фиксированной и с плавающей точкой.
Ваше представление является разновидностью (возможно, расширением) представления с плавающей точкой.
В то время как Вы сами неправомерно называете это представлением с фиксированной точкой.
У представления с фиксированной точкой не может быть поля для указания порядка (по-вашему - позиции разделителя), а у Вас есть.
Можете Вы от него безболезненно отказаться? Нет.
Значит, с плавающей точкой.
И отсутствие нормализации совершенно не указывает на то, что это якобы какой-то совершенно особый объект.

Прежде чем дальше писать всякий бред внимательно читаем. Сравнивать две абсолютно разные категории (типа разряды под реализацию Интерджер и разряды десятичного числа в естественной для человека записи) это весьма неожиданно для Вашего уровня. Дальше комментить не стал ибо и так ясно, что человек ставит личные эмоции выше желания навести порядок в статье и коде.

1. Мне очень жаль, что Вы не видите ничего общего между одними и другими разрядами, обо они суть одно и то же.
2. Переходить на личности - mauvais ton.

В статье наводить порядок уже поздно.
В коде - никогда не поздно. Включая перепроектирование. Благо, код изначально для этого приспособлен, что есть его несомненное достоинство.
А после этого, возможно, написать новую статью.

PS. Напрасно Вы на меня взъелись. И подход интересный. И код очень грамотно разделен на две части. Скажу честно, специально реализацию длинной арифметики я не искал, но за не одно десятилетие работы всякое попадалось. Могу сказать, из всего, что я видел - у Вас лучший вариант.