Длинная арифметика. Сложение, вычитание, умножение на короткое/длинное число

Длинная арифметика

Числа, для представления которых в стандартных типах данных не хватает количества разрядов, называются длинными. Реализация арифметических операций над такими «длинными» числами называется длинной арифметикой. Задачи на «длинную» арифметику возникают, когда разрядности стандартных типов данных (целые, длинные целые, вещественные числа) не хватает чтобы хранить результат (настолько он велик).

Например, вычислить 30! (30 факториал) = 265252859812191058636308480000000, это число больше чем, например, максимальное для типа int64 - 9223372036854775807. В этом случае используется прием хранения длинных чисел в виде строки или массива цифр, а чтобы выполнять арифметические действия с такими числами, необходимо написать специальные процедуры сложения, умножения и деления длинных чисел, которые основаны на правилах вычисления "в столбик".

Интерактивно: сложение, умножение и деление

Введите два числа и выберите действие. Числа разбиты на блоки по четыре цифры, как в программах ниже. Кнопками «назад» и «вперёд» проходят шаги алгоритма, «авто» проигрывает их сам. Меняйте числа: шаги пересчитываются. Для деления каждый блок частного подбирается двоичным поиском по диапазону 0–9999.

Итак Длинная арифметика — набор структур данных и алгоритмов, которые позволяют работать с числами гораздо большими, чем это позволяют стандартные типы данных.

Длинная арифметика используется:

При решении олимпиадных задач.
В компьютерах низкой разрядности, микроконтроллерах (например, процессор умеет работать только с числами длиной 8 бит, 8 двоичных разрядов, в 8 битах можно представить только числа от 0 до $2^8-1=255$, а требуется обрабатывать большие числа).
Криптография.
Математическое и финансовое ПО, требующее, чтобы результат вычисления на компьютере совпал до последнего разряда с результатом вычисления на бумаге. В частности, калькулятор Windows (начиная с 95)
«Спортивные» вычисления знаменитых трансцендентных чисел ("число Пи", "число e" и т. д.) с высокой точностью. Вещественное число - число, которое может возникать как результат измерения (Например: 4,31; 5,23432; корень из 2-х). Множество вещественных чисел больше чем множество рациональных дробей (чисел представляющихся в виде дроби), но меньше чем множество комплексных чисел. Комплексное число - расширение множества вещественных чисел за счёт добавления мнимой компоненты числа. Комплексное число представляется в виде: x+iy, где x и y - вещественные числа, а i-мнимая единица.
Высококачественные изображения фракталов.

Представление в компьютере длинных чисел

Реализация операций с длинными числами во многом определяется тем, как представить их в памяти компьютера. "Длинное" число можно записать, например, с помощью массива десятичных цифр, количество элементов в таком массиве равно количеству значащих цифр в "длинном" числе. При этом размер массива должен быть достаточным, чтобы разместить в нем и результат, например, умножения.

Классификация реализации длинной арифметики (преимущества и недостатки различных способов) Количество знаков может быть фиксированным (знаки хранятся в массиве с индексом от 0 до количества знаков минус 1) и с переменной длиной (отдельно ещё хравнится длина числа).

Количество цифр	Только целые числа	Действительные числа
Фиксированное	"+" Простота реализации
Переменное	"+" Экономия памяти

Разряды в позиционной системе счисления.

Рассмотрим реализацию операций в простейшем случае - с целыми положительными числами

Существуют и другие представления "длинных" чисел. Рассмотрим одно из них. Представим наше число
30! = 265252859812191058636308480000000 в виде: 30! = 2 * (10⁴)⁸ + 6525 * (10⁴)⁷ + 2859 * (10⁴)⁶ + 8121 * (10⁴)⁵ + 9105 * (10⁴)⁴ + 8636 * (10⁴)³ + 3084 * (10⁴)² + 8000 * (10⁴)¹ + 0000 * (10⁴)⁰.

Для вычислений его удобно хранить в виде массива:

Номер элемента в массиве А	0	1	2	3	4	5	6	7	8	9
Значение	9	0000	8000	3084	8636	9105	8121	2859	6525	2

Наше "длинное" число представлено в 10000-10 системе счисления (десятитысячно-десятичная система счисления, приведите аналогию с восьмерично-десятичной системой счисления), а "цифрами" числа являются четырехзначные числа. 9 в А [0] - длина числа. Число хранится "задом наперед", начиная с младшего разряда.

Алгоритмы чтения и записи длинных чисел

Ввод длинного числа из файла. Решение задачи начнем с описания данных.

Const MaxDig = 1000; { Максимальное количество цифр — четырехзначных! }
      Osn = 10000; { Основание нашей системы счисления, в элементах массива храним четырехзначные числа }
Type TLong = Array [0..MaxDig] Of Integer;  { Десятичных цифр в нашем числе }
  { В А[0] храним количество задействованных (ненулевых) элементов массива А. }

При обработке каждой очередной цифры входного числа старшая цифра элемента массива с номером i становится младшей цифрой числа в элементе i + 1, а вводимая цифра будет младшей цифрой числа из А[1]. В результате работы нашего алгоритма мы получили число, записанное "задом наперед".

procedure ReadLong(Var A : TLong);
var ch : char; i : Integer;
begin
  FillChar(A, SizeOf(A), 0); { Заполнение нулями массива }
  Read(ch);
  While Not(ch In ['0'..'9']) Do Read(ch); {пропуск не цифр во входном файле}
  While ch In ['0'..'9'] do begin
    For i := A[0] DownTo 1 do begin
      {"протаскивание" старшей цифры в числе из A[i] в младшую цифру числа из A[i+l]}
      A[i+l] := A[i+l] + (LongInt(A[i]) * 10) Div Osn;
      A[i] := (LongInt(A[i]) * 10) Mod Osn
    end;
    A[1] := A[l] + Ord(ch) - Ord('0');
    {добавляем младшую цифру к числу из А[1]}
    If A[A[0]+1] > 0 Then Inc(A[0]);
    {изменяем длину, число задействованных элементов массива А}
    Read(ch)
  end
end;

Чтение длинного числа

Число хранится в основании 10000: в элементах массива лежат четырёхзначные части числа, младшие первыми; в нулевом элементе записано количество занятых разрядов. Цифры читаются по одной: очередная цифра добавляется в младший разряд, а всё число предварительно умножается на 10 с переносом. Так же работает процедура ReadLong выше.

Реализация на Python

# Чтение длинного числа из строки цифр в основании 10000: a[0] — число занятых разрядов,
# a[1], a[2], ... — младшие разряды. Сложность: O(n * len) по времени для n цифр.
BASE = 10000


def read_long(digits):
    a = [0]  # a[0] хранит число занятых разрядов
    for ch in digits:
        if not ch.isdigit():  # пропускаем всё, кроме цифр
            continue
        carry = int(ch)
        for i in range(1, a[0] + 1):  # число умножаем на 10 и прибавляем цифру
            cur = a[i] * 10 + carry
            a[i] = cur % BASE
            carry = cur // BASE
        if carry:
            a.append(carry)
            a[0] += 1
    return a


def to_string(a):
    """Переводит представление обратно в десятичную строку."""
    if a[0] == 0:
        return "0"
    parts = [str(a[a[0]])] + [f"{a[i]:04d}" for i in range(a[0] - 1, 0, -1)]
    return "".join(parts)


if __name__ == "__main__":
    number = read_long("0012345678901234567890123456789")
    print(to_string(number))  # 12345678901234567890123456789

Реализация на C++

// Чтение длинного числа из строки цифр в основании 10000: a[0] — число занятых разрядов,
// a[1], a[2], ... — младшие разряды. Сложность: O(n * len) по времени для n цифр.
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int BASE = 10000;

// a[0] хранит число занятых разрядов, a[1..] — младшие разряды числа
vector<int> readLong(const string& digits) {
    vector<int> a(1, 0);
    for (char ch : digits) {
        if (ch < '0' || ch > '9') continue;  // пропускаем всё, кроме цифр
        int carry = ch - '0';
        for (int i = 1; i <= a[0]; i++) {  // число умножаем на 10 и прибавляем цифру
            int cur = a[i] * 10 + carry;
            a[i] = cur % BASE;
            carry = cur / BASE;
        }
        if (carry > 0) {
            a.push_back(carry);
            a[0]++;
        }
    }
    return a;
}

string toString(const vector<int>& a) {
    if (a[0] == 0) return "0";
    string s = to_string(a[a[0]]);
    for (int i = a[0] - 1; i >= 1; i--) {
        char buf[8];
        snprintf(buf, sizeof buf, "%04d", a[i]);
        s += buf;
    }
    return s;
}

int main() {
    vector<int> number = readLong("0012345678901234567890123456789");
    cout << toString(number) << "\n";  // 12345678901234567890123456789
    return 0;
}

Реализация на Rust


// Чтение длинного числа из строки цифр в основании 10000: a[0] — число занятых разрядов,
// a[1], a[2], ... — младшие разряды. Сложность: O(n * len) по времени для n цифр.
const BASE: u32 = 10000;

fn read_long(digits: &str) -> Vec<u32> {
    let mut a = vec![0u32]; // a[0] хранит число занятых разрядов
    for ch in digits.chars().filter(|c| c.is_ascii_digit()) {
        let mut carry = ch.to_digit(10).unwrap(); // очередная цифра
        for i in 1..=a[0] as usize {
            let cur = a[i] * 10 + carry;
            a[i] = cur % BASE;
            carry = cur / BASE;
        }
        if carry > 0 {
            a.push(carry);
            a[0] += 1;
        }
    }
    a
}

fn to_string(a: &[u32]) -> String {
    if a[0] == 0 {
        return "0".to_string();
    }
    let mut s = a[a[0] as usize].to_string();
    for i in (1..a[0] as usize).rev() {
        s.push_str(&format!("{:04}", a[i]));
    }
    s
}

fn main() {
    let number = read_long("0012345678901234567890123456789");
    println!("{}", to_string(&number)); // 12345678901234567890123456789
}

Задачи на длинную арифметику

Задача 1. (Районная олимпиада 1997).
Числа Фибоначчи выписываются подряд, начиная с Ф(1). Какая цифра будет на N-ом месте (N < 5000)?

Указание: Ф(n+1) = Ф(n) + Ф(n-1); Ф(1) = Ф(2) = 1

