Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 23.10.2016, 09:42   #1
leftdead76
 
Регистрация: 23.10.2016
Сообщений: 4
По умолчанию "Длинная арифметика" деление длинных чисел

Эту программу я нашел на просторах интернетов, но не понимаю как она работает, помогите разобраться, пожалуйста
Код:
// Lab3Alg.cpp: определяет точку входа для консольного приложения. 
// 
#include "stdafx.h" 
 
#include <math.h> 
#include <string> 
 
#include <iostream> 
#include <windows.h> 
 
using namespace std; 
#include <iostream> 
#include <string> 
 
////////////////////////////////////////////////////////////////////////////////////// 
typedef std::string T_num_s; 
////////////////////////////////////////////////////////////////////////////////////// 
void del_leading_zero(T_num_s& a) 
{ 
while (a.size() > 1 
&& a[0] == '0') 
{ 
a.erase(0, 1); 
} 
} 
////////////////////////////////////////////////////////////////////////////////////// 
bool less_for_big_int(T_num_s a, T_num_s b) 
{ 
del_leading_zero(a); 
del_leading_zero(b); 
 
return a.size() == b.size() ? a < b : a.size() < b.size(); 
} 
////////////////////////////////////////////////////////////////////////////////////// 
void reduce_big_int(T_num_s& minuend, const T_num_s& subtrahend)// функция деления в слобик больших чисел 
{ 
for (T_num_s::size_type cur_pos = 0; cur_pos < subtrahend.size(); ++cur_pos) 
{ 
T_num_s::size_type minuend_cur_pos = minuend.size() - 1 - cur_pos; 
T_num_s::size_type subtrahend_cur_pos = subtrahend.size() - 1 - cur_pos; 
 
char& cur_minuend_dig_ref = minuend[minuend_cur_pos]; 
const char& cur_subtrahend_dig_ref = subtrahend[subtrahend_cur_pos]; 
 
if (cur_minuend_dig_ref >= cur_subtrahend_dig_ref) 
{ 
cur_minuend_dig_ref -= cur_subtrahend_dig_ref - '0'; 
} 
else 
{ 
(cur_minuend_dig_ref -= cur_subtrahend_dig_ref - '0') += 10; 
for (int i = 1; ; ++i) 
{ 
if (minuend[minuend_cur_pos - i] == '0') 
{ 
minuend[minuend_cur_pos - i] = '9'; 
} 
else 
{ 
—minuend[minuend_cur_pos - i]; 
break; 
} 
} 
} 
del_leading_zero(minuend); 
} 
del_leading_zero(minuend); 
} 
////////////////////////////////////////////////////////////////////////////////////// 
void inc_big_int(T_num_s& a) 
{ 
for (T_num_s::size_type cur_pos = a.size() - 1;; —cur_pos) 
{ 
if (a[cur_pos] < '9') 
{ 
++a[cur_pos]; 
return; 
} 
else 
{ 
a[cur_pos] = '0'; 
if (cur_pos == 0) 
{ 
a.insert(0, "1"); 
return; 
} 
} 
} 
} 
////////////////////////////////////////////////////////////////////////////////////// 
T_num_s div_big_int(const T_num_s& a, const T_num_s& b)// функция деления в столбик 
{ 
if (b == "0") 
{ 
return "division into zero";// нельзя делить на 0 
} 
 
T_num_s res = "0"; 
T_num_s minuend = a;// делитель, ведущее число 
T_num_s subtrahend = b;// делимое 
 
while (subtrahend.size() < minuend.size()) 
{ 
subtrahend += '0';//прибавляем 0 к делителю 
} 
 
for (;;)//бесконечный цикл операций деления 
{ 
 
while (!less_for_big_int(minuend, subtrahend)) 
{ 
reduce_big_int(minuend, subtrahend); 
inc_big_int(res); 
} 
if (subtrahend.size() <= b.size()) 
{ 
break; 
} 
 
subtrahend.erase(subtrahend.size() - 1); 
res += '0'; 
del_leading_zero(res); 
} 
 
return res; 
} 
////////////////////////////////////////////////////////////////////////////////////// 
int main() 
{ 
for (;;) 
{ 
cout « "a = "; 
T_num_s a; 
cin » a; 
del_leading_zero(a); 
 
cout « "b = "; 
T_num_s b; 
cin » b; 
del_leading_zero(b); 
 
cout « "a / b = " 
« div_big_int(a, b) 
« endl 
« endl 
« endl; 
} 
}
leftdead76 вне форума Ответить с цитированием
Старый 23.10.2016, 11:46   #2
leftdead76
 
