Беседы о программировании :: 025 :: Длинная арифметика 15 :: Деление m/n

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

Беседы о программировании 023 :: Длинная арифметика 13 :: Деление 3/2. Часть II

Здесь завершается разговор о деление трёх лимбов на два. Показано как исправить ошибку из беседы 021 и рассмотрен алгоритм деления 3/2 без удвоенного лимба.

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

Изложены два алгоритма деления двух лимбов на один в том случае, когда удвоенного лимба нет. Эти алгоритмы сравниваются с теми, что изложены в беседе 018.

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

Излагается один из алгоритмов деления 3-х лимбов на 2 лимба, при условии, что имеется тип данных размером с удвоенный лимб. Эта важная операция лежит в основе деления длинных чисел.

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


Здесь рассматриваются функции определения минимума и максимума из двух чисел без знака. Данная статья — прямое продолжение статьи про эти же функции со знаком. Поэтому если вы её не читали, то лучше прочитать, так как здесь показана лишь разница метода 4 для знаковых и беззнаковых чисел, а также сводная таблица сравнения для всех вместе.

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

Беседы о программировании 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) — определение знака переменной»