C++ Перегрузка оператора / для деления длиннотельных чисел

Question

C++ Перегрузка оператора / для деления длиннотельных чисел

Роман Protocol Мыслитель (8562), закрыт 5 лет назад

Всем привет!
https://pastebin.com/T5jExsTv
Пишу код перегрузки деления Infinite_double на Infinite_double. Infinite_double - это класс, описанный мною, содержащий приватные поля
vector < int > mantissa (мантисса числа с плавающей запятой) и
unsigned long fract (количество цифр справа от запятой, то есть в дробной части числа)
а также ряд конструкторов и методов класса.
Я представляю число (мантиссу в частности) как набор цифр vector < цифра > + длина дробной части.
Clear_null(e1); - метод, удаляющий из мантиссы незначащие нули слева (в любом случае) и справа (пока не завершится проход дробной части).
Equalizer(e1, e2); - выравниватель дробной части. У экземпляров, передаваемых в этот метод будут одинаковы fract. То есть числа e1 и e2 будут иметь после запятой (справа от запятой) одинаковое количество цифр. Недостающие цифры мантиссы заполняются 0.
Например
e1 представляет число 84,99
e2 представляет число 603,90445
После Equalizer(e1, e2);
e1 представляет число 84,99000
e2 представляет число 603,90445
Division_Digit(temp, v2) - узнаёт сколько раз укладывается вектор v2 (как число) в вектор temp (как число). Это целочисленное деление с отбросом остатка максимум до 9 включительно.
Например, temp = 64, v2 = 15, тогда Division_Digit(temp, v2) = 4.

Я написал, работает вроде норм. делит - результаты правильные, но иногда запятая не туда встаёт. Например код
string st2 = "110";
Infinite_double id2(st2);
string st1 = "9";
Infinite_double id1(st1);
Infinite_double id3;
id3 = id2 / id1;
id3.Show_Number();
cout << endl;
выдаёт 1.222222222 вместо 12.22222222 А иногда правильно запятая ставится. Помогите сделать перегрузку /, чтобы во всех ситуациях - при любых делимом и делителе деление работало правильно и выдавало верный результат деления.
Спасибо тем, кто поможет!

Дополнен 5 лет назад

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

Дополнен 5 лет назад

В 55 строке для теста написано 10. Там нужно чтобы как - то определялось кол-во цифр мантиссы частного (результата деления). Как - то установить точность и её блюсти.

Answer 1

Юрий-17 Гений (76476) 5 лет назад

Как я понял, ставится задача сделать класс чисел с разрядностью превышающей разрядность стандартных чисел!?
Ошибку можно найти, но вот вопрос, хороший ли подход применён?
Первый вопрос про класс Infinite_double
Почему вектор содержит int, а не unsigned?
и "запятая" как я понял бежит по десятичным разрядам, а не двоичным!?

Роман ProtocolМыслитель (8562) 5 лет назад

> Как я понял, ставится задача сделать класс чисел с разрядностью превышающей разрядность стандартных чисел!?
Да.
> хороший ли подход применён?
Какие алгоритмы можете предложить для реализации деления?
> Почему вектор содержит int, а не unsigned?
Я предусмотрел спец положение -1 в каком либо разряде на случай ошибки, если в функцию что - то не то пришло или функция как - то не так работает. Тогда можно было бы использовать тип short. Он покороче остальных.
> "запятая" как я понял бежит по десятичным разрядам, а не двоичным
Да, по десятичным. Если двоичные разряды использовать и тип unsigned, то вектор больше памяти будет занимать чем при десятичных разрядах и тип unsigned. Если двоичные разряды использовать то vector < char >.
Чем предпочтительнее использовать число в двоичном предст-ении?

Юрий-17 Гений (76476) Я использую вариант, когда числа представлены в виде дробей, где числитель и знаменатель беззнаковые целые, но представлены в виде целочисленного массива с шаблонной подстановкой. В моём подходе есть, конечно минусы, разрядность чисел быстро увеличивается из-за чего расчёты тормозятся. Первый вариант был символьный (каждая цифра символ (байт)) но потом переделал под двоичную арифметику. Соответственно как небо от земли стало быстрее, но также через некоторое время, когда разрядность под несколько тысяч, начинает ттормозить. В Вашем варианте я предложил бы повторить стандарт IEEE - знак 1 старший бит, N бит - порядок и M бит - дробная часть двоичной нормализованной мантиссы. Если бы Вы этим занялись, то в итоге пришли бык самому оптимальному варианту.

