Skip to content

Latest commit

 

History

History
93 lines (74 loc) · 7.67 KB

assignment_6.md

File metadata and controls

93 lines (74 loc) · 7.67 KB
Практична робота №6

Розділяй, володарюй, перемножуй

Мета роботи:

Попрактикуватись в написанні алгоритмів типу "розділяй та володарюй" та прикладі алгоритму множення Карацуби, розібратись та реалізувати довгу арифметику на C#.

Трохи теорії

Ми з вами звикли, що у мовах програмування для відображення цілих чисел є різні типи даних - наприклад, int, long, byte тощо. Вони відрізняються в першу чергу кількістю байтів, а отже і діапазоном значень, що можуть представляти. Але що робити в ситуації, коли потрібно оперувати дуже великими числами? Наприклад, якщо для якогось наукового обчислення потрібно дізнатись точне, а не наближене значення виразу 74239472935792837 * 247389348784828974? Жоден із стандартних типів даних у C# не в змозі зберегти точний (не приблизний, бо приблизний може відобразити double) результат?

Набір алгоритмів, що дозволяють виконувати математичні операції для чисел, розмірність яких більша за максимальну розмірність обсичлювальної платформи називається довгою арифметикою (вікі). Фактично, ідея полягає в тому, щоб написати потрібні алгоритми множення, додавання, віднімання тощо програмно, а не розраховувати на можливості платформи. Довга арифметика має своє використання у криптографії, математичних пакетах та у системах з низькою розрядністю (наприклад, якщо на мікроконтролері що працює з 8-бітними числами треба перемножити більші числа).

Завдання

  1. Почніть з наступного коду:
public class BigInteger
{
    private int[] _numbers;

    public BigInteger(string value)
    {
        // convert here string representation to inner int array IN REVERSED ORDER
        // for example, "123434" must be converted to _numbers = {4, 3, 4, 3, 2, 1}
    }
}

Допишіть код в конструктор класу, що буде пертворювати рядок з числом на масив, значеннями якого будуть розряди числа. Після цього ви зможете створювати нове число:

var x = new BigInteger("1313234242425");
  1. Допишіть в клас метод ToString():
public override string ToString()
{
    // convert array back to string and return it
}

Метод має повернути рядок, що буде в зворотньому напрямку представляти число з масиву. Після цього ви зможете робити так:

Console.WriteLine(x); // 1313234242425
  1. Допишіть в клас методи для додавання та віднімання
    public BigInteger Add(BigInteger another)
    {
        // return new BigInteger, result of current + another
    }
    
    public BigInteger Sub(BigInteger another)
    {
        // return new BigInteger, result of current - another
    }

Всередині кожного метода реалізуйте звичайний алгоритм додавання або віднімання в стовбчик - почергова операція над кожним розрядом числа (які лежать в масиві) з переносом розрядів за необхідністю. Подумайте, як можна представити відʼємне число (наприклад, окремим булевим полем у BigInteger)

  1. Насправді, C# дозволяє для власних класів створювати не тільки методи з назвами, але і звичні нам символьні оператори типу + або -. Якщо ви тепер додасте до класу наступну коснтрукцію:
 public static BigInteger operator +(BigInteger a, BigInteger b) => a.Add(b);

То зможете користуватися не тільки методом, а звичним знаком!

var y = new BigInteger("23") + new BigInteger("45");

  1. Тепер час перейти до цікавішого - додати операцію множення. Ми будемо реалізовувати не звичне множення в стовбчик, а більш оптимізований та ефективний алгоритм Карацуби. Для початку, подивіться гарне відео зі стенфорського курсу, та вікі якщо хочете заглибитись трошки більше в історію та теорію, то і це відео.

  2. Напишіть консольну програму, що зчитує у користувача арифметичний вираз довільної довжини (з одним оператором) та виводить результат. Наприклад:

> 1789234569 * 16782345
< 30027551822884305

За додатковий бал, модифікуйте свою стару програму обчислення довільного арифметичного виразу (з практичної №1), щоб вона працювала з довгою арифметикою

Контрольні питання

  • Чим відрізняються від інших алгоритми типу "розділяй та володарюй"? Наведіть декільки прикладів таких алгоритмів.
  • Що таке довга арифметика?
  • Як працює алгоритм Карацуби та наскільки він простіший за множення "в стовбчик"?
  • Як у C# можно додати підтримку символьних операторів до класів?

Оцінювання

Максимальний бал - 8 (+1 додатковий):

  • Реалізація BigInteger та консольної програми - 2 бали;
  • Алгоритм множення Карацуби - _2 бали;
  • Відповіді на теоретичні питання - 2 бали;
  • Виконання додаткового практичного завдання при здачі - 2 бали;
  • Модифікація калькулятора з першої роботи для підтримки великих чисел - +1 бал;