Необходимо написать процедуру сложения «длинных» чисел (представленных в виде массивов отдельных разрядов A и B). В первой ячейке массива будем хранить «длину» числа (количество разрядов). Массив B содержит предыдущее вычисленное число Фибоначчи, а массив A – текущее число. Для удобства сложения полагаем Ф(0) = 0.

Программа на Basic для сложения 2 "длинных чисел":

DECLARE SUB LongAdd ()
DEFLNG A-Z
DIM SHARED A(10000), B(10000) 
'Длинные числа. A(0)-длина числа A, A(i)-i-ый разряд, 
A(0) = 1: A(1) = 1 'A=Ф(1)=1
B(0) = 1: B(1) = 0 'B=Ф(0)=0
L = 1 'L - общая длина строки, состоящей из чисел Фибоначчи

INPUT "N=", N
WHILE N > L 'Пока N-номер искомой цифры больше длины строки...
LongAdd 'найти очередное число Фибоначчи
L = L + A(0) 'и прибавить его длину к общей длине строки
WEND
PRINT A(L - N + 1) 'Как только N-ая цифра получена в явном виде, печатаем ее

'Процедура сложения двух "длинных" чисел A и B "в столбик"
'Результат сложения помещается в A, прежнее значение А переносится в B
SUB LongAdd
r = 0
FOR i = 1 TO A(0)
k = A(i) 'Запоминается i-ая цифра числа A
r = A(i) + B(i) + r 'Сумма i-ых разрядов чисел A и B с учетом переноса
A(i) = r MOD 10
r = r \ 10 'r - перенос в следующий разряд
B(i) = k 'Переносим запомненную i-ую цифру числа A в число B
NEXT
IF r <> 0 THEN 'Если в результате сложения старших разрядов оказался
A(0) = A(0) + 1 'ненулевой перенос, то "удлиняем" результат на 1 цифру
A(A(0)) = r
END IF
END SUB

Реализация на Python

# Сложение длинных чисел в столбик: O(max(n, m)) операций; число - список цифр, младшая цифра первая
from itertools import zip_longest


def add_long(a, b):
    """Складывает два неотрицательных длинных числа, заданных списками цифр."""
    result = []
    carry = 0  # перенос в следующий разряд
    for digit_a, digit_b in zip_longest(a, b, fillvalue=0):
        carry, digit = divmod(digit_a + digit_b + carry, 10)
        result.append(digit)
    if carry:
        result.append(carry)
    return result


def parse_long(text):
    """Строка десятичных цифр -> список цифр, младшая цифра первая."""
    return [int(symbol) for symbol in reversed(text)]


def format_long(digits):
    """Список цифр -> строка без ведущих нулей."""
    text = "".join(str(digit) for digit in reversed(digits)).lstrip("0")
    return text or "0"


def main():
    a = parse_long("99999999999999999999")
    b = parse_long("12345678901234567890")
    print(format_long(add_long(a, b)))


if __name__ == "__main__":
    main()

Реализация на Rust


// Сложение длинных чисел в столбик: O(max(n, m)) операций; число - вектор цифр, младшая цифра первая

pub fn add_long(a: &[u8], b: &[u8]) -> Vec<u8> {
    let mut result = Vec::new();
    let mut carry = 0; // перенос в следующий разряд
    for i in 0..a.len().max(b.len()) {
        let digit_a = a.get(i).copied().unwrap_or(0);
        let digit_b = b.get(i).copied().unwrap_or(0);
        let sum = digit_a + digit_b + carry;
        result.push(sum % 10);
        carry = sum / 10;
    }
    if carry > 0 {
        result.push(carry);
    }
    result
}

// Строка десятичных цифр -> вектор цифр, младшая цифра первая
pub fn parse_long(text: &str) -> Vec<u8> {
    text.bytes().rev().map(|byte| byte - b'0').collect()
}

// Вектор цифр -> строка без ведущих нулей
pub fn format_long(digits: &[u8]) -> String {
    let text: String = digits.iter().rev().map(|&digit| char::from(digit + b'0')).collect();
    let trimmed = text.trim_start_matches('0');
    if trimmed.is_empty() {
        "0".to_string()
    } else {
        trimmed.to_string()
    }
}

fn main() {
    let a = parse_long("99999999999999999999");
    let b = parse_long("12345678901234567890");
    println!("{}", format_long(&add_long(&a, &b)));
}

Реализация на C++

// Сложение длинных чисел в столбик: O(max(n, m)) операций; число - вектор цифр, младшая цифра первая
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>

using Digits = std::vector<int>;

Digits add_long(const Digits& a, const Digits& b) {
    Digits result;
    int carry = 0;  // перенос в следующий разряд
    for (std::size_t i = 0; i < std::max(a.size(), b.size()); ++i) {
        int digit_a = i < a.size() ? a[i] : 0;
        int digit_b = i < b.size() ? b[i] : 0;
        int sum = digit_a + digit_b + carry;
        result.push_back(sum % 10);
        carry = sum / 10;
    }
    if (carry > 0) {
        result.push_back(carry);
    }
    return result;
}

// Строка десятичных цифр -> вектор цифр, младшая цифра первая
Digits parse_long(const std::string& text) {
    Digits digits;
    for (auto it = text.rbegin(); it != text.rend(); ++it) {
        digits.push_back(*it - '0');
    }
    return digits;
}

