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
| #include <cstring>
#define BASE 10 //ñèñòåìà ñ÷èñëåíèÿ
#define MIN_LENGTH_FOR_KARATSUBA 4 //÷èñëà êîðî÷å óìíîæàþòñÿ êâàäðàòè÷íûì àëãîðèòìîì
typedef int digit; //âçÿò òîëüêî äëÿ ðàçðÿäîâ ÷èñëà
typedef unsigned long int size_length; //òèï äëÿ äëèííû ÷èñëà
using namespace std;
struct long_value { //òèï äëÿ äëèííûõ ÷èñåë
digit *values; //ìàññèâ ñ öèôðàìè ÷èñëà çàïèñàííûìè â îáðàòíîì ïîðÿäêå
size_length length; //äëèííà ÷èñëà
};
long_value sum(long_value a, long_value b) {
/* ôóíêöèÿ äëÿ ñóììèðîâàíèÿ äâóõ äëèííûõ ÷èñåë. Åñëè ñóììèðóþòñÿ ÷èñëà ðàçíîé äëèííû
* òî áîëåå äëèííîå ïåðåäåòñÿ â êà÷åñòâå ïåðâîãî àðãóìåíòà. Âîçâðàùàåò íîâîå
* íåíîðìàëèçîâàííîå ÷èñëî.
*/
long_value s;
s.length = a.length + 1;
s.values = new digit[s.length];
s.values[a.length - 1] = a.values[a.length - 1];
s.values[a.length] = 0;
for (size_length i = 0; i < b.length; ++i)
s.values[i] = a.values[i] + b.values[i];
return s;
}
long_value &sub(long_value &a, long_value b) {
/*ôóíêöèÿ äëÿ âû÷èòàíèÿ îäíîãî äëèííîãî ÷èñëà èç äðóãîãî. Èçìåíÿåò ñîäåðæèìîå ïåðâîãî
* ÷èñëà. Âîçâðàùàåò ññûëêó íà ïåðâîå ÷èñëî. Ðåçóëüòàò íå íîðìàëèçîâàí.
*/
for (size_length i = 0; i < b.length; ++i)
a.values[i] -= b.values[i];
return a;
}
void normalize(long_value l) {
/*Íîðìàëèçàöèÿ ÷èñëà - ïðèâåäåíèå êàæäîãî ðàçðÿäà â ñîîòâåòñòâèå ñ ñèñòåìîé ñ÷èñëåíèÿ.
*
*/
for (size_length i = 0; i < l.length - 1; ++i) {
if (l.values[i] >= BASE) { //åñëè ÷èñëî áîëüøå ìàêñèìàëüíîãî, òî îðãàíèçîâàâàåòñÿ ïåðåíîñ
digit carryover = l.values[i] / BASE;
l.values[i + 1] += carryover;
l.values[i] -= carryover * BASE;
} else if (l.values[i] < 0) { //åñëè ìåíüøå - çàåì
digit carryover = (l.values[i] + 1) / BASE - 1;
l.values[i + 1] += carryover;
l.values[i] -= carryover * BASE;
}
}
}
long_value karatsuba(long_value a, long_value b) {
long_value product; //ðåçóëüòèðóþùåå ïðîèçâåäåíèå
product.length = a.length + b.length;
product.values = new digit[product.length];
if (a.length < MIN_LENGTH_FOR_KARATSUBA) { //åñëè ÷èñëî êîðî÷å òî ïðèìåíÿòü íàèâíîå óìíîæåíèå
memset(product.values, 0, sizeof(digit) * product.length);
for (size_length i = 0; i < a.length; ++i)
for (size_length j = 0; j < b.length; ++j) {
product.values[i + j] += a.values[i] * b.values[j];
/* ñëó÷àå èçìåíåíèÿ MIN_LENGTH_FOR_KARATSUBA èëè BASE ðàññêîìåíòèðîâàòü ñëåäóþùèå
* ñòðîêè è ïîäîáðàòü ñîîòâ. çíà÷åíèÿ äëÿ èñêëþ÷åíèÿ ïåðåïîëíåíèÿ ðàçðÿäîâ.
* Íàïðèìåð äëÿ äåñÿòè÷íîé ñèñòåìû ñ÷èñëåíèÿ ÷èñëî 100, îçíà÷àåò, ÷òî îðãàíèçîâàâàåòñÿ
* ïåðåíîñ 1 ÷åðåç îäèí ðàçðÿä, 200 - ïåðåíîñ 2 ÷åðåç îäèí ðàçððÿä, 5000 - 5 ÷åðåç äâà.
* if (product.values[i + j] >= 100){
* product.values[i + j] -= 100;
* product.values[i + j + 2] += 1;
* }
*/
}
} else { //óìíîæåíèå ìåòîäîì Êàðàöóáû
long_value a_part1; //ìëàäøàÿ ÷àñòü ÷èñëà a
a_part1.values = a.values;
a_part1.length = (a.length + 1) / 2;
long_value a_part2; //ñòàðøàÿ ÷àñòü ÷èñëà a
a_part2.values = a.values + a_part1.length;
a_part2.length = a.length / 2;
long_value b_part1; //ìëàäøàÿ ÷àñòü ÷èñëà b
b_part1.values = b.values;
b_part1.length = (b.length + 1) / 2;
long_value b_part2; //ñòàðøàÿ ÷àñòü ÷èñëà b
b_part2.values = b.values + b_part1.length;
b_part2.length = b.length / 2;
long_value sum_of_a_parts = sum(a_part1, a_part2); //cóììà ÷àñòåé ÷èñëà a
normalize(sum_of_a_parts);
long_value sum_of_b_parts = sum(b_part1, b_part2); //cóììà ÷àñòåé ÷èñëà b
normalize(sum_of_b_parts);
long_value product_of_sums_of_parts = karatsuba(sum_of_a_parts, sum_of_b_parts);
// ïðîèçâåäåíèå ñóìì ÷àñòåé
long_value product_of_first_parts = karatsuba(a_part1, b_part1); //ìëàäøèé ÷ëåí
long_value product_of_second_parts = karatsuba(a_part2, b_part2); //ñòàðøèé ÷ëåí
long_value sum_of_middle_terms = sub(sub(product_of_sums_of_parts, product_of_first_parts), product_of_second_parts);
//íàõîæäåíèå ñóììû ñðåäíèõ ÷ëåíîâ
/*
* Ñóììèðîâàíèå ìíîãî÷ëåíà
*/
memcpy(product.values, product_of_first_parts.values,
product_of_first_parts.length * sizeof(digit));
memcpy(product.values + product_of_first_parts.length,
product_of_second_parts.values, product_of_second_parts.length
* sizeof(digit));
for (size_length i = 0; i < sum_of_middle_terms.length; ++i)
product.values[a_part1.length + i] += sum_of_middle_terms.values[i];
/*
* Çà÷èñòêà
*/
delete [] sum_of_a_parts.values;
delete [] sum_of_b_parts.values;
delete [] product_of_sums_of_parts.values;
delete [] product_of_first_parts.values;
delete [] product_of_second_parts.values;
}
normalize(product); //êîíå÷íàÿ íîðìàëèçàöèÿ ÷èñëà
return product;
} |
(
