Беседы о программировании 019 :: Функции min(a,b) и max(a,b) для чисел со знаком

Здесь рассматриваются функции определения минимума и максимума из двух чисел со знаком. Приводится 7 реализаций как с ветвлениями, так и без них, как для общего случая, так и для некоторых частных случаев. Код программ приведён для случая 32-битовых чисел. В конце выполнено сравнение всех функций между собой и обнаружено забавное свойство операции сравнения. Текст статьи полностью повторяет содержание видеозаписи.

Читать далее «Беседы о программировании 019 :: Функции min(a,b) и max(a,b) для чисел со знаком»

Беседы о программировании 018 :: Длинная арифметика 10 :: Деление 2/1. Часть I

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

Источники, которые указаны в презентации:

  • N. Moller, T. Granlund. Improved division by invariant integers.
  • R. Brent, P. Zimmermann. Modern Computer Arithmetic.
  • C. Burnikel, J. Ziegler. Fast Recursive Division.
  • Исходники Mini-GMP.

Беседы о программировании 017 :: Функция abs(x) — абсолютное значение числа

Не менее важной чем sign(x) для целых чисел является функция взятия абсолютного значения abs(x). Существуют разные варианты реализации этой функции (как с ветвлениями, так и без них) и мы, как обычно, изучим их реальную стоимость. Ниже в статье излагается то же, что на видео.

Читать далее «Беседы о программировании 017 :: Функция abs(x) — абсолютное значение числа»

Беседы о программировании 016 :: Функция sign(x) — определение знака переменной

Ниже по тексту излагается то же самое, что на видео. Это сделано для удобства посетителей — кому как удобно, так и изучайте материал.

Функция определения знака очень важна для многих прикладных задач, поэтому существует довольно много вариантов её реализации. Мне известно 7 вариантов, некоторые из которых, правда, очень похожи друг на друга. Тем не менее, я задумался: который из вариантов лучше? Давайте разбираться.

Читать далее «Беседы о программировании 016 :: Функция sign(x) — определение знака переменной»

Беседы о программировании 015 :: Длинная арифметика 09 :: Умножение вектора на вектор

В этой беседе я начинаю рассказ про умножение вектора на вектор. Излагается только тривиальный алгоритм и указаны названия алгоритмов, которые будут изложены впоследствии. Здесь же выполнено сравнение нашего умножения, версии из MiniGMP и реализации на ассемблере из библиотеки MPIR для Core 2 (x86_64).

Беседы о программировании 014 :: Длинная арифметика 08 :: Умножение вектора на лимб со сложением и вычитанием

Рассматривается операция умножения вектора на лимб с добавлением результата к другому вектору и с вычитанием результата из другого вектора. Выполнено сравнение трех вариантов исполнения и реализации из Mini-GMP.

Напоминаю, что проект по длинной арифметике теперь на GitHub.

Беседы о программировании 013 :: Длинная арифметика 07 :: Умножение вектора на лимб

Здесь показано как умножить вектор на число размером в один лимб. Описано два способа: технология LoHi и умножение через двойной лимб. Рассмотрена попытка переплюнуть компилятор на ассемблере.

Читать далее «Беседы о программировании 013 :: Длинная арифметика 07 :: Умножение вектора на лимб»

Открытие проекта ZCA

Библиотека длинной арифметики, создаваемая в учебных целях в рамках видеокурса «Беседы о программировании», вполне может рассматриваться как самостоятельный учебный проект. Я решил оформлять теперь этот проект отдельно и выложить его на GitHub.

Читать далее «Открытие проекта ZCA»

Беседы о программировании 012 :: Длинная арифметика 06 :: Сложение и вычитание со знаком

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

Читать далее «Беседы о программировании 012 :: Длинная арифметика 06 :: Сложение и вычитание со знаком»

Беседы о программировании 011 :: Подсчёт единичных битов

В этой беседе даётся обстоятельное описание всех известных мне подходов к подсчёту единичных битов в числах размером от 8 до 64 битов без знака. Показано, как основные приёмы позволяют строить различные алгоритмы, выполнено сравнение времени их работы и дана сводная таблица сравнения.

Статья, содержащая ту же информацию, опубликована мною на Хабре.

Читать далее «Беседы о программировании 011 :: Подсчёт единичных битов»