| 1 |
1 января 2016 г.-31 декабря 2016 г. |
Альтернативные методы вычисления функций действительного переменного |
| Результаты этапа: Исследованы (а) технология подготовки таблично ориентированных функций для нахождения значений функций одной вещественной переменной и (б) метод вытеснения для вычисления функций действительного переменного.
В качестве основной гипотезы принята шести этапная технология подготовки таблично ориентированных функций: (1) выбор и исследование класса модельных функций, (2) выбор алгоритмов вычисления табличных значений модельных функций, (3) выбор стандартных диапазонов и генерации значений модельных функций, (4) разработка способов хранения таблиц модельных функций, (5) разработка таблично ориентированных алгоритмов нахождения значений модельных функций, (6) анализ полученных алгоритмов.
Исследован метод вытеснения, предназначенный для вычисления значений (этап 2 технологии) логарифмических и показательных функций и зависящий от фиксированного набора констант, количество которых определяется длиной мантиссы двоичного представления чисел. Установлено, что при массовых расчетах для вычисления очередного логарифма помимо логических операций достаточно выполнить одно умножение. |
| 2 |
1 января 2017 г.-31 декабря 2017 г. |
Альтернативные методы вычисления функций действительного переменного |
| Результаты этапа: В 2017 году в рамках Проекта исследован специальный класс быстрых методов вычисления функций действительного переменного. В том числе,
- предложен общий подход к реализации алгоритмов вычисления элементарных функций;
- в развитие общего подхода разработаны алгоритмы вычисления двух модельных функций;
- выведены оценки трудоемкости модельных алгоритмов, демонстрирующие эффективность подхода.
Подход к вычислению элементарных функций основывается на том факте, что любое положительное число можно однозначно представить в нормализованном виде. Для некоторых элементарных функций это представление позволяет свести вычисление значений для произвольного аргумента к вычислению значений для аргументов из [0.5;1). В Проекте в качестве модельного алгоритма используется алгоритм вычисления двоичного логарифма.
В области [0.5;1) рассматриваются конечные фрагменты последовательности специального вида. В качестве иллюстрации получены первые 64 члена упомянутой последовательности с точностью до 64 двоичных знаков, а также получены формальные свойства последовательности: монотонность, рекуррентные зависимости и оценки погрешности.
Каждый модельный алгоритм базируется на заранее выбранном конечном фрагменте последовательности (на сетке из n узлов), что позволяет уточнить универсальные свойства последовательности.
Доказано, что свойства сетки позволяют построить весьма компактный алгоритм log2v1 вычисления двоичных логарифмов с точностью до n двоичных знаков после запятой. В описании алгоритма на паскалеподобном алгоритмическом языке считается известной процедура анализа нормализованных действительных чисел. Показана связь фрагментов алгоритма log2v1 со свойствами сетки. С точки зрения временной сложности-в-худшем-случае алгоритм log2v1 имеет сложность O(n).
Для определения сложность модельного алгоритма в среднем рассмотрено взаимно однозначное преобразование интервалов сетки, которое в свою очередь порождает разбиение области изменения аргумента на полуинтервалами с одинаковым количеством вычислительных операций. Каждое разбиение порождает средневзвешенную оценку сложности алгоритма log2v1, имеющую сложное выражение. Для средневзвешенной оценки приводится более компактное аналитическое выражение. При этом доказано, что если алгоритм log2v1 тестируется в серии испытаний, в которой аргументы равномерно распределены на [0.5; 1), то среднее количество делений, приходящихся на одно вычисление log2v1(x), имеет предел по вероятности, имеющий аналитическое выражение.
В развитие полученных результатов исследован вопрос о возможности усовершенствования алгоритма log2v1 с целью снижения его трудоемкости. Положительный ответ на этот вопрос связан с (предложенной) модификацией сетки. Показано, что модифицированная сетка обладает двумя дополнительными свойствами, которые трансформируются в два дополнительных утверждения. Учет дополнительных утверждений позволил построить и описать алгоритм log2v2, представляющий собой модифицированную версию алгоритма log2v1. Показана связь алгоритма log2v2 со свойствами модифицированной сетки. Особенность алгоритма log2v2 состоит в использовании специально построенного массива числовой информации. Показано, что с точки зрения временной сложности-в-худшем-случае алгоритм log2v2 также имеет оценку O(n) и в этом смысле алгоритм log2v2 не отличается от log2v1.
Отличие состоит в оценках средних сложностей алгоритмов. Выражение для оценки в среднем модифицированного алгоритма не представляет затруднений, определенные сложности представляет вывод компактного аналитического выражения. С этой целью в Проекте доказаны две леммы, позволившие получить аналитическую оценку сложности в среднем. Доказано, что сложность в среднем оригинального алгоритма в разы уступает сложности в среднем модифицированного алгоритма.
В предельном случае построенная сетка позволит находить первые n двоичных разрядов числа $log_2(x)$ вообще без использования операций деления/умножения над вещественными числами. При таком подходе расширенная сетка фактически играет роль специфической таблицы значений, а задача вычисления логарифма сводится к поиску в таблице. Намеченный таблично-ориентированный метод вычисления функций действительного переменного нуждается в отдельном исследовании. |
| 3 |
1 января 2018 г.-31 декабря 2018 г. |
Альтернативные методы вычисления функций действительного переменного |
| Результаты этапа: В исследовании рассмотрены ключевые аспекты технологии программной реализации таблично ориентированных функций вещественной переменной. Главная проблема технологии состоит в построении таблицы значений заданной функции для всех аргументов из некоторого стандартного диапазона. При этом погрешность вычислений и область определения функции определяются двоичным форматом представления чисел, а переход от значений функции для аргументов из стандартного диапазона к значениям функции для всей области определения не влияет на окончательную точность нахождения значений.
В исследовании представлены и обоснованы требования, которым должны удовлетворять методы формирования таблиц значений: во-первых, методы должны учитывать особенности и особенности процесса формирования, во-вторых, методы должны обеспечивать верификацию вычисленных значений. В интересах реализации и массового применения таблично ориентированных функций вычисленные значения необходимо эффективно сжимать с тем, чтобы обеспечить их относительно компактное хранение и быстрый поиск. Пилотное исследования таблично ориентированной технологии выполнено на наборе модельных функций, включающим элементарные и специальные функции.
В исследовании описывается подход к вычислению элементарных функций посредством специально построенной сетки узлов на полуинтервале [0.5;1). Для двух вариантов сетки узлов предложены алгоритмы вычисления логарифмов, а также приводятся и обосновываются оценки сложности этих алгоритмов. Показывается, что в зависимости от свойств сетки оценки средней трудоемкости вычислений могут изменяться весьма значительно.
В исследовании предлагаются особые структуры данных, названные таблицами точных произведений, обсуждаются вопросы их применения и ставится задача разработки практически применимых алгоритмов, ориентированных на построение таких таблиц. Исходя из понимания переборного характера упомянутых алгоритмов, в рамках исследования сформулированы и доказаны специальные свойства точных произведений, позволяющие отсекать на ранних этапах заведомо неуспешные варианты. Показывается, что учет специальных свойств существенно влияет на структуру переборного алгоритма и, в конечном итоге, позволяет строить практически значимые таблицы точных произведений, которые, в свою очередь, позволяют сократить объемы хранимой информации в таблично ориентированных реализациях функций действительного переменного.
|
