Беседы о программировании 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. Нормализация и сравнение»

005 :: Длинная арифметика 00 (Начало сериала)

Эта беседа открывает сериал «Длинная арифметика», в котором я постараюсь последовательно изложить основные приёмы современной длинной арифметики от простых алгоритмов до достаточно сложных. Конкретно в этой серии даются базовые представления и необходимые для начала ссылки (в том числе для новичков), а также описание структуры длинных чисел, с которыми мы будем работать дальше. В этой серии нет алгоритмов, это лишь вступление.

Читать далее «005 :: Длинная арифметика 00 (Начало сериала)»

Беседы о программировании 004 :: Остаток от деления на степень двойки ± 1

Рассматривается алгоритмический трюк, позволяющий выполнить быстрый поиск остатка от деления на числа вида 2n-1 и 2n+1. Показана общая идея, рассмотрены частные случаи деления 32-битовых и 64-битовых чисел, выполнено сравнение с обычной процедурой нахождения остатка.

Читать далее «Беседы о программировании 004 :: Остаток от деления на степень двойки ± 1»

Беседы о программировании 003 :: Проблема конвертирования десятичной дроби в формат с плавающей точкой IEEE-754

Эта видеобеседа посвящена одной важной проблеме конвертирования произвольной десятичной дроби в формат с плавающей точкой. Речь пойдёт об ошибке округления в процессе конвертирования. На момент записи видео автору не было известно ни одного компилятора, который был бы избавлен от такой ошибки. Вы узнаете о том, что перевод числа в формат с плавающей точкой – это не такая простая задача, как может показаться поначалу, особенно после просмотра различных уроков о том, как всё просто и замечательно в теории.

Читать далее «Беседы о программировании 003 :: Проблема конвертирования десятичной дроби в формат с плавающей точкой IEEE-754»

Простые тесты для проверки конвертирования десятичной дроби в формат с плавающей точкой IEEE-754

[ Обновление: пост ещё актуален, но 3-я беседа с пояснениями уже опубликована ]

Перед следующей, 3-й беседой я бы хотел, чтобы Вы проверили то, как Ваш компилятор языка Си/Си++ осуществляет конвертирование числа в формат с плавающей точкой (одинарной — float — и двойной — double — точности). Я даю несложную программу с несколькими довольно простыми тестами. Попробуйте её скомпилировать и запустить.

Читать далее «Простые тесты для проверки конвертирования десятичной дроби в формат с плавающей точкой IEEE-754»