Роман ProtocolМыслитель (8562) 5 лет назад

Я перегрузил и отладил перегрузку для операторов + -* > < <= >= == для обработки экземпляров класса Infinite_double и vector < int >.
Деление сложновато перегружать.

Юрий-17 Гений (76476) Ну работа с десятичным представлением двоичных чисел - не очень простая (в смысле отладки) задача. Поэтомк и отмечаю, что лучше делать в том, в чём изначально работает вычислительная машина

Роман ProtocolМыслитель (8562) 5 лет назад

Чтобы оправдать использование двоичных разрядов по объёму занимаемой памяти контейнером нужно подобрать тип данных как можно меньший, но не принимающий 10 позиций. Иначе по объёму памяти хранения десятичная запись предпочтительней, на мой взгляд. Это по одному параметру. Я не знаю, почему Вы предлагаете двоичную запись, может это быстрее считать будет ПК. Опишите преимущества использования двоичных разрядов.

Юрий-17 Гений (76476) Данные в ЭВМ, на которых практически все работают, изначально хранятся и обрпабатываются в двоичном виде. Десятичное только представление для воприятия человеком. Да, двоичная обработка и быстрее и эффективное использование памяти. Кроме того, чтобы не ошибаться со знаком олучше все данные в массиве содержать беззнаковые. Кроме того, вот у Вас проблемы с делением. А ведь в двоичной арифметике все арифметические операции намного проще, чем в десятичной, а значит и отладка проще!

Роман ProtocolМыслитель (8562) 5 лет назад

Я ввёл множество шаблонов. При объявлении экземпляров класса Infinite_double просто определяем шаблон класса, который пропишет все T во всех vector < T > мантиссы в коде.

Юрий-17 Гений (76476) Это хорошо, отчасти это помогает. Если бы ещё не тупизи Intel, то в данном случае вообще бы всё было замечательно (это я на счёт операции сдвига вправо и влево)

Роман ProtocolМыслитель (8562) 5 лет назад

Уже попались -1, значит ещё ошибка есть.
Это в случае 131072 / 17 ответ 770-1.-1-1-1-1-1 вместо 7710.11764.
-1 выбрасывает функция Division_Digit, если цифра более 9, что недопустимо.
template < typename T >
int Division_Digit(vector < T > &v2, vector < T > v1)
{
int rez = -1;
if (v2 == v1)
{
rez = 1;
v2.clear();
}
else
{
rez = 0;
for (unsigned u = 0; u < 9; ++u)
{
if (v2 >= v1)
{
v2 = v2 - v1;
Clear_null_v(v2);
++rez;
}
else
{
break;
}
}
if (v2 >= v1)
{
rez = -1;
}
}
return rez;
}

Юрий-17 Гений (76476) Вот слово "попалось" очень плохое. А если бы не попалось! А попалось уже когда ответственная работа!? Такие выкладки должны быть теоретически выверены с гарантией отсутствия непредвиденных ситуаций и небольшого но охватывающего всевозможные варианты тестового материала

Answer 2

Генрих Беляков Гуру (3279) 5 лет назад

Извини, но тут кажись дают х2 баллов! Я за баллом...

Голова РоботаПросветленный (36328) 5 лет назад

Количество баллов зависит от КПД. Чем больше бестолковых ответов (как этот), тем ниже КПД.

Answer 3

Каждый десятичный знак представлен элементом массива типа int ?
А что бы тогда просто не делать ascii арифметику? на массивах байтов? Я видел такие имплементации.
Далее, если интересно поучиться делать big number math посмотрите ка это сделано в cpython, или в gmplib.

Answer 4

Чем long double не угодил? Точность мантиссы 2^-112, это достаточно много, даже не знаю, где может понадобиться такая точность. Для отображение кол-ва чисел после запятой нужно обращаться к методам cout. Представление в виде строки это конечно забавно, но очень медленно - тем более деление очень дорогая операция и ее по возможности нужно заменять умножением. Советую вам также глянуть формат IEEE 754, как зерно для размышлений. Вообще при реализации сабжа задача сводиться к повторению битов мантиссы, начиная с момента когда наступает периодическое повторение, просто копировать дальше по массиву, естественно работать нужно с двоичным представлением.