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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 37, средняя оценка - 4.86
Vlad1993
7 / 3 / 1
Регистрация: 08.08.2012
Сообщений: 63
Завершенные тесты: 3
#1

Метод Карацубы умножения длинных чисел - C++

05.01.2013, 21:16. Просмотров 5123. Ответов 3
Метки нет (Все метки)

Реализован клас длинных чисел, с перегруженными операциями сложения, вычитания, умножения столбиком и реализован метод умножения Карацубы. Оба умножения дают правильный ответ,но метод Карацубы работает в десятки раз дольше даже на числах которые состоят из больше чем 100 цифр, хотя он должен работать быстрее. В чем ошибка?
Вот код:
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<iostream>
#include<string>
#include<vector>
#include<time.h>
 
using namespace std;
 
class Long{
    public:
        Long(string);
        Long();
        void GetLong();
        Long operator=(int);
        Long operator+(Long);
        Long operator-(Long);
        Long operator*(Long);
        friend int max(int,int);
        friend Long Karatsuba(Long,Long);
    private:
        vector<int> arr;
};
 
int max(int a,int b){
    return (a>b)?a:b;
}
 
Long::Long(){
}
 
Long::Long(string a){
    for(int i=0;i<a.size();i++)
        arr.push_back(a[a.size()-1-i]-'0');
}
 
void Long::GetLong(){
    for(int i=arr.size()-1;i>=0;i--)
        cout<<arr[i];
    cout<<endl;
}
 
Long Long::operator=(int a){
    do{
        (*this).arr.push_back(a%10);
        a=a/10;
    }while(a>0);
return (*this);
}
 
Long Long::operator+(Long a){
    Long result(*this);
    int temp=0;
    int k;
    for(int i=0;i<max(a.arr.size(),(*this).arr.size());i++){
        k=(i<result.arr.size()?result.arr[i]:0)+temp+(i<a.arr.size()?a.arr[i]:0);
        i<arr.size()?result.arr[i]=k%10:result.arr.push_back(k%10);
        temp=k/10;
    }
    if(k>=10)
        result.arr.push_back(temp);
return result;
}
 
Long Long::operator-(Long a){
    Long Temp(*this);
    int c=0;
    for(int i=0;i<(int)arr.size();++i){
            Temp.arr[i] -= c+(i<(int)a.arr.size() ? a.arr[i] : 0);
            c=(Temp.arr[i]<0);
            if(c)
                Temp.arr[i]+=10;
    }
    while (Temp.arr.size() > 1 && Temp.arr.back() == 0)
        Temp.arr.pop_back();
return Temp;
}
 
Long Long:: operator*(Long a){
    Long result;
    for(int i=0;i<arr.size()+a.arr.size();i++)
        result.arr.push_back(0);
    for (int i=0; i<arr.size(); ++i)
        for (int j=0, carry=0; j<(int)a.arr.size() || carry; ++j) {
            int cur = result.arr[i+j] + arr[i] *  (j < (int)a.arr.size() ? a.arr[j] : 0) + carry;
            result.arr[i+j] = int (cur % 10);
            carry = int (cur / 10);
        }
    while (result.arr.size() > 1 && result.arr.back() == 0)
        result.arr.pop_back();
return result;
}
 
Long Karatsuba(Long A,Long B){
    Long result;
    if(A.arr.size()<2 || B.arr.size()<2)
        return A*B;
    int i = (A.arr.size() + B.arr.size()) / 4;
    if (i >= A.arr.size())
        i = A.arr.size() / 2;
    if (i >= B.arr.size())
        i = B.arr.size() / 2;
    Long a; a.arr.insert(a.arr.begin(),A.arr.begin()+i,A.arr.end());
    Long b; b.arr.insert(b.arr.begin(),A.arr.begin(),A.arr.begin()+i);
    Long c; c.arr.insert(c.arr.begin(),B.arr.begin()+i,B.arr.end());
    Long d; d.arr.insert(d.arr.begin(),B.arr.begin(),B.arr.begin()+i);
    Long ac=Karatsuba(a,c);
    Long bd=Karatsuba(b,d);
    Long a_b=a+b;
    Long c_d=c+d;
    Long ab_cd=Karatsuba(a_b,c_d);
    Long ad_bc=ab_cd-(ac+bd);
    ad_bc.arr.insert(ad_bc.arr.begin(),i,0);
    ac.arr.insert(ac.arr.begin(),i+i,0);
return ac+bd+ad_bc;
}
 
