Universiteti jizzax filiali amaliy matematika fakulteti «kompyuter ilmlari va dasturlashtirish» kafedrasi

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.