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

Классы, Длинная арифметика, LongLong - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.72
Yellow2815
0 / 0 / 0
Регистрация: 03.06.2011
Сообщений: 12
17.06.2011, 22:25     Классы, Длинная арифметика, LongLong #1
Добрый день,

Задание изначально было такое:

Реализовать класс Money , используя для представления рублей класс LongLong.

Класс Money - представлен двумя полями LongLong для рублей и unsigned char для копеек. Дробная часть (копейки) при выводе на экран должна быть отделена от целой части запятой. Реализовать сложение, вычитание, деление сумм, деление суммы на дробное число, умножение на дробное число и операции сравнения.

Класс LongLong для работы с целыми числами из 64 бит. Число должно быть представлено двумя полями: unsigned long — старшая часть, unsigned long — младшая часть. Должны быть реализованы арифметические операции, присутствующие в С++ (без присваивания), и сравнения.

Класс Money реализовал, а проблема в следующем:

Сложение и умножение для LongLong довольно просто реализуется - складываем левые части, складываем правые. Если в левой появился новый разряд, прибавляем в правую. Вычитание тоже ясно, а как быть с умножением?! Как перемножить два longlong если они каждый из двух частей, причём long. Сколько где разрядов получится? Как сделать чтобы не сильно не вылез? А деление я вообще сложно представляю...

В общем, меня как раз и волнуют реализация умножения и деления. Буду рад любым советам. Видел на форуме Валерия Викторовича. Буду очень признателен, если он объяснит какими методами предполагалось решение его задач.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.06.2011, 22:25     Классы, Длинная арифметика, LongLong
Посмотрите здесь:

C++ Длинная арифметика
C++ Длинная арифметика))
Длинная арифметика. C++
Длинная арифметика C++
C++ Длинная арифметика
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
17.06.2011, 23:01     Классы, Длинная арифметика, LongLong #2
Цитата Сообщение от Yellow2815 Посмотреть сообщение
Сложение и умножение для LongLong довольно просто реализуется - складываем левые части, складываем правые. Если в левой появился новый разряд, прибавляем в правую.
Наверное правильнее оперировать понятиями старшая и младшая, а не левая и правая.
Это на ассемблере просто, там флаг переноса есть. На Си всё-таки посложнее. Ну ладно, будем считать, что просто.

Цитата Сообщение от Yellow2815 Посмотреть сообщение
Вычитание тоже ясно, а как быть с умножением?!
Для умножения могу посоветовать помедитировать над следующей формулой.
Предположим, что у нас есть числа размером 2*n разрядов.
Представим числа A и B половинами по n разрядов
A = (Ah << n) + Al
B = (Bh << n) + Bl
Тогда
A*B = ((Ah << n) + Al) * ((Bh << n) + Bl) = (Ah*Bh << 2*n) + ( (Ah*Bl + Al*Bh) << n ) + Al*Bl

Добавлено через 4 минуты
Цитата Сообщение от Yellow2815 Посмотреть сообщение
А деление я вообще сложно представляю...
А деление сдвигами и вычитаниями, как в школе учили — уголком. Медленно, но зато надёжно
Yellow2815
0 / 0 / 0
Регистрация: 03.06.2011
Сообщений: 12
17.06.2011, 23:23  [ТС]     Классы, Длинная арифметика, LongLong #3
Цитата Сообщение от grizlik78 Посмотреть сообщение
Наверное правильнее оперировать понятиями старшая и младшая, а не левая и правая.
Это на ассемблере просто, там флаг переноса есть. На Си всё-таки посложнее. Ну ладно, будем считать, что просто.
Когда Money делал, та же задача была с рублями и копейками, копейки сложили - получили рубль - отправили в рубль.

Цитата Сообщение от grizlik78 Посмотреть сообщение
Для умножения могу посоветовать помедитировать над следующей формулой.
Предположим, что у нас есть числа размером 2*n разрядов.
Представим числа A и B половинами по n разрядов
A = (Ah << n) + Al
B = (Bh << n) + Bl
Тогда
A*B = ((Ah << n) + Al) * ((Bh << n) + Bl) = (Ah*Bh << 2*n) + ( (Ah*Bl + Al*Bh) << n ) + Al*Bl
Помедитирую, спасибо за формулу.

