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

Длинная арифметика. Умножение двух длинных чисел. - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 154, средняя оценка - 4.95
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 13:44     Длинная арифметика. Умножение двух длинных чисел. #1
Есть 2 числа, храняющиеся в int векторах, нужна функция, которая возвращает их произведение также в виде вектора.
Либо простой и понятно описанный алгоритм, по которому можно такое сделать.
Заранее спасибо.
P.S. в гугл отправлять не надо-разбираться со сложными алгоритмами вроде БПФ у меня нет ни времени, ни желания.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 21:30  [ТС]     Длинная арифметика. Умножение двух длинных чисел. #21
Цитата Сообщение от vpupkin Посмотреть сообщение
Есть код на паскале
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Procedure Multiplication(A, B : DlChislo; Var C : DlChislo);
 Var I, J : Integer; P : Digit; VspRez : 0..99;
  Begin
    Zero(C);//Обнуление массива C
    For I := 1 To Dlina(A) Do {Цикл по количеству цифр
                               в первом числе}
     Begin
        P := 0; {Первоначально перенос равен нулю}
        For J := 1 To Dlina(B) Do {Цикл по количеству цифр
                                   во втором числе}
         Begin
           VspRez := A[I] * B[J] + P + C[I + J - 1];
           C[I + J - 1] := VspRez Mod 10; {Очередное значение цифры в
                                           разряде I + J - 1}
           P := VspRez Div 10 {Перенос в следующий разряд}
         End;
       C[I + J] := P {последний перенос может быть отличен от нуля,
                      запишем его в пока ещё свободный разряд}
     End
  End;
Перевел, как смог(паскаля не знаю) на с++
В чем ошибка?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
int main(){
    int a[]={1,2,3},b[]={4,5,6},c[5]={0},i,j,x,p;
    for (i = 0; i < 3; i++) {
        p=0;
        for (j = 0; j < 3; j++) {
            x=a[i]*b[j]+p+c[i+j];
            c[i+j]=x%10;
            p=x/10;
        }
    c[i+j+1]=p;
    }
    for (i = 0; i < 6; i++) {
    std::cout << c[i];
    }
    return 0;
}
И все-таки, может кто-нибудь помочь? Очень нужно. Заранее спасибо.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
30.04.2011, 21:34     Длинная арифметика. Умножение двух длинных чисел. #22
Фигня какая-то ввёл 5 5, он мне 3125 выдаёт...
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 21:35  [ТС]     Длинная арифметика. Умножение двух длинных чисел. #23
Ты бы почитал комментарии вверху кода программы для начала, она возводит число a в степень b.
5 в 5й степени равно 3125.
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
30.04.2011, 21:42     Длинная арифметика. Умножение двух длинных чисел. #24
тогда почему на 100 в 10 выдаётся фигня какая-то со всеми числами котррые есть на земле?
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 21:51  [ТС]     Длинная арифметика. Умножение двух длинных чисел. #25
Ну число там немаленькое получается, но в проге видимо баг...
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
30.04.2011, 21:53     Длинная арифметика. Умножение двух длинных чисел. #26
2 в 64 верно вычислил, а вот 100 в 10... да это ладно 10 в 100 ваще фигня, три строчки командной строки тирешками и всем числовым полем забиты)))
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,693
30.04.2011, 21:55     Длинная арифметика. Умножение двух длинных чисел. #27
kiborg_18, вообще, там и ограничения на вводимые данные написаны.
Измените основание, и будет вам счастье.

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
#include <iostream>
#include <vector>
#include <iomanip>
#define BASE 1000000
#define LEN 6
 
void power (std::vector <int> &, const int);
 
int main()
{
    std::vector <int> num;
    int var, pow;
 
    std::cin >> var >> pow;
    num.push_back (var);
 
    for (int i = 0; i < pow - 1; i++)
        power (num, var);
 
    std::cout << num.back ();
    for (int i = num.size () - 2; i >= 0; i--)
        std::cout << std::setfill ('0') << std::setw (LEN) << num[i];
 
    return 0;
}
 
void power (std::vector <int> &vec, const int var)
{
    int carry = 0;
    for (int i = 0; i < vec.size () || carry; i++)
    {
        if (i == vec.size ()) vec.push_back (0);
        carry += vec[i] * var;
        vec[i] = carry % BASE;
        carry /= BASE;
    }
}

Не по теме:

Можете баловаться )

vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 22:03  [ТС]     Длинная арифметика. Умножение двух длинных чисел. #28
С факториалом баловатся удобнее будет, 29!=8841761993739701954543616000000
Но для его реализации нужно будет использовать алгоритм умножения длинного числа на длинное, и таким образом мы из оффтопа возвращаемся к теме.
Если это умножение в столбик такое простое, то почему нигде нету его реализаций на с++?
Обещаю, что если мне дадут реализацию этого алгоритма, то через полчаса выложу код, который будет выводить факториал. Сможете играть сколько влезет - просто вбивайте число размером в пару тысяч и сидите с открытым ртом.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
30.04.2011, 22:06     Длинная арифметика. Умножение двух длинных чисел. #29
vpupkin, мать моя... Вы что же, не в состоянии написать умножение столбиком? Алгоритм я, например, помню с начальной школы, а если бы и не помнил - загуглил бы, на первой странице точно был бы алгоритм. А дальше дело техники...
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 22:08  [ТС]     Длинная арифметика. Умножение двух длинных чисел. #30
Я гуглю второй день-реализации только на паскале, которого я не знаю. Пытался перевести-не пашет.
И вообще, паскалю в этом плане кошернее, у него элементы массива могут быть отрицательные. Если писать через массивы на с++, то число по идее залезет в отрицательные элементы, и ничего хорошего из этого не выйдет.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
30.04.2011, 22:09     Длинная арифметика. Умножение двух длинных чисел. #31
Вот вам, откопал у себя, когда-то делал класс длинной арифметики...

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
Verylong operator*(const Verylong &left, const Verylong &right)
{
    if (left == Verylong::zero || right == Verylong::zero)
        return Verylong::zero;
 
    Verylong result;
    Verylong prod;
 
    unsigned digit;
 
    for (size_t i = 0; i < right._verylong.size(); ++i)
    {
        digit = right._verylong[i] - '0';
 
        prod = left * digit;
        prod = prod._multi_ten(i);
 
        result += prod;
    }
 
    result._sign = Verylong::pos;
 
    if (left._sign != right._sign)
        result._sign = Verylong::neg;
 
    return result;
}
Добавлено через 35 секунд
Надеюсь, умножение длинного на короткое вы написать в состоянии?..

Ну и сумму двух длинных.
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 22:11  [ТС]     Длинная арифметика. Умножение двух длинных чисел. #32
Длинное на короткое элементарно пишется, и я об этом писал уже в этой темке...
Покопаюсь в вашем исходнике, спасибо.
И сумма/разность тоже знаю.
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,693
30.04.2011, 22:20     Длинная арифметика. Умножение двух длинных чисел. #33
Для вычисления факториала умножение двух длинных не нужно)
Второе,
Цитата Сообщение от vpupkin Посмотреть сообщение
И вообще, паскалю в этом плане кошернее, у него элементы массива могут быть отрицательные. Если писать через массивы на с++, то число по идее залезет в отрицательные элементы, и ничего хорошего из этого не выйдет.
смысла в этом вообще не вижу.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
30.04.2011, 22:22     Длинная арифметика. Умножение двух длинных чисел. #34
Цитата Сообщение от neske Посмотреть сообщение
смысла в этом вообще не вижу
Я тоже...

Цитата Сообщение от neske Посмотреть сообщение
Для вычисления факториала умножение двух длинных не нужно
Ну... Если берётся факториал длинного числа, то нужно)))
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,693
30.04.2011, 22:27     Длинная арифметика. Умножение двух длинных чисел. #35
silent_1991, у меня комп взорвется, если я буду вычислять 879837492373874923 в факториале )

Просто привели пример с 29!, и про реализацию сказали, я и возразил.

!
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
// output : var!
 
#include <iostream>
#include <vector>
#include <iomanip>
#define BASE 1000000
#define LEN 6
 
void power (std::vector <int> &, const int);
 
int main()
{
    std::vector <int> num;
    int var;
 
    std::cin >> var;
    num.push_back (1);
 
    for (int i = 2; i <=var  ; i++)
        power (num, i);
 
    std::cout << num.back ();
    for (int i = num.size () - 2; i >= 0; i--)
        std::cout << std::setfill ('0') << std::setw (LEN) << num[i];
 
    return 0;
}
 
void power (std::vector <int> &vec, const int var)
{
    int carry = 0;
    for (int i = 0; i < vec.size () || carry; i++)
    {
        if (i == vec.size ()) vec.push_back (0);
        carry += vec[i] * var;
        vec[i] = carry % BASE;
        carry /= BASE;
    }
}
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 22:29  [ТС]     Длинная арифметика. Умножение двух длинных чисел. #36
Число получается до 2х раз длинее, чем его множители, и просто приписать слева еденичку не получится. А так как во всех алгоритмах, что я видел, была реализация на паскале, то по идее должно вытянутся либо влево, либо вправо. Учитывая, что при счете в столбик суммы уезжают влево, то вытянется тоже влево, т.е. заедет за 0.
...
Извиняюсь за этот бред, в половину четвертого ночи у меня проблемы с формулировкой мыслей.
silent_1991, что делает эта строчка?
C++
1
prod = prod._multi_ten(i);
Впрочем неважно, суть алгоритма в том, что он делает столько же длинных сумм и умножений длинного на короткое, сколько и цифр в наименьшем числе?) В общем то да, просто... А по времени это не чревато? Скажем, 10^2000 * 10^2500 за секунду уложится?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
30.04.2011, 22:31     Длинная арифметика. Умножение двух длинных чисел. #37
neske, ну, если столбиком - то да, взорвётся)) А если БПФ, думаю, выдержит, родимый)))

Добавлено через 46 секунд
vpupkin, умножает длинное на 10 ^ i (простым приписыванием нулей в конец).

Добавлено через 24 секунды
vpupkin, разумеется, не уложится, столбик - прожорливая штука.
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,693
30.04.2011, 22:41     Длинная арифметика. Умножение двух длинных чисел. #38
vpupkin, кстати, в том линке, где еще непонятные 111, это ll1, то есть (long long)1
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 22:44  [ТС]     Длинная арифметика. Умножение двух длинных чисел. #39
Эм... Всмысле 1? Еденица, записанная с помощью 8 байт? о_О
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.04.2011, 23:21     Длинная арифметика. Умножение двух длинных чисел.
Еще ссылки по теме:

C++ Умножение двух длинных чисел
C++ Длинная арифметика: умножение двух длинных чисел
Длинная арифметика: сумма двух строк C++

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

Или воспользуйтесь поиском по форуму:
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,693
30.04.2011, 23:21     Длинная арифметика. Умножение двух длинных чисел. #40
Взял алгоритм по той ссылке, которую я тебе дал, убрал только эту ll1.
Могли бы и вы так попробовать.
+ Я тут взял основание 10, для простоты примера.

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
#include <iostream>
#include <vector>
#include <iomanip>
#include <string>
#include <cstdlib>
#define BASE 10
#define LEN 1
 
typedef std::vector <int> type;
 
void readlong (type &);
void mult (type &, type &, type &);
 
int main()
{
    type a, b, rez;
 
    std::cout << "First long number: ";
    readlong (a);
    std::cout << "Second long number: ";
    readlong (b);
 
    mult (a, b, rez);
 
    std::cout << rez.back ();
    for (int i = rez.size () - 2; i >= 0; i--)
        std::cout << rez[i];
 
    return 0;
}
 
void readlong (type &vec)
{
    std::string str;
    std::cin >> str;
 
    for (int i = str.size (); i > 0; i--)
        vec.push_back (atoi (str.substr (i - LEN, LEN).c_str()));
}
 
void mult (type &a, type &b, type &rez)
{
    rez.resize (a.size() + b.size());
    for (int i = 0; i < a.size(); ++i)
        for (int j = 0, carry = 0; j < b.size() || carry; ++j)
        {
            long long cur = rez[i+j] + a[i] * (j < b.size() ? b[j] : 0) + carry;
            rez[i+j] = cur % BASE;
            carry = cur / BASE;
        }
 
    while (rez.size() > 1 && rez.back() == 0)
        rez.pop_back();
}
Yandex
Объявления
30.04.2011, 23:21     Длинная арифметика. Умножение двух длинных чисел.
Ответ Создать тему
Опции темы

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