Прикладная дискретная математика
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


ПДМ, 2013, номер 2(20), страницы 101–114 (Mi pdm414)  

Вычислительные методы в дискретной математике

Эффективное по времени и памяти вычисление логарифмической функции вещественного аргумента на машине Шёнхаге

С. В. Яхонтов

Санкт-Петербургский государственный университет, г. Санкт-Петербург, Россия

Аннотация: Строится алгоритм FLE быстрого вычисления логарифмической функции $\ln(1+x)$ вещественного аргумента на полуинтервале $[2^{-5},1-2^{-5})$ на машине Шёнхаге с оракульной функцией и даётся верхняя оценка его временной и емкостной сложности. Алгоритм FLE строится на основе разложения в ряд Тейлора по аналогии с алгоритмом быстрого вычисления экспоненты FEE, при этом дополнительно строится модифицированный алгоритм двоичного деления ModifBinSplit для гипергеометрических рядов. Для алгоритмов ModifBinSplit и FLE показывается квазилинейность по времени и линейность по памяти при вычислении на машине Шёнхаге, то есть принадлежность классу Sch(FQLIN-TIME//LIN-SPACE). Для расчёта логарифмической функции на произвольном промежутке используется мультипликативная редукция интервала. Для расчёта логарифмической функции на произвольном промежутке используется мультипликативная редукция интервала.

Ключевые слова: логарифмическая функция, алгоритмические вещественные функции, квазилинейная временная сложность, линейная ёмкостная сложность.

Полный текст: PDF файл (632 kB)
Список литературы: PDF файл   HTML файл
Тип публикации: Статья
УДК: 510.25+510.52+519.688

Образец цитирования: С. В. Яхонтов, “Эффективное по времени и памяти вычисление логарифмической функции вещественного аргумента на машине Шёнхаге”, ПДМ, 2013, № 2(20), 101–114

Цитирование в формате AMSBIB
\RBibitem{Yak13}
\by С.~В.~Яхонтов
\paper Эффективное по времени и памяти вычисление логарифмической функции вещественного аргумента на машине Шёнхаге
\jour ПДМ
\yr 2013
\issue 2(20)
\pages 101--114
\mathnet{http://mi.mathnet.ru/pdm414}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm414
  • http://mi.mathnet.ru/rus/pdm/y2013/i2/p101

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:313
    Полный текст:124
    Литература:36
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021