Algoritmik tillar va dasturlash

Uzun sonlarni ko‘paytirish
Uzun sonlar a ni qisqa b ga ko‘paytiradi (b < {\rm base}) va natijani a da saqlaydi:
int carry = 0;
for (size_t i=0; iif (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();
Bu erda biz bo‘linishni amalga oshirgandan so‘ng, yo‘q bo‘lgan predikatni saqlab qolish uchun etakchi nollarni olib tashlaymiz. (Izoh: qo‘shimcha optimallashtirish usuli. Agar ish tezligi juda muhim bo‘lsa, unda siz ikkita bo‘linishni bittasiga almashtirishga urinib ko‘rishingiz mumkin: bo‘linishning faqat butun qismini hisoblang (kodda bu yuk o‘zgaruvchisi) va keyin bo‘linishning qolgan qismini hisoblang (bitta ko‘paytirish operatsiyasi yordamida). Qoida tariqasida, ushbu usul kodni tezlashtirishga imkon beradi, garchi unchalik katta bo‘lmasa ham.)
Ikki uzun sonlarni ko‘paytirish
A ni b ga ko‘paytiradi va natijani c da saqlaydi:
lnum c (a.size()+b.size());
for (size_t i=0; ifor (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();
Uzun sonlarni qisqa qismga bo‘lish
Uzun sonlar a ni qisqa b ga ajratadi (b < base), xususiy a da saqlanadi, qolgan qismi tashuvchida:
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();
Bu erda g’oya raqamning o‘zini emas, balki uning faktorizatsiyasini, ya’ni unga kiritilgan har bir oddiyning darajasini saqlashdir. Ushbu usulni amalga oshirish juda oson va ko‘paytirish va bo‘linish operatsiyalarini bajarish juda oson, ammoqo‘shish yoki ayirish mumkin emas. Boshqa tomondan, bu usul "klassik" yondashuvga nisbatan xotirani sezilarli darajada tejaydi va ko‘paytirish va bo‘linishni sezilarli darajada (asimptotik) tezroq bajarishga imkon beradi. Ushbu usul ko‘pincha qiyin modul bo‘yicha bo‘linish zarur bo‘lganda qo‘llaniladi: keyin raqamni ushbu modulning oddiy bo‘linmalarida darajalar shaklida va boshqa raqamni — xuddi shu moduldagi qoldiqni saqlash kifoya.Oddiy modullar tizimi bo‘yicha Uzun sonlar arifmetik (Xitoy teoremasi yoki Garner sxemasi)
Xitoy qoldiqlari teoremasi ta’kidlaganidek, bu 0 dan 0 gacha bo‘lgan har qanday raqamni minus bitta modul mahsulotiga noyob tarzda saqlash uchun etarli. Bunday holda, Garnerning algoritmi mavjud bo‘lib, u ushbu tiklashni modulli ko‘rinishdan oddiy, "klassik" raqam shakliga o‘tkazishga imkon beradi. Shunday qilib, bu usul "klassik" Uzun sonlar arifmetikaga nisbatan xotirani tejaydi (garchi ba’zi hollarda faktorizatsiya usuli kabi radikal bo‘lmasa ham). Bundan tashqari, modulli shaklda siz qo‘shish, ayirish va ko‘paytirishni juda tez bajarishingiz mumkin - barchasi tizim modullari soniga mutanosib bo‘lgan asimptotik bir vaqtning o‘zida. Biroq, bularning barchasi raqamni ushbu modulli turdan oddiy shaklga juda ko‘p vaqt talab qiladigan tarjima qilish evaziga beriladi, buning uchun ko‘p vaqt sarflashdan tashqari, ko‘paytirish bilan "klassik" Uzun sonlar arifmetikani amalga oshirish kerak bo‘ladi.Bundan tashqari, oddiy modullar tizimi bo‘yicha raqamlarni bunday ko‘rinishda bo‘lish mumkin emas.