Если в JavaScript сложить два небольших числа, компьютер легко с этим справится. Но если попросить его сложить числа, например, на 500 знаков, то будет ошибка: язык не рассчитан на такие огромные числа.
А вот человеку неважно, какой длины числа складывать: хоть 100 знаков, хоть 500, хоть тысяча. Если есть лист бумаги, ручка и достаточно времени, человек сложит любые числа. Сегодня мы научим компьютер тоже так делать.
Чтобы было понятнее, запустите этот JavaScript-код в консоли браузера и посмотрите на ошибку:
var a = 7983577598237509273059298347502798357759823750927305929834750279835345234952394529345238721948571908745082345234523452345234523452934570293452345234577598237509273052345345345929834750279835775982375092730592983475079835775982375092730592983475027983577598237509273059298347502798353452349523945293452387219485719087450823452345234523452345234529345702934523452345775982375092730523453453459298347502798357759823750927305929834750;
var b = 92385482375823598236459872635923854823758235982364598726359238548237582323412345293457293745092734509273405972923453872430918723545983452435729752934579238475928345245734523645987268983592385482375823598236459872639;
var c;
c = a+b;
console.log(c);Вы и так это знаете, но нам нужно для будущего алгоритма:
- Записываем сначала число подлиннее, а под ним — число покороче (или просто друг под другом, если они одной длины).
- Записывать надо с выравниванием по правой стороне.
- Складываем числа по разрядам по очереди: единицы с единицами, десятки с десятками и так далее.
- Если после разрядного сложения получилось двузначное число, единица добавляется в следующий разряд и учитывается при следующем сложении
- Так шаг за шагом мы перебираем все разряды, и у нас в результате получается сумма.
Даже если у нас тысяча разрядов, всё, что мы делаем на каждом шаге, — это складываем два числа от 0 до 9 и переносим единицу, если она появилась.
Простой пример сложения в столбик с переносом единицы:
Почему компьютеру сложно работать с такими длинными числами и как это исправить
Всё дело в размере памяти, которую компьютер выделяет для переменной. Если это не специальный математический язык для обработки огромных чисел, то обычно на целое число выделяется до 8 байт. Этого хватает для большинства бытовых задач, но для экстремально больших чисел этого мало — нужны специальные библиотеки.
Лайфхак: работать с числами как со строками
Мы не будем использовать библиотеки, а пойдём другим путем: мы будем представлять число не как число, а как строку, состоящую из цифр. У строк нет таких ограничений, как у чисел: строки могут быть любой длины. Если мы научимся работать с этими строками как будто это числа, то сможем складывать что угодно любого размера.
Вот такое мы и будем делать для JavaScript.
Что делаем
Мы напишем на JavaScript код, который будет запрашивать у пользователя два целых положительных числа и складывать их. Логика будет такая:
- Просим ввести числа, но на самом деле мы их получим в виде строк.
- Сразу проверяем, нет ли в строке чего-то кроме цифр. Если есть — говорим, что это не число, и останавливаемся.
- Перебираем все разряды справа налево и складываем числа попарно и результат добавляем к строке с общим результатом.
- Если в результате такого мини-сложения получилось число больше 10 — переносим единицу в следующий разряд.
- Делаем так до тех пор, пока не закончатся разряды в числах.
В итоге мы получим строку с результатом сложения — это и будет наш ответ.
Запрашиваем строки и проверяем, числа это или нет
В самом начале нам нужно просто получить от пользователя две строки и проверить, нет ли там лишних символов кроме цифр. Для такой проверки напишем короткую функцию, в основе которой будет лежать такая команда:
isNaN() — она пробует перевести в число ту строку, которая стоит в скобках.
Если не получилось перевести, то команда возвращает true, а если получилось — false. Так мы проверим каждую строку, и, если в какой-то из них не только числа, — останавливаем скрипт и выводим ошибку.
Теперь про остановку скрипта. Один из приёмов, чтобы остановить скрипт в любом месте, — сгенерировать ошибку вручную. Это можно сделать так:
throw new Error('Текст ошибки');
Как только скрипт встречает такое, он выбрасывает текст ошибки в консоль и останавливается:
Запишем всё это на JavaScript:
// проверка, это число или нет
function isNumber(s){
// по умолчанию считаем, что в функцию передали число
flag = true;
// если это пустая строка, то возвращаем false — признак того, что это не число
if (s.length = 0) {return(false)}
// раз дошли досюда, то строка не пустая и можно проверить все символы подряд
for (let i = 0; i < s.length; i++) {
// переводим символ в число и смотрим, будет ли ошибка
// если ошибка есть — помечаем, что это не число
if (isNaN(s[i]) == true) {flag = false};
}
// возвращаем результат обработки, число это или нет
return(flag)
}
// запрашиваем первое
var num1 = prompt("Введите первое слагаемое");
// проверяем, число это или нет
if (!isNumber(num1)) {
// если нет — выводим сообщение
alert('Это не число');
// останавливаем программу с ошибкой
throw new Error('Первое слагаемое — не число');
}
// то же самое делаем со вторым числом
var num2 = prompt("Введите второе слагаемое");
if (!isNumber(num2)) {
alert('Это не число');
throw new Error('Второе слагаемое — не число');
}Выравниваем числа по длине
Чтобы нам было удобнее складывать в столбик, пойдём на такую хитрость: в то число, в котором меньше символов, мы добавим нули спереди. Они не изменят конечный результат, но с ними алгоритм получится гораздо проще. А если по длине числа одинаковые, то пусть так и остаётся.
// делаем числа одной длины, чтобы удобно было складывать
// если второе длиннее первого
if (num1.length < num2.length) {
// то получаем разницу в длине чисел
var diff = num2.length - num1.length
// и добавляем впереди первого числа столько же нулей
for (let i = 0; i < diff; i++) {
num1 = '0' + num1;
}
// то же самое — если первое длиннее второго
} else if (num1.length > num2.length) {
var diff = num1.length - num2.length
for (let i = 0; i < diff; i++) {
num2 = '0' + num2;
}
} Складываем разряды
Вспомогательная штука, которая нам ещё понадобится, — функция сложения двух чисел. Её особенность в том, что туда попадают только разрядные числа — от 0 до 9. Ещё туда может попасть дополнительная единица при переносе разряда. Но в любом случае это очень маленькие числа, с которыми компьютер гарантированно справится.
Особенность функции в том, что она и на вход получает две строки, и на выходе тоже возвращает строку, а не числа. Если про это забыть и вернуть просто результат в виде числа, то придётся это обрабатывать отдельно в основном алгоритме, а это неэффективно.
// складываем два числа, которые на самом деле — строки
function plus(a,b) {
// тут будет результат
var result ='';
// переводим строки в числа
x = parseInt(a);
y = parseInt(b);
// получаем результат
result += x+y;
// и возвращаем ответ в виде строки
return(String(result));
}Основной алгоритм
Мы сделали всю предварительную работу:
- получили числа от пользователя;
- убедились в том, что это числа;
- сделали их одинаковой длины;
- научились складывать разряды.
Теперь сделаем главное: научим компьютер складывать в столбик. Если при сложении разрядов получается число от 0 до 9, то всё просто: мы приписываем его к результату и идём к следующей паре разрядов. Но если мы складываем, например, 9 и 3, то получим двузначное число и единицу надо будет переносить в следующий разряд. Обработка такого переноса — самое сложное место в этом алгоритме.
Чтобы обработать разрядный перенос, мы заведём отдельную переменную. Как только у нас появляется перенос, мы устанавливаем флаг и по нему обрабатываем этот перенос. Читайте комментарии, чтобы разобраться в алгоритме:
// складываем любые два целых числа
function bigplus(a,b) {
// признак переноса
var carry = false;
// тут будет наш результат
var summ = '';
// переменная для промежуточных вычислений
var temp = '';
// число, которое добавится к результату
var digit;
// вспомогательная переменная, используем для складывания перенесённой единицы
var plusOne = '';
// перебираем все символы в числах по очереди
for (let i = 0; i < b.length; i++) {
// если нужно перенести единицу в следующий разряд
if (carry) {
// добавляем её к следующему разряду в первом числе
plusOne = plus(a[a.length -1 - i],'1');
// и складываем два числа уже с учётом переноса
temp = plus(plusOne, b[b.length -1 - i]);
// если единицу переносить не нужно
} else {
// то просто складываем два числа
temp = plus(a[a.length -1 - i], b[b.length -1 - i]);
}
// если после сложения получилось однозначное число
if (temp.length == 1) {
// просто добавляем его к результату
summ = temp + summ;
// и переноса нет
carry = false;
// если число двузначное
} else {
// помечаем, что будет перенос, потому что получилось больше 10
carry = true;
// получаем единицы, например, если у нас получилось 12, то берём оттуда 2
digit = temp[1];
// и добавляем эти единицы к результатам
summ = digit + summ;
//
}
}
// после всего цикла обрабатываем последний перенос, если он получился
if (carry) {
// просто приписываем единицу к результату
summ = '1' + summ;
}
// возвращаем результат
return(summ);
}Считаем любую сумму
У нас есть все кирпичики программы. Собираем их в нужном порядке и получаем готовый скрипт. Чтобы проверить, работает он или нет, скормим ему длинные числа из самого начала статьи, где JavaScript сразу сломался:
// проверка, это число или нет
function isNumber(s){
// по умолчанию считаем, что в функцию передали число
flag = true;
// если это пустая строка, то возвращаем false — признак того, что это не число
if (s.length = 0) {return(false)}
// раз дошли досюда, то строка не пустая и можно проверить все символы подряд
for (let i = 0; i < s.length; i++) {
// переводим символ в число и смотрим, будет ли ошибка
// если ошибка есть — помечаем, что это не число
if (isNaN(s[i]) == true) {flag = false};
}
// возвращаем результат обработки, число это или нет
return(flag)
}
// складываем два числа, которые на самом деле — строки
function plus(a,b) {
// тут будет результат
var result ='';
// переводим строки в числа
x = parseInt(a);
y = parseInt(b);
// получаем результат
result += x+y;
// и возвращаем ответ в виде строки
return(String(result));
}
// складываем любые два целых числа
function bigplus(a,b) {
// признак переноса
var carry = false;
// тут будет наш результат
var summ = '';
// переменная для промежуточных вычислений
var temp = '';
// число, которое добавится к результату
var digit;
// вспомогательная переменная, используем для складывания перенесённой единицы
var plusOne = '';
// перебираем все символы в числах по очереди
for (let i = 0; i < b.length; i++) {
// если нужно перенести единицу в следующий разряд
if (carry) {
// добавляем её к следующему разряду в первом числе
plusOne = plus(a[a.length -1 - i],'1');
// и складываем два числа уже с учётом переноса
temp = plus(plusOne, b[b.length -1 - i]);
// если единицу переносить не нужно
} else {
// то просто складываем два числа
temp = plus(a[a.length -1 - i], b[b.length -1 - i]);
}
// если после сложения получилось однозначное число
if (temp.length == 1) {
// просто добавляем его к результату
summ = temp + summ;
// и переноса нет
carry = false;
// если число двузначное
} else {
// помечаем, что будет перенос, потому что получилось больше 10
carry = true;
// получаем единицы, например, если у нас получилось 12, то берём оттуда 2
digit = temp[1];
// и добавляем эти единицы к результатам
summ = digit + summ;
//
}
}
// после всего цикла обрабатываем последний перенос, если он получился
if (carry) {
// просто приписываем единицу к результату
summ = '1' + summ;
}
// возвращаем результат
return(summ);
}
// запрашиваем первое
var num1 = prompt("Введите первое слагаемое");
// проверяем, число это или нет
if (!isNumber(num1)) {
// если нет — выводим сообщение
alert('Это не число');
// останавливаем программу с ошибкой
throw new Error('Первое слагаемое — не число');
}
// то же самое делаем со вторым числом
var num2 = prompt("Введите второе слагаемое");
if (!isNumber(num2)) {
alert('Это не число');
throw new Error('Второе слагаемое — не число');
}
// делаем числа одной длины, чтобы удобно было складывать
// если второе длиннее первого
if (num1.length < num2.length) {
// то получаем разницу в длине чисел
var diff = num2.length - num1.length
// и добавляем впереди первого числа столько же нулей
for (let i = 0; i < diff; i++) {
num1 = '0' + num1;
}
// то же самое — если первое длиннее второго
} else if (num1.length > num2.length) {
var diff = num1.length - num2.length
for (let i = 0; i < diff; i++) {
num2 = '0' + num2;
}
}
// считаем сумму и выводим результат
alert(bigplus(num1,num2));
