В этой беседе я начинаю рассказ про умножение вектора на вектор. Излагается только тривиальный алгоритм и указаны названия алгоритмов, которые будут изложены впоследствии. Здесь же выполнено сравнение нашего умножения, версии из MiniGMP и реализации на ассемблере из библиотеки MPIR для Core 2 (x86_64).
Рубрика: Беседы о программировании
Беседы о программировании 014 :: Длинная арифметика 08 :: Умножение вектора на лимб со сложением и вычитанием
Рассматривается операция умножения вектора на лимб с добавлением результата к другому вектору и с вычитанием результата из другого вектора. Выполнено сравнение трех вариантов исполнения и реализации из Mini-GMP.
Напоминаю, что проект по длинной арифметике теперь на GitHub.
Беседы о программировании 013 :: Длинная арифметика 07 :: Умножение вектора на лимб
Здесь показано как умножить вектор на число размером в один лимб. Описано два способа: технология LoHi и умножение через двойной лимб. Рассмотрена попытка переплюнуть компилятор на ассемблере.
Читать далее «Беседы о программировании 013 :: Длинная арифметика 07 :: Умножение вектора на лимб»
Беседы о программировании 012 :: Длинная арифметика 06 :: Сложение и вычитание со знаком
Здесь мы завершаем разговор об основных функциях сложения и вычитания. Речь пойдёт о создании класса знаковых векторов и реализаций функций сложения и вычитания для них на основе уже реализованных ранее функций для беззнаковых векторов.
Беседы о программировании 011 :: Подсчёт единичных битов
В этой беседе даётся обстоятельное описание всех известных мне подходов к подсчёту единичных битов в числах размером от 8 до 64 битов без знака. Показано, как основные приёмы позволяют строить различные алгоритмы, выполнено сравнение времени их работы и дана сводная таблица сравнения.
Статья, содержащая ту же информацию, опубликована мною на Хабре.
Читать далее «Беседы о программировании 011 :: Подсчёт единичных битов»
Беседы о программировании 010 :: Длинная арифметика 05 :: Вычитание векторов
В этой беседе кратко объясняется алгоритм вычитания векторов. Во многом всё аналогично сложению, поэтому основной упор делается на пояснении разницы между вычитанием и сложением. В конце приводится таблица сравнения алгоритмов.
Архив к видео [ zip ]
Беседы о программировании 009 :: Длинная арифметика 04. Сложение векторов III
Выполнена реализация сложения векторов «на месте». Показано, что в этом случае программа может работать быстрее, а при некоторых вариантах входных данных даже существенно быстрее.
Читать далее «Беседы о программировании 009 :: Длинная арифметика 04. Сложение векторов III»
Беседы о программировании 008 :: Длинная арифметика 03. Сложение векторов II
Выполнена реализация сложения векторов на ассемблере двумя способами. Две реализации сравниваются с тремя реализациями, написанными в прошлый раз. Показан более точный способ измерения времени с помощью runexe.
Читать далее «Беседы о программировании 008 :: Длинная арифметика 03. Сложение векторов II»
Беседы о программировании 007 :: Длинная арифметика 02. Сложение векторов I
Это первая часть бесед о сложении векторов. Рассматриваются три приёма, с помощью которых можно зафиксировать переполнение (перенос) при сложении двух беззнаковых чисел. Эти три приёма легли в основу процедуры сложения векторов с произвольной длиной, которая состоит из двух частей: сложения вектора с одним лимбом и сложение векторов с одинаковой длиной. Все реализованные процедуры протестированы, в конце показан результат измерения времени их работы. Также выполнено сравнение наших функций с функцией из Mini-GMP.
Читать далее «Беседы о программировании 007 :: Длинная арифметика 02. Сложение векторов I»
Беседы о программировании 006 :: Длинная арифметика 01. Нормализация и сравнение
В этой серии из цикла бесед о длинной арифметике рассматривается понятие базового беззнакового вектора, которое лежит в основе всех действий над длинными числами. Даются описания процедур нормализации и сравнения векторов. Здесь положено начало учебной программе, которая будет неким более широким аналогом Mini-GMP, переписанным на новый лад.
Читать далее «Беседы о программировании 006 :: Длинная арифметика 01. Нормализация и сравнение»