// Вектор цифр -> строка без ведущих нулей
std::string format_long(const Digits& digits) {
    std::string text;
    for (auto it = digits.rbegin(); it != digits.rend(); ++it) {
        text += static_cast<char>('0' + *it);
    }
    const std::size_t first = text.find_first_not_of('0');
    return first == std::string::npos ? "0" : text.substr(first);
}

int main() {
    Digits a = parse_long("99999999999999999999");
    Digits b = parse_long("12345678901234567890");
    std::cout << format_long(add_long(a, b)) << '\n';
    return 0;
}

Реализация знаковой длинной целой арифметики для Delphi: cложение, вычитание, умножение и деление.

{ Самая простая знаковая длинная целая арифметика }
{ Реализация вычислений "в столбик": сложения, вычитания, умножения, деления, остатка от деления }
Const MaxLen = 3000; { Максимальная длина длинного числа }
var Base : Integer = 10; { Основание системы счисления (можно установить в начале программы) }

Type Long = array [-1..MaxLen] of Integer;
  { В -1-ой позиции находится знак,  -1 - отрицательное число, +1 - положительное, 0 - ноль }

{ Получить цифру в виде символа по её значению }
{ 0 -> '0', 1 -> '1', 2 -> '2', ... 9 -> '9', 'A' -> 10, ... 'F' -> 15 }
function Digit( Dig:Integer ):Char;
begin
  case Dig of
    0..9: Result := Chr(Ord('0')+Dig);
    10..35: Result := Chr(Ord('A')+Dig-10);
  else
    raise EOverflow.Create('Слишком большая цифра. Невозможно вывести!');
  end;
end;

{ Получаем из "короткого" числа int64 длинное (используется для инициализации длинных чисел) }
function ToLong( N:Int64 ):Long;
var i : integer;
begin
  fillChar(Result,sizeOf(Result),0);
  { Знак }
  if N=0 then Result[-1]:=0  { Число равно 0 }
  else if N>0 then Result[-1]:=1 { Число положительное }
  else begin Result[-1] := -1; N := -N ; end; { Число отрицательное, дальше будем }
  i := 0;
  while N > 0 do begin
    Result[i] := N mod Base;
    N := N div Base;
    inc(i);
  end;
end;

{ Получаем из "длинного" короткое если это возможно }
function ToInt( L:Long ):Int64;
var
  i : Integer;
  X : Int64;
begin
  X := 1; { Base в нужной степени }
  Result := 0;
  for i:=0 to MaxLen do begin
    assert( L[i] >= 0 );
    Inc( Result, X*L[i] );
    X := X * Base; { Получаем Base в следующей степени }
  end;
  Result := Result * L[-1]; { Умножаем на знак }
end;

{ Перевод "длинного числа" в строку (для вывода) }
function ToString( Var L:Long ):String;
var i : Integer;
begin
  { Сначала учитываем знак }
  Case L[-1] of
    -1: Result := '-';
    0,1: Result := '';
  end;
  { Выводим число по цифрам }
  for i:=Len(L) downto 0 do
    Result := Result + Digit(L[i]);
end;

{ Приведение нуля в нормальный вид }
procedure FixZero( Var L:Long );
var
  i : Integer;
begin
  for i:=0 to MaxLen do
    if L[i]<>0 then 
      exit;
  L[-1]:=0;
end;

{ Учёт переноса в старшие разряды }
procedure FixUp( Var L:Long );
var i : Integer;
begin
  for i:=0 to MaxLen-1 do begin
    inc( L[i+1], L[i] div Base );
    L[i] := L[i] mod Base;
  end;
  FixZero(L);
end;

{ Учёт заёма из старших разрядов }
procedure FixDown( Var L:Long );
var i : Integer;
begin
  for i:=0 to MaxLen-1 do
    while L[i] < 0 do begin
      inc( L[i], Base );
      dec( L[i+1], 1 );
    end;
  FixZero(L);
end;

{ Больше или равно по абсолютному значению с учётом сдвига B на Sdvig_B цифр влево }
function isGreatEq_Abs( A,B:Long; Sdvig_B:Integer=0 ):boolean;
var i : Integer;
begin
  for i:=MaxLen-Sdvig_B downto 0 do begin
    if A[i+Sdvig_B]>B[i] then begin Result := true; exit; end;
    if A[i+Sdvig_B]< B[i] then begin Result := false; exit; end;
  end;
  Result := true; { A и B равны }
end;

{ Больше или равно с учётом знака }
function isGreatEq( A,B:Long ):boolean; { Больше ли A B }
begin
  case A[-1] of
    -1: case B[-1] of
       -1: Result := isGreatEq_Abs(B,A); { A отрицательно B отрицательно }
        0: Result := false; { A отрицательно B ноль }
       +1: Result := false; { A отрицательно B положительно }
       end;
     0: case B[-1] of
       -1: Result := true; { A ноль B отрицательно }
        0: Result := true; { A ноль B ноль }
       +1: Result := isGreatEq_Abs(A,B); { A ноль B положительно }
       end;
    +1: case B[-1] of
       -1: Result := true; { A положительно B отрицательно }
        0: Result := true; { A положительно B ноль }
       +1: Result := isGreatEq_Abs(A,B); { A положительно B положительно }
       end;
  end;
end;

{ Сложение по абсолютному значению }
function Add_Abs( A,B:Long ):Long;
var i : Integer;
begin
  for i:=0 to MaxLen do Result[i] := A[i] + B[i];
  FixUp(Result);
end;

{ Вычитание по абсолютному значению с возможным сдвигом (сдвиг нужен при делении) }
function Sub_Abs( A,B:Long; Sdvig_B:Integer=0 ):Long;
var i : Integer;
begin
  assert( isGreatEq_Abs(A,B) );
  for i:=0 to Sdvig_B-1 do Result[i] := A[i];
  for i:=Sdvig_B to MaxLen do Result[i] := A[i] - B[i-Sdvig_B];
  FixDown(Result);
end;

{ Сложение "длинных" с учётом знака }
function Add( A,B:Long ):Long;
begin
  { Рассмотрим 2 случая: }
  if A[-1] = B[-1] then begin { A и B одного знака }
    Result := Add_Abs(A,B);
    Result[-1] := A[-1]; { Тогда знак их суммы такой же как у A и B }
  end else begin { A и B с разными знаками }
    { Тогда знак суммы равен знаку наибольшего из них по абсолютному значению,
      а значение - разности абсолютных значений }
    if isGreatEq_Abs(A,B) then begin
      REsult := Sub_Abs(A,B); { Если A больше по абсолютному значению - вычитаем из A B }
      Result[-1] := A[-1];
    end else begin { иначе из B A }
      Result := Sub_Abs(B,A);
      Result[-1] := B[-1];
    end;
  end;
end;

{ Вычитание "длинных" с учётом знака }
function Sub( A,B:Long ):Long;
begin
  B[-1] := -B[-1]; { Изменяем знак и складываем }
  Result := Add(A,B);
end;

{ Перемножение длинных }
function Mul( A,B:Long ):Long;
var i,j : Integer;
begin
  fillChar(Result,sizeOf(Result),0);
  for i:=0 to MaxLen do
    for j:=0 to MaxLen-i do
      Inc( Result[i+j], A[i]*B[j] );
  Result[-1] := A[-1] * B[-1]; { Знаки перемножаются }
  FixUp(Result);
end;

{ Возведение в квадрат }
function Sqr( A:Long ):Long;
begin
  Result := Mul(A,A);
end;

{ Длинное деление }
function LDiv( A,B:Long ):Long;
var Sdvig_B : Integer;
begin
  fillChar(Result,sizeOf(Result),0);
  Result[-1] := A[-1] * B[-1]; { Знаки перемножаются }
  for Sdvig_B:=Len(A)-Len(B) downto 0 do
    while isGreatEq_Abs(A,B,Sdvig_B) do begin
      A := Sub_Abs(A,B,Sdvig_B);
      Inc( Result[Sdvig_B] );
    end;
  FixUp(Result);
end;

{ Остаток при целочисленном делении }
function LMod( A,B:Long ):Long;
var Sdvig_B : Integer;
begin
  for Sdvig_B:=Len(A)-Len(B) downto 0 do
    while isGreatEq_Abs(A,B,Sdvig_B) do
      A := Sub_Abs(A,B,Sdvig_B);
  Result := A;
  Result[-1] := 1;
end;

Деление длинного числа на короткое делитель выполняется в столбик от старшей цифры к младшей: за один проход получаются частное (LDiv) и остаток (LMod).

Реализация на Python

# Деление длинного числа на короткое (LDiv - частное, LMod - остаток) в столбик: O(n) операций
def divmod_short(digits, divisor):
    """Делит число (список цифр, младшая первая) на короткое divisor >= 1; возвращает (частное, остаток)."""
    quotient = []
    remainder = 0
    # Идём от старшей цифры к младшей: остаток приписываем справа к текущей цифре
    for digit in reversed(digits):
        current = remainder * 10 + digit
        quotient.append(current // divisor)
        remainder = current % divisor
    quotient.reverse()
    # Убираем ведущие нули частного, оставляя хотя бы одну цифру
    while len(quotient) > 1 and quotient[-1] == 0:
        quotient.pop()
    return quotient, remainder


def parse_long(text):
    """Строка десятичных цифр -> список цифр, младшая цифра первая."""
    return [int(symbol) for symbol in reversed(text)]


def format_long(digits):
    """Список цифр -> строка без ведущих нулей."""
    text = "".join(str(digit) for digit in reversed(digits)).lstrip("0")
    return text or "0"


def main():
    quotient, remainder = divmod_short(parse_long("12345678901234567890"), 97)
    print(format_long(quotient), remainder)


if __name__ == "__main__":
    main()

Реализация на Rust


// Деление длинного числа на короткое (LDiv - частное, LMod - остаток) в столбик: O(n) операций
// Делитель должен быть не больше 2^32: промежуточное значение remainder * 10 + цифра помещается в u64

pub fn divmod_short(digits: &[u8], divisor: u64) -> (Vec<u8>, u64) {
    let mut quotient = Vec::with_capacity(digits.len());
    let mut remainder = 0;
    // Идём от старшей цифры к младшей: остаток приписываем справа к текущей цифре
    for &digit in digits.iter().rev() {
        let current = remainder * 10 + u64::from(digit);
        quotient.push((current / divisor) as u8);
        remainder = current % divisor;
    }
    quotient.reverse();
    // Убираем ведущие нули частного, оставляя хотя бы одну цифру
    while quotient.len() > 1 && quotient.last() == Some(&0) {
        quotient.pop();
    }
    (quotient, remainder)
}

// Строка десятичных цифр -> вектор цифр, младшая цифра первая
pub fn parse_long(text: &str) -> Vec<u8> {
    text.bytes().rev().map(|byte| byte - b'0').collect()
}

// Вектор цифр -> строка без ведущих нулей
pub fn format_long(digits: &[u8]) -> String {
    let text: String = digits.iter().rev().map(|&digit| char::from(digit + b'0')).collect();
    let trimmed = text.trim_start_matches('0');
    if trimmed.is_empty() {
        "0".to_string()
    } else {
        trimmed.to_string()
    }
}

fn main() {
    let (quotient, remainder) = divmod_short(&parse_long("12345678901234567890"), 97);
    println!("{} {}", format_long(&quotient), remainder);
}

Реализация на C++

// Деление длинного числа на короткое (LDiv - частное, LMod - остаток) в столбик: O(n) операций
// Делитель должен быть не больше 2^32: промежуточное значение remainder * 10 + цифра помещается в 64 бита
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

using Digits = std::vector<int>;
using u64 = std::uint64_t;

// Делит число (вектор цифр, младшая первая) на короткое divisor; возвращает (частное, остаток)
std::pair<Digits, u64> divmod_short(const Digits& digits, u64 divisor) {
    Digits quotient;
    u64 remainder = 0;
    // Идём от старшей цифры к младшей: остаток приписываем справа к текущей цифре
    for (auto it = digits.rbegin(); it != digits.rend(); ++it) {
        const u64 current = remainder * 10 + static_cast<u64>(*it);
        quotient.push_back(static_cast<int>(current / divisor));
        remainder = current % divisor;
    }
    std::reverse(quotient.begin(), quotient.end());
    // Убираем ведущие нули частного, оставляя хотя бы одну цифру
    while (quotient.size() > 1 && quotient.back() == 0) {
        quotient.pop_back();
    }
    return {quotient, remainder};
}

// Строка десятичных цифр -> вектор цифр, младшая цифра первая
Digits parse_long(const std::string& text) {
    Digits digits;
    for (auto it = text.rbegin(); it != text.rend(); ++it) {
        digits.push_back(*it - '0');
    }
    return digits;
}

// Вектор цифр -> строка без ведущих нулей
std::string format_long(const Digits& digits) {
    std::string text;
    for (auto it = digits.rbegin(); it != digits.rend(); ++it) {
        text += static_cast<char>('0' + *it);
    }
    const std::size_t first = text.find_first_not_of('0');
    return first == std::string::npos ? "0" : text.substr(first);
}

int main() {
    const auto [quotient, remainder] = divmod_short(parse_long("12345678901234567890"), 97);
    std::cout << format_long(quotient) << ' ' << remainder << '\n';
    return 0;
}

Реализация на Python

# Вычитание длинных чисел в столбик с заёмом: O(n) операций; требуется a >= b
from itertools import zip_longest


def sub_long(a, b):
    """Вычитает b из a (a >= b); числа - списки цифр, младшая цифра первая."""
    result = []
    borrow = 0  # заём из старшего разряда
    for digit_a, digit_b in zip_longest(a, b, fillvalue=0):
        digit = digit_a - digit_b - borrow
        borrow = 0
        if digit < 0:
            digit += 10
            borrow = 1
        result.append(digit)
    if borrow:
        raise ValueError("требуется a >= b")
    return strip_zeros(result)


def strip_zeros(digits):
    """Убирает незначащие нули в старших разрядах, оставляя хотя бы одну цифру."""
    while len(digits) > 1 and digits[-1] == 0:
        digits.pop()
    return digits


def parse_long(text):
    """Строка десятичных цифр -> список цифр, младшая цифра первая."""
    return [int(symbol) for symbol in reversed(text)]


def format_long(digits):
    """Список цифр -> строка без ведущих нулей."""
    text = "".join(str(digit) for digit in reversed(digits)).lstrip("0")
    return text or "0"


def main():
    a = parse_long("100000000000000000000")
    b = parse_long("12345678901234567890")
    print(format_long(sub_long(a, b)))


if __name__ == "__main__":
    main()

Реализация на Rust


// Вычитание длинных чисел в столбик с заёмом: O(n) операций; требуется a >= b

// Возвращает a - b или None, если a < b
pub fn sub_long(a: &[u8], b: &[u8]) -> Option<Vec<u8>> {
    let mut result = Vec::new();
    let mut borrow: i32 = 0; // заём из старшего разряда
    for i in 0..a.len().max(b.len()) {
        let digit_a = i32::from(a.get(i).copied().unwrap_or(0));
        let digit_b = i32::from(b.get(i).copied().unwrap_or(0));
        let mut digit = digit_a - digit_b - borrow;
        borrow = 0;
        if digit < 0 {
            digit += 10;
            borrow = 1;
        }
        result.push(digit as u8);
    }
    if borrow != 0 {
        return None;
    }
    while result.len() > 1 && result.last() == Some(&0) {
        result.pop();
    }
    Some(result)
}

// Строка десятичных цифр -> вектор цифр, младшая цифра первая
pub fn parse_long(text: &str) -> Vec<u8> {
    text.bytes().rev().map(|byte| byte - b'0').collect()
}

// Вектор цифр -> строка без ведущих нулей
pub fn format_long(digits: &[u8]) -> String {
    let text: String = digits.iter().rev().map(|&digit| char::from(digit + b'0')).collect();
    let trimmed = text.trim_start_matches('0');
    if trimmed.is_empty() {
        "0".to_string()
    } else {
        trimmed.to_string()
    }
}

fn main() {
    let a = parse_long("100000000000000000000");
    let b = parse_long("12345678901234567890");
    println!("{}", format_long(&sub_long(&a, &b).unwrap()));
}

Реализация на C++

// Вычитание длинных чисел в столбик с заёмом: O(n) операций; требуется a >= b
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

using Digits = std::vector<int>;

// Убирает незначащие нули в старших разрядах, оставляя хотя бы одну цифру
void strip_zeros(Digits& digits) {
    while (digits.size() > 1 && digits.back() == 0) {
        digits.pop_back();
    }
}

// Возвращает a - b; бросает исключение, если a < b
Digits sub_long(const Digits& a, const Digits& b) {
    Digits result;
    int borrow = 0;  // заём из старшего разряда
    for (std::size_t i = 0; i < std::max(a.size(), b.size()); ++i) {
        int digit_a = i < a.size() ? a[i] : 0;
        int digit_b = i < b.size() ? b[i] : 0;
        int digit = digit_a - digit_b - borrow;
        borrow = digit < 0 ? 1 : 0;
        result.push_back(digit < 0 ? digit + 10 : digit);
    }
    if (borrow != 0) {
        throw std::invalid_argument("требуется a >= b");
    }
    strip_zeros(result);
    return result;
}

// Строка десятичных цифр -> вектор цифр, младшая цифра первая
Digits parse_long(const std::string& text) {
    Digits digits;
    for (auto it = text.rbegin(); it != text.rend(); ++it) {
        digits.push_back(*it - '0');
    }
    return digits;
}

// Вектор цифр -> строка без ведущих нулей
std::string format_long(const Digits& digits) {
    std::string text;
    for (auto it = digits.rbegin(); it != digits.rend(); ++it) {
        text += static_cast<char>('0' + *it);
    }
    const std::size_t first = text.find_first_not_of('0');
    return first == std::string::npos ? "0" : text.substr(first);
}

int main() {
    Digits a = parse_long("100000000000000000000");
    Digits b = parse_long("12345678901234567890");
    std::cout << format_long(sub_long(a, b)) << '\n';
    return 0;
}

Реализация на Python

# Умножение длинных чисел столбиком: O(n * m) операций для чисел из n и m цифр
def mul_long(a, b):
    """Умножает два неотрицательных длинных числа, заданных списками цифр (младшая первая)."""
    result = [0] * (len(a) + len(b))
    for i, digit_a in enumerate(a):
        carry = 0
        for j, digit_b in enumerate(b):
            # Накопленная цифра, произведение цифр и перенос дают новую цифру и перенос
            carry, result[i + j] = divmod(result[i + j] + digit_a * digit_b + carry, 10)
        result[i + len(b)] += carry
    return strip_zeros(result)


def strip_zeros(digits):
    """Убирает незначащие нули в старших разрядах, оставляя хотя бы одну цифру."""
    while len(digits) > 1 and digits[-1] == 0:
        digits.pop()
    return digits


def parse_long(text):
    """Строка десятичных цифр -> список цифр, младшая цифра первая."""
    return [int(symbol) for symbol in reversed(text)]


def format_long(digits):
    """Список цифр -> строка без ведущих нулей."""
    text = "".join(str(digit) for digit in reversed(digits)).lstrip("0")
    return text or "0"


def main():
    a = parse_long("12345678901234567890")
    b = parse_long("98765432109876543210")
    print(format_long(mul_long(a, b)))


if __name__ == "__main__":
    main()

Реализация на Rust


// Умножение длинных чисел столбиком: O(n * m) операций для чисел из n и m цифр

pub fn mul_long(a: &[u8], b: &[u8]) -> Vec<u8> {
    let mut result = vec![0u32; a.len() + b.len()];
    for (i, &digit_a) in a.iter().enumerate() {
        let mut carry = 0;
        for (j, &digit_b) in b.iter().enumerate() {
            // Накопленная цифра, произведение цифр и перенос дают новую цифру и перенос
            let total = result[i + j] + u32::from(digit_a) * u32::from(digit_b) + carry;
            result[i + j] = total % 10;
            carry = total / 10;
        }
        result[i + b.len()] += carry;
    }
    let mut digits: Vec<u8> = result.into_iter().map(|digit| digit as u8).collect();
    while digits.len() > 1 && digits.last() == Some(&0) {
        digits.pop();
    }
    digits
}

// Строка десятичных цифр -> вектор цифр, младшая цифра первая
pub fn parse_long(text: &str) -> Vec<u8> {
    text.bytes().rev().map(|byte| byte - b'0').collect()
}

// Вектор цифр -> строка без ведущих нулей
pub fn format_long(digits: &[u8]) -> String {
    let text: String = digits.iter().rev().map(|&digit| char::from(digit + b'0')).collect();
    let trimmed = text.trim_start_matches('0');
    if trimmed.is_empty() {
        "0".to_string()
    } else {
        trimmed.to_string()
    }
}

fn main() {
    let a = parse_long("12345678901234567890");
    let b = parse_long("98765432109876543210");
    println!("{}", format_long(&mul_long(&a, &b)));
}

Реализация на C++

// Умножение длинных чисел столбиком: O(n * m) операций для чисел из n и m цифр
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>

using Digits = std::vector<int>;

// Убирает незначащие нули в старших разрядах, оставляя хотя бы одну цифру
void strip_zeros(Digits& digits) {
    while (digits.size() > 1 && digits.back() == 0) {
        digits.pop_back();
    }
}

Digits mul_long(const Digits& a, const Digits& b) {
    Digits result(a.size() + b.size(), 0);
    for (std::size_t i = 0; i < a.size(); ++i) {
        int carry = 0;
        for (std::size_t j = 0; j < b.size(); ++j) {
            // Накопленная цифра, произведение цифр и перенос дают новую цифру и перенос
            int total = result[i + j] + a[i] * b[j] + carry;
            result[i + j] = total % 10;
            carry = total / 10;
        }
        result[i + b.size()] += carry;
    }
    strip_zeros(result);
    return result;
}

// Строка десятичных цифр -> вектор цифр, младшая цифра первая
Digits parse_long(const std::string& text) {
    Digits digits;
    for (auto it = text.rbegin(); it != text.rend(); ++it) {
        digits.push_back(*it - '0');
    }
    return digits;
}

// Вектор цифр -> строка без ведущих нулей
std::string format_long(const Digits& digits) {
    std::string text;
    for (auto it = digits.rbegin(); it != digits.rend(); ++it) {
        text += static_cast<char>('0' + *it);
    }
    const std::size_t first = text.find_first_not_of('0');
    return first == std::string::npos ? "0" : text.substr(first);
}

int main() {
    Digits a = parse_long("12345678901234567890");
    Digits b = parse_long("98765432109876543210");
    std::cout << format_long(mul_long(a, b)) << '\n';
    return 0;
}

Быстрое умножение длинных чисел: FFT

Школьный способ перемножает два числа по $n$ знаков, делая около $n^2$ умножений цифр. Для чисел по миллиону знаков это $10^{12}$ операций, поэтому такой способ не годится. Быстрое преобразование Фурье (FFT) перемножает такие числа за $O(n \log n)$ операций.

Идея: число — это многочлен

Разобьём число на блоки по четыре знака, то есть возьмём основание $B = 10^4$. Число становится многочленом $A(x) = a_0 + a_1 x + a_2 x^2 + \dots$, где $x = B$, а $a_i$ — блоки числа от младших к старшим. Произведение чисел — это произведение многочленов. Его коэффициенты — свёртка коэффициентов сомножителей: $c_k = \sum_{i+j=k} a_i b_j$. Перенос разрядов в конце превращает коэффициенты обратно в число.

Шаги алгоритма

Разбить оба числа на блоки по 4 знака. Для чисел по $10^6$ знаков получается по $250\,000$ блоков.
Дополнить массивы нулями до степени двойки $N \ge 500\,000$, то есть до $N = 2^{19} = 524\,288$.
Вычислить FFT каждого массива: это значения многочлена в $N$ точках — корнях из единицы $\omega^k = e^{2\pi i k / N}$.
Перемножить значения поточечно: $\hat C_k = \hat A_k \cdot \hat B_k$. Свёртка в точках становится обычным умножением.
Обратное FFT даёт коэффициенты $c_k$ с ошибкой округления. Округлить их до целых.
Выполнить перенос разрядов: к $c_k$ добавляют перенос из предыдущего разряда, остаток по модулю $B$ — очередной блок результата.

Наглядно: 1234 × 5678 через FFT

Тот же алгоритм на маленьком примере: числа записаны цифрами, основание $10$, размер преобразования $N = 8$. Кнопками можно пройти все шаги: разложение на коэффициенты, бабочки FFT, поточечное умножение, обратное FFT и перенос разрядов.

Оценка времени и точности

Для $n = 10^6$ знаков $N = 2^{19}$. Одно FFT содержит $\frac{N}{2}\log_2 N \approx 5 \cdot 10^6$ бабочек, а всего преобразований три, то есть около $1{,}5 \cdot 10^7$ операций. Школьный способ дал бы $(2{,}5 \cdot 10^5)^2 \approx 6{,}25 \cdot 10^{10}$ умножений блоков.

Вещественные числа в компьютере хранятся с ограниченной точностью, поэтому коэффициенты округляются с ошибкой. Проверка на случайных числах по миллиону знаков дала максимальную ошибку $0{,}004$, а на числах из одних девяток (худший случай) — $0{,}016$. Пока ошибка меньше $0{,}5$, округление даёт верную цифру, поэтому блоки по 4 знака безопасны. Блоки по 3 знака дают больший запас, но размер $N$ становится $2^{20}$. Без ошибок округления работают преобразования по простому модулю (NTT).

Измерено: умножение двух миллионнозначных чисел через FFT в библиотеке numpy заняло $0{,}2$ с, точное произведение встроенным алгоритмом Python — $1{,}6$ с.