Вычисление чисел Бернулли
В этом примере мы реализуем и анализируем алгоритм нахождения чисел Бернулли на языке программирования Julia.
Введение
Числа Бернулли — это последовательность рациональных чисел, которые играют важную роль в теории чисел, математическом анализе и других разделах математики. Они появляются, например, в разложении функций в ряд Тейлора, в формуле Эйлера-Маклорена и при вычислении сумм степеней натуральных чисел. Алгоритм Акиямы–Танигавы позволяет эффективно вычислять числа Бернулли с помощью рекуррентных соотношений.
Основная часть
Реализация функции для вычисления отдельного числа Бернулли
Функция bernoulli(n) вычисляет n-е число Бернулли по алгоритму Акиямы–Танигавы. Параметр n - индекс числа Бернулли. Функция возвращает рациональное число типа Rational{BigInt}.
function bernoulli(n)
# Создаём вектор для промежуточных вычислений размером n+1, элементы типа Rational{BigInt}
A = Vector{Rational{BigInt}}(undef, n + 1)
# Запускаем цикл по m от 0 до n
for m = 0 : n
# Инициализируем первый элемент согласно формуле: A[m+1] = 1 / (m+1)
A[m + 1] = 1 // (m + 1)
# Обратный цикл по j от m до 1 для обновления элементов A
for j = m : -1 : 1
# Обновляем A[j] по рекуррентной формуле
A[j] = j * (A[j] - A[j + 1])
end
end
# Возвращаем первое значение вектора A, которое соответствует числу Бернулли B_n
return A[1]
end
Вывод нечётных чисел Бернулли
Функция display(n) выводит на экран только нечётные числа Бернулли от до .
Нечётные числа Бернулли имеют нечётные числители.
function display(n)
# Вычисляем все числа Бернулли от 0 до n
B = map(bernoulli, 0 : n)
# Определяем ширину для выравнивания вывода: максимальное количество символов в числителе
pad = mapreduce(x -> ndigits(numerator(x)) + Int(x < 0), max, B)
# Вычисляем ширину заголовка (например, номера B(60) будет 2 символа)
argdigits = ndigits(n)
# Итерация по индексам от 0 до n
for i = 0 : n
# Проверяем, является ли числитель числа Бернулли нечётным
if numerator(B[i + 1]) & 1 == 1
# Выводим результат в виде "B( 0) = 1 / 1"
println(
"B(", lpad(i, argdigits), ") = ",
lpad(numerator(B[i + 1]), pad), " / ", denominator(B[i + 1])
)
end
end
end
Вызов функции для отображения чисел Бернулли до
display(60)
Более эффективное вычисление списка чисел Бернулли
Функция BernoulliList(len) вычисляет сразу весь список чисел Бернулли от до , что более эффективно, чем вычислять их по одному.
function BernoulliList(len)
# Вектор для промежуточных значений
A = Vector{Rational{BigInt}}(undef, len + 1)
# Вектор для хранения результата
B = similar(A)
# Цикл по индексу n от 0 до len
for n in 0 : len
# Инициализируем A[n+1] = 1/(n+1)
A[n + 1] = 1 // (n + 1)
# Внутренний цикл обновляет A[j]
for j = n : -1 : 1
A[j] = j * (A[j] - A[j + 1])
end
# Сохраняем n-е число Бернулли (первый элемент A) в B
B[n + 1] = A[1]
end
# Возвращаем вектор с числами Бернулли
return B
end
Перебираем список чисел и выводим только те, у которых числитель нечётный
for (n, b) in enumerate(BernoulliList(60))
# Проверка на нечётность числителя
isodd(numerator(b)) && println("B($(n-1)) = $b")
end
Заключение
В этом примере мы изучили и реализовали алгоритм вычисления чисел Бернулли на языке Julia. Мы рассмотрели два подхода: вычисление по одному числу и вычисление всего списка сразу, второй вариант оказался более эффективным. Результат выводится в удобочитаемом формате, причем только числа с нечётными числителями, так как они представляют наибольший интерес. Это важный элемент при решении задач математического анализа, теории чисел и комбинаторики.
Пример разработан с использованием материалов Rosetta Code