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

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

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

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

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

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

در اینجا ما حساب طولانی را فقط برای اعداد صحیح غیرمنفی شرح می‌دهیم. برای توسعه الگوریتم‌ها جهت پشتیبانی از اعداد صحیح منفی، باید یک پرچم اضافی «عدد منفی» تعریف و نگهداری شود یا از نمایش اعداد صحیح به روش مکمل دو استفاده کرد.

ساختمان داده

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

typedef vector<int> lnum;

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

const int base = 1000*1000*1000;

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

خروجی

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

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

توجه داشته باشید که a.size() را به عدد صحیح تبدیل می‌کنیم تا در صورتی که vector کمتر از ۲ عنصر داشته باشد، از سرریز زیرین عدد صحیح بدون علامت جلوگیری شود.

ورودی

برای خواندن یک عدد صحیح طولانی، نمایش آن را در یک 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ی از باقیمانده‌های تقسیم آن عدد بر هر یک از آن اعداد اول ذخیره کنیم.

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

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

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

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

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

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

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

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

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

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

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

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

مسائل تمرینی