Учим компьютер складывать числа любой длины

Учим компьютер складывать числа любой длины

Человек умеет складывать в столбик, а компьютер — нет

Если в JavaScript сложить два небольших числа, компьютер легко с этим справится. Но если попросить его сложить числа, например, на 500 знаков, то будет ошибка: язык не рассчитан на такие огромные числа. 

А вот человеку неважно, какой длины числа складывать: хоть 100 знаков, хоть 500, хоть тысяча. Если есть лист бумаги, ручка и достаточно времени, человек сложит любые числа. Сегодня мы научим компьютер тоже так делать.

Чтобы было понятнее, запустите этот JavaScript-код в консоли браузера и посмотрите на ошибку:

var a = 7983577598237509273059298347502798357759823750927305929834750279835345234952394529345238721948571908745082345234523452345234523452934570293452345234577598237509273052345345345929834750279835775982375092730592983475079835775982375092730592983475027983577598237509273059298347502798353452349523945293452387219485719087450823452345234523452345234529345702934523452345775982375092730523453453459298347502798357759823750927305929834750;
var b = 92385482375823598236459872635923854823758235982364598726359238548237582323412345293457293745092734509273405972923453872430918723545983452435729752934579238475928345245734523645987268983592385482375823598236459872639;
var c;
c = a+b;
console.log(c);

Вы и так это знаете, но нам нужно для будущего алгоритма:

  1. Записываем сначала число подлиннее, а под ним — число покороче (или просто друг под другом, если они одной длины).
  2. Записывать надо с выравниванием по правой стороне.
  3. Складываем числа по разрядам по очереди: единицы с единицами, десятки с десятками и так далее.
  4. Если после разрядного сложения получилось двузначное число, единица добавляется в следующий разряд и учитывается при следующем сложении
  5. Так шаг за шагом мы перебираем все разряды, и у нас в результате получается сумма.

Даже если у нас тысяча разрядов, всё, что мы делаем на каждом шаге, — это складываем два числа от 0 до 9 и переносим единицу, если она появилась. 

Простой пример сложения в столбик с переносом единицы:

Учим компьютер складывать числа любой длины

Почему компьютеру сложно работать с такими длинными числами и как это исправить

Всё дело в размере памяти, которую компьютер выделяет для переменной. Если это не специальный математический язык для обработки огромных чисел, то обычно на целое число выделяется до 8 байт. Этого хватает для большинства бытовых задач, но для экстремально больших чисел этого мало — нужны специальные библиотеки. 

Лайфхак: работать с числами как со строками

Мы не будем использовать библиотеки, а пойдём другим путем: мы будем представлять число не как число, а как строку, состоящую из цифр. У строк нет таких ограничений, как у чисел: строки могут быть любой длины. Если мы научимся работать с этими строками как будто это числа, то сможем складывать что угодно любого размера.

Вот такое мы и будем делать для JavaScript.

Что делаем

Мы напишем на JavaScript код, который будет запрашивать у пользователя два целых положительных числа и складывать их. Логика будет такая:

  1. Просим ввести числа, но на самом деле мы их получим в виде строк.
  2. Сразу проверяем, нет ли в строке чего-то кроме цифр. Если есть — говорим, что это не число, и останавливаемся.
  3. Перебираем все разряды справа налево и складываем числа попарно и результат добавляем к строке с общим результатом.
  4. Если в результате такого мини-сложения получилось число больше 10 — переносим единицу в следующий разряд.
  5. Делаем так до тех пор, пока не закончатся разряды в числах.

В итоге мы получим строку с результатом сложения — это и будет наш ответ.

Запрашиваем строки и проверяем, числа это или нет

В самом начале нам нужно просто получить от пользователя две строки и проверить, нет ли там лишних символов кроме цифр. Для такой проверки напишем короткую функцию, в основе которой будет лежать такая команда:

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));

Текст:

Михаил Полянин

Редактор:

Максим Ильяхов

Художник:

Алексей Сухов

Корректор:

Ирина Михеева

Вёрстка:

Кирилл Климентьев

Соцсети:

Виталий Вебер

Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
medium