-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathSource.cpp
143 lines (121 loc) · 24.8 KB
/
Source.cpp
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
135
136
137
138
139
140
141
142
143
#include <iostream>
#include <fstream>
#include <string>
#include "Long.h"
#include "Real.h"
#include <ctime>
#include <thread>
#include <future>
using namespace std;
int main() {
//Long c = "70325678965131513541321351327849311521002888629258367278493115210028886292583672784931152100288862925836713513513521610144576234925983745823915672784931152100288862925836738088862944654562135131351351352161014457625615251321351315513541321351313513513521610144576234925983745823915678088865135413213514465456561513213513151354121789651315135413213513135135135216101445762349259837458239156735131351351352161014457622151354132135131351351352161014457623492598374582391567808886294465456213535131351351352161311313513513521610144576234925983745856181219651623915678088865135413213513135135135216101445762349259837458239156780888629446545621352944654562135151354132135131351351352161014457623492598374582391567808886294465456213535413213513135135135216132138513213583135158468347452834652863474528346528634528364582362458528364582365656151321351315135459837458239172359178235162365824367583465283465836283674528367452836745283465286345283645823624582346258367529483834652836458516244616132458846845241607032567896513151354132135132784931152100288862925836727849311521002888629258367278493115210028886292583671351351352161014457623492598374582391567278493115210028886292583673808886294465456213513135135135216101445762561525132135131551354132135131351351352161014457623492598374582391567808886513541321351446545656151321351315135412178965131513541321351313513513521610144576234925983745823915673513135135135216101445762215135413213513135135135216101445762349259837458239156780888629446545621353513135135135216131131351351352161014457623492598374585618121965162391567808886513541321351313513513521610144576234925983745823915678088862944654562135294465456213515135413213513135135135216101445762349259837458239156780888629446545621353541321351313513513521613213851321358313515846834745283465286347452834652863452836458236245852836458236565615132135131513545983745823917235917823516236582436758346528346583628367452836745283674528346528634528364582362458234625836752948383465283645851624461613245870325678965131513541321351327849311521002888629258367278493115210028886292583672784931152100288862925836713513513521610144576234925983745823915672784931152100288862925836738088862944654562135131351351352161014457625615251321351315513541321351313513513521610144576234925983745823915678088865135413213514465456561513213513151354121789651315135413213513135135135216101445762349259837458239156735131351351352161014457622151354132135131351351352161014457623492598374582391567808886294465456213535131351351352161311313513513521610144576234925983745856181219651623915678088865135413213513135135135216101445762349259837458239156780888629446545621352944654562135151354132135131351351352161014457623492598374582391567808886294465456213535413213513135135135216132138513213583135158468347452834652863474528346528634528364582362458528364582365656151321351315135459837458239172359178235162365824367583465283465836283674528367452836745283465286345283645823624582346258367529483834652836458516244616132458846845241607032567896513151354132135132784931152100288862925836727849311521002888629258367278493115210028886292583671351351352161014457623492598374582391567278493115210028886292583673808886294465456213513135135135216101445762561525132135131551354132135131351351352161014457623492598374582391567808886513541321351446545656151321351315135412178965131513541321351313513513521610144576234925983745823915673513135135135216101445762215135413213513135135135216101445762349259837458239156780888629446545621353513135135135216131131351351352161014457623492598374585618121965162391567808886513541321351313513513521610144576234925983745823915678088862944654562135294465456213515135413213513135135135216101445762349259837458239156780888629446545621353541321351313513513521613213851321358313515846834745283465286347452834652863452836458236245852836458236565615132135131513545983745823917235917823516236582436758346528346583628367452836745283674528346528634528364582362458234625836752948383465283645851624461613245870325678965131513541321351327849311521002888629258367278493115210028886292583672784931152100288862925836713513513521610144576234925983745823915672784931152100288862925836738088862944654562135131351351352161014457625615251321351315513541321351313513513521610144576234925983745823915678088865135413213514465456561513213513151354121789651315135413213513135135135216101445762349259837458239156735131351351352161014457622151354132135131351351352161014457623492598374582391567808886294465456213535131351351352161311313513513521610144576234925983745856181219651623915678088865135413213513135135135216101445762349259837458239156780888629446545621352944654562135151354132135131351351352161014457623492598374582391567808886294465456213535413213513135135135216132138513213583135158468347452834652863474528346528634528364582362458528364582365656151321351315135459837458239172359178235162365824367583465283465836283674528367452836745283465286345283645823624582346258367529483834652836458516244616132458846845241607032567896513151354132135132784931152100288862925836727849311521002888629258367278493115210028886292583671351351352161014457623492598374582391567278493115210028886292583673808886294465456213513135135135216101445762561525132135131551354132135131351351352161014457623492598374582391567808886513541321351446545656151321351315135412178965131513541321351313513513521610144576234925983745823915673513135135135216101445762215135413213513135135135216101445762349259837458239156780888629446545621353513135135135216131131351351352161014457623492598374585618121965162391567808886513541321351313513513521610144576234925983745823915678088862944654562135294465456213515135413213513135135135216101445762349259837458239156780888629446545621353541321351313513513521613213851321358313515846834745283465286347452834652863452836458236245852836458236565615132135131513545983745823917235917823516236582436758346528346583628367452836745283674528346528634528364582362458234625836752948383465283645851624461613245870325678965131513541321351327849311521002888629258367278493115210028886292583672784931152100288862925836713513513521610144576234925983745823915672784931152100288862925836738088862944654562135131351351352161014457625615251321351315513541321351313513513521610144576234925983745823915678088865135413213514465456561513213513151354121789651315135413213513135135135216101445762349259837458239156735131351351352161014457622151354132135131351351352161014457623492598374582391567808886294465456213535131351351352161311313513513521610144576234925983745856181219651623915678088865135413213513135135135216101445762349259837458239156780888629446545621352944654562135151354132135131351351352161014457623492598374582391567808886294465456213535413213513135135135216132138513213583135158468347452834652863474528346528634528364582362458528364582365656151321351315135459837458239172359178235162365824367583465283465836283674528367452836745283465286345283645823624582346258367529483834652836458516244616132458846845241607032567896513151354132135132784931152100288862925836727849311521002888629258367278493115210028886292583671351351352161014457623492598374582391567278493115210028886292583673808886294465456213513135135135216101445762561525132135131551354132135131351351352161014457623492598374582391567808886513541321351446545656151321351315135412178965131513541321351313513513521610144576234925983745823915673513135135135216101445762215135413213513135135135216101445762349259837458239156780888629446545621353513135135135216131131351351352161014457623492598374585618121965162391567808886513541321351313513513521610144576234925983745823915678088862944654562135294465456213515135413213513135135135216101445762349259837458239156780888629446545621353541321351313513513521613213851321358313515846834745283465286347452834652863452836458236245852836458236565615132135131513545983745823917235917823516236582436758346528346583628367452836745283674528346528634528364582362458234625836752948383465283645851624461613245870325678965131513541321351327849311521002888629258367278493115210028886292583672784931152100288862925836713513513521610144576234925983745823915672784931152100288862925836738088862944654562135131351351352161014457625615251321351315513541321351313513513521610144576234925983745823915678088865135413213514465456561513213513151354121789651315135413213513135135135216101445762349259837458239652863452836458236245852836458236565615132135131513545983745823917235917823516236582436758346528346583628367452836735135135216132138513213583135158468347452834652863474528346528634528364582362458528364582365656151321351315135459837458239172359178235162365824367583465283465836283674528367452836745283465286345283645823624582346258367529483834652836458516244616132458703256789651315135413213513278493115210028886292583672784931152100288862925836727849311521002888629258367135135135216101445762349259837458239156727849311521002888629258367380888629446545621351313513513521610144576256152513213513155135413213513135135135216101445762349259837458239156780888651354132135144654565615132135131513541217896513151354132135131351351352161014457623492598374582391567351313513513521610144576221513541321351313513513521610144576234925983745823915678088862944654562135351313513513521613113135135135216101445762349259837458561812196516239156780888651354132135131351351352161014457623492598374582391567808886294465456213529446545621351513541321351313513513521610144576234925983745823915678088862944654562135354132135131351351352161321385132135831351584683474528346528634745283465286345283645823624585283645823656561513213513151354598374582391723591782351623658243675834652834658362836745283674528367452834652863452836458236245823462583675294838346528364585162446161324588468452416070325678965131513541321351327849311521002888629258367278493115210028886292583672784931152100288862925836713513513521610144576234925983745823915672784931152100288862925836738088862944654562135131351351352161014457625615251321351315513541321351313513513521610144576234925983745823915678088865135413213514465456561513213513151354121789651315135413213513135135135216101445762349259837458239156735131351351352161014457622151354132135131351351352161014457623492598374582391567808886294465456213535131351351352161311313513513521610144576234925983745856181219651623915678088865135413213513135135135216101445762349259837458239156780888629446545621352944654562135151354132135131351351352161014457623492598374582391567808886294465456213535413213513135135135216132138513213583135158468347452834652863474528346528634528364582362458528364582365656151321351315135459837458239172359178235162365824367583465283465836283674528367452836745283465286345283645823624582346258367529483834652836458516244616132458703256789651315135413213513278493115210028886292583672784931152100288862925836727849311521002888629258367135135135216101445762349259837458239156727849311521002888629258367380888629446545621351313513513521610144576256152513213513155135413213513135135135216101445762349259837458239156780888651354132135144654565615132135131513541217896513151354132135131351351352161014457623492598374582391567351313513513521610144576221513541321351313513513521610144576234925983745823915678088862944654562135351313513513521613113135135135216101445762349259837458561812196516239156780888651354132135131351351352161014457623492598374582391567808886294465456213529446545621351513541321351313513513521610144576234925983745823915678088862944654562135354132135131351351352161321385132135831351584683474528346528634745283465286345283645823624585283645823656561513213513151354598374582391723591782351623658243675834652834658362836745283674528367452834652863452836458236245823462583675294838346528364585162446161324588468452416070325678965131513541321351327849311521002888629258367278493115210028886292583672784931152100288862925836713513513521610144576234925983745823915672784931152100288862925836738088862944654562135131351351352161014457625615251321351315513541321351313513513521610144576234925983745823915678088865135413213514465456561513213513151354121789651315135413213513135135135216101445762349259837458239156735131351351352161014457622151354132135131351351352161014457623492598374582391567808886294465456213535131351351352161311313513513521610144576234925983745856181219651623915678088865135413213513135135135216101445762349259837458239156780888629446545621352944654562135151354132135131351351352161014457623492598374582391567808886294465456213535413213513135135135216132138513213583135158468347452834652863474528346528634528364582362458528364582365656151321351315135459837458239172359178235162365824367583465283465836283674528367452836745283465286345283645823624582346258367529483834652836458516244616132458656515365165165165132248468452416";
//Long a = "2784931152100288151354132135132784931152100288862925836727849311521002888629258367278493115210028886292583671351351352161014457623492598374582391567278493115210028886292583673808886294465456213513135135135216101445762561525132135131551354132135131351351352161014457623492598374582391567808886513541321351446545656151321351315135412178965131513541321351313513513521610144576234925983745823915673513135135135216101445762215135413213513135135135216101445762349259837458239156780888629446545621353513135135135216131131351351352161014457623492598374585618121965162391567808886513541321351313513513521610144576234925983745823915678088862944654562135294465456213515135413213513135135135216101445762349259837458239156780888629446545621353541321351313513513521613213851321358313515846834745283465286347452834652863452836458236245852836458236565615132135131513545983745823917235917823516236582436758346528346583628367452836745283674528346528634528364582362458234625836752948383465283645851624461613245884684524160703256789651315135413213513278493115210028886292583672784931152100288862925836727849311521002888629258367135135135216101445762349259837458239156727849311521002888629258367380888629446545621351313513513521610144576256152513213513155135413213513135135135216101445762349259837458239156780888651354132135144654565615132135131513541217896513151354132135131351351352161014457623492598374582391567351313513513521610144576221513541321351313513513521610144576234925983745823915678088862944654562135351313513513521613113135135135216101445762349259837458561812196516239156780888651354132135131351351352161014457623492598374582391567808886294465456213529446545621351513541321351313513513521610144576234925983745823915678088862944654562135354132135131351351352161321385132135831351584683474528346528634745283465286345283645823624585283645823656561513213513151354598374582391723591782351623658243675834652834658362836745283674528367452834652863452836458236245823462583675294838346528364585162446161324587032567896513151354132135132784931152100288862925836727849311521002888629258367278493115210028886292583671351351352161014457623492598374582391567278493115210028886292583673808886294465456213513135135135216101445762561525132135131551354132135131351351352161014457623492598374582391567808886513541321351446545656151321351315135412178965131513541321351313513513521610144576234925983745823915673513135135135216101445762215135413213513135135135216101445762349259837458239156780888629446545621353513135135135216131131351351352161014457623492598374585618121965162391567808886513541321351313513513521610144576234925983745823915678088862944654562135294465456213515135413213513135135135216101445762349259837458239156780888629446545621353541321351313513513521613213851321358313515846834745283465286347452834652863452836458236245852836458236565615132135131513545983745823917235917823516236582436758346528346583628367452836745283674528346528634528364582362458234625836752948383465283645851624461613245884684524160703256789651315135413213513278493115210028886292583672784931152100288862925836727849311521002888629258367135135135216101445762349259837458239156727849311521002888629258367380888629446545621351313513513521610144576256152513213513155135413213513135135135216101445762349259837458239156780888651354132135144654565615132135131513541217896513151354132135131351351352161014457623492598374582391567351313513513521610144576221513541321351313513513521610144576234925983745823915678088862944654562135351313513513521613113135135135216101445762349259837458561812196516239156780888651354132135131351351352161014457623492598374582391567808886294465456213529446545621351513541321351313513513521610144576234925983745823915678088862944654562135354132135131351351352161321385132135831351584683474528346528634745283465286345283645823624585283645823656561513213513151354598374582391723591782351623658243675834652834658362836745283674528367452834652863452836458236245823462583675294838346528364585162446161324587032567896513151354132135132784931152100288862925836727849311521002888629258367278493115210028886292583671351351352161014457623492598374582391567278493115210028886292583673808886294465456213513135135135216101445762561525132135131551354132135131351351352161014457623492598374582391567808886513541321351446545656151321351315135412178965131513541321351313513513521610144576234925983745823915673513135135135216101445762215135413213513135135135216101445762349259837458239156780888629446545621353513135135135216131131351351352161014457623492598374585618121965162391567808886513541321351313513513521610144576234925983745823915678088862944654562135294465456213515135413213513135135135216101445762349259837458239156780888629446545621353541321351313513513521613213851321358313515846834745283465286347452834652863452836458236245852836458236565615132135131513545983745823917235917823516236582436758346528346583628367452836745283674528346528634528364582362458234625836752948383465283645851624461613245884684524160703256789651315135413213513278493115210028886292583672784931152100288862925836727849311521002888629258367135135135216101445762349259837458239156727849311521002888629258367380888629446545621351313513513521610144576256152513213513155135413213513135135135216101445762349259837458239156780888651354132135144654565615132135131513541217896513151354132135131351351352161014457623492598374582391567351313513513521610144576221513541321351313513513521610144576234925983745823915678088862944654562135351313513513521613113135135135216101445762349259837458561812196516239156780888651354132135131351351352161014457623492598374582391567808886294465456213529446545621351513541321351313513513521610144576234925983745823915678088862944654562135354132135131351351352161321385132135831351584683474528346528634745283465286345283645823624585283645823656561513213513151354598374582391723591782351623658243675834652834658362836745283674528367452834652863452836458236245823462583675294838346528364585162446161324587032567896513151354132135132784931152100288862925836727849311521002888629258367278493115210028886292583671351351352161014457623492598374582391567278493115210028886292583673808886294465456213513135135135216101445762561525132135131551354132135131351351352161014457623492598374582391567808886513541321351446545656151321351315135412178965131513541321351313513513521610144576234925983745823915673513135135135216101445762215135413213513135135135216101445762349259837458239156780888629446545621353513135135135216131131351351352161014457623492598374585618121965162391567808886513541321351313513513521610144576234925983745823915678088862944654562135294465456213515135413213513135135135216101445762349259837458239156780888629446545621353541321351313513513521613213851321358313515846834745283465286347452834652863452836458236245852836458236565615132135131513545983745823917235917823516236582436758346528346583628367452836745283674528346528634528364582362458234625836752948383465283645851624461613245884684524160703256789651315135413213513278493115210028886292583672784931152100288862925836727849311521002888629258367135135135216101445762349259837458239156727849311521002888629258367380888629446545621351313513513521610144576256152513213513155135413213513135135135216101445762349259837458239156780888651354132135144654565615132135131513541217896513151354132135131351351352161014457623492598374582391567351313513513521610144576221513541321351313513513521610144576234925983745823915678088862944654562135351313513513521613113135135135216101445762349259837458561812196516239156780888651354132135131351351352161014457623492598374582391567808886294465456213529446545621351513541321351313513513521610144576234925983745823915678088862944654562135354132135131351351352161321385132135831351584683474528346528634745283465286345283645823624585283645823656561513213513151354598374582391723591782351623658243675834652834658362836745283674528367452834652863452836458236245823462583675294838346528364585162446161324587032567896513151354132135132784931152100288862925836727849311521002888629258367278493115210028886292583671351351352161014457623492598374582391567278493";
Long c = "222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222";
Long a = "1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111";
Long b = "555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555";
Long prime2 = 12247;
auto t = clock();
// cout << (a + b) * (a + b) - a*a + b*b << endl;
cout << prtest_SolovStras(prime2, 26) << endl;
cout << prtest_Lehmann(prime2, 26) << endl;
cout << prtest_RabinMiller(prime2, 26) << endl;
/*
cout << c.karac_mul(a) - c.strassen_mul(a) << endl;
cout << c.strassen_mul(a) - c.toomcook_mul(a) << endl;
cout << c.strassen_mul(a) - c.mul(a) << endl;
*/
/*
Long prime = 41;
cout << "Checking if " << prime << " is prime: 50*4 iterations:" << endl;
auto t = clock();
cout << prtest_SolovStras(prime, 26) << endl;
cout << (clock() - t) / 26<< endl;
t = clock();
cout << prtest_Lehmann(prime, 26) << endl;
cout << (clock() -t ) / 26 << endl;
t = clock();
cout << prtest_RabinMiller(prime, 26) << endl;
cout << (clock() - t) / 26 << endl;
system("pause");
Long prime2 = 331;
cout << "Checking if " << prime2 << " is prime: 50*4 iterations:" << endl;
t = clock();
//cout << prtest_SolovStras(prime2, 26) << endl;
cout << (clock() - t) / 26 << endl;
t = clock();
cout << prtest_Lehmann(prime2, 26) << endl;
cout << (clock() - t) / 26 << endl;
t = clock();
cout << prtest_RabinMiller(prime2, 26) << endl;
cout << (clock() - t) / 26 << endl;
system("pause");
cout << "Checking if multiplications right? 0 -- for yes" << endl;
t = clock();
cout << (c.mul(a) - c.karac_mul(a)) + (c.toomcook_mul(a) - c.strassen_mul(a)) << endl;
cout << (t - clock()) << endl;
system("pause");
cout << "Time of each met for " << c << " * " << a << endl;
t = clock();
for (int i = 0; i < 50; ++i) {
c.mul(a);
}
cout << (clock() - t) / 50 << endl;
t = clock();
for (int i = 0; i < 50; ++i) {
c.karac_mul(a);
} cout << (clock() - t) / 50 << endl;
t = clock();
for (int i = 0; i < 50; ++i) {
c.toomcook_mul(a);
}cout << (clock() - t) / 50 << endl;
t = clock();
for (int i = 0; i < 50; ++i) {
c.strassen_mul(a);
}cout << (clock() - t) / 50 << endl;
t = clock();
system("pause");
cout << "Time of each met for " << c << " * " << b << endl;
t = clock();
for (int i = 0; i < 50; ++i) {
c.mul(b);
}cout << (clock() - t) / 50 << endl;
t = clock();
t = clock();
for (int i = 0; i < 50; ++i) {
c.karac_mul(b);
}cout << (clock() - t) / 50 << endl;
t = clock();
for (int i = 0; i < 50; ++i) {
c.toomcook_mul(b);
}cout << (clock() - t) / 50 << endl;
t = clock();
for (int i = 0; i < 50; ++i) {
c.strassen_mul(b);
}cout << (clock() - t) / 50 << endl;
t = clock();
system("pause");
cout << c.mul(a) << endl;
cout << c.toomcook_mul(a) << endl;
cout << "2222222222222222222222222222222222222222222222222222222222222222222222222222222222222 * 1111111111111111111111111111111111" << endl;
cout << Long("2222222222222222222222222222222222222222222222222222222222222222222222222222222222222").mul( Long("2222222222222222222222222222222222222222222222222222222222222222222222222222222222222")) << endl;
cout << Long("2222222222222222222222222222222222222222222222222222222222222222222222222222222222222").toomcook_mul(Long("2222222222222222222222222222222222222222222222222222222222222222222222222222222222222")) << endl;
system("pause");
cout << c.karac_mul(a) - c.strassen_mul(a)<< endl;
cout << c.strassen_mul(a) - c.toomcook_mul(a) << endl;
cout << c.strassen_mul(a) - c.mul(a) << endl;
system("pause");
t = clock();
cout << "c div binary a = " << c / a << endl;
cout << clock() - t << endl;
Long r = null;
t = clock();
cout << "c div not fbinary a = " << c.divide2(a, r) << endl;
cout << clock() - t << endl;
t = clock();
cout << "c * inverse(Long(a)) = " << c.mult_inv(a) << endl;
cout << clock() - t << endl;
*/
int l = 0;
cin >> l;
return 0;
}