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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 154, средняя оценка - 4.95
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
#1

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

29.04.2011, 13:44. Просмотров 21136. Ответов 55
Метки нет (Все метки)

Есть 2 числа, храняющиеся в int векторах, нужна функция, которая возвращает их произведение также в виде вектора.
Либо простой и понятно описанный алгоритм, по которому можно такое сделать.
Заранее спасибо.
P.S. в гугл отправлять не надо-разбираться со сложными алгоритмами вроде БПФ у меня нет ни времени, ни желания.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.04.2011, 13:44
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Длинная арифметика. Умножение двух длинных чисел. (C++):

Длинная арифметика: умножение двух длинных чисел - C++
Всем привет! Снова к Вам за помощью. Алгоритм умножения двух длинных чисел: void...

Длинная арифметика(вычитание длинных целых чисел) - C++
Добрый вечер! Очень нужна помощь. Мне нужно написать программы для сложения больших целых чисел(разрядности около 200), вычитания и что-то...

Реализовать оператор сравнения в классе длинных чисел (длинная арифметика) - C++
Здравствуйте, дорогие форумчане. Недавно назрел вопрос, как бы сделать сравнение чисел длинной арифметики в дальнейшем коде? Сравнение...

Умножение двух длинных чисел - C++
Приветствую, помогите исправить процедуру умножения двух длинных чисел: void CALL_TYPE Multiply(unsigned char *u,int N, unsigned char...

Длинная арифметика. Перемножение двух больших чисел - C++
Насчет алгоритма выполнения не могу пока что сказать ничего. Дело в том, что после того, как ввожу первое число и нажимаю Enter, каретка...

Длинная арифметика. Перемножение двух больших чисел. Пропуск итераций - C++
Программа работает корректно с числами, оканчивающимися не на нуль. Пробовал выводить слово "iter" в каждом проходе цикла, но при работе с...

55
neske
1504 / 871 / 84
Регистрация: 26.03.2010
Сообщений: 2,985
29.04.2011, 13:48 #2
гугл, гугл.. по вашему это сложные алгоритмы? http://e-maxx.ru/algo/big_integer
1
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 13:52  [ТС] #3
Видел это, так и не смог заставить работать этот код. Пробовал также и без класса, base сделал равным 10-0 эффекта.
0
neske
1504 / 871 / 84
Регистрация: 26.03.2010
Сообщений: 2,985
29.04.2011, 13:59 #4
Это я когда-то писал, может вам поможет. Работа с вектором, но тут длинное на короткое умножается. Под свое задание заточите сами.

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
/*Входной файл INPUT.TXT в первой строке содержит числа A и B, разделенные пробелом. (1 <= A <= 9, 1 <= B <= 104)
В выходной файл OUTPUT.TXT выведите одно число – результат возведения в степень, без лидирующих нулей.*/
 
#include <iostream>
#include <vector>
#include <iomanip>
#define BASE 1000000000
#define LEN 9
 
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;
    }
}
1
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 14:03  [ТС] #5
Длинное на короткое я тоже писал, правда без векторов.
Банально умножил каждую цифру массива на b, затем прошелся циклом с конца и собрал остатки.
А вот как длинное на длинное-не представляю.
0
neske
1504 / 871 / 84
Регистрация: 26.03.2010
Сообщений: 2,985
29.04.2011, 14:05 #6
Возьмите мой код за основу, а алгоритм умножения с вышеупомянутого сайта.
0
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 14:13  [ТС] #7
Я предпочитаю разбираться в алгоритмах с помощью дебаггера, так более нагляднее=)
А в вышеупомянутом сайте меня смущает миллиардная система счисления а также вот этот код
C++
1
1ll
0
silent_1991
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
29.04.2011, 18:08 #8
В чём сложность реализовать умножение столбиком? Школьный алгоритм, реализуется без каких-либо изменений.
0
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 18:15  [ТС] #9
Ну на бумажке-то просто, но программно, во-первых придется реализовывать еще и сравнение этих чисел, чтобы большее было вверху, а также суммы n слагаемых, где n-количество цифр в наименьшем числе.
Настолько не оптимальный алгоритм мне тоже не нужен, по идее программно это делается проще.
0
silent_1991
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
29.04.2011, 18:25 #10
Цитата Сообщение от vpupkin Посмотреть сообщение
по идее программно это делается проще
Зря вы так думаете.Столбиком - самый простой способ. Дальше идут Карацуба и Фурье.
0
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 18:37  [ТС] #11
Ну даже я понимаю, что сравнение и длинную сумму делать необязательно, можно это как-то оптимизировать... Поэтому прошу выложить исходник данной функции, можно без векторов.
Наверняка завалялся у кого-нибудь... Заранее спасибо.
0
eXXXXXXXXXXX
30 / 30 / 3
Регистрация: 24.02.2011
Сообщений: 126
29.04.2011, 18:52 #12
А есть ограничения на длину перемножаемых чисел? А то можно результат хранить в 64-битном массиве, намного быстрее будет.
0
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 18:54  [ТС] #13
Есть, результат не более 6000 символов=)
А хранить по несколько цифр в 1 элементе массива дело, конечно, оптимизирующее, но обращаться к ним неудобно будет...
0
silent_1991
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
29.04.2011, 19:32 #14
vpupkin, вас не поймёшь. Сначала вы просите простой и понятный алгоритм - вам советуют столбиком, вы говорите "ненене, слишком медленно". Вам говорят, что быстрее - сложнее, вы говорите "даже я понимаю, что можно оптимизировать". Понимаете - оптимизируйте. Ладно, вам говорят, что можно хранить число не поцыферно, а блоками, вы "ненене, сложно обращаться". Уважаемый, закон природы - за то, чтобы сделать одну вещь проще, нужно платить усложнением другой вещи.
1
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 20:52  [ТС] #15
Есть код на паскале
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;
}
0
30.04.2011, 20:52
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.04.2011, 20:52
Привет! Вот еще темы с ответами:

длинная арифметика. Умножение большого числа на малое - C++
Столкнулся с небольшой проблемой: при умножении большого числа (примерно 9 знаков) на небольшое выводит непонятно что, но с малыми числами...

Длинная арифметика: сумма двух строк - C++
int One = strlen(BufOne); int Two = strlen(BufTwo); int MaxL = max(One, Two); char *Result = (char*)malloc(MaxL); int a; double...

Арифметика длинных чисел с плавающей запятой - C++
Добрый вечер, есть ли у кого исходники основных операций * / + - больших чисел с плавающей запятой? Например дано: char * a =...

Длинная арифметика, деление чисел - C++
http://www.cyberforum.ru/attachment.php?attachmentid=393890&amp;stc=1&amp;d=1398936287 Помоги с решием , желательно код.Заранее спасибО!


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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