Агуулгыг алгасах

Дурын нарийвчлалтай арифметик

Дурын нарийвчлалтай арифметик буюу "bignum" эсвэл зүгээр "урт арифметик" гэж нэрлэгддэг зүйл нь стандарт өгөгдлийн төрөлд багтахаас хамаагүй том тоог боловсруулах боломж олгодог өгөгдлийн бүтэц ба алгоритмуудын багц юм. Дурын нарийвчлалтай арифметикийн хэд хэдэн төрлийг энд үзүүлэв.

Сонгодог бүхэл тооны урт арифметик

Гол санаа нь тоог ямар нэг суурьт "цифрүүд"-ийн массив хэлбэрээр хадгалах явдал юм. Хамгийн түгээмэл хэрэглэгддэг суурьнууд бол аравтын, аравтын зэрэг ($10^4$ эсвэл $10^9$) болон хоёртын систем юм.

Энэ хэлбэрийн тоонууд дээрх үйлдлийг багана нэмэх, хасах, үржүүлэх, хуваах "сургуулийн" алгоритмаар гүйцэтгэнэ. Мөн хурдан үржүүлэх алгоритмуудыг ашиглах боломжтой: хурдан Фурье хувиргалт ба Карацубагийн алгоритм.

Энд бид зөвхөн сөрөг биш бүхэл тооны урт арифметикийг тайлбарлана. Алгоритмуудыг сөрөг бүхэл тоог боловсруулахаар өргөтгөхийн тулд нэмэлт "сөрөг тоо" тэмдэглэгээ оруулж хадгалах, эсвэл хоёрын нөхөх бүхэл тооны илэрхийллийг ашиглах хэрэгтэй.

Data Structure

We'll store numbers as a vector<int>, in which each element is a single "digit" of the number.

typedef vector<int> lnum;

To improve performance we'll use $10^9$ as the base, so that each "digit" of the long number contains 9 decimal digits at once.

const int base = 1000*1000*1000;

Digits will be stored in order from least to most significant. All operations will be implemented so that after each of them the result doesn't have any leading zeros, as long as operands didn't have any leading zeros either. All operations which might result in a number with leading zeros should be followed by code which removes them. Note that in this representation there are two valid notations for number zero: an empty vector, and a vector with a single zero digit.

Output

Printing the long integer is the easiest operation. First we print the last element of the vector (or 0 if the vector is empty), followed by the rest of the elements padded with leading zeros if necessary so that they are exactly 9 digits long.

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

Note that we cast a.size() to integer to avoid unsigned integer underflow if vector contains less than 2 elements.

Input

To read a long integer, read its notation into a string and then convert it to "digits":

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()));

If we use an array of char instead of a string, the code will be even shorter:

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

If the input can contain leading zeros, they can be removed as follows:

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

Addition

Increment long integer $a$ by $b$ and store result in $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;
}

Subtraction

Decrement long integer $a$ by $b$ ($a \ge b$) and store result in $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();

Note that after performing subtraction we remove leading zeros to keep up with the premise that our long integers don't have leading zeros.

Multiplication by short integer

Multiply long integer $a$ by short integer $b$ ($b < base$) and store result in $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();

Additional optimization: If runtime is extremely important, you can try to replace two divisions with one by finding only integer result of division (variable carry) and then use it to find modulo using multiplication. This usually makes the code faster, though not dramatically.

Multiplication by long integer

Multiply long integers $a$ and $b$ and store result in $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();

Division by short integer

Divide long integer $a$ by short integer $b$ ($b < base$), store integer result in $a$ and remainder in 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 модулиар үлдэгдэл хэлбэрээр хадгална.

Анхны модультай урт бүхэл тооны арифметик (Гарнерийн алгоритм)

Санаа нь анхны тоонуудын багц сонгож (ихэвчлэн стандарт бүхэл тооны өгөгдлийн төрөлд багтахаар жижиг), бүхэл тоог тэдгээр анхны тоо бүрд хуваасны үлдэгдлүүдийн вектор хэлбэрээр хадгалах явдал юм.

Хятадын үлдэгдлийн теорем нь энэ илэрхийлэл нь 0-ээс эдгээр анхны тоонуудын үржвэр хасах нэг хүртэлх дурын тоог цор ганц байдлаар сэргээхэд хангалттай гэж хэлдэг. Гарнерийн алгоритм нь ийм илэрхийллээс тоог ердийн бүхэл тоо болгон сэргээх боломж олгодог.

Энэ арга нь сонгодог аргатай харьцуулбал санах ой хэмнэх боломж олгодог (хэдийгээр хэмнэлт нь үржигдэхүүнд задаргааны илэрхийллийнх шиг эрс биш ч). Түүнчлэн модуль болгон ашигласан анхны тоонуудын тоотой пропорциональ хугацаанд хурдан нэмэх, хасах, үржүүлэх боломж олгодог (хэрэгжүүлэлтийг Хятадын үлдэгдлийн теорем өгүүллээс үзнэ үү).

Харин үүний хариуд бүхэл тоог ердийн хэлбэр рүү буцаан хувиргах нь нэлээд их хөдөлмөр шаарддаг бөгөөд үржүүлэлттэй сонгодог дурын нарийвчлалтай арифметик хэрэгжүүлэхийг шаарддаг. Түүнчлэн энэ арга хуваалтыг дэмждэггүй.

Бутархайн дурын нарийвчлалтай арифметик

Программчлалын тэмцээнд бутархай нь бүхэл тооноос бага тохиолддог бөгөөд бутархайн хувьд урт арифметик хэрэгжүүлэх нь хамаагүй төвөгтэй байдаг тул программчлалын тэмцээнд бутархай урт арифметикийн зөвхөн бага дэд хэсэг тохиолддог.

Хураагдашгүй бутархайн арифметик

Тоог хураагдашгүй бутархай $\frac{a}{b}$ хэлбэрээр илэрхийлнэ, энд $a$ ба $b$ нь бүхэл тоо. Бутархай дээрх бүх үйлдлийг эдгээр бутархайн бүхэл тоон хүртвэр ба хуваарь дээрх үйлдэл хэлбэрээр илэрхийлж болно. Ихэвчлэн энэ нь хүртвэр ба хуваарийг хадгалахад сонгодог дурын нарийвчлалтай арифметик ашиглахыг шаарддаг боловч заримдаа стандарт 64 битийн бүхэл тооны өгөгдлийн төрөл хангалттай байдаг.

Хөвөгч цэгийн байрлалыг тусдаа төрөл болгон хадгалах

Заримдаа бодлого нь халилт эсвэл доош халилт зөвшөөрөхгүйгээр маш бага эсвэл маш том тоог боловсруулахыг шаарддаг. Стандарт double өгөгдлийн төрөл 8-10 байт ашигладаг бөгөөд зэрэг илтгэгчийн утгыг $[-308; 308]$ мужид зөвшөөрдөг ба энэ нь заримдаа хангалтгүй байж болно.

Арга нь маш энгийн: зэрэг илтгэгчийн утгыг хадгалахад тусдаа бүхэл тоон хувьсагч ашиглах ба үйлдэл бүрийн дараа хөвөгч цэгтэй тоог нормчилно, өөрөөр хэлбэл зэрэг илтгэгчийг харгалзан тохируулах замаар $[0.1; 1)$ интервал руу буцаана.

Ийм хоёр тоог үржүүлэх эсвэл хуваах үед тэдгээрийн зэрэг илтгэгчийг харгалзан нэмэх эсвэл хасах ёстой. Тоонуудыг нэмэх эсвэл хасах үед эхлээд нэгийг нь зэрэг илтгэгчийн утгуудын ялгаатай тэнцүү зэрэгт дэвшүүлсэн 10-аар үржүүлэх замаар нийтлэг зэрэг илтгэгчид оруулах ёстой.

Эцэст нь тэмдэглэхэд зэрэг илтгэгчийн суурь нь 10-тай тэнцүү байх шаардлагагүй. Хөвөгч цэгтэй тооны дотоод илэрхийлэлд үндэслэвэл зэрэг илтгэгчийн суурь болгон 2-ыг ашиглах нь хамгийн утга учиртай.

Дасгал бодлогууд