ProGrammer
Сайт о программировании, математике и моделировании
Вычисление остатка в длинной арифметике
3 Декабрь
Итак, теперь умеем умножать числа, но в алгоритмах ГОСТ Р 34.10-94 требуется уметь вычислять произведение двух чисел по модулю простого числа. Для его реализации необходимо произвести вычисление остатка от деления 2n-значного числа на n-значное. Эта операция называется редукцией по модулю. Выполнять ее можно двумя способами. Первый состоит в том, что необходимо выполнить процедуру деления и взять остаток. Второй метод носит имя П. Монтгомери, который предложил модифицировать саму операцию редукции. Что из этого получилось, рассмотрим далее. Читать дальше >
Возведение в квадрат длинного числа
3 Декабрь
Если немного заскочить вперед и посмотреть на любой из приведенных далее алгоритмов возведения в степень, то можно видеть, что одним из путей ускорения этой процедуры является ускорение работы алгоритма возведения во вторую степень. делать это можно, по крайней мере, тремя способами:
- умножать операнд на себя самого, используя при этом один из приведенных выше алгоритмов умножения,
- использовать модификацию метода Карацубы,
- воспользоваться методом «треугольника». Читать дальше >
Умножение длинных чисел
3 Декабрь
Умножение в столбик.
С умножением дело обстоит не так просто, как с операциями сложения и вычитания. Дело в том, что известный нам со школы алгоритм умножения “в столбик” не самый быстрый. Вот он.
Алгоритм 1.3. Умножение «в столбик» длинных чисел С = А*В Читать дальше >
Длинная арифметика. Сложение и вычитание
3 Декабрь
Складывать и вычитать учат с первого класса школы. И в отличие от умножения ничего более эффективного, чем “первоклассный” школьный алгоритм “в столбик” и не надо придумывать.. Итак, ниже приведен алгоритм вычисления суммы С =А + В чисел А и В длины n цифр. При этом помимо n — значного результата С возвращается также бит переноса из старших разрядов d. Читать дальше >
Внутреннее представление длинных чисел в памяти компьютера
3 Декабрь
Прежде всего, введем обозначение. Обозначим через m длину в байтах машинного слова, которое используется в качестве минимального элемента памяти. Конкретный выбор зависит от того, какой максимальный длинны элемент данных можно умножать без потери разрядов. Для процессоров Intel начиная с модели 80386 – m=32. Для процессора Digital Alpha можно использовать m=64. Читать дальше >
Длинная арифметика
3 Декабрь
Известно, что арифметические действия, выполняемые компьютером в ограниченном числе разрядов, не всегда позволяют получить точный результат. Более того, мы ограничены размером (величиной) чисел, с которыми можем работать, так как для представления чисел в компьютере используются стандартные типы данных. Поэтому в некоторых случаях мы сами должны позаботиться о представлении чисел в машине и о точном выполнении арифметических операций над ними.
Числа, для представления которых в стандартных компьютерных типах данных не хватает количества двоичных разрядов, называются «длинными». Реализация арифметических операций над такими «длинными» числами получила название «длинной арифметики». Читать дальше >
Умножение двумерного массива на число
3 Декабрь
Заполнение матрицы элементами, окаймляющими элемент Akl, определенным образом
3 Декабрь
Постановка задачи:
Матрицу А(m, n) заполнить следующим образом. Для заданных k и l элементу akl присвоить значение 1; элементам, окаймляющим его (соседним с ним по вертикали, горизонтали и диагоналям) – значение 2; элементам следующего окаймления – значение 3 и так далее до заполнения всей матрицы. Читать дальше >
Нахождение наибольшего общего делителя двух натуральных чисел
3 Декабрь
Постановка задачи:
Найти наибольший общий делитель (НОД) двух введенных натуральных чисел, используя алгоритм Евклида (алгоритм Евклида: вычитаем из большего меньшее до тех пор, пока они не сравняются, полученное в результате число и есть НОД).
Решение:
Наибольшим общим делителем (НОД) двух целых чисел называется такое наибольшее по модулю число, которое делит эти два числа. Так как натуральные числа это положительные целые числа, то при вводе двух чисел а и b должно проверяться условие, что они больше нуля. Читать дальше >
Очереди и стеки
3 Декабрь
Стек – упорядоченный список, в котором добавление и удаление элементов всегда происходит на одном конце списка. Работает по принципу: Первый вошел -> последний вышел. Добавление элемента в стек называется проталкиванием элемента, а удаление – выталкиванием. Объявить стеки: Читать дальше >
