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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.78
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
25.09.2012, 23:03     Длинная арифметика #1
Нужно реализовать сложение и умножение больших чисел.
Есть идея, необходима помощь в реализации на C++.
Собственно, идеи такие...
Сумма: берём 2 массива, записываем их в строки, затем добавляем к меньшему числу нули так, чтоб их длина стала одинаковой. Затем, начиная с последнего элемента каждого массива, поэлементно суммируем элементы и остаток деления этой суммы на 10 записываем в начало новой строки. Если результат целочисленного деления суммы на 10 больше 0, то к следующему остатку предварительно прибавляем этот результат. И так до начала массива.
Произведение: берём последний элемент меньшего массива и умножаем поэлементно на больший массив, с делением на 10 (как в предыдущем пункте) и получаем новый массив. Далее с предпоследним элементом делаем тоже самое, затем в конце приписываем к нему '0' и производим сумму последних. Повторяем до тех пор, пока не достигнем начало меньшего массива.
Вот, что я пока написал. Понимаю, что бред, но может его можно исправить. Помогите, пожалуйста, очень срочно нужно
код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>
#include <string>
 
int CtI(char x) // char в int
{
    return int(x)-48;
}
 
char ItC(int x) // int в char
{
    return char(x+48);
}
 
std::string adapt(std::string x, std::string y) // дописываем нули
{
    std::string::iterator iter = y.begin();
        y.insert(iter, x.size() - y.size(), '0');
    return y;
}
 
std::string sum_func(std::string x, std::string y)
{
    
    std::string::iterator x_iter = x.begin();
    std::string::iterator y_iter = y.begin();
    x.insert(x_iter, '0');
    y.insert(y_iter, '0');
    if (x.size() > y.size())
        y = adapt(x,y);
    if (x.size() < y.size())
        x = adapt(y,x);
    std::string sum;
    std::string::iterator sum_iter = sum.begin();
    int temp = 0;
    for (x_iter = --x.end(), y_iter = --y.end(); x_iter != x.begin(); --x_iter, --y_iter) // для того, чтоб цикл выполнился до
    {                                                                                     // конца мы заранее добавили по нолику
        if (temp != 0)
        {
            sum.insert(sum_iter, ItC((CtI(*x_iter)+CtI(*y_iter))%10+temp));
            temp = 0;
        }
        else
            sum.insert(sum_iter, ItC((CtI(*x_iter)+CtI(*y_iter))%10));
        temp = (CtI(*x_iter)+CtI(*y_iter))/10;
    }
    if (temp != 0)
        sum.insert(sum_iter, ItC(temp));
    else
        sum.erase(sum_iter);
    return sum;
}
 
