Арифметика чисел в b-ичной системе счисления (Длинная арифметика) — различия между версиями
(Новая страница: «{{В разработке}} ==Представление в памяти== ==Сложение, вычитание, умножение, деление на коро…») |
|||
| Строка 1: | Строка 1: | ||
{{В разработке}} | {{В разработке}} | ||
| + | |||
| + | {{Определение | ||
| + | |definition= | ||
| + | Длинная арифметика — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных. | ||
| + | }} | ||
| + | |||
| + | Основная идея заключается в том, что число хранится в виде массива его цифр. | ||
| + | |||
| + | Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), либо двоичная система счисления. | ||
==Представление в памяти== | ==Представление в памяти== | ||
| + | |||
| + | Один из вариантов хранения длинных чисел можно реализовать в виде массива целых чисел, где каждый элемент — это одна цифра числа. Для повышения эффективности удобно работать в системе по основанию миллиард (может храниться в ''int32''), т.е. каждый элемент вектора содержит не одну, а сразу 9 цифр. | ||
| + | |||
| + | Цифры будут храниться в массиве в таком порядке, что сначала идут наименее значимые цифры (т.е. единицы, десятки, сотни, и т.д.). | ||
| + | |||
| + | Кроме того, все операции будут реализованы таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль. | ||
==Сложение, вычитание, умножение, деление на короткое, деление на длинное== | ==Сложение, вычитание, умножение, деление на короткое, деление на длинное== | ||
==Подбор значения очередной цифры в алгоритме деления в столбик== | ==Подбор значения очередной цифры в алгоритме деления в столбик== | ||
Версия 20:36, 15 декабря 2010
| Определение: |
| Длинная арифметика — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных. |
Основная идея заключается в том, что число хранится в виде массива его цифр.
Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), либо двоичная система счисления.
Представление в памяти
Один из вариантов хранения длинных чисел можно реализовать в виде массива целых чисел, где каждый элемент — это одна цифра числа. Для повышения эффективности удобно работать в системе по основанию миллиард (может храниться в int32), т.е. каждый элемент вектора содержит не одну, а сразу 9 цифр.
Цифры будут храниться в массиве в таком порядке, что сначала идут наименее значимые цифры (т.е. единицы, десятки, сотни, и т.д.).
Кроме того, все операции будут реализованы таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.
