Довге віднімання

Як від одного числа зі ста цифр відняти інше число зі ста цифр? Звичайний JavaScript number не завжди зможе точно відповісти на це запитання. Проте ми можемо скористатися алгоритмом, який вивчили ще у школі, — відніманням у стовпчик.

У цій статті ми розберемо, навіщо потрібне довге віднімання, перетворимо знайомі дії на алгоритм і реалізуємо його на TypeScript. В інтерактивному playground можна пройти обчислення крок за кроком і побачити, як позичання переходить між розрядами.

Працюватимемо з двома невід’ємними цілими числами A і B, для яких гарантується A ≥ B. Тому результат у цій реалізації завжди буде невід’ємним.

Спробуйте самі

Введіть два невід’ємні цілі числа або виберіть готовий приклад. Перше число має бути не меншим за друге. Натисніть Порахувати, а потім використовуйте повзунок чи кнопки Назад і Далі, щоб пройти віднімання розряд за розрядом.

Для покрокового перегляду зручніше почати з коротких чисел, наприклад 12 − 5. Щоб побачити, як позичання проходить через кілька розрядів, спробуйте 1000 − 1.

Навіщо потрібне довге віднімання

У JavaScript для звичайних числових обчислень найчастіше використовують тип number. Але він не може точно зберігати цілі числа будь-якої довжини.

Найбільше ціле число, з яким JavaScript може безпечно виконувати обчислення, зберігається у властивості Number.MAX_SAFE_INTEGER:

Number.MAX_SAFE_INTEGER;
// 9007199254740991

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

9007199254740992 === 9007199254740993;
// true

Математично це два різні числа, але тип number уже не може надійно їх розрізнити. Велике число може втратити точність ще до того, як потрапить у нашу функцію, а отже, результат віднімання також може виявитися неправильним.

Щоб цього уникнути, зберігатимемо великі числа як рядки. Рядок зберігає кожен символ без змін, тому ми можемо брати по одній цифрі, віднімати їх і поступово формувати точний результат.

У JavaScript також існує BigInt, який у реальному проєкті часто буде простішим рішенням:

1000000000000000000000000n - 1n;
// 999999999999999999999999n

У цій реалізації ми навмисно не використовуємо BigInt. Наша мета — розібратися, як працює арифметика великих чисел усередині, а не лише отримати готову відповідь.

Як ми віднімаємо числа в стовпчик?

Розберімо віднімання на прикладі: 875 − 492 = 383.

Ми рухаємося справа наліво й на кожному кроці віднімаємо цифри одного розряду.

1. Починаємо з крайніх правих цифр — 5 та 2. Отримуємо 5 − 2 = 3 і записуємо 3 у результат.
2. Переходимо до наступної пари — 7 та 9. Отримуємо 7 − 9 = −2. Оскільки різниця від’ємна, позичаємо один десяток: −2 + 10 = 8. Записуємо 8, а позичання передаємо до наступного розряду.
3. Переходимо до цифр 8 та 4. Також враховуємо позичання з попереднього кроку: 8 − 4 − 1 = 3. Записуємо 3. Нового позичання не виникає.

Отримуємо 383. На кожному кроці нам потрібні лише дві поточні цифри та інформація про позичання з попереднього розряду. У програмі це позичання зберігатиметься у змінній borrow.

Перетворюємо дії людини на алгоритм

Тепер перетворімо описані вище дії на точну послідовність кроків, яку зможе виконати програма.

1. Створюємо змінну borrow із початковим значенням 0. У ній зберігатимемо інформацію про позичання з попереднього розряду.
2. Починаємо з останніх символів обох рядків.
3. Перетворюємо поточні символи на числа та зберігаємо їх у змінних digitA і digitB.
4. Віднімаємо від digitA значення digitB і поточне значення borrow.
5. Якщо різниця від’ємна, додаємо до неї 10 і встановлюємо borrow = 1.
6. Якщо різниця невід’ємна, встановлюємо borrow = 0.
7. Додаємо отриману цифру до результату.
8. Переходимо на одну позицію ліворуч в обох рядках.
9. Повторюємо дії, доки в першому рядку залишаються цифри.
10. Перевертаємо зібраний результат і прибираємо початкові нулі.

Обчислення різниці поточного розряду та оновлення позичання виглядають так:

