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

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

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

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

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

Для покрокового перегляду зручніше почати з коротких чисел, наприклад95 + 5 або 500 + 500.

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

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

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

Number.MAX_SAFE_INTEGER;
// 9007199254740991

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

9007199254740992 === 9007199254740993;
// true

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

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

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

999999999999999999999999n + 1n;
// 1000000000000000000000000n

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

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

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

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

1. Починаємо з крайніх правих цифр — 2 та 5. Отримуємо 2 + 5 = 7 і записуємо 7 у результат.
2. Переходимо до наступної пари — 9 та 7. Отримуємо 9 + 7 = 16. Записуємо 6, а 1 переносимо до наступного розряду.
3. Додаємо 4 та 8, а також 1, яку перенесли з попереднього кроку: 4 + 8 + 1 = 13. Записуємо 3, а 1 знову переносимо.
4. Цифр більше не залишилося, але після останнього кроку залишився перенос — 1. Записуємо його на початку результату.

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

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

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

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

Для отримання цифри результату та нового переносу потрібні дві формули:

const resultDigit = sum % 10;
const carryOut = Math.floor(sum / 10);

Якщо сума поточного стовпчика дорівнює 16, вираз16 % 10 поверне 6 — цифру результату. Вираз Math.floor(16 / 10) поверне 1 — перенос до наступного розряду.

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

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

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

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

    const sum = digitA + digitB + carry;

    result += sum % 10;
    carry = Math.floor(sum / 10);

    i--;
    j--;
  }

  return result.split("").reverse().join("");
};

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

Якщо передати велике значення як number, воно може втратити точність ще до виклику функції. Ми не перетворюємо весь рядок на число: на кожному кроці перетворюється лише одна цифра від 0 до 9.

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

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

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

Якщо в одному рядку цифри вже закінчилися, алгоритм використовує 0. Наприклад, додавання 95 + 5 можна уявити як 95 + 05.

Для чого carry в умові циклу

Цикл працює, доки залишилася хоча б одна цифра або перенос. У прикладі 999 + 1 = 1000 після обробки всіх цифр у carry все ще залишається 1. Без цієї перевірки остання одиниця не потрапила б у результат.

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

Алгоритм рухається справа наліво, але кожну цифру додає в кінець рядка. Для 492 + 875 результат послідовно формується як"7", "76", "763" і "7631". Тому перед поверненням рядок потрібно перевернути.

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

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

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

type AdditionStep = {
  index: number;
  digitA: number;
  digitB: number;
  carryIn: number;
  sum: number;
  resultDigit: number;
  carryOut: number;
  partialResult: string;
};

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

1. columnAddition повертає готовий результат.
2. traceAddition формує масив проміжних станів.
3. Playground показує стан steps[currentStep].

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

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

95 + 5 = 100

Показує додавання чисел різної довжини та появу нового розряду.

500 + 500 = 1000

Показує, що нулі всередині результату не можна пропускати.

999999 + 1 = 1000000

Один перенос проходить через усі розряди. На кожному кроці алгоритм записує 0 і знову переносить 1 ліворуч.

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

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

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

Позначимо довжину більшого з двох чисел як n.

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

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

Висновок

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

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

Цей самий підхід можна використати і для довгого віднімання, але замість переносу там доведеться працювати з позикою.