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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ присвоить стрке двумерного масива значение http://www.cyberforum.ru/cpp-beginners/thread729915.html
у меня есть масив - mas; и вот кусок кода где надо присвоить второй строке масива значение 5.. вроде правильно написал не понимаю почему не работает.... for(i=1; i<2; i++) { for(j=0; j<5;...
C++ c++ перегрузка функций и еще пара просьб Доброй ночи! вот имеется код с классом объектом которого является комплексное число. класс нужно дополнить динамическим массивом, например, названием комплексного числа(такое уж дурацкое задание) и... http://www.cyberforum.ru/cpp-beginners/thread729913.html
Фиксированный квант времени в алгоритме планирования FCFS C++
Здравствуйте. Вот код программы, планировщика, который работает по алгоритму FCFS. В нем реализованы два состояния: готовность и выполнение. Как дополнить код, чтоб было состояние ОЖИДАНИЯ и...
Создать класс файл с методом top50 по расширению C++
Создать класс File. Добавить метод, который считает сколько файлов на определённом диске. Создать метод Competition. Он показывает файлов какого типа больше всего, а также их кол-во. Метод...
C++ Удалить среднею букву в нечетных словах текста http://www.cyberforum.ru/cpp-beginners/thread729905.html
Нужно удалить в каждом нечетном слове среднею букву, я смог дойти только до такого: удаляет онли в первом слове, дальше уж не знаю, как составить алгоритм, нужна Ваша помощь. #include <iostream>...
C++ Преобразуйте КА к детерминированному виду и минимизируйте полученный КА Помогите с решением задачки: Задан КА: M({S,R,Z}, {a,b}, δ, S, {Z}), δ(S,a) = {S.R}, δ(R,b) = {R}. δ(R,a) = {Z}. Преобразуйте его к детерминированному виду и минимизируйте полученный КА. ... подробнее

Показать сообщение отдельно
HrundelB
0 / 0 / 0
Регистрация: 20.11.2011
Сообщений: 13

Деление длинного числа на длинное - 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru