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

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

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

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

29.04.2011, 13:44. Просмотров 22230. Ответов 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
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
30.04.2011, 21:09 #16
G++
comparision between signed and unsigned integer expression
C++
1
2
3
 for (int i = 0; i < vec.size () || carry; i++)
    {
        if (i == vec.size ()) vec.push_back (0);
0
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 21:13  [ТС] #17
Цитата Сообщение от kiborg_18 Посмотреть сообщение
G++
comparision between signed and unsigned integer expression
C++
1
2
3
 for (int i = 0; i < vec.size () || carry; i++)
    {
        if (i == vec.size ()) vec.push_back (0);
???
С реализацией в виде векторов я потом разбираться буду, сейчас хотя бы на массивах написать хочу, их отлаживать проще. Перевел с паскаля - не работает...
0
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
30.04.2011, 21:19 #18
neske, В вашем коде компиллятор даёт ошибку на
C++
1
2
3
for (int i = 0; i < vec.size () || carry; i++)
    {
        if (i == vec.size ()) vec.push_back (0);
comparision between signed and unsigned integer expression
Что делать? не компиллируется g++
0
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 21:21  [ТС] #19
Суровый у вас компилятор однако... Предупреждение за ошибку считает
C++
1
2
3
for (unsigned int i = 0; i < vec.size () || carry; i++)
    {
        if (i == vec.size ()) vec.push_back (0);
Так должен скомпилировать
0
silent_1991
30.04.2011, 21:25
  #20

Не по теме:

vpupkin, может там педантик врублен...

1
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;
}
И все-таки, может кто-нибудь помочь? Очень нужно. Заранее спасибо.
0
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
30.04.2011, 21:34 #22
Фигня какая-то ввёл 5 5, он мне 3125 выдаёт...
0
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 21:35  [ТС] #23
Ты бы почитал комментарии вверху кода программы для начала, она возводит число a в степень b.
5 в 5й степени равно 3125.
1
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
30.04.2011, 21:42 #24
тогда почему на 100 в 10 выдаётся фигня какая-то со всеми числами котррые есть на земле?
0
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 21:51  [ТС] #25
Ну число там немаленькое получается, но в проге видимо баг...
0
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
30.04.2011, 21:53 #26
2 в 64 верно вычислил, а вот 100 в 10... да это ладно 10 в 100 ваще фигня, три строчки командной строки тирешками и всем числовым полем забиты)))
0
neske
1520 / 887 / 89
Регистрация: 26.03.2010
Сообщений: 3,050
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;
    }
}

Не по теме:

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

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

длинная арифметика. Умножение большого числа на малое - 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 Помоги с решием , желательно код.Заранее спасибО!


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

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

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