Многоразрядные числа и длинная арифметика

Как считать с числами, которые не помещаются ни в один тип. 11 класс, углублённый уровень — пара шестнадцатая.

Уроки 31–32 поурочного плана: «Многоразрядные целые числа, задачи длинной арифметики» и практическая работа «Реализация вычислений с многоразрядными числами». На прошлой паре искали простые числа до миллионов. Сегодня — числа в сотни и тысячи цифр: как их хранить и как с ними считать.

Когда числа не помещаются

целый тип	наибольшее число	цифр
32 бита (int в C++)	2 147 483 647	10
64 бита (long long)	9 223 372 036 854 775 807	19

Как хранить длинное число

Список цифр младшими вперёд: первой стоят единицы, потом десятки, сотни…

8497 →

a[i] — цифра при 10ⁱ: номер элемента совпадает с номером разряда.

Блоками по несколько цифр

Хранить по одной цифре расточительно: в элемент списка помещается и 3, и 4, и 9 цифр. Блоки по три цифры — это система счисления с основанием 1000.

Сложение столбиком

Идём от младшего разряда. В разряд пишем последнюю цифру суммы, а перенос уходит в следующий разряд.

x = a[i] + b[i] + p, цифра — x % 10, перенос — x // 10.
Перенос при сложении — 0 или 1: больше 9 + 9 + 1 = 19 не бывает.
Перенос из старшего разряда — новая цифра: сумма n-значных бывает n + 1-значной.

Вычитание и умножение на однозначное

Вычитание — заём

Цифра меньше вычитаемой — занимаем единицу у старшего разряда и прибавляем 10. Над разрядом, у которого заняли, — «−1».

Умножение на цифру

x = a[i]·d + p, цифра — x % 10, перенос — x // 10. Перенос бывает до 8: 9·9 + 8 = 89.

Сложение в программе

a — это 8497, b — 865, оба младшими вперёд. Список a не короче b; — когда цифры b кончились.

Умножение длинного на короткое

4096·7 = 28 672: a станет [2, 7, 6, 8, 2]. Цифры пишутся прямо на место старых.

Сколько цифр и сколько это стоит

Сколько цифр

У натурального x цифр ⌊lg x⌋ + 1. У mⁿ — ⌊n·lg m⌋ + 1.

2¹⁰⁰: 100·0,30103 = 30,103 → 31 цифра.

Произведение m-значного и n-значного — m + n − 1 или m + n: 10·10 = 100, 99·99 = 9801.

Сколько действий

Сложение n-значных — по действию на разряд: порядка n.

Умножение столбиком m-значного на n-значное — каждая цифра на каждую: порядка m·n.

Блоки по k цифр сокращают сложение в k раз, а умножение — в k·k раз.

Практическая работа: числа в тысячи цифр

int в Python длинный: 7¹²³⁴ — число из 1043 цифр, считается мгновенно. Строка s — его десятичная запись.

что спросили	что печатаем
сумма цифр	k после цикла по s
сколько цифр	len(s)
сколько раз цифра 0	s.count('0')
первые пять цифр	s[:5]
n! или Фибоначчи	сначала цикл, потом str()

То же своим списком цифр

Что верно, а что нет

Верно

Цифры удобно хранить младшими вперёд.
Сумма двух n-значных — не больше n + 1 цифры.
Умножение столбиком — порядка m·n действий.
int в Python длинный сам.

Неверно

«Перенос при сложении бывает 2». Не больше 1.
«[3, 2, 1] младшими вперёд — это 321». Это 123.
«Блок 5 внутри числа — это 500». Это 005.
«У 2ⁿ ровно n цифр». У 2¹⁰ — четыре.

Что делаем дальше

Обзорный практикум — шесть задач, все сразу на странице, в любом порядке: понятия, переносы и займы столбиком, длинное число в списке, что напечатает программа, сколько цифр, практическая работа.
Столбики — на черновике, как на слайдах. Код в задачах — картинкой, его читают.
Шестой вопрос — практическая работа: свою программу пишем в IDLE.
Ответ везде — целое число, без пробелов между разрядами.

Отметка: закрыто 6 из 6 — «5», 5 — «4», 3 или 4 — «3». Исправленная задача не засчитывается — за ошибку приходит новая, добирать можно до пятёрки.

За работу

Практикум «Многоразрядные числа и длинная арифметика» — в общей папке и на сайте. Не успел на уроке — пройди дома: вариант будет другой, сдаётся тем же кодом.

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