تست کردن سرریز

فرض کنيد می خواهيد تابعی بنويسيد که عبارت را محاسبه کند، در صورتيکه حاصل از کمتر بود، حاصل را برگرداند، و در غير اين صورت عدد 1- را برگرداند. از چه راه حلی استفاده می کنيد؟ (با فرض اينکه a و b و p از کوچکتر هستند.)

از کلاس Big Integer استفاده کنيد. حاصل را حساب کنيد، و سپس حاصل را با مقايسه کنيد. در ++C و C اين روش احمقانه ترين روش است (چون احتمالا بايد اين نوع داده را خودتان پياده سازی کنيد) ولی اگر از Java يا Python استفاده می کنيد، اين روش، روش خوب و ساده ايست.

توجه: در راه حل های بعدی از اين نکته که نوع داده ی عدد صحيح 64 بيتی (long long در ++C) می تواند اعدادی تا بزرگی را نگهداری کند استفاده کرده ايم.

چون از محدوده ی long long بيرون نمی زند، به راحتی می توانيم دو عدد کوچکتر از را با هم جمع کنيم، و سپس با مقايسه کنيم تا بفهميم که حاصل از 1- بزرگتر است يا نه. همان طور که احتمالا می دانيد، عمل ضرب را می توان با استفاده از عمل جمع پياده سازی کرد. کد اين تابع را در زير مشاهده می کنيد:

long long multiply(long long a, long long b)
{
	if(b == 0) return 0;
	long long result = multiply(a, b / 2);
	if(result == -1) return -1;
	result += result;
	if(b % 2) result += a;
	if(result > 1000000000000000000ll) return -1;
	return result;
}

و عمل توان را با استفاده از عمل عمل ضرب می توان پياده سازی کرد:

long long power(long long a, long long b)
{
	if(b == 0) return 1;
	long long result = power(a, b / 2);
	if(result == -1) return -1;
	result = multiply(result, result);
	if(result == -1) return -1;
	if(b % 2) multiply(result, a);
	if(result == -1) return -1;
	return result;
}

اين روش نسبت به روش قبل ساده تر و عاقلانه تر (در صورت عدم وجود امکانات) می باشد، ولی ساده ترين روش نيست!

با استفاده از عمل تقسيم می توان حداکثر مقداری که می توانيم در يک عدد ضرب کنيم تا حاصل کوچکتر از شود را پيدا کرد. با استفاده از اين نکته، کارمان کمی ساده تر می شود و می توانيم به صورت زير عمل کنيم:

long long multiply(long long a, long long b)
{
	if(b == 0) return 0;
	long long maxp = 1000000000000000000ll / b;
	if(a > maxp) return -1;
	return a * b;
}

استفاده از لگاريتم در مبنای 10. فرض کنيد می خواهيم را محاسبه کنيم. اگر به صورت زير عمل کنيم:

long long power(long long a, long long b)
{
	if(b == 0) return 1;
	long long result = power(a, b / 2);
	result *= result;
	if(b % 2) result *= a;
	return result;
}
 
long long calc(long long a, long long b, long long p)
{
	double L = log10(a) + p * log10(b);
	if(L > 18)return -1 ;
	return a * power(b, p) ;
}

ممکن است بعضی اوقات نتيجه گيری اشتباهی کنيم، چون اختلاف لگاريتم و کمتر از می باشد و با اين مقايسه ها اين اختلاف ها مشخص نمی شوند.

چون عمرا از محدوده ی long long خارج نیست و تمام اعداد کوچکتر يا مساوی دارای لگاريتمی کمتر از 18.5 هستند، حتی با در نظر گرفتن خطاهای محاسباتی، می توان به روش زير عمل کرد:

long long power(long long a, long long b)
{
	if(b == 0) return 1;
	long long result = power(a, b / 2);
	result *= result;
	if(b % 2) result *= a;
	return result;
}
 
long long calc(long long a, long long b, long long p)
{
	double L = log10(a) + p * log10(b);
	if(L > 18.5) return -1 ;
	long long result = a * power(b, p);
	if(result > 1000000000000000000ll) return -1;
	return result ;
}

مزيت روش آخر نسبت به روش های ديگر اين است که تمام چک های خارج از محدوده بودن تنها در يک نقطه انجام می گيرد، و بالطبع احتمال اشتباه کردن برنامه نويس کمتر است.