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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 37, средняя оценка - 4.86
Vlad1993
7 / 3 / 1
Регистрация: 08.08.2012
Сообщений: 62
Завершенные тесты: 3
05.01.2013, 21:16     Метод Карацубы умножения длинных чисел #1
Реализован клас длинных чисел, с перегруженными операциями сложения, вычитания, умножения столбиком и реализован метод умножения Карацубы. Оба умножения дают правильный ответ,но метод Карацубы работает в десятки раз дольше даже на числах которые состоят из больше чем 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
05.01.2013, 21:34     Метод Карацубы умножения длинных чисел #2
Даю 75%, что тормозит на этих инсёртах в вектор. Попробуйте заменить его на deque.
Vlad1993
7 / 3 / 1
Регистрация: 08.08.2012
Сообщений: 62
Завершенные тесты: 3
05.01.2013, 23:10  [ТС]     Метод Карацубы умножения длинных чисел #3
К сожалению, deque не помог, для чисел длиной около 1000 цифр умножение столбиком работает в 8 раз быстрее
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
06.01.2013, 00:20     Метод Карацубы умножения длинных чисел #4
Попробуйте ещё уменьшить количество копирований. Передавайте аргументы в функцию по ссылке.

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

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

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