Дълги числа

Long Numbers

Какво са "Дълги числа"? Кога би ни се наложило да ги ползваме? Ефективни имплементации.

Автор: Александър Георгиев

Сблъсквали ли сте се с проблема, когато 32-битовите числа не са ви достатъчни за да съхраните отговора за дадена задача или подзадача? Тогава трябва да ползвате 64-битов тип или да държите отговора под модул. Какво става, обаче, ако дори 64-битовите типове не са достатъчни?

Примерен проблем

Ели се чуди кое е 1000-ното число на Фибоначи. Напомняме, че числата на Финбоначи са дефинирани като:

F₀ = 0;
F₁ = 1;
F_i = F_i-2 + F_i-1, за i ≥ 2.

Какъв е проблемът?

?	1000-ното число на Фибоначи е: 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

Даденият проблем не е изчислително толкова сложен - дори линейно да намираме всяко следващо число на Фибоначи ще са ни нужни едва 1000 събирания. Тъй като просто събираме предходните две числа, то всяко следващо ще е с най-много една цифра по-дълго от предходното. Следователно, 1000-ното число ще е с не повече от 1000 цифри. Най-простият алгоритъм, в който започваме с 0 и 1 и събираме N пъти би работел за приблизително O(N²) време (ако приемем, че събирането на две числа с дължина L става за O(L)).
Проблемът тук е, че отговорът ще надхвърля многократно възможностите на 64-, а дори и 128-битов тип. Наистина, 64-битовият тип поддържа до около 19 десетични цифри.

Дълги числа

?	Много от по-модерните езици (например Java и Python) включват имплементации на дълги числа, които са добре тествани и имплементирани (демек верни и бързи). За съжаление, C++ не е един от тези езици.

За справянето с този проблем са възникнали така наречените "дълги числа" - тоест библиотека, която извършва стандартните аритметични операции върху числа, по-големи от максималния тип на процесора. Тъй като е невъзможно операции с толкова големи числа да се извършват хардуерно, вместо това се ползва софтуерна емулация (програма), която прави това в паметта, вместо в регистрите на процесора.

Основна идея

Добре, как можем да направим събиране на две 20-цифрени числа? Оказва се, че относително просто - можем да разбием всяко от числата в масив, който пази във всяка своя клетка по една цифра от число. Така получаваме два масива с по 20 елемента, във всеки от които има числа между 0 и 9, включително. Резултатът от събирането ще има най-много 21 цифри, тоест може да е масив с 21 клетки от същия тип.

Самото събиране протича по следния начин. Започвайки от най-младшите цифри (тоест първо единици, после десетици, после стотици и т.н.), събираме всяка клетка със съответната ѝ от другия масив, като сумата им запазваме в клетката на масива за резултата. Понякога ще се случи тази сума да е по-голяма или равна на 10, в който случай имаме "едно наум" и добавяме единица към следващата клетка от резултата (съседната по-старша цифра).

В най-прост смисъл тези масиви с цифри наричаме "дълги числа".

Други аритметични операции

До тук разгледахме само събиране (впрочем, то често ще е единствената операция, която ще ви трябва). Какво можем да кажем за останалите възможни аритметични операции? Както се оказва, те не са много различни. Можем да имплементираме на компютър "алгоритмите" за събиране, изваждане, умножение, и деление, на които са ни учили в училище.

С малки подробности. Например, при изваждане може да се получи отрицателно число. Как да отбележим, че даден масив от цифри е "отрицателен"? Можем да решим този проблем тривиално, като освен масива пазим и допълнителна променлива, която ни показва дали числото е отрицателно или положително.
Освен това, по всяко време трябва да знаем точно колко цифри има дългото число. Например, хубаво имаме две 20-цифрени числа, но след изваждане, например, резултатът може да е с под 20 цифри; или след умножение да е с около 40. Затова ни трябва и променлива, която показва колко цифрено е числото.
Така вече данните, които ни трябват за горната задача биха били нещо от сорта на:

struct Long {
    bool
 positive;
    int
 digits[1024
],
 numDigits;
};

Разбира се, ако искаме да напишем по-"гъвкава" имплементация, цифрите можем да пазим в динамичен масив. Така бихме имали:

struct Long {
    bool
 positive;
    vector
 <
int
>
 digits;
};

База на числата

Забелязахте ли, че пазим само по една десетична цифра във всяка клетка на масива? Ако масивът е от int-ове (което е стандартно, тъй като операциите с int са най-бързи), то всяка клетка поддържа числа до над 2 милиарда (или 4 милиарда, ако ползваме unsigned). А ние ползваме до 10. Какво разхищение!

Добре, а защо не преминем към друга база (бройна система)? Например 100-тична? Така всяка цифра ще е число между 0 и 99, включително, операциите се извършват отново без проблем, а съкратихме броя цифри на половина! А с това забързахме и операциите поне двойно.

Развивайки идеята нататък, можем да видим, че една от удобните бройни системи, които можем да ползваме, е едномилиардна (тоест число между 0 и 999,999,999 във всяка клетка). Тя е удобна, тъй като е лесно да се премине в десетична от нея, сборът на две клетки не прехвърля максимума на 32-битовия тип, а сборът на произведението на две клетки не прехвърля максимума на 64-битовия тип. Така ползваме девет пъти по-малко памет и операциите са ни поне девет пъти по-бързи от стандартното. За съжаление, имплементацията е малко по-сложна (трябва да внимаваме за overflow при умножение; печатането на числото е съвсем малко по-трудно).

Трикове

Тук даваме някакви трикове, с които можете да жертвате бързодействие в полза на леснота на имплементация.

Обратен ред на цифрите

Оказва се, че е по-удобно за имплементация, ако пазим цифрите на числото в "обратен" ред - тоест в нулевата клетка на масива пазим най-младшата цифра (цифрата на единиците, при база 10), в клетката с индекс едно пазим втората най-младша цифра (цифрата на десетиците, при база 10) и т.н. Това е удобно, тъй като обикновено извършваме операциите именно в този ред (помислете си как правите операциите на лист). Допълнително, това е удобно, тъй като като прибавяме нова цифра към числото (след събиране или умножение, например) то тази цифра е най-старша на числото. Ако я пазихме на първа позиция в масива, щеше да се наложи да преместим всички други цифри, за да я вмъкнем. Вместо това, по този начин добавянето на нова цифра ни е константно.

Дълги и Къси числа

Можем да разбием числата на два типа: "дълги" и "къси". За "късо" число ще считаме число, което е по-малко от базата, която сме избрали. Демек ако сме избрали база 10, това число ще е между 0 и 9, включително. Ако сме избрали база 1,000,000,000, това число ще е между 0 и 999,999,999, включително.

За да спечелим бързодействие може да разглеждаме различни случаи ако имаме операция на дълго с дълго и на дълго с късо число. Имплементацията на всички операции, в които (поне) едното от числата е късо, е далеч по-лесна и бърза.

Лесно деление

Делението на дълго с дълго число е най-сложната за имплементиране основна операция (тоест събиране, изваждане, умножение, и деление). Забележете, че ако делим дълго число на някакво сравнително малко ("късо" число, например такова, което заема една цифра от базата, която сме избрали), това не е толкова трудно - единственото трудно е да делим дълго на друго дълго число. Като пример се замислете как бихте имплементирали деление на 2 (не е много сложно).

Ако ни се наложи да имплементираме деление на дълго с дълго, но не държим да е кой-знае колко бързо, можем вместо да го имплементираме, да ползваме двоично търсене. Двоичното ще правим по отговора, а сметките вътре изискват единствено деление на късото число 2 и умножение на дълго с дълго (което е значително по-лесно за имплементиране).

Двоична база

Казахме, че можем да ползваме база, различна от 10, за да забързаме операциите и да спестим известно количество памет. Все пак, базата, която избрахме, беше степен на 10 - тъй като сме свикнали с операциите в тази база и е сравнително очевидно (за човек) какво се случва с цифрите.

За компютрите, обаче, такъв тип бази не са много удобни. Например през цялото време имаме деление и намиране на остатък по тази база. Защо, тогава, не ползваме база, която е точна степен на 2 (вместо на 10)? Така делението и намирането на остатъка можем да извършваме само с побитови операции, които са много по-бързи! Допълнително, можем лесно да имплементираме "побитови" операции в дълго число и да направим дългите си числа почти еквивалентни на стандартните целочислени типове.

Проблемът тук е, че входните числа често са ни зададени в 10-тична бройна система. Така при "създаване" на дългото число трябва да го превърнем в бройната система, която сме избрали - което не е толкова тривиално, ако тя не е степен на 10. Обратното също е вярно - най-често ще искаме да изпечатаме резултата в 10-тична бройна система, затова ще ни трябва и обратното превръщане от (степен на) двоична към 10-тична.

Имплементация

Тук ще покажем базовата имплементация на основните операции (сравнение, събиране, изваждане, умножение и деление). При нея не сме ползвали никой от триковете за забързване на операциите - тя е чисто с "научни" цели - тоест да покаже каква е основната идея и как можем лесно да имплементираме тези операции.

След няколко имплементации от моя страна (това ми е трета цялостна) по време на кодерския ми живот, стигнах до извода, че е далеч по-лесно, ако числата бяха само положителни. В противен случай е много лесно да се обърка някой знак, или да се получи (например) отрицателна нула.
Оказва се, че е по-лесно ако се раздели същинската операция от нагласянето на знака. Двете логики са относително независими и можем да имплементираме в отделни функции. В първата от тях ще се справяме с операцията, ако числата бяха без знак (вземаме по абсолютна стойност както самите входни числа, така и резултата от операцията). Във втората ще извикаме първата (за да намерим все пак какви цифри има резултата) и ще донагласим знака, спрямо знаците на двете входни числа.
Както ще видите (особено ако вече сте пробвали да пишете дълги числа), така нещата стават далеч по-чисто.

Последно, преди да започнем със самата имплементация - повечето операции са бинарни - тоест приемат два аргумента. Обикновено между тях има и знак (например '<', '+', '-', '*', '/'). Така можем да кръстим числата "ляво" и "дясно", в зависимост от коя страна на знака стоят. В кода по-нататък ще ги именуваме lvalue (left-hand side value) и rvalue (right-hand side value).

База

Ще ползваме стандартната база 10, с която сме добре свикнали.

Данни

Както и по-горе, ще дефинираме тип "дълго число", който пази знак и цифрите на числото. Ще ползваме STL-ски vector за цифрите, като така няма да се налага сами да менажираме паметта си.

struct Long {
    bool
 positive;
    vector
 <
int
>
 digits;
};

Инициализация

Трябва да имаме начин, по който да "създаваме" дълго число (с потенциално много цифри). Един често ползван и удобен начин за това е да го създаваме от string. За удобство, можем да направим конструктор, който приема стринг като аргумент и създава дълго число от този стринг. Алтернативно, ще направим и конструктор по подразбиране, който инициализиара числото с нула. Така структурата, която ще ползваме, става:

struct Long {
    bool
 positive;
    vector
 <
int
>
 digits;
    Long() {
        positive =
 true
;
        digits.push_back(0
);
    }
    Long (string value) {
        positive =
 true
;
        int
 endAt =
 0
;
        if
 (value[0
] =
=
 '-'
 |
|
 value[0
] =
=
 '+') {
            positive =
 value[0
] =
=
 '+'
;
            endAt+
+
;
        }
        for
 (int
 i =
 (int
)value.size() -
 1
;
 i >
=
 endAt;
 i-
-)
            digits.push_back(value[i] -
 '0'
);
        if
 ((int
)digits.size() =
=
 1
 &
&
 digits[0
] =
=
 0)
            positive =
 true
;
    }
};

Печатане

Очевидно е хубаво да имаме някакъв лесен начин да печатаме числото. Една възможност е да имаме функция, която го превръща обратно в string, който можем да изпечатаме по много начини (както с cout, така и с printf).

string toString(Long value) {
    string
 ret;
    if
 (!value.positive)
        ret +
=
 '-'
;
    for
 (int
 i =
 (int
)value.digits.size() -
 1
;
 i >
=
 0
;
 i-
-)
        ret +
=
 value.digits[i] +
 '0'
;
    return
 ret;
}

Нормализация

Ще направим един допълнителен метод, който нормализира числото - тоест премахва водещи нули, и го прави положително, ако е нула (за да нямаме отрицателна нула, която може да се получи при някои от операциите).

Long fix(Long num) {
    while
 ((int
)num.digits.size() >
 1
 &
&
 num.digits.back() =
=
 0)
        num.digits.pop_back();
    if
 ((int
)num.digits.size() =
=
 1
 &
&
 num.digits[0
] =
=
 0)
        num.positive =
 true
;
    return
 num;
}

Сравнение по абсолютна стойност

Сравнението има следната семантика: функцията ще връща -1, ако лявото е по-малко, 0 ако са равни и +1 ако лявото е по-голямо.

// Returns -1 if lvalue is less, 0 if equal, or +1 if lvalue is greater.
int
 absoluteCompare(Long lvalue, Long rvalue) {
    if
 (lvalue.digits.size() !
= rvalue.digits.size())
        return
 lvalue.digits.size() <
 rvalue.digits.size() ?
 -
1
 :
 1
;
    for
 (int
 i =
 (int
)lvalue.digits.size() -
 1
;
 i >
=
 0
;
 i-
-)
        if
 (lvalue.digits[i] !
= rvalue.digits[i])
            return
 lvalue.digits[i] <
 rvalue.digits[i] ?
 -
1
 :
 1
;
    return
 0
;
}

Събиране по абсолютна стойност

Long absoluteAdd(Long lvalue, Long rvalue) {
    // Guarantee |lvalue| >= |rvalue|
    if
 (absoluteCompare(lvalue,
 rvalue) <
 0)
        swap(lvalue,
 rvalue);
    int
 carry =
 0
;
    for
 (int
 i =
 0
;
 i <
 (int
)lvalue.digits.size();
 i+
+) {
        if
 (i <
 (int)rvalue.digits.size())
            carry +
=
 rvalue.digits[i];
        lvalue.digits[i] +
=
 carry;
        carry =
 0
;
        if
 (lvalue.digits[i] >
=
 10) {
            lvalue.digits[i] -
=
 10
;
            carry =
 1
;
        }
    }
    if (carry)
        lvalue.digits.push_back(carry);
    return
 fix(lvalue);
}

Изваждане по абсолютна стойност

Long absoluteSubtract(Long lvalue, Long rvalue) {
    // Guarantee |lvalue| >= |rvalue|
    if
 (absoluteCompare(lvalue,
 rvalue) <
 0)
        swap(lvalue,
 rvalue);
    int
 carry =
 0
;
    for
 (int
 i =
 0
;
 i <
 (int
)lvalue.digits.size();
 i+
+) {
        if
 (i <
 (int)rvalue.digits.size())
            carry +
=
 rvalue.digits[i];
        lvalue.digits[i] -
=
 carry;
        carry =
 0
;
        if
 (lvalue.digits[i] <
 0) {
            lvalue.digits[i] +
=
 10
;
            carry =
 1
;
        }
    }
    return
 fix(lvalue);
}

Умножение по абсолютна стойност

Long absoluteMultiply(Long lvalue, Long rvalue) {
    Long ret;
    for
 (int
 i =
 0
;
 i <
 (int
)lvalue.digits.size();
 i+
+) {
        Long add;
        add.digits.resize(i,
 0
);
        int
 carry =
 0
;
        for
 (int
 c =
 0
;
 c <
 (int
)rvalue.digits.size();
 c+
+) {
            carry +
=
 lvalue.digits[i] *
 rvalue.digits[c];
            add.digits.push_back(carry %
 10
);
            carry /
=
 10
;
        }
        if (carry)
            add.digits.push_back(carry);
        ret =
 absoluteAdd(ret,
 add);
    }
    return
 fix(ret);
}

Деление по абсолютна стойност

Long absoluteDivide(Long lvalue, Long rvalue) {
    Long ret;
    Long left,
 right =
 lvalue;
    while
 (absoluteCompare(left,
 right) <
=
 0) {
        Long mid =
 absoluteAdd(left,
 right);
        int
 carry =
 0
;
        for
 (int
 i =
 (int
)mid.digits.size() -
 1
;
 i >
=
 0
;
 i-
-) {
            carry =
 carry *
 10
 +
 mid.digits[i];
            mid.digits[i] =
 carry /
 2
;
            carry %
=
 2
;
        }
        mid =
 fix(mid);
        if
 (absoluteCompare(absoluteMultiply(mid,
 rvalue),
 lvalue) <
=
 0) {
            ret =
 mid;
            left =
 absoluteAdd(mid,
 Long("1"
));
        }
        else {
            right =
 absoluteSubtract(mid,
 Long("1"
));
        }
    }
    return
 fix(ret);
}

Операции със знак

Остана да направим функции, които се справят със знака при различните операции. Както ще видите, те не са толкова трудни - само трябва да внимаваме да не получим отрицателна нула. Затова викаме функцията fix() преди да върнем всеки резултат (макар и на някои места това да не е нужно).

// Returns -1 if lvalue is less, 0 if equal, or +1 if lvalue is greater.
int
 compare(Long lvalue, Long rvalue) {
    if
 (lvalue.positive !
= rvalue.positive)
        return
 !
lvalue.positive ?
 -
1
 :
 1
;
    return
 absoluteCompare(lvalue,
 rvalue) *
 (lvalue.positive ?
 +
1
 :
 -
1
);
}

Long add(Long lvalue, Long rvalue) {
    Long ret;
    if
 (lvalue.positive =
= rvalue.positive) {
        ret =
 absoluteAdd(lvalue,
 rvalue);
        ret.positive =
 lvalue.positive;
    }
    else {
        ret =
 absoluteSubtract(lvalue,
 rvalue);
        ret.positive =
 absoluteCompare(lvalue,
 rvalue) <
 0
 ?
            rvalue.positive :
 lvalue.positive;
    }
    return
 fix(ret);
}

Long subtract(Long lvalue, Long rvalue) {
    Long ret;
    if
 (lvalue.positive !
= rvalue.positive) {
        ret =
 absoluteAdd(lvalue,
 rvalue);
        ret.positive =
 lvalue.positive;
    }
    else {
        if
 (absoluteCompare(lvalue,
 rvalue) =
=
 -
1) {
            ret =
 absoluteSubtract(rvalue,
 lvalue);
            ret.positive =
 !
rvalue.positive;
        }
        else {
            ret =
 absoluteSubtract(lvalue,
 rvalue);
            ret.positive =
 lvalue.positive;
        }
    }
    return
 fix(ret);
}

Long multiply(Long lvalue, Long rvalue) {
    Long ret =
 absoluteMultiply(lvalue,
 rvalue);
    ret.positive =
 (lvalue.positive =
=
 rvalue.positive);
    return
 fix(ret);
}

Long divide(Long lvalue, Long rvalue) {
    Long ret =
 absoluteDivide(lvalue,
 rvalue);
    ret.positive =
 (lvalue.positive =
=
 rvalue.positive);
    return
 fix(ret);
}

Ефективна имплементация

Предоставяме и що-годе ефективна имплементация, която ползва истинско деление и някои от начините за оптимизиране на бързодействието (база 1,000,000 и отделни имплементации на операциите дълго-с-дълго и дълго-с-късо). Имплементацията е предоставена като клас, който е сравнително удобен/лесен за ползване.
Имплементация и тестове: Long.h | LongTester.cpp

Примерни задачи

Можете да пробвате да решите задачата Crypto, където се налага да правим сметките ползвайки дълги числа.

Допълнителни материали

За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.

Страницата е посетена 9256 пъти.

Дълги числа

Long Numbers

Примерен проблем

Какъв е проблемът?

Дълги числа

Основна идея

Други аритметични операции

База на числата

Трикове

Обратен ред на цифрите

Дълги и Къси числа

Лесно деление

Двоична база

Имплементация

База

Данни

Инициализация

Печатане

Нормализация

Сравнение по абсолютна стойност

Събиране по абсолютна стойност

Изваждане по абсолютна стойност

Умножение по абсолютна стойност

Деление по абсолютна стойност

Операции със знак

Ефективна имплементация

Примерни задачи

Допълнителни материали

Предложете корекция