پرش به محتویات

حساب با دقت دلخواه

ببین، «حساب با دقت دلخواه» که بهش "bignum" یا خیلی ساده‌تر «حساب طولانی» هم میگن، یه سری ساختار داده و الگوریتمه که بهت اجازه میده با عددهایی کار کنی که خیلی بزرگ‌تر از اون چیزی هستن که توی تایپ‌های استاندارد مثل long long جا میشن. اینجا قراره چند مدل مختلف از این روش‌ها رو با هم ببینیم.

حساب طولانی کلاسیک برای اعداد صحیح

ایده اصلیش اینه که عدد رو به شکل یه آرایه از «رقم‌ها»ش توی یه مبنای خاص ذخیره کنیم. چندتا مبنای رایج هم هستن، مثل مبنای ۱۰، توان‌هایی از ۱۰ (مثلاً $10^4$ یا $10^9$) و مبنای ۲.

عملیات روی این عددها هم دقیقاً با همون الگوریتم‌های «دوران مدرسه» مثل جمع و تفریق و ضرب و تقسیم ستونی انجام میشه. البته میشه از الگوریتم‌های ضرب سریع‌تر مثل تبدیل فوریه سریع (FFT) و الگوریتم کاراتسوبا هم استفاده کرد.

اینجا ما فقط حساب طولانی برای عددهای صحیح نامنفی رو توضیح میدیم. اگه بخوای الگوریتم‌ها رو برای پشتیبانی از عددهای منفی هم گسترش بدی، باید یه فلگ (flag) اضافه برای علامت منفی تعریف کنی و حواست بهش باشه، یا اینکه از روش نمایش مکمل دو (two's complement) استفاده کنی.

ساختار داده

ما عددها رو توی یه vector<int> ذخیره می‌کنیم که هر عنصرش یه «رقم» از اون عدد بزرگه حساب میشه.

typedef vector<int> lnum;

برای اینکه عملکرد بهتری داشته باشیم، از مبنای $10^9$ استفاده می‌کنیم. اینجوری هر «رقم» از عدد طولانی ما، در واقع ۹ تا رقم دهدهی رو یک‌جا توی خودش نگه میداره.

const int base = 1000*1000*1000;

رقم‌ها رو از کم‌ارزش به پرارزش ذخیره می‌کنیم (یعنی برعکس چیزی که می‌نویسیم). همه عملیات‌ها رو هم جوری پیاده‌سازی می‌کنیم که بعد از هر عملیات، نتیجه هیچ صفر پیشرو (leading zero) نداشته باشه، البته به شرطی که خود عملوندها هم صفر پیشرو نداشته باشن. هر عملیاتی که ممکنه باعث ایجاد صفر پیشرو بشه، باید آخرش یه کدی داشته باشه که این صفرها رو حذف کنه. حواست باشه که توی این نمایش، دو تا حالت معتبر برای عدد صفر داریم: یه vector خالی، یا یه vector که فقط یه دونه صفر توشه.

خروجی

چاپ کردن یه عدد طولانی، ساده‌ترین کار ممکنه. اول آخرین عنصر vector رو چاپ می‌کنیم (یا اگه vector خالی بود، صفر چاپ می‌کنیم). بعدش بقیه عنصرها رو، اگه لازم بود با صفرهای پیشرو (leading zeros) چاپ می‌کنیم تا دقیقاً ۹ رقم طول داشته باشن.

printf ("%d", a.empty() ? 0 : a.back());
for (int i=(int)a.size()-2; i>=0; --i)
    printf ("%09d", a[i]);

یه نکته: a.size() رو به int کست می‌کنیم تا اگه vector کمتر از ۲ تا عنصر داشت، دچار underflow توی اعداد بدون علامت (unsigned integer) نشیم.

ورودی

برای خوندن یه عدد طولانی، اول اون رو توی یه string می‌خونیم و بعد به «رقم‌»های خودمون تبدیلش می‌کنیم:

for (int i=(int)s.length(); i>0; i-=9)
    if (i < 9)
        a.push_back (atoi (s.substr (0, i).c_str()));
    else
        a.push_back (atoi (s.substr (i-9, 9).c_str()));

اگه به جای string از آرایه char استفاده کنی، کد حتی کوتاه‌تر هم میشه:

for (int i=(int)strlen(s); i>0; i-=9) {
    s[i] = 0;
    a.push_back (atoi (i>=9 ? s+i-9 : s));
}

اگه ورودی ممکنه صفرهای پیشرو داشته باشه، اینجوری می‌تونی حذفشون کنی:

while (a.size() > 1 && a.back() == 0)
    a.pop_back();

جمع

اینم کد اضافه کردن عدد طولانی $b$ به $a$ و ذخیره نتیجه توی خود $a$:

int carry = 0;
for (size_t i=0; i<max(a.size(),b.size()) || carry; ++i) {
    if (i == a.size())
        a.push_back (0);
    a[i] += carry + (i < b.size() ? b[i] : 0);
    carry = a[i] >= base;
    if (carry)  a[i] -= base;
}

تفریق

اینم کد کم کردن عدد طولانی $b$ از $a$ (با فرض $a \ge b$) و ذخیره نتیجه توی خود $a$:

int carry = 0;
for (size_t i=0; i<b.size() || carry; ++i) {
    a[i] -= carry + (i < b.size() ? b[i] : 0);
    carry = a[i] < 0;
    if (carry)  a[i] += base;
}
while (a.size() > 1 && a.back() == 0)
    a.pop_back();

دقت کن که بعد از تفریق، صفرهای پیشرو رو حذف می‌کنیم تا با این فرض که عددهامون صفر پیشرو ندارن، هماهنگ باشیم.

ضرب در عدد صحیح کوتاه

ضرب عدد طولانی $a$ در یه عدد کوتاه $b$ (که $b < base$) و ذخیره نتیجه توی خود $a$:

int carry = 0;
for (size_t i=0; i<a.size() || carry; ++i) {
    if (i == a.size())
        a.push_back (0);
    long long cur = carry + a[i] * 1ll * b;
    a[i] = int (cur % base);
    carry = int (cur / base);
}
while (a.size() > 1 && a.back() == 0)
    a.pop_back();

یه بهینه‌سازی کوچولو: اگه زمان اجرا خیلی برات مهمه، می‌تونی سعی کنی دو تا عملیات تقسیم رو با یکی جایگزین کنی. یعنی فقط خارج قسمت (متغیر carry) رو پیدا کنی و بعد باقیمانده رو با استفاده از ضرب به دست بیاری. این کار معمولاً کد رو سریع‌تر می‌کنه، هرچند نه خیلی زیاد.

ضرب در عدد صحیح طولانی

ضرب دو تا عدد طولانی $a$ و $b$ و ذخیره نتیجه توی $c$:

lnum c (a.size()+b.size());
for (size_t i=0; i<a.size(); ++i)
    for (int j=0, carry=0; j<(int)b.size() || carry; ++j) {
        long long cur = c[i+j] + a[i] * 1ll * (j < (int)b.size() ? b[j] : 0) + carry;
        c[i+j] = int (cur % base);
        carry = int (cur / base);
    }
while (c.size() > 1 && c.back() == 0)
    c.pop_back();

تقسیم بر عدد صحیح کوتاه

تقسیم عدد طولانی $a$ بر یه عدد کوتاه $b$ (که $b < base$). خارج قسمت توی خود $a$ ذخیره میشه و باقیمانده توی carry برگردونده میشه:

int carry = 0;
for (int i=(int)a.size()-1; i>=0; --i) {
    long long cur = a[i] + carry * 1ll * base;
    a[i] = int (cur / b);
    carry = int (cur % b);
}
while (a.size() > 1 && a.back() == 0)
    a.pop_back();

حساب اعداد صحیح طولانی با نمایش به صورت تجزیه

ایده این روش اینه که عدد صحیح رو به شکل تجزیه به عامل‌های اولش ذخیره کنیم. یعنی توان‌های اعداد اولی که اون عدد رو می‌سازن.

پیاده‌سازی این روش خیلی ساده‌ست و بهت اجازه میده ضرب و تقسیم رو خیلی راحت انجام بدی (از نظر پیچیدگی زمانی هم سریع‌تر از روش کلاسیکه)، ولی خب برای جمع و تفریق اصلاً مناسب نیست. تازه، در مقایسه با روش کلاسیک، از نظر حافظه هم خیلی بهینه‌تره.

این روش اغلب برای محاسبات به پیمانه یه عدد غیر اول M استفاده میشه؛ توی این حالت، یه عدد به صورت توان‌های مقسوم‌علیه‌های M که عدد رو می‌سازن، به علاوه باقیمانده به پیمانه M ذخیره میشه.

حساب اعداد صحیح طولانی در پیمانه‌های اول (الگوریتم گارنر)

ایده اینجا اینه که یه سری عدد اول انتخاب کنیم (معمولاً اونقدر کوچیک که توی تایپ‌های استاندارد جا بشن) و بعد یه عدد صحیح بزرگ رو به شکل یه vector از باقیمانده‌هاش به این اعداد اول ذخیره کنیم.

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

این روش در مقایسه با رویکرد کلاسیک باعث صرفه‌جویی توی حافظه میشه (هرچند نه به اندازه روش تجزیه). علاوه بر این، بهت اجازه میده جمع، تفریق و ضرب رو خیلی سریع و در زمانی متناسب با تعداد اعداد اولی که به عنوان پیمانه استفاده کردی، انجام بدی (برای پیاده‌سازیش یه نگاهی به مقاله قضیه باقیمانده چینی بنداز).

نقطه ضعفش اینه که تبدیل عدد به شکل عادی خودش خیلی پرزحمته و نیاز به پیاده‌سازی حساب با دقت دلخواه کلاسیک به همراه ضرب داره. تازه، این روش از تقسیم هم پشتیبانی نمی‌کنه.

حساب با دقت دلخواه برای اعداد کسری

عددهای کسری توی مسابقات برنامه‌نویسی کمتر از عددهای صحیح دیده میشن و پیاده‌سازی حساب طولانی براشون خیلی سخت‌تره. برای همین، توی مسابقه‌ها معمولاً فقط با یه بخش کوچیکی از حساب طولانی کسری سروکار داریم.

حساب در کسرهای ساده‌نشدنی

یه عدد به صورت یه کسر ساده‌نشدنی $\frac{a}{b}$ نمایش داده میشه که $a$ و $b$ اعداد صحیح هستن. همه عملیات روی کسرها رو میشه به عملیات روی صورت و مخرج صحیح این کسرها تبدیل کرد. معمولاً این کار نیاز به استفاده از حساب با دقت دلخواه کلاسیک برای ذخیره صورت و مخرج داره، ولی گاهی وقتا یه تایپ عدد صحیح ۶۴ بیتی داخلی هم کافیه.

ذخیره موقعیت ممیز شناور به عنوان نوع جداگانه

گاهی وقتا یه مسئله ازت می‌خواد با عددهای خیلی کوچیک یا خیلی بزرگ کار کنی، بدون اینکه سرریز (overflow) یا سرریز زیرین (underflow) اتفاق بیفته. تایپ double داخلی از ۸-۱۰ بایت استفاده می‌کنه و توان‌ها رو توی بازه $[-308; 308]$ نگه میداره که گاهی ممکنه کافی نباشه.

رویکرد خیلی ساده‌ست: از یه متغیر صحیح جداگانه برای ذخیره توان استفاده می‌کنی و بعد از هر عملیات، عدد ممیز شناور رو نرمال‌سازی می‌کنی. یعنی با تنظیم مناسب توان، عدد رو به بازه $[0.1; 1)$ برمی‌گردونی.

وقتی دو تا عدد از این نوع رو ضرب یا تقسیم می‌کنی، توان‌هاشون باید به ترتیب جمع یا تفریق بشن. موقع جمع یا تفریق هم، اول باید با ضرب کردن یکی از اون‌ها در ۱۰ به توان اختلاف توان‌هاشون، اون‌ها رو به یه توان مشترک برسونی.

به عنوان نکته آخر، مبنای توان حتماً نباید ۱۰ باشه. با توجه به نمایش داخلی اعداد ممیز شناور، منطقی‌ترین کار اینه که از ۲ به عنوان مبنای توان استفاده کنی.

مسائل تمرینی