int main()
{
    std::string x, y;
    std::cin >> x >> y;
    std::cout << sum_func(x,y);
    std::cin.get(); std::cin.get(); 
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.09.2012, 23:03     Длинная арифметика
Посмотрите здесь:

Длинная арифметика C++
C++ Длинная арифметика
C++ Длинная арифметика
C++ Длинная арифметика
C++ Длинная арифметика
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
27.09.2012, 09:35     Длинная арифметика #21
Зачем мучаться с десятичной системой? Возьмите основание, равное количеству чисел, представимых байтом, а тип элемента байт. Складывать можно так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TLongNamber TLongNamber:: operator + (TLongNamber &Right)
{
 TLongNamber Result;
 byte *p1, *p2, *p3;
 word buffer;
 word f;
 word o=UCHAR_MAX+1;
 for (p1=Litle, p2=Right->Litle, p3=Result->Litle, f=0; p1>=Big; --p1, --p2, --p3)
 {
  buffer=(word)(*p1)+(word)(*p2)+f;
  f=buffer/o;
  *p3=buffer%o;
 }
 return Result;
}
Добавлено через 1 час 3 минуты
Можно даже не делить, а сдвигать, а остаток выделять макросом.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
TLongNamber TLongNamber:: operator + (TLongNamber &Right)
{
 TLongNamber Result;
 byte *p1, *p2, *p3;
 word buffer;
 word f;
 for (p1=Litle, p2=Right->Litle, p3=Result->Litle, f=0; p1>=Big; --p1, --p2, --p3)
 {
  buffer=(word)(*p1)+(word)(*p2)+f;
  f=buffer>>sizeof(byte);
  *p3=LOWBYYE(buffer);
 }
 return Result;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
27.09.2012, 10:18     Длинная арифметика #22
Цитата Сообщение от taras atavin Посмотреть сообщение
Зачем мучаться с десятичной системой? Возьмите основание, равное количеству чисел, представимых байтом, а тип элемента байт.
тут будет проблема перевести в удобный для пользователя формат(десятичный) и обратно
основание нужно брать равным степени десятки
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
27.09.2012, 10:25     Длинная арифметика #23
Для этих целей приняты переводы при вводе/выводе.
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
27.09.2012, 10:41     Длинная арифметика #24
Цитата Сообщение от taras atavin Посмотреть сообщение
Для этих целей приняты переводы при вводе/выводе.
я про это и говорил, при вводе выводе придется реализовывать длинную арифметику на десятичной базе
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
27.09.2012, 10:47     Длинная арифметика #25
С какого перепугу? Арифметика делается во внутреннем представлении и не зависит ни от второго основания, ни от направления перевода.
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
27.09.2012, 10:52     Длинная арифметика #26
Цитата Сообщение от taras atavin Посмотреть сообщение
С какого перепугу? Арифметика делается во внутреннем представлении и не зависит ни от второго основания, ни от направления перевода.
ну ладно, давай так - ты напишешь функцию перевода десятичного числа из строки в число с основанием 256, потом обратно
даже при обратном преобразовании нужно реализовывать сложение, напиши хотя бы алгоритм а?
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
27.09.2012, 11:01     Длинная арифметика #27
Откуда всплыла константа?
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
27.09.2012, 11:07     Длинная арифметика #28
Цитата Сообщение от taras atavin Посмотреть сообщение
Откуда всплыла константа?
Цитата Сообщение от taras atavin Посмотреть сообщение
Зачем мучаться с десятичной системой? Возьмите основание, равное количеству чисел, представимых байтом, а тип элемента байт.
byte --> 2^8 вроде бы
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
27.09.2012, 11:10     Длинная арифметика #29
Цитата Сообщение от vndtta Посмотреть сообщение
byte --> 2^8 вроде бы
Байт - единица адресной организации памяти, а не информации и в принципе может быть любым, хоть 9 тритов (19 683 представимых значений). То, что большинство современных машин имеет 8-ми битные байты сути не меняет и в исходнике не упомянуто.
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
27.09.2012, 11:17     Длинная арифметика #30
Цитата Сообщение от taras atavin Посмотреть сообщение
Байт - единица адресной организации памяти, а не информации и в принципе может быть любым, хоть 9 тритов (19 683 представимых значений). То, что большинство современных машин имеет 8-ми битные байты сути не меняет и в исходнике не упомянуто.
ладно, и ты считаешь, что тс сейчас сидит в каком-нибудь НИИ и бороздит интернет с какого-нить мэйнфрейма с 36-битной архитектрой? в общем сказки
алгоритм перевода плз в студию
запихни любой байт, какой удобно, на алгоритм не повлияет ведь?
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
27.09.2012, 11:23     Длинная арифметика #31
Нет, конечно. Речь о том, что мои исходники и формулировки в этой теме учитывают любые нестандарты и даже слухи о том, что пятое поколение будет троичным. Ну так, на всякий случай. А то вдруг ему вообще для контроллера на какой ни будь "левой" архитектуре? Может там байт равен биту, или, наоборот 64-м битам.

Добавлено через 4 минуты
Для перевода во внутренне представление, кстати, нужно деление с остатком, а не умножение.
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
27.09.2012, 11:30     Длинная арифметика #32
Цитата Сообщение от taras atavin Посмотреть сообщение
Нет, конечно. Речь о том, что мои исходники и формулировки в этой теме учитывают любые нестандарты и даже слухи о том, что пятое поколение будет троичным. Ну так, на всякий случай. А то вдруг ему вообще для контроллера на какой ни будь "левой" архитектуре? Может там байт равен биту, или, наоборот 64-м битам.

Добавлено через 4 минуты
Для перевода во внутренне представление, кстати, нужно деление с остатком, а не умножение.
я в курсе, т.е. ты согласен, что нужна длинная арифметика на десятичной базе?
речь кстати шла о сложении и переводе в пользовательский формат
даже при обратном преобразовании нужно реализовывать сложение
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
27.09.2012, 14:18     Длинная арифметика #33
Цитата Сообщение от vndtta Посмотреть сообщение
т.е. ты согласен, что нужна длинная арифметика на десятичной базе?
Нет, конечно.

Добавлено через 3 минуты
Ну можно с младших разрядов умножением.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
27.09.2012, 15:37     Длинная арифметика #34
Применение любых оснований счисления для внутреннего представления вроде байта-слова в Си++ сталкивается со следующей проблемой: переполнения. Они никак не ловятся простыми средствами. Или складывать два uint32_t в один uint64_t и смотреть, что там в старшем бите, или ассемблерные вставки. Первое не особо эффективно, второе требует геморроя для того, чтобы оно было переносимо. Для умножения, естессно, только первый вариант, так что без особой разницы.

Как именно там внутри представляется — это дело десятое. Выводить длинные числа в большинстве случаев надо реже, чем производить операции над ними, так что потери при переводе в десятичную систему по крайней мере морально оправданы. Естественно, они будут значительными, потому что это очень много неудобных делений. Если представлять в десятичном виде, то места будет жрать чуть больше, и скорость чуть меньше: надо ж делать лишнее вычитание основания счисления, тогда как в двоичном виде флаг переполнения заполняется автомагически. Именно поэтому и спорно. Вроде как и чуть медленнее десятичное основание, но я бы не сказал, что драматически: вычитание всё же штука быстрая. Правда, при умножении беда — делить на десятичное основание, — да.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
27.09.2012, 15:47     Длинная арифметика #35
Так ведь сложение то происходит сразу в двойной разрядности.
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
27.09.2012, 23:11     Длинная арифметика #36
vlad_light, немного поправил первые три функции. Вывод смотрится проще (как я раньше-то его не исправил?), конвертеры сразу переворачивают. Т.е. функция inverse больше не нужна.
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void Output (const std::string& str)
{
    std::cout << str;
}
 
std::vector<int> StrToInt (const std::string& str)
{
    std::vector<int> vec(str.crbegin(), str.crend());
 
    for (auto iter = vec.begin(); iter!= vec.end(); ++iter)
    {
        *iter -= '0';
    }
    return std::move(vec);
}
 
std::string IntToStr (const std::vector<int>& vec)
{
    std::string str(vec.crbegin(), vec.crend());
 
    for (auto iter = str.begin(); iter!= str.end(); ++iter)
    {
        *iter += '0';
    }
    return std::move(str);
}

Класс, если упрощенно, это совокупность данных и методов, которые работают с этими данными. Здесь в качестве данных было бы логично сделать массив, который хранит числа. А в качестве методов - арифметические операции над этими массивом.
Не надо создавать класс ради того, чтобы создать класс. Задайте сами себе вопрос - какой смысл в классе для длинной арифметики, у которого только 2 доступных метода - ввод и вывод.
Назовите класс уже традиционно big_int (BigInt или как больше нравится) и вперед) Советую для начала не лезть в перегрузку операторов. Просто разберитесь, что такое класс.
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
27.09.2012, 23:48  [ТС]     Длинная арифметика #37
какой смысл в классе для длинной арифметики
Я видел, как делают плюсики вместо моих Add и т.п., например, a+b смотрится красивее, чем Add(a,b). Говорили, это в классе делается.
И ещё вопрос: Вы пишете cbegin(), cend(). Чем они отличаются от begin() и end()? И что делает функция std::move?
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
27.09.2012, 23:54     Длинная арифметика #38
Цитата Сообщение от vlad_light Посмотреть сообщение
Я видел, как делают плюсики вместо моих Add и т.п., например, a+b смотрится красивее, чем Add(a,b). Говорили, это в классе делается.
Да, это делается в классе, но
Цитата Сообщение от I.M. Посмотреть сообщение
Советую для начала не лезть в перегрузку операторов. Просто разберитесь, что такое класс.
Цитата Сообщение от vlad_light Посмотреть сообщение
cbegin(), cend()
Они возвращают const_iterator. Поэтому и буква 'c' в начале имени метода стоит.

Цитата Сообщение от vlad_light Посмотреть сообщение
std::move
Хм, если коротко и без технических подробностей, то она позволяет минимизировать накладные расходы при возвращении из функции объекта по значению. Пользоваться ей всегда и везде не стоит
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.09.2012, 15:45     Длинная арифметика
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
28.09.2012, 15:45     Длинная арифметика #39
Смысл в длинной арифметике появляется, например, при рассчёте перемещений на борту корабля в единой галактической локации. Причём, ещё и с длинно-плавающей запятой, а не в длинно-целой арифметике.
Yandex
Объявления
28.09.2012, 15:45     Длинная арифметика
Ответ Создать тему
Опции темы

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