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

Эффективное по времени и памяти вычисление логарифмической функции вещественного аргумента на машине Шёнхаге | Прикладная дискретная математика. 2013. № 2(20).

Строится алгоритм FLE быстрого вычисления логарифмической функции ln(1 + ж) вещественного аргумента на полуинтервале [2 -5,1 — 2 -5) на машине Шёнхаге с оракульной функцией и даётся верхняя оценка его временной и емкостной сложности. Алгоритм FLE строится на основе разложения в ряд Тейлора по аналогии с алгоритмом быстрого вычисления экспоненты FEE, при этом дополнительно строится модифицированный алгоритм двоичного деления ModifBinSplit для гипергеометрических рядов. Для алгоритмов ModifBinSplit и FLE показывается квазилинейность по времени и линейность по памяти при вычислении на машине Шёнхаге, то есть принадлежность классу Sch(FQLIN-TIME//LIN-SPACE). Для расчёта логарифмической функции на произвольном промежутке используется мультипликативная редукция интервала.
  • Title Эффективное по времени и памяти вычисление логарифмической функции вещественного аргумента на машине Шёнхаге
  • Headline Эффективное по времени и памяти вычисление логарифмической функции вещественного аргумента на машине Шёнхаге
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 2(20)
  • Date:
  • DOI
Ключевые слова
логарифмическая функция, алгоритмические вещественные функции, квазилинейная временная сложность, линейная ёмкостная сложность, logarithmic function, algorithmic real functions, quasi-linear time complexity, linear space complexity
Авторы
Ссылки
Muller J.-M. Elementary functions. Algorithms and implementation. Boston: Birkhauser, 1997. 204 p.
Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах // Доклады АН СССР. 1962. Т. 145. №2. С. 293-294.
Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления. М.: Физмат-лит, 2003. Т. 2.
Косовская Т. М., Косовский Н. К. Принадлежность классу FP дважды полиномиальных паскалевидных функций над подпрограммами из FP // Компьютерные инструменты в образовании. 2010. №3. С. 3-7.
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536c.
Карацуба Е. А. Быстрое вычисление дзета-функции Римана Z(s) для целых значений аргумента s // Проблемы передачи информации. 1995. Т. 31. No. 4. С. 69-80.
Карацуба Е. А. Быстрое вычисление дзета-функции Гурвица и L-рядов Дирихле // Проблемы передачи информации. 1998. Т. 34. №4. С. 342-353.
Карацуба Е. А. Быстрое вычисление Z(3) // Проблемы передачи информации. 1993. Т. 29. №1. С. 68-73.
Karatsuba C. А. Fast evaluation of Bessel functions // Integral Transforms and Special Functions. 1993. V. 1. No. 4. P. 269-276.
Haible B. and Papanikolaou T. Fast multiple-presicion evaluation of series of rational numbers // Proc. of the Third Intern. Symposium on Algorithmic Number Theory, Portland, Oregon, USA. June 21-25, 1998. P. 338-350.
Карацуба Е. А. Fast evaluation of hypergeometric function by FEE // Proc. 3rd CMFT conference on computational methods and function theory, Nicosia, Cyprus, October 13-17, 1997. Singapore: World Scientific, 1999. Ser. Approx. Decompos. V. 11. P. 303-314.
Карацуба Е. А. Быстрые вычисления трансцендентных функций // Проблемы передачи информации. 1991. Т. 27. Вып. 4. С. 76-99.
Schonhage A., Grotefeld A. F. W, and Vetter E. Fast algorithms. A multitape Turing machine implementation. Leipzig: Brockhaus AG, 1994. 298 p.
Ko K. Complexity theory of real functions. Boston: Birkhauser, 1991. 310 p.
Карацуба Е. А. Быстрое вычисление exp(x) // 17-я Всесоюз. школа по теории информации и её приложениям. Проблемы передачи информации. 1990. Т. 26. №3. С. 109.
Яхонтов С. В., Косовский Н. К., Косовская Т. М. Эффективные по времени и памяти алгоритмические приближения чисел и функций: учеб. пособие. СПб., 2012. 256с.
Яхонтов С. В. Эффективное по времени и по памяти вычисление экспоненциальной функции комплексного аргумента на машине Шёнхаге // Вестник С.-Петербург. унта. Сер. 10. Прикладная математика. Информатика. Процессы управления. 2011. Вып. 4. С.97-110.
Яхонтов С. В. Вычисление гипергеометрических рядов с квазилинейной временной и линейной емкостной сложностью // Вестник Самарского государственного технического университета. Сер. Физико-математические науки. 2011. Вып. 2 (17). С. 239-249.
Эффективное по времени и памяти вычисление логарифмической функции вещественного аргумента на машине Шёнхаге | Прикладная дискретная математика. 2013. № 2(20).
Эффективное по времени и памяти вычисление логарифмической функции вещественного аргумента на машине Шёнхаге | Прикладная дискретная математика. 2013. № 2(20).
Полнотекстовая версия