|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
23.10.2016, 09:42 | #1 |
Регистрация: 23.10.2016
Сообщений: 4
|
"Длинная арифметика" деление длинных чисел
Эту программу я нашел на просторах интернетов, но не понимаю как она работает, помогите разобраться, пожалуйста
Код:
|
23.10.2016, 11:46 | #2 |
Регистрация: 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 и выводит результат на экран. |
23.10.2016, 17:15 | #3 |
Форумчанин
Регистрация: 24.01.2011
Сообщений: 774
|
Как-то я писал ужасный класс для длинной арифметики.
Главный его минус: он большой, плохо протестирован и при этом не поддерживает умножение и деление. Главные плюсы: для сложения, вычитания, префиксного сложения и вычитания, сравнения на равенство и неравенство, ввода и вывода в stream перегружены операторы. Плюс, где только можно, использована move-семантика. Число в нём записано в системе счисления на основе миллиарда, цифры хранятся в 4-байтовых целых внутри вектора. Может будет полезно. P.S. а то, для чего я его писал, через два дня написания этого монстра решил делать на Python.
a.k.a. Angelicos Phosphoros
Мой сайт |
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Длинная Арифметика. Деление. | 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 |