Цитата Сообщение от grizlik78 Посмотреть сообщение
А деление сдвигами и вычитаниями, как в школе учили — уголком. Медленно, но зато надёжно
Столбиком? так там же две части? какой алгоритм предполагается?
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
17.06.2011, 23:33     Классы, Длинная арифметика, LongLong #4
Цитата Сообщение от Yellow2815 Посмотреть сообщение
Столбиком? так там же две части? какой алгоритм предполагается?
По-моему это всё-таки называется уголком. В столбик умножают
Предполагается что у нас уже есть реализованные функции сравнения, вычитания и, хотя бы, умножение на 2 (а лучше сдвиг влево).
Участвую делимое, делитель и частное
сначала делитель сдвигаем влево по одному разряду (умножаем на 2) до тех пор, пока делитель меньше делимого. Количество сдвигов определяет число разрядов целой части частного.
Если получим делитель больше делимого, придётся вернуться на разряд назад.
Ну а дальше просто.
Если делимое больше-равно делителя, вычитаем делитель из делимого и прибавляем к частному единицу. Если меньше — ничего не меняется. Дальше сдвигаем делитель на разряд вправо, частное на разряд влево и повторяем столько раз, сколько нужно
Ну, тонкости уже во время реализации продумать можно. Рекомендую поделить разные числа в двоичной форме на листочке вручную
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
18.06.2011, 08:46     Классы, Длинная арифметика, LongLong #5
1. Умножение можно делать многократным сложением - в цикле
2. Деление можно делать многократным вычитанием - в цикле

Сложение младших частей и перенос.
1. Младшая часть LongLong - беззнаковая.
2. Если при сложении получается число, которое меньше обоих слагаемых - значит есть перенос.
Проверьте на числах из одной цифры:
6+7 = 13. В младшей части осталось 3 - меньше 6 и меньше 7.
Поэтому учесть перенос - легко.

Изучайте машинное представление чисел...
Yellow2815
0 / 0 / 0
Регистрация: 03.06.2011
Сообщений: 12
18.06.2011, 17:28  [ТС]     Классы, Длинная арифметика, LongLong #6
Цитата Сообщение от grizlik78 Посмотреть сообщение
По-моему это всё-таки называется уголком. В столбик умножают
Конечно, уголком... это я утомился и допустил опечатку))

ValeryLaptev,
А цикл вы считаете нормальным решением данной задачи?


Спасибо за советы, выходные частично посвящу этой задаче. Посмотрим, что получится...
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
18.06.2011, 17:38     Классы, Длинная арифметика, LongLong #7
Цитата Сообщение от Yellow2815 Посмотреть сообщение
Конечно, уголком... это я утомился и допустил опечатку))

ValeryLaptev,
А цикл вы считаете нормальным решением данной задачи?

Спасибо за советы, выходные частично посвящу этой задаче. Посмотрим, что получится...
Да. Реализовали базовую операцию вычитания, отладили ее. Теперь в делении можно использовать ГАРАНТИРОВАННО правильную функцию. Если ошибки есть, то только в НОВОМ тексте.
Yellow2815
0 / 0 / 0
Регистрация: 03.06.2011
Сообщений: 12
18.06.2011, 18:03  [ТС]     Классы, Длинная арифметика, LongLong #8
ValeryLaptev,
Это задание можно без перегрузки операторов делать?
То есть просто методы класса описать и всё? И потом функции только вызывать?

А то я уже задания из второго семинара поделал, там 8-чные числа, 16-чные.. И меня перемкнуло, что здесь тоже нужно перегрузку операторов делать, а это ведь не обязательно да?
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
18.06.2011, 18:48     Классы, Длинная арифметика, LongLong #9
Да, первый раз - без перегрузки. Потом будет и с конструкторами, и с перегрузкой...
Yellow2815
0 / 0 / 0
Регистрация: 03.06.2011
Сообщений: 12
20.06.2011, 16:12  [ТС]     Классы, Длинная арифметика, LongLong #10
Возник вопрос

Как быть если с числом 10000000000
в старшую часть поместится 10, а в младшую 000000000.
Тогда общее число станет 100, вместо 10000000000.

