Человек умеет складывать в столбик, а компьютер — нет
Если в JavaScript сложить два небольших числа, компьютер легко с этим справится. Но если попросить его сложить числа, например, на 500 знаков, то будет ошибка: язык не рассчитан на такие огромные числа.
А вот человеку неважно, какой длины числа складывать: хоть 100 знаков, хоть 500, хоть тысяча. Если есть лист бумаги, ручка и достаточно времени, человек сложит любые числа. Сегодня мы научим компьютер тоже так делать.
Чтобы было понятнее, запустите этот JavaScript-код в консоли браузера и посмотрите на ошибку:
Как работает сложение в столбик
Вы и так это знаете, но нам нужно для будущего алгоритма:
- Записываем сначала число подлиннее, а под ним — число покороче (или просто друг под другом, если они одной длины).
- Записывать надо с выравниванием по правой стороне.
- Складываем числа по разрядам по очереди: единицы с единицами, десятки с десятками и так далее.
- Если после разрядного сложения получилось двузначное число, единица добавляется в следующий разряд и учитывается при следующем сложении
- Так шаг за шагом мы перебираем все разряды, и у нас в результате получается сумма.
Даже если у нас тысяча разрядов, всё, что мы делаем на каждом шаге, — это складываем два числа от 0 до 9 и переносим единицу, если она появилась.
Простой пример сложения в столбик с переносом единицы:
Почему компьютеру сложно работать с такими длинными числами и как это исправить
Всё дело в размере памяти, которую компьютер выделяет для переменной. Если это не специальный математический язык для обработки огромных чисел, то обычно на целое число выделяется до 8 байт. Этого хватает для большинства бытовых задач, но для экстремально больших чисел этого мало — нужны специальные библиотеки.
Лайфхак: работать с числами как со строками
Мы не будем использовать библиотеки, а пойдём другим путем: мы будем представлять число не как число, а как строку, состоящую из цифр. У строк нет таких ограничений, как у чисел: строки могут быть любой длины. Если мы научимся работать с этими строками как будто это числа, то сможем складывать что угодно любого размера.
Вот такое мы и будем делать для JavaScript.
Что делаем
Мы напишем на JavaScript код, который будет запрашивать у пользователя два целых положительных числа и складывать их. Логика будет такая:
- Просим ввести числа, но на самом деле мы их получим в виде строк.
- Сразу проверяем, нет ли в строке чего-то кроме цифр. Если есть — говорим, что это не число, и останавливаемся.
- Перебираем все разряды справа налево и складываем числа попарно и результат добавляем к строке с общим результатом.
- Если в результате такого мини-сложения получилось число больше 10 — переносим единицу в следующий разряд.
- Делаем так до тех пор, пока не закончатся разряды в числах.
В итоге мы получим строку с результатом сложения — это и будет наш ответ.
Запрашиваем строки и проверяем, числа это или нет
В самом начале нам нужно просто получить от пользователя две строки и проверить, нет ли там лишних символов кроме цифр. Для такой проверки напишем короткую функцию, в основе которой будет лежать такая команда:
isNaN() — она пробует перевести в число ту строку, которая стоит в скобках.
Если не получилось перевести, то команда возвращает true, а если получилось — false. Так мы проверим каждую строку, и, если в какой-то из них не только числа, — останавливаем скрипт и выводим ошибку.
Теперь про остановку скрипта. Один из приёмов, чтобы остановить скрипт в любом месте, — сгенерировать ошибку вручную. Это можно сделать так:
throw new Error('Текст ошибки');
Как только скрипт встречает такое, он выбрасывает текст ошибки в консоль и останавливается:
Запишем всё это на JavaScript:
Выравниваем числа по длине
Чтобы нам было удобнее складывать в столбик, пойдём на такую хитрость: в то число, в котором меньше символов, мы добавим нули спереди. Они не изменят конечный результат, но с ними алгоритм получится гораздо проще. А если по длине числа одинаковые, то пусть так и остаётся.
Складываем разряды
Вспомогательная штука, которая нам ещё понадобится, — функция сложения двух чисел. Её особенность в том, что туда попадают только разрядные числа — от 0 до 9. Ещё туда может попасть дополнительная единица при переносе разряда. Но в любом случае это очень маленькие числа, с которыми компьютер гарантированно справится.
Особенность функции в том, что она и на вход получает две строки, и на выходе тоже возвращает строку, а не числа. Если про это забыть и вернуть просто результат в виде числа, то придётся это обрабатывать отдельно в основном алгоритме, а это неэффективно.
Основной алгоритм
Мы сделали всю предварительную работу:
- получили числа от пользователя;
- убедились в том, что это числа;
- сделали их одинаковой длины;
- научились складывать разряды.
Теперь сделаем главное: научим компьютер складывать в столбик. Если при сложении разрядов получается число от 0 до 9, то всё просто: мы приписываем его к результату и идём к следующей паре разрядов. Но если мы складываем, например, 9 и 3, то получим двузначное число и единицу надо будет переносить в следующий разряд. Обработка такого переноса — самое сложное место в этом алгоритме.
Чтобы обработать разрядный перенос, мы заведём отдельную переменную. Как только у нас появляется перенос, мы устанавливаем флаг и по нему обрабатываем этот перенос. Читайте комментарии, чтобы разобраться в алгоритме:
Считаем любую сумму
У нас есть все кирпичики программы. Собираем их в нужном порядке и получаем готовый скрипт. Чтобы проверить, работает он или нет, скормим ему длинные числа из самого начала статьи, где JavaScript сразу сломался: