What is your best way to do timing of a program?
How to minimize Windows perturbations?
void vitesse(unsigned long long cand) {
unsigned long long fact;
auto start = high_resolution_clock::now();
for (int i = 0; i < rept; i++) {
fact = IsSFactNonDiv(cand);
}
auto stop = high_resolution_clock::now();
auto duration2 = duration_cast<microseconds>(stop - start);
start = high_resolution_clock::now();
for (int i = 0; i < rept; i++) {
fact = IsSFactDiv(cand);
}
stop = high_resolution_clock::now();
auto duration1 = duration_cast<microseconds>(stop - start);
cout << cand << "\t" << fact << "\t" << duration1.count() / 1000.0 << " ms" << "\t"
<< duration2.count() / 1000.0 << " ms" << endl;
}
What I have tried:
#include <iostream>
#include <chrono>
#include <math.h>
using namespace std;
using namespace std::chrono;
#define rept 1000000
long long primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 0 };
inline long long FactModulo(long long cand, long long fact) {
while (cand >= fact) {
if (cand & 1) {
cand = cand - fact;
}
cand = cand >> 1;
}
return cand;
}
inline long long FactFold(long long cand, long long shift, long long Mask) {
do {
cand = (cand >> shift) + (cand & Mask);
} while (cand >> shift);
return cand;
}
long long IsSFactNonDiv(long long Cand) {
long long Mask, Prime, tmp;
int Size;
if ((Cand & 1) == 0) {
return 2;
}
Size = 32;
Mask = (0ULL - 1) >> (64 - Size);
long long N32 = (Cand >> Size) + (Cand & Mask);
Size = 16;
Mask = (0ULL - 1) >> (64 - Size);
long long N16 = (N32 >> Size) + (N32 & Mask);
Prime = 17;
Size = 8;
Mask = (0ULL - 1) >> (64 - Size);
long long N8 = FactFold(N16, Size, Mask);
Size = 4;
Mask = (0ULL - 1) >> (64 - Size);
if ((N8 >> Size) == (N8 & Mask)) {
return Prime;
}
Prime = 5;
Size = 4;
Mask = (0ULL - 1) >> (64 - Size);
long long N4 = FactFold(N8, Size, Mask);
Size = 2;
Mask = (0ULL - 1) >> (64 - Size);
if ((N4 >> Size) == (N4 & Mask)) {
return Prime;
}
Prime = 3;
Size = 2;
Mask = (0ULL - 1) >> (64 - Size);
long long N2 = FactFold(N4, Size, Mask);
if (N2 == Prime) {
return Prime;
}
return Cand;
}
long long IsSFactDiv(long long cand) {
if ((cand & 1) == 0) {
return 2;
}
for (int p = 1; primes[p] != 0; p++) {
if (primes[p] * primes[p] > cand) {
break;
}
if (cand % primes[p] == 0) {
return primes[p];
}
}
return cand;
}
long long TD_SRW(long long Cand) {
long long SPrimes[] = { 2, 3, 5, 0 };
long long Wheel[] = { 6, 4, 2, 4, 2, 4, 6, 2, 0 };
long long Div;
long long Top = sqrt(Cand);
for (long long Ind = 0; SPrimes[Ind] != 0; Ind++) {
Div = SPrimes[Ind]; if (SPrimes[Ind] > Top) {
return Cand;
}
if (Cand % SPrimes[Ind] == 0) {
return SPrimes[Ind];
}
}
Div = 1;
while (Div <= Top) {
for (long long Ind = 0; Wheel[Ind] != 0; Ind++) {
Div += Wheel[Ind];
if (Div > Top) {
break;
}
if (Cand % Div == 0) {
return Div;
}
}
}
return Cand;
}
void vitesse(unsigned long long cand) {
unsigned long long fact;
auto start = high_resolution_clock::now();
for (int i = 0; i < rept; i++) {
fact = IsSFactNonDiv(cand);
}
auto stop = high_resolution_clock::now();
auto duration2 = duration_cast<microseconds>(stop - start);
start = high_resolution_clock::now();
for (int i = 0; i < rept; i++) {
fact = IsSFactDiv(cand);
}
stop = high_resolution_clock::now();
auto duration1 = duration_cast<microseconds>(stop - start);
cout << cand << "\t" << fact << "\t" << duration1.count() / 1000.0 << " ms" << "\t"
<< duration2.count() / 1000.0 << " ms" << endl;
}
int main() {
unsigned long long tmp;
cout << "integer factorization: Small Primes" << endl;
cout << __DATE__ << " " << __TIME__ << endl << endl;
cout << "Timing" << endl;
cout << "Integer\tFactor\tDivision\tMyMethod" << endl;
vitesse(6561); vitesse(125); vitesse(2401); vitesse(14641); vitesse(3601); vitesse(83521); vitesse(49999);
tmp = (1LL << 62) - 5;
vitesse(tmp);
tmp = (1LL << 62) - 27;
vitesse(tmp);
return 0;
}