Click here to Skip to main content
15,890,897 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
What is your best way to do timing of a program?
How to minimize Windows perturbations?
C++
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:

C++
//============================================================================
// Name        : IntFact.cpp
// Author      : Patrice T
// Version     :
// Copyright   : Your copyright notice
// Description : Integer Factorization: Checking Small Primes faster than division
//============================================================================

#include <iostream>
#include <chrono>
#include <math.h>
using namespace std;
using namespace std::chrono;

// Number of repeat for timing
#define rept 1000000
// #define rept 1

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) {
	// my modulo
	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) {
	// fold integer on itself
	do {
		cand = (cand >> shift) + (cand & Mask);
	} while (cand >> shift);
	return cand;
}

long long IsSFactNonDiv(long long Cand) {
	long long Mask, Prime, tmp;
	int Size;
	// fact 2
	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) {
// test des petits diviseurs par la division, sauf 2
	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;
}

// Trial Division: Square Root + Wheel
// Check all numbers until Square Root and Skip useless factors with a wheel
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);
	// Check small primes
	for (long long Ind = 0; SPrimes[Ind] != 0; Ind++) {
		Div = SPrimes[Ind]; // for debug purpose
		if (SPrimes[Ind] > Top) {
			return Cand;
		}
		if (Cand % SPrimes[Ind] == 0) {
			return SPrimes[Ind];
		}
	}
	// Start the Wheel
	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); // 3
	vitesse(125); // 5
	vitesse(2401); // 7
	vitesse(14641); // 11
	vitesse(3601); // 13
	vitesse(83521); // 17
	vitesse(49999);
	tmp = (1LL << 62) - 5;
	vitesse(tmp);
	tmp = (1LL << 62) - 27;
	vitesse(tmp);

	return 0;
}
Posted
Updated 1-Jan-21 10:21am
v2

1 solution

I use this in windows : High Resolution Timing[^] and I have found there is no good way to do what you are asking. The best thing I have found is to raise the priority of the calculating thread so it will be interrupted as seldom as possible. Even then, testing times can vary widely. I usually end up timing a few tests, usually 3 or 5, and averaging them. The function for that is SetThreadPriority.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900