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

@GoldenId · Регистрация: 11.11.2010

Студворк — интернет-сервис помощи студентам

"Я не понимаю алгоритм деления, объясните" спрашивать не собираюсь.

Пишу длинную арифметику с фиксированной точкой. В задании сказано, что целая и дробная часть должны храниться в отдельных массивах char'ов. Каждый char - десятичная цифра. Индексация обоих - от десятичной точки. Определил встроенный в класс

C++
1
typedef unsigned int size_type;

Когда писал операторы +, -, *, столкнулся с тем, что регулярно нужно обрабатывать уменьшение size_type от нуля на единицу (--) в циклах. Приходится писать дополнительный код. Но это полбеды.

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

C++
1
2
3
    bool ihp1 = true;           // в целой ли части старшая значащая цифра делимого
    size_type ih1 = intlen - 1; // позиция в целой части; факт использования зависит от ihp1
    size_type fh1;              // позиция в дробной части; факт использования зависит от ihp1

и получается код вроде:

Гроб

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    if( ihp1 )                  // первая значащая цифра в делимом - в целой части
    {
        if( ihp2 ) {                // первая значащая цифра в делителе - в целой части
            if( ih1 < ih2 )     // соотношение положений цифр
                sub >>= ( dh = ih2 - ih1 );
            else
                sub <<= ( dh = ih1 - ih2 )/*, t = ( fh2 + 1 >= fh1 ) ? ( fh2 - fh1 + 1 ) : 0*/;
            //t = ih2 + fh1 + 2;
        } else                  // первая значащая цифра в делителе - в дробной части
            sub <<= ( dh = ih1 + fh2 + 1 )/*, t = ( fh2 + 1 >= fh1 ) ? ( fh2 - fh1 + 1 ) : 0*/;
        t = ih1 + fraclen + 1;
    } else {                    // первая значащая цифра в делимом - в дробной части
        if( ihp2 )              // первая значащая цифра в делителе - в целой части
            sub >>= ( dh = ih2 + fh1 + 1 )/*, t = ( fh2 + 1 >= fh1 ) ? ( fh2 - fh1 + 1 ) : 0*/;
        else {                  // первая значащая цифра в делителе - в дробной части
            if( fh1 < fh2 )
                sub <<= ( dh = fh2 - fh1 );
            else
                sub >>= ( dh = fh1 - fh2 );
            //t = ih2 + fh1 + 2;
        }
        t = fraclen - fh1;
    }

В одном месте меня хватило это написать, но дальше возникли проблемы с разрядностью, и когда я попытался их порешать, полезли необходимости в ещё нескольких позициях в числах, а это ещё n*m*... случаев - и тут я завалился.

Скажите, что я делаю неправильно?

C++
1
typedef unsigned int size_type;

- ошибка проектирования? Нужно singed?
Может быть делать не

так

Code
1
2
3
4
5
6
целая часть           : ц  ц  ц
индекс в ней          : 2  1  0
десятичная точка      :          .
дробная часть         :             д  д  д
индекс в ней          :             0  1  2
дублирование индекса 0:       ↑     ↑

, а

так

Code
1
2
3
4
5
целая часть           : ц  ц  ц
десятичная точка      :          .
дробная часть         :             д  д  д
неиспользуемая цифра  :             ↑
общая индексация      : 2  1  0       -1 -2

?

Спасибо дочитавшим до конца.

Добавлено через 6 часов 38 минут
Кроме того наклёвывается ещё одна проблема. Даже если распределять общую индексацию целой и дробной частей

так

Code
1
2
3
4
целая часть           : ц  ц  ц
десятичная точка      :          .
дробная часть         :             д  д  д
общая индексация      : 2  1  0    -1 -2 -3

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

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

Если *this - делимое, занимающее разряды [h1..l1], rhs - делитель, занимающий разряды [h2..l2], у меня есть три основных переменных:

quot - частное, инициализируется нулём, занимает разряды [h1-h2 .. l1+l2-2*h2-1]. С ним в этом смысле гладко.
rem - остаток, инициализируется *this, т.е. сначала должен занимать разряды [h1..l1], но для того, чтобы выполнять вычитание из него, должен иметь к началу этого вычитания разряды [h1 .. l1+l2-h2-1]
sub - скользящее вычитаемое, инициализируется rhs, т.е. сначала должно иметь разряды [h2..l2], но потом для первого вычитания из остатка (rem), его нужно сдвинуть sub <<= h1-h2;, а в конечном итоге он должен иметь те же разряды, что и остаток: [h1 .. l1+l2-h2-1].

В итоге я не могу разобраться, как увязать создание объектов этих чисел с изменением их разрядности и той самой Большой тройкой, которая настолько точна в плане проектирования.

Я бы мог написать

C++
1
2
    Fraction rem( rem_intlen, rem_fraclen );
    rem.copyfrom( *this );

но меня же заругают за нарушение принципов ООП.

Кроме того, как совместить выделение памяти, копирование значения из rhs, сдвиг для sub, увеличение разрядности и идиому copy-and-swap я не представляю.

Добавлено через 1 час 53 минуты
Да, при использовании

такого проектирования

Code
1
2
3
4
целая часть           : ц  ц  ц
десятичная точка      :          .
дробная часть         :             д  д  д
общая индексация      : 2  1  0    -1 -2 -3

такой код

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
            // заготавливаем два индекса и флаг положения в произведении условными операторами;
            // там где получаются отрицательные значения, этот индекс использоваться не будет,
            // там, где 0 - этот индекс не имеет значения
            ipr =
                ip1 ? ( ip2 ? true : ( i1 > f2 ) ) : ( ip2 ? ( i2 > f1 ) : false );
            ir =
                ip1 ? ( ip2 ? ( i1 + i2 ) : ( i1 - f2 - 1 ) ) : ( ip2 ? ( i2 - f1 - 1 ) : 0 );
            fr =
                ip1 ? ( ip2 ? 0 : ( f2 - i1 /*- 1*/ ) ) : ( ip2 ? ( f1 - i2 /*- 1*/ ) : ( f1 + f2 + 1 ) );
            // используем ссылку для удобного многократного доступа к цифре результата
            digit_type& r = ipr ? res.int_[ir] : res.frac[fr];
            r +=
                  ( ip1 ? int_[i1] : frac[f1] )
                * ( ip2 ? rhs.int_[i2] : rhs.frac[f2] )
                + t;            // перемножаем цифры множителей и прибавляем перенос
            t = r / 10;         // обновляем перенос
            r %= 10;            // убираем старший разряд из текущей цифры

превращается в

такой

C++
1
2
3
4
5
6
7
8
9
            // используем ссылку для удобного многократного доступа к цифре результата
            digit_type& r = res.getd(p1 + p2);
 
            // цифра произведения равна произведению цифр множителей плюс перенос
            r += getd(p1) * rhs.getd(p2) + t;
            
            // обрабатываем перенос в следующий разряд
            t = r / 10;
            r %= 10;

,
а

такой

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
            // переходим к следующей цифре с учётом целой и дробной части
            if( !ip2 )
            {
                if( f2 ==  0 )
                    ip2 = true;
                else
                    f2--;
            } else
            {
                i2++;
                if( i2 >= rhs.intlen )
                    break;
            }

в

такой

C++
1
p2++

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .