Bigint

Краен срок:
27.11.2020 17:00
Точки:
15

Тази задача няма да е много практическа, но ще ви даде шанса да правите малко аритметика с Rust и да имплементирате малко built-in trait-ове. Искаме да имплементирате някаква форма на "Big integer". Тоест, число, което може да има теоретично безкрайно много цифри, за разлика от вградените числови типове, които всички си имат някакъв твърд лимит.

Конструиране

Започваме от някаква базова дефиниция на типа:

#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
    sign: i8,
    digits: Vec<u8>,
}

Първото, което е важно да отбележим, е че имате сравнителна свобода във вътрешната имплементация на структурата и на метода. Полетата, които сме дали не са публични -- няма да можем да ги тестваме директно, и няма да се опитваме. Всички тестове ще сравняват един Bigint с друг Bigint или ще викат методи и ще проверяват резултата. Все пак може да следвате полетата, които сме ви дали като насока.

Derive-овете имат следната цел:

  • Debug: За да можем да използваме Bigint в assertion-и.
  • PartialEq, Eq: За да можем да сравняваме две числа.

Идеята на тези конкретни полета е да запазим всяка цифра като отделен u8 и знака на числото като i8, което е или -1 (за отрицателно число) или 1 (за положително). В нашата имплементация, нулата има знак 1, което улеснява някои неща.

В какъв ред са digits? Ваш избор. Не е нужно да мислите твърде много за performance, няма проблеми да викате .reverse() на вектора, когато ви е нужно. Но направете ясен избор в какъв ред ги държите, за да получавате правилни резултати при аритметични операции.

Продължаваме с някои базови методи:

impl Bigint {
    /// Конструира нов Bigint със стойност "0" и положителен знак.
    /// Това може да означава празен вектор с цифри или масив с една цифра `0` -- ваш избор.
    ///
    pub fn new() -> Self {
        todo!()
    }

    /// Конструира нов Bigint с подадените цифри и знак.
    ///
    /// Тук е добро място където можете да вкарате малко валидация и нормализиране на входа -- да
    /// премахнете допълнителни нули или да се погрижите, че нулата винаги има консистентен знак.
    /// Стига да се погрижите винаги да използвате функцията при конструириане на нови Bigint-ове.
    ///
    /// Тази функция НЕ Е публична, така че НЕ Е задължителна -- ако не ви трябва, може смело да я
    /// изтриете.
    ///
    fn from_components(digits: Vec<u8>, sign: i8) -> Self {
        todo!()
    }

    /// Връща `true` ако числото е положително. Нулата не е положителна.
    pub fn is_positive(&self) -> bool {
        todo!()
    }

    /// Връща `true` ако числото е отрицателно. Нулата не е отрицателна.
    pub fn is_negative(&self) -> bool {
        todo!()
    }
}

Както казахме по-горе -- условие, което винаги трябва да е изпълнено е положителната нула и отрицателната нула да са равни. Може да го имплементирате при конструиране, или може да си имплементирате собствен PartialEq, където да направите това сравнение. Само внимавайте с PartialEq -- ще използваме равенство за сравнение на Bigint-ове, така че ако имате бъг там, може да се счупи доста :).

(А можете ли просто да върнете true в собствена имплементация на Bigint, за да минават всички тестове? На теория да, на практика не, така че по-добре не пробвайте :))

Ще има нужда да конвертираме и низове до bigint-ове, така че нека имплементираме FromStr:

use std::str::FromStr;

#[derive(Debug)]
pub struct ParseError;

impl FromStr for Bigint {
    type Err = ParseError;

    /// Очакваме низа да е във формат десетично цяло число с опционален знак, тоест всички тези
    /// неща би трябвало да върнат `Ok` резултат с конструиран Bigint:
    ///
    ///     Bigint::from_str("123") // => положителен знак по подразбиране
    ///     Bigint::from_str("+123")
    ///     Bigint::from_str("-123")
    ///
    /// Това включва нулата, като имате предвид че, както казахме, +0 и -0 трябва да са
    /// еквивалентни.
    ///
    /// Ако подадения низ е празен, това връща същото като да сме подали "0". Ако подадения низ е
    /// само "+" или "-", ваше решение е дали да е нула или да е грешка, няма да го тестваме.
    ///
    /// Ако подадения низ започва с нули, това няма значение -- игнорират се. Тоест, конструиране с
    /// "00123" ще е същото като конструиране с "123".
    ///
    /// Ако сме подали низ, който включва каквито и да е други символи освен цифрите 0-9 (и
    /// опционален начален знак), очакваме да върнете `ParseError`.
    ///
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        todo!()
    }
}

Съветваме да си тествате решението с разнообразни невалидни входове, string processing can be tricky :).

Сравнения

Имплементирайте trait-ове за сравнение на bigint-ове:

use std::cmp::Ordering;

impl PartialOrd for Bigint {
    /// Две цели числа винаги могат да се сравнят, така че "частичното" равенство е същото като
    /// пълното.
    ///
    fn partial_cmp(&self, other: &Bigint) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Bigint {
    /// Ако едното от числата е положително, а другото -- отрицателно, положителното е по-голямо.
    ///
    /// Ако едното от числата има по-голям брой цифри, то ще бъде по-голямото. (Стига да не са нули
    /// -- вероятно е добра идея да се погрижите да няма започващи нули при конструкция.)
    ///
    /// Ако двете числа имат еднакъв брой цифри, лексикографско сравнение на числата ще ви даде
    /// правилен резултат -- от по-значимите цифри към по-малко значимите. Внимавайте в какъв ред
    /// си държите цифритe и дали не трябва да ги обърнете.
    ///
    /// Ако двете числа са отрицателни, сравнението по абсолютна стойност ще е обърнато (-1 е
    /// по-голямо от -2) -- погледнете документацията на `Ordering` за това как лесно можете да
    /// обърнете резултата.
    ///
    fn cmp(&self, other: &Bigint) -> Ordering {
        todo!()
    }
}

Разгледайте документацията на std::cmp::Ordering, че даже и на std::cmp, за да прецените как да имплементирате този trait.

Аритметични операции

Събирането и изваждането са единствените аритметични операции, които ще изискваме, за да не ви създаваме твърде много еднообразна работа.

use std::ops::{Add, Sub};

impl Add for Bigint {
    type Output = Bigint;

    /// За да съберете две числа, първия въпрос е: какви са им знаците?
    ///
    /// - Ако и двете са положителни, събираме ги цифра по цифра и слагаме на резултата положителен
    ///   знак.
    /// - Ако и двете са отрицателни, пак можем да ги съберем цифра по цифра и да сложим
    ///   отрицателен знак на крайния резултат.
    /// - Ако имат различни знаци, намираме по-голямото *по абсолютна стойност*. Изваждаме цифрите
    ///   на по-малкото от по-голямото. Знака на резултата е знака на по-голямото по абсолютна
    ///   стойност. Ако са равни, резултата трябва да е нула (която винаги се очаква да е
    ///   положителна).
    ///
    /// При събиране цифра по цифра, не забравяйте да пренасяте "едно наум" ако резултата е
    /// по-голям от десетична цифра. При различна дължина на списъците от цифри, можете да
    /// запълните с нули, да внимавате с индексите, или нещо по средата.
    ///
    fn add(self, other: Self) -> Self {
        todo!()
    }
}

impl Sub for Bigint {
    type Output = Bigint;

    /// Изваждането често се имплементира като събиране с отрицателен знак. Тоест, `A - B` е
    /// еквивалентно на `A + (-B)`. Можете да имплементирате изваждането като форма на събиране, и
    /// в него да пакетирате логиката. Или можете да проверите знаците и да разделите логиката по
    /// събиране и по изваждане между `add` и `sub`.
    ///
    /// При изваждане, също не забравяйте "едното наум", ако цифрата от която вадите е по-малката,
    /// което ще се преведе до едно "-1" на следващата цифра. Погрижете се винаги да вадите от
    /// по-голямото по абсолютна стойност число, и после сложете какъвто знак се налага.
    ///
    /// Внимавайте с типовете -- изваждане на unsigned от unsigned число може да се счупи.
    ///
    fn sub(self, other: Self) -> Self {
        todo!()
    }
}

Внимавайте да не се оплетете в имплементацията на събиране и изваждане. Има доста дребни детайли и лесно можете да изпуснете някой, ако не карате стъпка по стъпка и ако се опитвате да имплементирате "оптимално" решение. Съветваме да си напишете няколко теста, да имплементирате работещо решение, и чак тогава да мислите дали можете да го промените както на вас ви харесва. Повтаряме, че бързината на решението няма значение за задачата.

Бихте могли да си организирате логиката в отделни помощни функции, които са скрити за външния свят, примерно:

/// Незадължително
fn add_digits(mut left: Vec<u8>, mut right: Vec<u8>) -> Vec<u8> {
    todo!()
}

/// Незадължително
fn subtract_digits(mut larger: Vec<u8>, mut smaller: Vec<u8>) -> Vec<u8>  {
    todo!()
}

Те могат да приемат вход с конкретни характеристики, за който се приема че вече сме приложили някаква логика, примерно при изваждане може да сме се погрижили да намерим по-голямото и по-малкото, или сме запълнили нули за да имат еднаква дължина. Примерно.

Важно е да не забравяте, че това е "bigint", целта му е да съхранява числа, които имат потенциално безкраен брой цифри. Ако по време на събиране или изваждане сумирате цифрите в нормално число, това ще счупи някои тестове. Нарочно не сме тествали с големи числа във всички тестове, но го имайте предвид.

Съвети

  • Отново, не мислете твърде много за performance, освен ако разбира се много не ви сърби :).
  • В тоя ред на мисли (ефективност), пазенето на десетична цифра в u8 е малко wasteful. Бихте могли да пазите числата в base-255, т.е. всяка "цифра" да бъде едно число от 0-255. Трябва повече да внимавате при събиране и пренасяне. Не ви съветваме, с цел да поддържате нещата прости и лесно дебъгваеми, но преценете си.
  • Пишете си тестове. Има edge cases, напишете си няколко извиквания, колкото да пробвате че сте нацелили логиката.
  • Свободни сте да имплементирате и други trait-ове, било то защото ви помагат (примерно може да ви е полезно да имплементирате Neg за някои операции, или Display, за да си печатате числата в човешки вид) или просто защото искате да се пробвате, за да експериментирате с Rust.

Базов тест: 02/test_basic.rs