let diff = digitA - digitB - borrow;

if (diff < 0) {
  diff += 10;
  borrow = 1;
} else {
  borrow = 0;
}

Наприклад, якщо digitA = 7, digitB = 9, а borrow = 0, спочатку отримуємо diff = −2. Оскільки різниця від’ємна, додаємо 10. У результат записуємо 8, а в borrow зберігаємо 1 для наступного розряду.

Якщо цифри першого числа достатньо для віднімання, позичання не потрібне. У такому разі різниця одразу стає цифрою результату, а borrow повертається до 0.

Реалізація на TypeScript

Ось повна реалізація чистої функції довгого віднімання:

export const columnSubtraction = (strA: string, strB: string) => {
  let i = strA.length - 1;
  let j = strB.length - 1;
  let borrow = 0;
  let result = "";

  while (i >= 0) {
    const digitA = Number(strA[i]);
    const digitB = j >= 0 ? Number(strB[j]) : 0;

    let diff = digitA - digitB - borrow;

    if (diff < 0) {
      diff += 10;
      borrow = 1;
    } else {
      borrow = 0;
    }

    result += diff;

    i--;
    j--;
  }

  const resultWithoutZero = result
    .split("")
    .reverse()
    .join("")
    .replace(/^0+/, "");

  return resultWithoutZero || "0";
};

Чому числа передаються як рядки

Якщо передати велике значення як number, воно може втратити точність ще до виклику функції. Тому обидва числа передаються як рядки.

Ми не перетворюємо весь рядок на число. На кожному кроці алгоритм перетворює лише один символ від "0" до "9". Одна цифра безпечно поміщається у тип number.

Навіщо потрібні два індекси

Індекси i та j починають з останніх позицій відповідних рядків:

let i = strA.length - 1;
      let j = strB.length - 1;

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

Що відбувається, якщо числа мають різну довжину

За умовою A ≥ B, тому перше число не може мати менше значущих цифр, ніж друге. Але друге число може закінчитися раніше. У такому випадку алгоритм використовує 0:

const digitB = j >= 0 ? Number(strB[j]) : 0;

Наприклад, віднімання 12345 − 67 можна уявити як 12345 − 00067.

Як працює borrow

Змінна borrow зберігає інформацію про позичання з попереднього, правішого розряду. Її значення завжди дорівнює 0 або 1.

Спочатку від поточної цифри першого числа віднімаємо цифру другого числа та попереднє позичання:

let diff = digitA - digitB - borrow;

Якщо diff від’ємне, поточному розряду не вистачає значення. Тоді позичаємо один десяток, додаємо 10 до різниці та передаємоborrow = 1 наступному розряду.

Якщо різниця невід’ємна, нового позичання немає і borrow стає рівним 0.

Чому в умові циклу достатньо i ≥ 0

Основний цикл має таку умову:

while (i >= 0)

За умовою перше число не менше за друге, тому нам достатньо обробити всі цифри першого числа. Коли i стає меншим за 0, усі розряди вже обчислені.

На відміну від переносу в додаванні, позичання не може створити нову цифру ліворуч від першого числа. Після обробки найстаршого розряду цикл має завершитися.

Чому результат потрібно перевернути

Алгоритм рухається справа наліво, але кожну нову цифру додає в кінець рядка. Для 1000 − 1 результат послідовно формується як "9", "99", "999" і "9990".

Цифри збережені у зворотному порядку, тому перед поверненням результат потрібно перевернути:

result.split("").reverse().join("")

Після цього "9990" перетворюється на "0999".

Навіщо прибирати початкові нулі

Запис "0999" математично правильний, але звичайно ми записуємо відповідь як "999". Тому після розвороту прибираємо всі нулі на початку:

.replace(/^0+/, "")

Якщо відняти число саме від себе, наприклад 5 − 5, після видалення нулів залишиться порожній рядок. Тому функція завершується так:

return resultWithoutZero || "0";

Якщо resultWithoutZero порожній, функція поверне "0".

Як працює покрокова візуалізація

Функція columnSubtraction знає лише про арифметику: вона приймає два рядки та повертає готовий результат. Вона нічого не знає про Astro, React, поля введення, кнопки або повзунок.

Для playground потрібно зберігати не лише фінальну відповідь, а й проміжний стан після обробки кожного розряду. Один крок можна описати таким типом:

type SubtractionStep {
  digitA: number;
  digitB: number;
  borrowIn: number;
  rawDiff: number;
  resultDigit: number;
  borrowOut: number;
  partialResult: string;
};

Які дані зберігає один крок

digitA і digitB — цифри, які віднімаємо на поточному кроці.

borrowIn — позичання, яке прийшло з попереднього, правішого розряду. Якщо воно дорівнює 1, цю одиницю потрібно додатково відняти від digitA.

rawDiff — різниця до позичання десятка. Наприклад, для 2 − 5 вона дорівнює −3.

resultDigit — цифра, яку записуємо в результат. Якщо rawDiff = −3, після додавання десятка отримуємо resultDigit = 7.

borrowOut показує, чи потрібно передати позичання наступному розряду. Значення 1 означає, що на наступному кроці від цифри першого числа треба буде додатково відняти одиницю.

partialResult зберігає частину відповіді, яку алгоритм уже встиг обчислити.

Як розділена відповідальність

Рішення складається з трьох частин:

1. columnSubtraction виконує арифметику та повертає готовий результат.
2. traceSubtraction повторює ті самі кроки та формує масив проміжних станів.
3. Playground показує один елемент масиву: steps[currentStepIndex].

Повзунок і кнопки Назад та Далі не запускають арифметику заново. Вони лише змінюють currentStepIndex, після чого React показує відповідний крок із уже готового масиву.

Завдяки такому поділу чиста функція залишається незалежною від інтерфейсу, а playground лише візуалізує дані, які підготував traceSubtraction.

Особливі випадки

12 − 5 = 7

Цей приклад показує одне позичання. У розряді одиниць отримуємо 2 − 5 = −3, тому додаємо десяток і записуємо 7. У наступному розряді враховуємо позичання: 1 − 0 − 1 = 0.

Усередині алгоритму результат спочатку матиме вигляд "07". Початковий нуль потрібно прибрати, щоб повернути "7".

1000 − 1 = 999

Позичання послідовно проходить через кілька нульових розрядів. На кожному із трьох перших кроків алгоритм записує 9 і передає позичання далі ліворуч.

В останньому розряді обчислюємо 1 − 0 − 1 = 0. Після розвороту внутрішній результат матиме вигляд "0999", а після видалення початкового нуля — "999".

100 − 91 = 9

Цей приклад містить граничний проміжний результат: 0 − 9 − 1 = −10. Після позичання десятка отримуємо −10 + 10 = 0 і передаємо позичання до наступного розряду.

Повний внутрішній результат після розвороту дорівнює "009". Алгоритм має прибрати обидва початкові нулі та повернути "9".

55555 − 12349 = 43206

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

Дуже довгі числа

Такий приклад демонструє головну користь алгоритму: він працює за межами Number.MAX_SAFE_INTEGER, оскільки не перетворює весь рядок на тип number.

Довжина чисел не змінює принцип роботи. Алгоритм так само рухається справа наліво, обробляє по одному розряду та передає borrow між сусідніми кроками.

Складність алгоритму

Позначимо кількість цифр першого числа як n. За умовою A ≥ B, тому перше число має не менше значущих цифр, ніж друге.

• Time: O(n) — кожен розряд першого числа обробляється один раз.
• Space: O(n) — потрібно зберігати рядок результату.

Результат віднімання не може мати більше цифр, ніж перше число. Після видалення початкових нулів він може виявитися коротшим. Наприклад, результат 1000 − 1 містить три цифри, а результат 100 − 91 — лише одну.

Висновок

Віднімання у стовпчик здається звичайною шкільною вправою, але насправді це повноцінний алгоритм. У нього є початковий стан, точний порядок кроків, змінна для позичання та умова завершення.

Довге віднімання дозволяє точно працювати з цілими числами, які не поміщаються в безпечний діапазон number. Замість однієї великої операції алгоритм виконує багато маленьких: віднімає дві цифри, враховує позичання та рухається справа наліво.

Довге додавання і довге віднімання використовують однакову загальну ідею: складне обчислення над великими числами розбивається на прості операції над окремими цифрами. Різниця полягає в тому, яку інформацію ми передаємо до наступного розряду: перенос у додаванні або позичання у відніманні.