:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Быстрые вычисления
  Быстрое вычисление функций и констант




  Функции



Быстрое возведение в степень
Логарифмический алгоритм возведения в степень. Применяется практически везде.

Тригонометрические функции
Быстрое вычисление функций и аркфункций с нужной точностью.

Вычисление функции Эйлера
Количество чисел, меньших N и взаимно простых с ним.

Вычисление факториала
Точный алгоритм вычисления факториала и наметки к реализации.

Gamma function
Эффективные методы вычисления аппроксимации факториала и гамма-функции.

Квадратный корень - метод Ньютона
Разобрано применение метода Ньютона для квадратного корня. С исходником.

Вычисление квадратного корня из целого числа
Целочисленное приближение к квадратному корню из целого числа.

Точное вычисление обратного числа, корня m-й степени
Быстрые итеративные методы для корней и обратного числа.

  Константы



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

Квадратный корень из 2
Вкусно, быстро, полезно. С исходником..

The Euler constant gamma
Вычисление гамма - константы Эйлера.

The Apery's constant
Вычисление константы Apery: дзета-функции от 3. Т.е бесконечной суммы 1/n, n=1,2....

Логарифм 2
Вычисление логарифма 2 разными способами.

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

Вычисление с большой точностью числа е
Классический метод с исходником, а также ряд продвинутых.

Вычисление N-го знака
Способы быстрого вычисления N-го бита различных констант. С примерами..

Числа Фибоначчи за O(logn)

Binary splitting method
Большинство рядов, используемых для вычисления констант, имеют время O(n2) Этот метод вкупе с FFT-умножением позволяет вычислять за O(n log(n)3) (или даже O(n log(n)2). С примерами.

Acceleration of the convergence of series
Методы улучшения сходимости бесконечных серий с целью более быстрых и точных вычислений.

Ссылки на материалы о быстрых алгоритмах от Е.А. Карацубы

Быстрые алгоритмы и метод БВЕ

Метод Карацубы "Divide and conquer"

Ответы на часто задаваемые