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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Удаление строки в массиве http://www.cyberforum.ru/cpp-beginners/thread753597.html
Не получается удалить строку в массиве int xy; //массив для хранения координат вершин на экране ... int q=0; // строка новой матрицы int s=0; // столбец новой матрицы int xynew; // сюда переписываем новый массив без удаленной вершины for(int i=0, q=0; i<kv; i++) { if (veryd==!i) // veryd номер строки которую надо удалить
C++ Аргумент типа int не совместим с параметрами типа int* помогите, ошибка в программе "аргумент типа int не совместим с параметрами типа int*" #include <stdio.h> #include <conio.h> #include <stdlib.h> #define k 5 int sum(int *a, int n) { if (n==1) return a; else return a+sum(a,n-1); http://www.cyberforum.ru/cpp-beginners/thread753587.html
C++ Написать программу, которая находит в массиве значения, повторяющиеся два и более раз, и показывает их на экран
Подскажите, пожалуйста, как вывести повторяющиеся два или более раз числа в массиве.
Менеджмент жесткого диска при многопоточности C++
Пусть у меня 4-ех ядерный процессор, и запущено 4 рабочих потока (в одном процессе). Казалось бы, что все хорошо, но диск-то у меня один! Есть какие- нибудь паттерны программирования многопоточных приложений, пытающихся "развести" потоки так, чтобы они одновременно не работали с жестким диском (или другими комплектующими)? Например, одинаковые потоки можно запускать со сдвигом по времени...
C++ Вывести минимальное нечетное число. Что не так? http://www.cyberforum.ru/cpp-beginners/thread753575.html
Сейчас программа выводит любое минимальное число, будь-то четное или нечетное. Подскажите, пожалуйста, что исправить? const int size=10; int ar={8,36,69,45,13,12,49,5,67,26}; int min=ar; for (int i=0; i<size; i++) {
C++ Чтение с файла Вот у меня есть код , но при попытке считать из него числа почему выдает не то что нужно , в чем может быть ошибка ? #include <iostream> #include <fstream> using namespace std ; void main () { подробнее

Показать сообщение отдельно
Vlad1993
7 / 3 / 1
Регистрация: 08.08.2012
Сообщений: 62
Завершенные тесты: 3
05.01.2013, 21:16     Метод Карацубы умножения длинных чисел
Реализован клас длинных чисел, с перегруженными операциями сложения, вычитания, умножения столбиком и реализован метод умножения Карацубы. Оба умножения дают правильный ответ,но метод Карацубы работает в десятки раз дольше даже на числах которые состоят из больше чем 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 22:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru