Pull to refresh
12
Karma
0
Rating
Дмитрий Протопопов @dprotopopov

Программирование

Компиляторная бомба: 29 байт кода → 16 ГБ .exe

Должно быть — Данный код определяет функцию main как большой массив и инициализирует его ПОСЛЕДНИЙ элемент (а не первый)

Аппроксимируем функцию с помощью нейросети

Цель была обозначена в самом начале статьи — освоение библиотеки работы с нейронной сетью, в большей мере для саморазвития. Полного исследования я не делал.
Запуская программу при разных параметрах (коэффициент переобучения, количество итераций обучения, количество нейронов внутреннего слоя) я получал разные (в том числе не особо удовлетворительные) результаты.
Я и ранее использовал тему аппроксимации функций для статьи habr.com/post/277541

Аппроксимируем функцию с помощью нейросети

Вы правы — я сперва определил разрывную в точке M функцию E(x,M) для указании в формуле, а потом быстро заменил её на непрерывную функцию сигмоида S(x) = 1 / (1 + exp(-x)).
Значение 1/2 при x=M я указал для похожести со значением S(0)=1/2.

Аппроксимируем функцию с помощью нейросети

«наилучшим образом» зависит от выбранной методики сравнения двух функций, например среднеквадратичное отклонение, или максимальное отклонение или другая методика сравнения.
Далее для нейросети я использовал cost = tf.losses.mean_squared_error(y, model) — минимизация среднеквадратичного отклонения.

Расчет биномиальных коэффициентов с использованием Фурье-преобразований

Где
FFT – операция прямого преобразования Фурье
BFT – операция обратного преобразования Фурье

Расчет биномиальных коэффициентов с использованием Фурье-преобразований

внёс изменения в статью и в библиотеку 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);
}

Расчет биномиальных коэффициентов с использованием Фурье-преобразований

Да, сам я виноват — использовал обозначения у полинома и у вектора одинаковые.
полином от переменной 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

Расчет биномиальных коэффициентов с использованием Фурье-преобразований

умножить-разделить? — это имеется ввиду?
Просто мне интересны сейчас темы с использованием Фурье-преобразований.

Расчет биномиальных коэффициентов с использованием Фурье-преобразований

все пишут за 2-5 минут — это треугольник Паскаля.
При вычислении с помощью треугольника Паскаля трудоёмкость имеет оценку O(n^2).
или покажите формулу/алгоритм — можно в виде публикации.
… я не волшебник — я только учусь…

Расчет биномиальных коэффициентов с использованием Фурье-преобразований

Спасибо, поправил текст.
Да, конечно все понимают, что биномиальные коэффициенты симметричны, причём с ростом n график приближается к графику нормального распределения (после соответствующего нормирования).
причина по которой все смотрят не на половину — формула (a+b)^n — при подстановке реальных чисел — там вычисленные значения разложения различаются — то есть вычисляют значения C(i,n)*a^i*b^(n-i)

Расчет биномиальных коэффициентов с использованием Фурье-преобразований

описался — вот правильно:
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

Расчет биномиальных коэффициентов с использованием Фурье-преобразований

Согласен, что для приближенного вычисления больших коэффициентов лучше воспользоваться рядом Стирлинга.
Просто мне интересны сейчас темы с использованием Фурье-преобразований.

Расчет биномиальных коэффициентов с использованием Фурье-преобразований

при x=0.5 влезет больше (см. параметры метода GetDoubles)
только полученные коэффициенты надо будет умножать на 2^i

Расчет биномиальных коэффициентов с использованием Фурье-преобразований

реальную скорость алгоритма

Вот вам и тема для исследования.
Хотя всё это можно оценить и теоретически, зная спецификацию процессора.
В статье есть небольшая обманка — возведение в степень тоже может быть выполнено за O(log n) операций умножения на дискретном процессоре.

Расчет биномиальных коэффициентов на Си (С++) и Python

взятое возвращаю кармой.
Можете сравнить и описать на Хабре эксперимент для разных типов данных, для C++ и C# — многих заинтересует.

Расчет биномиальных коэффициентов с использованием Фурье-преобразований

расчет погрешностей не делал.
при расчёте надо смотреть на упаковку double в соответствии с IEEE — это мантиса+экспонета = 64 бита

Расчет биномиальных коэффициентов на Си (С++) и Python

Мой ответ на Вашу публикацию habrahabr.ru/post/274729 — Расчет биномиальных коэффициентов с использованием Фурье-преобразований

Information

Rating
5,885-th
Location
Москва, Москва и Московская обл., Россия
Date of birth
Registered
Activity