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

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

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

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

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

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

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

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

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

Беседы о программировании 002 :: Замена целочисленного деления на умножение и сдвиг (теория)

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

Читать далее «Беседы о программировании 002 :: Замена целочисленного деления на умножение и сдвиг (теория)»

Беседы о программировании 001 :: Бинарный поиск

 

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

Читать далее «Беседы о программировании 001 :: Бинарный поиск»

Задача 1 — Бинарный поиск

[ Обновление: Данный пост более не актуален, см. тему Беседы о программировании 001 :: Бинарный поиск ]

Первая беседа будет посвящена бинарному поиску. Я расскажу о некоторых неочевидных для меня в прошлом соображениях по части данного алгоритма.

Читать далее «Задача 1 — Бинарный поиск»