Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 31
Интересно. В статье прямо заимствованы фрагменты из моей статьи Расчет биномиальных коэффициентов на Си (С++) , но об этом даже не упомянуто.
Я полагаю, что расчет C(67,33) по треугольнику Паскаля с запоминанием (дальше они не влезают в unsigned64) потребует меньше времени, чем этот Фурье несмотря на «худший» O (n-то не велико, а алгоритм расчета намного сложнее). А уж расчет всех коэффициентов для n<=67 по треугольнику вообще самый быстрый.
Я полагаю, что расчет C(67,33) по треугольнику Паскаля с запоминанием (дальше они не влезают в unsigned64) потребует меньше времени, чем этот Фурье несмотря на «худший» O (n-то не велико, а алгоритм расчета намного сложнее). А уж расчет всех коэффициентов для n<=67 по треугольнику вообще самый быстрый.
Для n=67 было бы интересно сравнить время Паскаль vs Фурье. Можно в тактовых единицах.
Добавил ссылку на статью habrahabr.ru/post/274689
меня терзают жуткие сомнения. можно посмотреть расчет погрешностей?
Было бы значительно лучше, если бы вы добавили реальную скорость этого алгоритма и какого-нибудь из упомянутого выше поста. Интересно, начиная с каких N получается выигрыш?
> При вычислении с помощью треугольника Паскаля трудоёмкость имеет оценку O(n^2).
> При вычислении с помощью быстрых Фурье-преобразований трудоёмкость имеет оценку O(n*log n).
Сам массив значений биномиальных коэффициентов от С_n^0 до C_n^n занимает что-то типа O(n^2) бит. Как вы умудрились их посчитать за асимптотически меньшее время?
> При вычислении с помощью быстрых Фурье-преобразований трудоёмкость имеет оценку O(n*log n).
Сам массив значений биномиальных коэффициентов от С_n^0 до C_n^n занимает что-то типа O(n^2) бит. Как вы умудрились их посчитать за асимптотически меньшее время?
Конечно здесь имеется в виду приближённое вычисление, без длинной арифметики — вон, в коде double повсюду. Преобразование фурье с длинными числами вообще редкая в применении вещь.
Тогда с тем же успехом можно сложить первые эннадцать рядом треугольника Паскаля в массив и объявить о революционном алгоритме, который вычисляет биномиальные коэффициенты за O(1).
Для приближенного вычисления больших коэффициентов уж лучше воспользоваться рядом Стирлинга.
Для приближенного вычисления больших коэффициентов уж лучше воспользоваться рядом Стирлинга.
Чем вас не устроил стандартный алгоритм за O(n)?
Согласен, что для приближенного вычисления больших коэффициентов лучше воспользоваться рядом Стирлинга.
Просто мне интересны сейчас темы с использованием Фурье-преобразований.
Просто мне интересны сейчас темы с использованием Фурье-преобразований.
Ряд Стирлинга асимптотический и на контесте вы с ним Accepted никогда не получите. Особенно, если биномиальные коэффициенты нужно по простому модулю считать. Я говорю про стандартный алгоритм, который все пишут за 2-5 минут.
все пишут за 2-5 минут — это треугольник Паскаля.
При вычислении с помощью треугольника Паскаля трудоёмкость имеет оценку O(n^2).
или покажите формулу/алгоритм — можно в виде публикации.
… я не волшебник — я только учусь…
При вычислении с помощью треугольника Паскаля трудоёмкость имеет оценку O(n^2).
или покажите формулу/алгоритм — можно в виде публикации.
… я не волшебник — я только учусь…
Теперь, когда вы знаете, что он существует и тривиален, вам не составит труда его придумать. Разве можно лишать вас этого удовольствия?
умножить-разделить? — это имеется ввиду?
Просто мне интересны сейчас темы с использованием Фурье-преобразований.
Просто мне интересны сейчас темы с использованием Фурье-преобразований.
внёс изменения в статью и в библиотеку FFTTools.
спасибо.
public static void GetLongs(long[] array, long x = 1)
{
var n = array.Length — 1;
if (array.Length > 0) array[0] = 1;
for (var i = 0; i < n; i++)
array[i + 1] = x*array[i]*(n — i)/(i + 1);
}
спасибо.
public static void GetLongs(long[] array, long x = 1)
{
var n = array.Length — 1;
if (array.Length > 0) array[0] = 1;
for (var i = 0; i < n; i++)
array[i + 1] = x*array[i]*(n — i)/(i + 1);
}
Учитывая интересы автора, наверное, тем, что в нём нет преобразования Фурье. :)
Рассмотрим полином F(x)=1+x и его свёртку с самим собой n раз
Fx..xF = SUM С( i, n-1 )*x^i
Я не понял это место.
По каким значениям t надо суммировать при свёртке, чтобы получить то что написано?
Fx..xF(t) = SUM F(i1(0))*...*F(i(n-1)) | i1(0)+...+i(n-1)=t
описался — вот правильно:
Fx..xF(t) = SUM F(i(1))*...*F(i(n-1)) | i(1)+...+i(n-1)=t
x=1
F(0) == 1
F(1) == x
Fx..xF(t) = SUM F(i(1))*...*F(i(n-1)) | i(1)+...+i(n-1)=t
x=1
F(0) == 1
F(1) == x
По-прежнему непонятно.
Вот в этом нет смысла, к примеру.
F(x)=1+x
F(0) == 1
F(1) == x
Вот в этом нет смысла, к примеру.
Да, сам я виноват — использовал обозначения у полинома и у вектора одинаковые.
полином от переменной x может быть записан как вектор коэффициентов полинома/многочлена.
чтобы не плодить обозначений через F обозначаю и полином и вектор коэффициентов. Прочтение зависит от контекста.
F(x)=1+x — это полином/многочлен
x=1 — это присвоение переменной x значения
F[0] = 1 — это элемент с индексом 0 в векторе
F[1] = x — это элемент с индексом 1 в векторе
Fx..xF[t] = SUM F[i[1]]*...*F[i[n-1]] | i[1]+...+i[n-1]=t
полином от переменной x может быть записан как вектор коэффициентов полинома/многочлена.
чтобы не плодить обозначений через F обозначаю и полином и вектор коэффициентов. Прочтение зависит от контекста.
F(x)=1+x — это полином/многочлен
x=1 — это присвоение переменной x значения
F[0] = 1 — это элемент с индексом 0 в векторе
F[1] = x — это элемент с индексом 1 в векторе
Fx..xF[t] = SUM F[i[1]]*...*F[i[n-1]] | i[1]+...+i[n-1]=t
«в расчете биномиальныХ коэффициентов.»
У Вас опечатка.
Вставлю немного своих дилетантских соображений:
Интересно, все ли обращали внимание на, казалось бы, элементарную вещь с выводом треугольника Паскаля (если через массивы), что считать можно только половину строки: ), а массив можно просто переворачивать, правда, нужна проверка на четность, чтобы переворачивать и такие строки +6+15+20+15+6+.
У Вас опечатка.
Вставлю немного своих дилетантских соображений:
Интересно, все ли обращали внимание на, казалось бы, элементарную вещь с выводом треугольника Паскаля (если через массивы), что считать можно только половину строки: ), а массив можно просто переворачивать, правда, нужна проверка на четность, чтобы переворачивать и такие строки +6+15+20+15+6+.
Спасибо, поправил текст.
Да, конечно все понимают, что биномиальные коэффициенты симметричны, причём с ростом n график приближается к графику нормального распределения (после соответствующего нормирования).
причина по которой все смотрят не на половину — формула (a+b)^n — при подстановке реальных чисел — там вычисленные значения разложения различаются — то есть вычисляют значения C(i,n)*a^i*b^(n-i)
Да, конечно все понимают, что биномиальные коэффициенты симметричны, причём с ростом n график приближается к графику нормального распределения (после соответствующего нормирования).
причина по которой все смотрят не на половину — формула (a+b)^n — при подстановке реальных чисел — там вычисленные значения разложения различаются — то есть вычисляют значения C(i,n)*a^i*b^(n-i)
Замечания по обозначениям.
1. В преобразовании Фурье для аналоговых сигналов используется коэффициент 1/sqrt(2pi), а в ДПФ — 1/2pi. Логично использовать что-то одно.
2. А с крышечкой — это симметричная квадратная матрица, а не вектор (не точно скопирован текст из википедии)
3. Обратное БПФ — это обычно ifft. Как расшифровать BFT? В яндекс-поиске первое после ссылок на Ваши тексты — BFT: Bit Filtration Technique.
1. В преобразовании Фурье для аналоговых сигналов используется коэффициент 1/sqrt(2pi), а в ДПФ — 1/2pi. Логично использовать что-то одно.
2. А с крышечкой — это симметричная квадратная матрица, а не вектор (не точно скопирован текст из википедии)
3. Обратное БПФ — это обычно ifft. Как расшифровать BFT? В яндекс-поиске первое после ссылок на Ваши тексты — BFT: Bit Filtration Technique.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Расчет биномиальных коэффициентов с использованием Фурье-преобразований