Регистрация: 23.10.2016
Сообщений: 4
По умолчанию Ответ найден

вот если кому надо будет
Операции с длинными числами - это операции со строками.
Обычно размер чила ограничивается размеров регистра, но если нам нужны более длинные числа,
то мы можем хранит их в виде строки и уже перекладывать мат логику на строки, как тут и сделано.
Так размер нашего числа, грубо говоря, ограничивается не регистром в 16 байт, а размером строки.
Какой размер в Си у стринг, 4ГБ?
Хотя строки, оканчивающись нулём, имеют размер ... размер ОЗУ.
(хотя возможно реализовать, чтоб ограничивались размером ПЗУ, но это будет слишком медленно, да и кому надо)
Теперь сам функционал:
del_leading_zero - если в строка начинается с нулей - удалить их

less_for_big_int - определяет какое из чисел больше
сравнивает длины по их длине, какое длинее то и больше.
Возникает вопрос, если длины одинаковые, то происходит сравнение адресов строк, что не есть логично.

reduce_big_int - производит вычитание из числа (хранящиеся в виде строки) minuend, число (хранящиеся в виде строки) subtrahend
Вычитание производится путём побайтового вычитания с конца строки (с младших разрядов числа)
Если текущий байт в minuend >= текущего байта в subtrahend, то просто вычитает их (9 - 7 = 2)
Если minuend < subtrahend, то вычитнаине выглядит так (7 - 9 + 10 = 8), +10 - это заём из старших разряов
Этот заём дальше как раз и вычитается вот тут —minuend[minuend_cur_pos - i];
Только вопрос, почему здесь унарный минус (даже не минус, а дефис) вместо декремента? надо --minuend[minuend_cur_pos - i];
Хм, а если занимать неоткуда, то произойдёт переполнение и хорошо, если, у Вас программа просто упадёт.
Причём переполнение также может произойти, если длина subtrahend больше, чем у minuend.
Функция не безопасная.

inc_big_int - увеличивает значения числа в строке на единицу

div_big_int - произвоит целочисленное деление строки а на б
Деление происходит след образом, например 123456789 поделим на 10
число 10 будет расширено до 100_000_000
Далее вычитаем из 123456789 число 100_000_000, пока 123456789 > 100000000
Вычитание произошло один раз, записываем это в res. res = 1
Далее 23456789 - 10_000_000. Операция прошла 2 раза, запишем в res = 12
3456789 - 1_000_000, 3 раза => res = 123
...
89 - 10, 8 раз => res = 12345678
А далее конец, т.к. делитель стал равен своему первоначальному значению 10
В результате получили 12345678, остаток 9, но он просто выкидывается.

main - запрашивает на ввод 2 числа в виде строки делит их с помощью div_big_int и выводит результат на экран.
leftdead76 вне форума Ответить с цитированием
Старый 23.10.2016, 17:15   #3
New man
Форумчанин
 
Регистрация: 24.01.2011
Сообщений: 774
По умолчанию

Как-то я писал ужасный класс для длинной арифметики.

Главный его минус: он большой, плохо протестирован и при этом не поддерживает умножение и деление.

Главные плюсы: для сложения, вычитания, префиксного сложения и вычитания, сравнения на равенство и неравенство, ввода и вывода в stream перегружены операторы.
Плюс, где только можно, использована move-семантика.

Число в нём записано в системе счисления на основе миллиарда, цифры хранятся в 4-байтовых целых внутри вектора.

Может будет полезно.

P.S. а то, для чего я его писал, через два дня написания этого монстра решил делать на Python.
Вложения
Тип файла: 7z LongArithmeticCPP.7z (3.6 Кб, 38 просмотров)
a.k.a. Angelicos Phosphoros
Мой сайт
New man вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Длинная Арифметика. Деление. cr1me Общие вопросы Delphi 9 28.05.2013 18:34
Длинная арифметика:деление двух чисел luis_elgoro Помощь студентам 0 10.04.2012 16:40
длинная арифметика: деление Dеlphi Общие вопросы C/C++ 0 19.01.2011 13:19
Длинная арифметика на C#(деление) Mr_Dark Общие вопросы .NET 1 21.06.2009 21:57
Длинная арифметика: деление Vadik(R) Помощь студентам 1 27.03.2009 12:08