Почему выполнение программы ускоряется?

Question

[@ _ @]

Выполнял упражнение из одной книги по С++. Ниже приведенная прога получает от пользователя число, которое будет в последствии являться знаменателем дробей, которые выведет программа. Она будет составлять дроби, значение которых буде меньше 1.
Короче если вы введете 6, то сперва получите на выходе 1/6 2/6 3/6 4/6 5/6 6/6.
(Вывод программы: 1/61/31/22/35/61)
После чего программа будет перемножать полученные дроби по принципу "каждый с каждым".

Ну так вот, я заметил во время тестов, что если ввести очень большое число (я вводил такое, чтоб превышало максимально допустимое значение (например, 111111111111111111111111111111111)), то время между выводом очередной дроби постепенно заметно уменьшается (например, если первая дробь выводится на экран через 5 секунд, то вторая дробь выведется через 3 секунды и т.д.).

Почему так происходит?

#include <iostream>
#include <cmath>
using namespace std;

class fraction
{
	private:
		int num;
		int denom;
	public:
		fraction(): num(0), denom(0)
		{	}

		fraction(int n, int d): num(n), denom(d)
		{	}

		void getfraction()
		{
			char _;
			cin >> num >> _ >> denom;
		}

		void getfraction(int n, int d)
		{
			num = n;
			denom = d;
		}

		void showfraction()
		{
			lowterms();
			cout << num << '/' << denom;
		}

		void fadd(fraction, fraction);
		void fsub(fraction, fraction);
		void fmul(fraction, fraction);
		void fdiv(fraction, fraction);

		void lowterms();
};

void fraction::fadd(fraction f1, fraction f2)
{
	num = f1.num*f2.denom + f2.num*f1.denom;
	denom = f1.denom * f2.denom;
}

void fraction::fsub(fraction f1, fraction f2)
{
	num = f1.num*f2.denom - f2.num*f1.denom;
	denom = f1.denom * f2.denom;
}

void fraction::fmul(fraction f1, fraction f2)
{
	num = f1.num * f2.num;
	denom = f1.denom * f2.denom;
}

void fraction::fdiv(fraction f1, fraction f2)
{
	num = f1.num * f2.denom;
	denom = f1.denom * f2.num;
}

void fraction::lowterms()
{
	long tnum, tdenom, temp, gcd;
	tnum = labs(num);
	tdenom = labs(denom);
	if(tdenom == 0)
	{ cout << "Unavailable denominator!"; exit(1); }
	else if(tnum == 0)
	{ num = 0; denom = 1; return; }
	while(tnum != 0)
	{
		if(tnum < tdenom)
		{ temp = tnum; tnum = tdenom; tdenom = temp; }
		tnum = tnum - tdenom;
	}
	gcd = tdenom;
	num = num / gcd;
	denom = denom / gcd;
}

int main()
{
	fraction f1, f2, f;
	int denom;
	cin >> denom;
	for(int i = 1; i < denom; i++)
	{
		f.getfraction(i, denom);
		f.showfraction();
	}

	cout << endl;
	for(int i = 0; i < 107; i++)
	{ cout << '-'; }
	cout << endl;
	
	for(int i = 1; i < denom; i++)
	{
		f1.getfraction(i, denom);
		f1.showfraction();
		for(int j = 1; j < denom; j++)
		{
			f2.getfraction(j, denom);
			f.fmul(f1, f2);
			f.showfraction();
		}
		cout << endl;
	}
	return 0;
}

Answer 1

[Mercury13]

Потому что у вас неэффективный алгоритм вычисления НОД, работающий на вычитании, а не на делении с остатком.
Естественно, НОД(1,6) = НОД(1, 6−1=5) = НОД(1, 5−1=4) = НОД(1, 4−1=3) = НОД(1, 3−1=2) = НОД(1, 2−1=1) = НОД(1, 1−1=0) = 1
НОД(2,6) = НОД(2, 6−2=4) = НОД(2, 4−2=2) = НОД(2, 2−2=0) = 2
С арифметическим переполнением никак не связано. Просто даже в результате переполнения получились немаленькие числа.

Как надо: НОД(1,6) = НОД(6, 1%6=1) = НОД(1, 6%1=0) = 1
Аналогично для НОД(6,2) — в общем, сходится довольно быстро.