Форум программистов, компьютерный форум CyberForum.ru

Деление длинного числа на длинное - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.68
HrundelB
0 / 0 / 0
Регистрация: 20.11.2011
Сообщений: 13
13.12.2012, 05:27     Деление длинного числа на длинное #1
Всем привет!

Решил написать длинную арифметику в самом ее классическом варианте, когда все операции производятся школьным столбиком. Но вот незадача: я использую основание системы счисления 10^9 (миллиард), т.е. каждая цифра моего большого числа от 0 до 999999999. При написании алгоритма деления длинного числа на длинное возникла проблема: поскольку делить на длинное число мы не умеем, то в алгоритме столбика деление нескольких старших разрядов делимого на делитель я осуществляю вычитаниями. Суть в том, что если мы, например, делим число 999999999 на что-то в районе миллиарда, то вычитаний будет около 9ти, и мы спокойно запишем эту цифру в частное. Однако, если я делю число порядка миллиарда на маленькое число, например, 3ку, то вычитаний будет уже миллиард.

Чтобы было понятнее, напишу пример:
Делим число "123456789 123456789" на число "1 123456789" - двузначное на двузначное. Первым шагом вычитаем из старшего разряда "123456789" наш делитель "1 123456789" - не делится, значит берем еще разряд. Теперь вычитаем из числа "123456789 123456789" наш делитель "1 123456789" пока можем вычитать в цикле while. Видно невооруженным глазом, что вычитаний будет порядка миллиарда, что существенно увеличивает время работы деления.

Есть ли какие-то алгоритмы, в которых числа не нужно вычитать? Перерыл весь интернет, ничего не нашел.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.12.2012, 05:27     Деление длинного числа на длинное
Посмотрите здесь:

C++ Находим длину самого длинного числа
C++ Инвертировать младший байт длинного целого числа
C++ Перевод длинного двоичного числа в десятичную СС
C++ Деление длинного числа
Вывод длинного числа вместо нуля C++
C++ Количество делителей длинного числа
C++ Старшая и младшая часть длинного числа
Как вычислить 2 в степени длинного числа? C++
Посчитать 2 в степени целого длинного числа C++
C++ Многократное "длинное" деление (длинного на короткое)
C++ Написать программу которая находит целую часть от деления длинного числа на длинное
Перевод длинного десятичного числа в шестнадцатиричное C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
NEbO
584 / 452 / 49
Регистрация: 22.01.2009
Сообщений: 1,173
Записей в блоге: 1
Завершенные тесты: 1
13.12.2012, 06:21     Деление длинного числа на длинное #2
в "классическом" варианте берется основание системы 2, 256 (1 байт), 2^16 (2 байта), 2^32 (4 байта) ну или 2^64 для 64 - битных систем. алгоритм для них примерно одинаков, и основан на том, как выполняется деление в процессоре. а выполняется оно на основе операций сдвиг-вычитание, насколько я помню, основных "классических" алгоритмов 3. вот то, что получилось найти за 5 минут:
алгоритм: http://www.distedu.ru/mirror/_inform...nform/div.html
пример: http://www.distedu.ru/mirror/_inform...m/divsamp.html
еще где-то на интуите было, даже с картинками.
этот алгоритм по аналогии масштабируется на 1, 2 или 4 байта -- и становится все просто. имхо, если писать что-то такое, то имеет смысл только на ассемблере с применением sse и очень аккуратно. на 64-битных машинках основной цикл для чисел не сверх большой разрядности неплохо кладется непосредственно в регистры, без обращения к памяти на запись -- подобная реализация, наверное, была бы интересной, хотя может кто-то уже реализовал...
в противном случае, если цель поизучать алгоритмы -- то это хорошо, см. ссылки выше. если же нужно непосредстенно готовое решение, есть замечательные библиотеки gmp (целые числа), mpfr и mpc (числа с плавающей запятой). в любом случае, ради интереса, можно сравнить свою реализацию с ними=) успехов
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
13.12.2012, 08:25     Деление длинного числа на длинное #3
HrundelB, а зачем такое огромное основание? Если основание 16, то на каждом шаге будет не более 15-ти вычитаний. Результат длинный? Эйси. Предположим в твоём варианте результат стазначный. 100*1000000000=100000000000. 100*lg(1000000000)/lg(16)*15=11220. Нужны комментарии?
HrundelB
0 / 0 / 0
Регистрация: 20.11.2011
Сообщений: 13
14.12.2012, 00:03  [ТС]     Деление длинного числа на длинное #4
NEbO, спасибо! Это конечно интересное предложение, но мне, во-первых, хотелось бы все таки доделать ту реализацию, которую я уже на половину сделал, а во-вторых, на ассемблере писать не вариант) А делать сдвиги и вычитания, когда каждая цифра в отдельном элементе массива или вообще односвязного списка - не очень то удобно)

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


taras atavin, большое основание (а точнее не просто большое, а являющееся "машинным словом", т.е. оперируем интами, которые аккурат влезают в разрядность процессора) позволяет очень быстро производить умножение, с помощью которого тысяча факториал (1000!) вычисляется за 0,23 сек, при том, что те же методы но с основанием 10 считают его 25 секунд. И это я еще молчу, что умножение - простой столбик, а факториал - обыкновенная и медленная рекурсия.

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

Добавлено через 7 часов 47 минут
NEbO, разобрался с двоичным делением и возник вопрос - и как же это можно масштабировать такое деление на 4 байта допустим? В оригинальном алгоритме считается, что цифра может быть только 0м или 1цей, что позволяет после одного вычитания сразу сказать - надо добавить единицу в частное или нет. Если масштабировать алгоритм на 4 байта, то каждая цифра (именно цифра, не число) будет принимать значение от 0 до 11111111111111111111111111111111 (32 бита). Теперь представь, что мы делим однозначное число 11111111111111111111111111111111 (ну грубо говоря максимально возможную цифру) на число 101. Сколько ж вычитаний сделать придется?)

Здесь та же самая беда, нет разницы, десятичная система счисления или двоичная. Если основание системы очень большое, то вычитаний будет много. В примере выше естессно предполагается, что это только старшие разряды, а за ними еще огромные хвосты цифр. Поэтому разделить инт на инт конечно не можем.
Yandex
Объявления
14.12.2012, 00:03     Деление длинного числа на длинное
Ответ Создать тему
Опции темы

Текущее время: 21:13. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru