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

С++ для начинающих

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

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

13.12.2012, 05:27. Просмотров 3039. Ответов 3
Метки нет (Все метки)

Всем привет!

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

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

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

Многократное "длинное" деление (длинного на короткое) - C++
В общем есть задача на перевод с одной системы счисления в другие, где нужно использовать длинную арифметику (деление длинного на...

Деление длинного числа - C++
Почему-то правильно считает только если делить на 200, например, на 20- неправильно, на 2, соответственно тоже...Подскажите, пожалуйста,...

Написать программу которая находит целую часть от деления длинного числа на длинное - C++
Оба числа находятся в массивах. И ответ тоже. Деление столбиком.

Количество делителей длинного числа - C++
Уважаемые знатоки, помогите пожалуйста с задачей на длинную арифметику Задача заключается в том, чтобы найти количество делителей...

Перевод длинного двоичного числа в десятичную СС - C++
Как можно перевести число из двоичной системы счисления в десятичную ели число длиной в 100-300 знаков...

Вывод длинного числа вместо нуля - C++
предполагаю что проблема мелкая, но либо меня гугл забанил, либо ввожу в поиск не то.. перейдем к делу, 1) программа создает...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
NEbO
587 / 455 / 49
Регистрация: 22.01.2009
Сообщений: 1,180
Записей в блоге: 1
Завершенные тесты: 2
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 (числа с плавающей запятой). в любом случае, ради интереса, можно сравнить свою реализацию с ними=) успехов
1
taras atavin
Ушёл с форума.
3569 / 1753 / 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. Нужны комментарии?
0
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. Сколько ж вычитаний сделать придется?)

Здесь та же самая беда, нет разницы, десятичная система счисления или двоичная. Если основание системы очень большое, то вычитаний будет много. В примере выше естессно предполагается, что это только старшие разряды, а за ними еще огромные хвосты цифр. Поэтому разделить инт на инт конечно не можем.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.12.2012, 00:03
Привет! Вот еще темы с ответами:

Перевод длинного десятичного числа в шестнадцатиричное - C++
Здравствуйте. Очень интересует меня вопрос: как перевести большое число (до 2^128), представленное в виде строки из 10-ричной СС в число...

Находим длину самого длинного числа - C++
Ребята, наверное это легко но я чего то не допонимаю:( Написать программу, которая в текстовом файле, состоящем из строк длиной не...

Старшая и младшая часть длинного числа - C++
Есть класс с 2-мя полями целого типа, в которых хранятся старшая и младшая части. Как их выделить? Что представляют из себя эти части?...

Как вычислить 2 в степени длинного числа? - C++
Посчитать 2 в степени длинного числа.


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
14.12.2012, 00:03
Ответ Создать тему
Опции темы

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