Такая проблема возникает не только при вводе(что я решил), но и при вычитании...
как быть?
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
20.06.2011, 16:16     Классы, Длинная арифметика, LongLong #11
Непонятно, с чего это общее станет 100? Если старшая часть не равна нулю, то в младшей все нули значащие, и, к примеру, при выводе их нужно будет выводить все.
Yellow2815
0 / 0 / 0
Регистрация: 03.06.2011
Сообщений: 12
20.06.2011, 16:21  [ТС]     Классы, Длинная арифметика, LongLong #12
Цитата Сообщение от grizlik78 Посмотреть сообщение
Непонятно, с чего это общее станет 100? Если старшая часть не равна нулю, то в младшей все нули значащие, и, к примеру, при выводе их нужно будет выводить все.

так ведь младшая часть у нас unsigned long. а ей что 0, что 0000000. Всё едино.
Простой вывод числа - можно организовать, а вот после вычитания как быть. Сносить разряды из старшей части что ли? Так нам нули надо сохранить... или наоборот в старшую часть нули перекидывать?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
21.06.2011, 15:30     Классы, Длинная арифметика, LongLong #13
Yellow2815, если хоть что-то есть в старшей части, а младшая равна нулю, то в ней на самом деле лежит 20 нулей. Просто запоминаем это и действуем по обстоятельствам.
Yellow2815
0 / 0 / 0
Регистрация: 03.06.2011
Сообщений: 12
21.06.2011, 17:55  [ТС]     Классы, Длинная арифметика, LongLong #14
silent_1991, )) Это хорошо, для вывода сгодится, а вот при таком числе
1000000000000001, делаем разбиение
старшая 1000000 и младшая 000000001.
Что в младшей?
В общем очень не просто. Длинная арифметика лучше реализуется с массивами.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
21.06.2011, 18:03     Классы, Длинная арифметика, LongLong #15
Цитата Сообщение от Yellow2815 Посмотреть сообщение
Это хорошо, для вывода сгодится, а вот при таком числе
1000000000000001, делаем разбиение
старшая 1000000 и младшая 000000001.
Что в младшей?
Хочется кое что уточнить. Я вот всё не могу понять, что же за представление используется для хранения младшей части, если в примерах там 9 разрядов. Кстати, эти разряды двоичные? Если двоичные, то что это, отдельные биты в некоторой целочисленной переменной?
Ну а непосредственно по вопросу, в младшей части число 1. Но при вычитании двойки в младшей части должно оказаться максимально возможное значение этой младшей части. А старшая должна уменьшиться на 1, то есть да — произойдёт заём из старшей части. Для получения полного числа младшая и старшая части складываются (мысленно) с разными весами. Младшая с весом один, старшая с весом равным максимуму младшей плюс один.

Добавлено через 50 секунд
Если всё не так, то требуется нам подробно объяснить, что понимается под младшей и старшей частями.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
21.06.2011, 18:08     Классы, Длинная арифметика, LongLong #16
grizlik78, как только переполняется младшая часть, это самое переполнение идёт в старшую.

Yellow2815, у вас абстрактный пример, число полностью поместится в младшей части.
А действуем так: если старшая часть не пустая, то берём младшую часть, дописываем к ней спереди нули, которых не хватает, чтобы в общем получилось 20 разрядов - получаем реальную младшую часть, при приклеивании к которой старшей получим исходное число.
Yellow2815
0 / 0 / 0
Регистрация: 03.06.2011
Сообщений: 12
21.06.2011, 18:09  [ТС]     Классы, Длинная арифметика, LongLong #17
Цитата Сообщение от grizlik78 Посмотреть сообщение
Хочется кое что уточнить. Я вот всё не могу понять, что же за представление используется для хранения младшей части, если в примерах там 9 разрядов. Кстати, эти разряды двоичные? .
разряды десятичные
В задании указано unsigned long для младшей части и long для старшей. Применяя к классу money для старшей тоже будет unsigned long. undigned long 0..4294967295 чтобы избежать проблем с наибольшим разрядом, я его не стал учитывать и младшая часть максимальная - это 999999999.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.06.2011, 18:13     Классы, Длинная арифметика, LongLong
Еще ссылки по теме:

C++ Длинная арифметика
C++ Длинная арифметика
C++ Длинная арифметика

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

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
21.06.2011, 18:13     Классы, Длинная арифметика, LongLong #18
Вернее нет, хранить надо по 19 разрядов, двадцатый - неполноценный :-D

Добавлено через 3 минуты
Yellow2815, ах да, я, блин, в уме long long держу, long будет 2^32...
Но суть не меняется, просто цифр меньше.
Yandex
Объявления
21.06.2011, 18:13     Классы, Длинная арифметика, LongLong
Ответ Создать тему
Опции темы

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