int main(void){
    string s;
    cin>>s;
    Long a(s);
    cin>>s;
    Long b(s);
    double t1=(double)clock();
    Long c=Karatsuba(a,b);
    double t2=((double)clock()-t1)/CLOCKS_PER_SEC;
    cout<<t2<<endl;
    c.GetLong();
    double t3=(double)clock();
    Long d=a*b;
    double t4=((double)clock()-t3)/CLOCKS_PER_SEC;
    cout<<t4<<endl;
    d.GetLong();
    system("Pause");
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.01.2013, 21:16     Метод Карацубы умножения длинных чисел
Посмотрите здесь:

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

Вычислить сумму двух длинных бинарных чисел, используя сложение чисел в двоичной системе счисления - C++
Задано положительное и отрицательное число в двоичной системе.Составить программу вычисления суммы этих чисел, используя сложения чисел в...

Умножение длинных чисел - C++
не работает процедура умножения длинных чисел. переводил с паскаля по книге Окулова &quot;Программирование в алгоритмах&quot;. вроде все верно...

Разность длинных чисел - C++
Подскажите как реализовать разность длинных чисел Добавлено через 36 секунд Причем длинные числа задаются линейными списками

Сложение длинных чисел - C++
Здравствуйте, при решении задачи возникла ошибка при складывании элементов массивов. Получаются числа не являющиеся верным ответом к...

Умножение длинных чисел - C++
Доброго времени суток дорогие брограммисты. Сейчас занимаюсь с длинной арифметикой по книге, автор которой к сожалению предоставил...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
05.01.2013, 21:34     Метод Карацубы умножения длинных чисел #2
Даю 75%, что тормозит на этих инсёртах в вектор. Попробуйте заменить его на deque.
Vlad1993
7 / 3 / 1
Регистрация: 08.08.2012
Сообщений: 63
Завершенные тесты: 3
05.01.2013, 23:10  [ТС]     Метод Карацубы умножения длинных чисел #3
К сожалению, deque не помог, для чисел длиной около 1000 цифр умножение столбиком работает в 8 раз быстрее
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.01.2013, 00:20     Метод Карацубы умножения длинных чисел
Еще ссылки по теме:

Класс длинных чисел - C++
не выводит сумму number1 и number2, помогите, пожалуйста #include &lt;iostream&gt; #include &lt;istream&gt; #include &lt;vector&gt; #include...

Деление длинных чисел - C++
Код который делит очень длинное число на обычное число. Если вводить 121 и 2 выводит неправильный ответ. Какие условия надо поставить...

Умножение длинных чисел - C++
Найти произведение двух длинных чисел(целые числа, десятичная запись которых может содержать до 255 цифр). Нужно решить при помощи функций,...

Сравнение длинных чисел >, < - C++
Доброго времени суток всем. помогите пожалуйста прояснить алгоритм сравнения относительно длинных чисел (например 2 в 512 степени) ,...

Деление длинных чисел столбиком - C++
Привет. У меня возникла проблема при написании курсовой. Необходимо реализовать деление двух больших чисел(записанных &quot;зеркально&quot;). Хотя я...

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


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

Или воспользуйтесь поиском по форуму:
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
06.01.2013, 00:20     Метод Карацубы умножения длинных чисел #4
Попробуйте ещё уменьшить количество копирований. Передавайте аргументы в функцию по ссылке.

Плюс, метод Карацубы асимптотически быстрее умножения в столбик. Так что для маленьких чисел он будет медленнее умножения в столбик. А так как вы рекурсивно вызываете его для вычисления частичных произведений, то они рано или поздно доходят до маленьких. И тормозят. Плюс копирования, много копирований при рекурсии.

Обычно выбирают некоторую границу длины чисел, при пересечении которой умножение в столбик заменяется на метод Карацубы (а затем на БПФ). В тот же GMP переходит на метод Карацубы только для чисел длиннее 100-200 десятичных цифр.
Yandex
Объявления
06.01.2013, 00:20     Метод Карацубы умножения длинных чисел
Ответ Создать тему
Опции темы

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