Т.е. надо дкт?

Например.

Они работают быстрее не по этому.

Знаешь как быстрее — запили.

И надо для любых N, либо там дальше с табличками, аля n = 8? А какая точность нужна?

N любое как в FFTW, точность как хотя бы как наивная реализация DCT.

Знаешь как быстрее — запили.

Ну я пока не знаю как оно работает.

N любое как в FFTW, точность как хотя бы как наивная реализация DCT.

Ну я взял fftw_plan_r2r_1d(N, x, X, FFTW_REDFT10, FFTW_MEASURE) - вроде твоё. Но результаты разные.

http://www.fftw.org/fftw3_doc/1d-Real_002deven-DFTs-_0028DCTs_0029.html#1d-Re... - тут вроде формулка такая же, только множитель 2?, а не sqrt(2 / N) * s(k) как тут: https://unix4lyfe.org/dct-1d/

Но чёт не особо воспроизводятся результаты.

Я вроде как запилил формулку из манула:

void f(int n, double * x, double * y) {
  for(int k = 0; k < n; ++k) {
    double sum = 0.;
    for(int j = 0; j < n ; ++j) {
      sum += x[j] * cos(M_PI * (j + 0.5) * k/n);
    }
    y[k] = sum * 2;
  }
}

Но не фортануло, чет. Помоги, пж.

k/n == 0, что ли? ліл

k/n == 0, что ли?

Почему 0? Если ты не про первую итерацию, то ты про инты, - оно само кастится, либо о чем ты?

Сделай множитель как в FFTW, у них сказано:

In defining the discrete cosine transform, some authors also include additional factors of √2(or its inverse) multiplying selected inputs and/or outputs. This is a mostly cosmetic change that makes the transform orthogonal, but sacrifices the direct equivalence to a symmetric DFT.

брутфорсом такие задачи решают только лалки анскильные :)

там всё — бпф :)

здесь: http://web.mit.edu/~emin/www.old/source_code/fft/fft.c анскильное решение почти в лоб (несколько усовершенствованным методом), http://fftw.org лет 15 взад считался самым пацанским решением. сейчас, естественно, есть значительно лучше.

лет 15 взад считался самым пацанским решением. сейчас, естественно, есть значительно лучше.

Что есть лучше? Знаю MKL и CUDA, есть что-нибудь опенсорсовое?

Чёт я не знаю как называется такой класс рисовалок

Так этож визуал, пытаюсь нарисовать эффект от психоделиков.

гугл не помогает

гугли попиксельное рисование.

1. любой «разделяй и властвуй» хорошо параллелится.

2. сумматоров в видеокартах сильно больше.

3. ....

4. профит.

любой «разделяй и властвуй» хорошо параллелится.

Любой не будет быстрее FFTW. Я про реализации поинтересовался.

шо, опять?

то что они перестали публиковать результаты бенчмарков лет 8 взад тебе как бы ни на что не намекает? возьми clfft, например.

ну вперёд, предложи не брутфорс. Ладно, уберём даже условие с треугольниками по синим точкам.

Как выявить максимальную популяцию точек на попугай при неизвестном попугае, но попугай треульный.

http://web.mit.edu/~emin/www.old/source_code/fft/fft.c

Говно и то для n=const.

анскильное решение почти в лоб (несколько усовершенствованным методом)

Где взять не анскильное?

сейчас, естественно, есть значительно лучше.

Где их можно найти?

ну вперёд, предложи не брутфорс

надо было ходить на уроки геометрии...

ну ладно, объясню для детей с задержкой в умственном развитии...

для начала ты должен научиться вычислять попадает ли красная точка внутрь синего треугольника. за этим — в гугл. потом берёшь 3 синие точки и строишь треугольник. проверяешь все ли красные точки туда попали. если ни одной — строишь треугольник по другим точкам, если все — конец, если есть, но не все — на основе этого треугольника строишь новый, побольше. гоуту начало.

> http://web.mit.edu/~emin/www.old/source_code/fft/fft.c

Говно и то для n=const.

зато алгоритм реализован правильно. сойдёт для проверки твоего говна.

Где взять не анскильное?

если для не предназначенных для быстрых вычислений x86-64 — http://fftw.org/

> сейчас, естественно, есть значительно лучше.

Где их можно найти?

http://amd.com/

потом берёшь 3 синие точки и строишь треугольник. проверяешь все ли красные точки туда попали.

Это всегда будет так, при равномерном распаределении.

если все — конец

Оло, балаболка, задача заключается нахождении минимального треугольника по синим точкам внутри которого самая большая популяция красных точек на еденицу площади.

гоуту начало.

Балаболка - это и есть брутфорс. Что сказать-то хотел? Обосраться?

зато алгоритм реализован правильно. сойдёт для проверки твоего говна.

Чем сойдёт?

если для не предназначенных для быстрых вычислений x86-64

Такие куллстори.

http://amd.com/

Конкретней.

Это всегда будет так, при равномерном распаределении.

тебя мама не учила не говорить слова смысл которых ты не понимаешь?

задача заключается нахождении минимального треугольника

это тебе домашнее задание. если ты вдруг с первого раза угадал треугольник куда попали все красные точки, то надо уменьшать треугольник пока все помещаются. мне лень писать такие простыни, а задача для такого школьника как ты большая — на неделю домашней работы потянет.

это и есть брутфорс. Что сказать-то хотел? Обосраться?

обосрался в очередной раз ты. брутфорс — перебор всех треугольников — сложность o(n*n*n). здесь треугольники только увеличиваются — сложность o(n).

Чем сойдёт?

правильным ответом. чтобы ты смог проверить своё говно.

Конкретней.

юзай поиск если межушного нервного узла на это хватит.

тебя мама не учила не говорить слова смысл которых ты не понимаешь?

Обосрался.

это тебе домашнее задание. если ты вдруг с первого раза угадал треугольник куда попали все красные точки, то надо уменьшать треугольник пока все помещаются. мне лень писать такие простыни, а задача для такого школьника как ты большая — на неделю домашней работы потянет.

Обосрался.

брутфорс — перебор всех треугольников

Кто же это сказал?

здесь треугольники только увеличиваются — сложность o(n).

Чего? Что ты несёшь.

Чего увеличивать. Как же меня одалевает разговаривать с «людьми» с уровнем развития в районе амёбы.

Повторю ещё раз, дана задача:

нахождении минимального треугольника по синим точкам внутри которого самая большая популяция красных точек на еденицу площади.

Жду решения не брутфорсом. Продолжай дальше играть в дурочка.

правильным ответом. чтобы ты смог проверить своё говно.

Да ты гений, правильный ответ я могу получить и в любой либе. А ещё раз, зачем же нужен код?

юзай поиск если межушного нервного узла на это хватит.

Т.е. куракерай ты, а ищи я? Ну это же замечательно.

Обосрался.

обосрался в своём утверждении о том что любой треугольник из синих точек будет содержать все красные — ты.

Обосрался.

это один из граничных случаев в этой задаче. если бы ты начал писать код, то наткнулся бы на ещё несколько. мне лень описывать словами каждый if в программе которую ты даже не начал писать. когда начнёшь писать — спрашивай конкретно — отвечу.

брутфорс — перебор всех треугольников

Кто же это сказал?

http://en.wikipedia.org/wiki/Brute-force_search

Чего? Что ты несёшь.

я несу свет просвещения в твою пустую голову. в данном случае это заключается в том, что я показываю тебе правильное решение задачи.

Жду решения не брутфорсом.

ты тему созданного тобой же треда читал? задачу здесь решаешь ты. я её решил ещё в школе.

А ещё раз, зачем же нужен код?

потому что когда тебе показали fftw ты закукарекал что это слишком много?

Т.е. куракерай ты, а ищи я?

ещё раз. в этом треде ты просишь у меня помощи в нахождении задачи, которую ты будешь решать. я помогаю понемногу, но делать всё за тебя не буду.

обосрался в своём утверждении о том что любой треугольник из синих точек будет содержать все красные — ты.

Рили? И где же я такое сказал? Он всегда будет содержать не все красные, кроме данных с заранее подобранным инвариантом. Не ну конечно в случайных данных это же возможно, но шанс стремиться к нулю.

это один из граничных случаев в этой задаче. если бы ты начал писать код, то наткнулся бы на ещё несколько. мне лень описывать словами каждый if в программе которую ты даже не начал писать. когда начнёшь писать — спрашивай конкретно — отвечу.

Я не прошу тебя писать код - ты мне опиши. Ты пытаешься мне кукарекать про задачу, которую мне задал какой-то вася - та задача примитивна.

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

Мне тебе 3-й раз её повторить?

http://en.wikipedia.org/wiki/Brute-force_search

Правильно, чтобы решить задачу нам надо обойти все точки - раз. Это первый брутфорс.

Далее, нам надо построить по ним треугольники и посчитать популяцию внутри них с коррекцией на площать. Оптимизировать в открытом пространстве каким-нибудь блочным отсевом мы вряд ли сможем. Это только приближенное решение. Т.е. без построения всех треугольников мы не можем определить точную в них популяцию.

я несу свет просвещения в твою пустую голову. в данном случае это заключается в том, что я показываю тебе правильное решение задачи.

Ещё раз - та задача мне интересна и пока ты не пречитаешь вторую - это не имеет смысла.

Ты бы лучше мне помог и дал правильную формулку для того алгоритма ффт, что юзается у пацанов. Я поглядел там дкт в fftw - там линейная сложность.

Гуглёж по быстрому дкт не особо что-то даёт.

ты тему созданного тобой же треда читал? задачу здесь решаешь ты. я её решил ещё в школе.

Я не решаю эту задачу. Я лишь сказал, что сопутсвующая задача не реализуема не брутфорсом, а начальная задача невозможна, т.е. не имеет ответа на реальных данных.

потому что когда тебе показали fftw ты закукарекал что это слишком много?

Естественно это много и запилено оно как говно. Там тонны кодогинераторов и говновложений - это нечитая лапша и из неё не выведешь формул решения.

Код нужен, что бы я узнал алгоритм решения. Я погуглил ещё fft - они все обёртки на ффтв.

ещё раз. в этом треде ты просишь у меня помощи в нахождении задачи, которую ты будешь решать. я помогаю понемногу, но делать всё за тебя не буду.

Тут дело не в задаче, а в твоём утверждении, которое к задачам не имеет никакого отношения.

Вот помоги мне, если ты знаешь - помоги найти алгоритм из fftw и твоих илитных решаек. Яж его буду тыщу лет искать.

O(n) это вообще-то брутфорс.

И где же я такое сказал?

у тебя ещё и дислексия... здесь: Накидайте задачек. (комментарий)

опять врёшь:

Он всегда будет содержать не все красные

и употребляешь слова смысл которых не понимаешь:

данных с заранее подобранным инвариантом

Мне тебе 3-й раз её повторить?

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

Правильно, чтобы решить задачу нам надо обойти все точки

не надо.

Оптимизировать в открытом пространстве

открытое пространство — это содержимое твоей черепной коробки.

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

зачем это тебе надо? тебя кто-то просил вычислить количество красных точек в каждом возможном треугольнике?

Ты бы лучше мне помог и дал правильную формулку для того алгоритма ффт, что юзается у пацанов.

да не вопрос: http://en.wikipedia.org/wiki/Fast_Fourier_transform

пацаны заняты другими вещами: локальностью по данным чтобы хорошо параллелилось, попаданием в кеши, удобным раскладыванием для simd и т.д.

Я поглядел там дкт в fftw - там линейная сложность.

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

тогда отсортируй массив таким брутфорсом, лалка анскильная

у тебя ещё и дислексия... здесь: Накидайте задачек. (комментарий)

Там описка - в любом треугольнике всегда будут не все красные точки - ты можешь удостовериться в этом выше - я про это уже писал.

и употребляешь слова смысл которых не понимаешь:

Конкретные примеры слов, а так же причина по которой ты сделла этот вывов.

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

Накидайте задачек. (комментарий) - вот, тут написано какую задачу тебе надо решить.

Изначально задача мой сформулирована тут : Накидайте задачек. (комментарий), только к этой задаче относится все мои заключения. Меня не интересует твой кукаретинг про то, что ты там видел, а что не видел.

зачем это тебе надо? тебя кто-то просил вычислить количество красных точек в каждом возможном треугольнике?

Да. «постараться захватить как можно больше красных точек» - в изначальном условии, которое я в связи с его примитивностью и убогостью расширил до «в минимальном треугольнике», чтобы задача имела хоть какой-то смысл, кроме поиска самого большого треугольника.

да не вопрос: http://en.wikipedia.org/wiki/Fast_Fourier_transform

Я просил для школьников, ты понимаешь, что у меня образование 3класса начальной школы. Яж нихрена там не пойму, мне надо объяснить - помоги мне.

пацаны заняты другими вещами: локальностью по данным чтобы хорошо параллелилось, попаданием в кеши, удобным раскладыванием для simd и т.д.

Этим же самым занят и я, поэтому мне надо правильно агоритмическое решение я уже буду заниматься этим.

Именно для этого я ищу задачи.

посмотрел и ничего не понял — так и скажи.

Естественно она там с каким-то множителем зависящим от n, но оно ближе к линейному, чем к квадратичному.

ты не сказал о каком из восьми типов dct

Сказал и показал формулу в мануале.

во-вторых, к линейной асимптоте можно свести только

Я этого не знаю и тобою не спорю.

так что ты не осилишь.

А ты мне помоги накатать примитивно реализованный алгоритм пацанов. Я тебя похвалю и поблагодарю. Пазязя.

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

У меня перевес развития, если у обычного не прикладного технаря/математика перевес не в сторону запила, то у меня 99% перевес в сторону запила. Т.е. пилить решать задачки я могу на уровне написания кода намного сложнее рядовой матанилиты, а вот знания даже математики у меня на уровне школьника.

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

Я конечно пытаюсь осилить все ваши матаны и прочее, но какбэ я не осилю это за 2дня, а пилить-то что-то сопутствующие надо.

Тут задача многовложенная и на каждом уровне есть своя подзадача, у которой есть свой брутфорс.

Та же быстрая сортировка - разбиение списка - брутфорс, но разбиений надо не брутфорс раз.

Брутфорс - это перебор(применение) всех возможных применений операции к набору данных.

Язабан.

Изначально задача мой сформулирована тут

это не задача, а параша какая-то. задача здесь: Накидайте задачек. (комментарий)

да не вопрос: http://en.wikipedia.org/wiki/Fast_Fourier_transform

Я просил для школьников

я тебе дал пример кода: http://web.mit.edu/~emin/www.old/source_code/fft/fft.c , но ты облил его говном. значит, понять не смог, то есть безнадёжен.

А ты мне помоги накатать примитивно реализованный алгоритм пацанов.

повторно дал ссылку выше. пацаны запилили то же самое, а потом начали прикручивать свои скильные оптимизации. 20 лет прикручивали и получили fftw. ты не можешь разобраться в паре сотен тысяч строк кода из-за своей анскильности. в свою очередь, я считаю тех, кто пилит такие проекты на си без крестов наркоманами, но это вопрос второй.

Пойми простую вещь - я обычный школьник

Я джва года шдал этого признания!!!!1

Пойми простую вещь - я обычный школьник
я через пару дней сваливаю в жопу

Наконец-то царя в армию забирают.

Тут задача многовложенная и на каждом уровне есть своя подзадача, у которой есть свой брутфорс.

Та же быстрая сортировка - разбиение списка - брутфорс, но разбиений надо не брутфорс раз.

Боже мой, что ты несешь //_-

Не у него просто перекос в подготовке. Талант есть, а знаний нету.

Вот и несет иногда )))

Таки матрица расстояний?!

А как задача вне темы может быть?

http://en.wikipedia.org/wiki/Path_tracing

http://en.wikipedia.org/wiki/Monte_Carlo_integration#Example

Это типо реверсированный расчёт физического распространения лучей от камеры и далее по отражениям.

Вот ещё — http://madebyevan.com/webgl-path-tracing/ (и даже «рилтайм» со сбрасыванием SPP) и портянка http://github.com/evanw/webgl-path-tracing.

Вообще CG это сразу тригонометрия и лин. ал. (например http://en.wikipedia.org/wiki/Transformation_matrix, http://en.wikipedia.org/wiki/3D_projection, http://en.wikipedia.org/wiki/Camera_matrix), потом оптика материалов.

Царю надо код из быстрых функций писать, так что - перебор.

А как задача вне темы может быть?

Легко. Тема нужна для решения задачи, т.е. для реализации. Для альтернативной реализации решать задачу не нужно.

Это всё хорошо, но зачем мне это? В ней 1% вычислений и 99% лишнего мусора, зачем мне ради одного процента нужно мне тратить время и разбираться в этих 99%? Мне это не особо интересно.

Что конкретно не так? Пришел с пары и решил покупакерать?

Конкретно объясняешь что не так я несу, а так попутно несёшь так.

Не у него просто перекос в подготовке. Талант есть, а знаний нету.

Мне вот просто интересно, что можешь сделать ты, чего не могу не сделать я? Разве сваять лабу, либо покусать меня гуйнёй.

это не задача, а параша какая-то. задача здесь: Накидайте задачек. (комментарий)

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

Давай я тебе объясню в чем штука, все мои заявления относятся только к моей формулировки задачи, ибо это было описано. Ты либо это признаёшь и благополучно обсираешься, либо ты это не признаешь и твой кукаретинг не имеет смысла, ибо про «задача сдесь» я ничего не говорил. Это тоже равносильно обсёру.

я тебе дал пример кода: http://web.mit.edu/~emin/www.old/source_code/fft/fft.c , но ты облил его говном. значит, понять не смог, то есть безнадёжен.

Насколько я прочитал в википедии - там есть 2 основные операции - разбиение датасета на бревно и сборка его обратно. Где мне на это посмотреть?

А что мне там понимать? Зачем мне этот мусор с какими-то псевдооптимизациями от деревенского Васи для частного случая. Я хочу просто код из которого бы я увидил суть проиходящего, но как всегда в мире бывает - код либо лаба, либо fftw. Лаба бесполезна, а fftw не читаем в принципе, т.е. без понимания темы не поймёшь эти тонны говнокода.

В этом и суть, что код-то и нужен, что не погружаясь в теорию понять суть проиходящего хотябы на уровне вычислений. Т.е. мне абсалютно насрать что такое дпф и нахрен оно нужно, какой матаппарат за ним стоит и прочее.

Для меня это набор инструкций.

Пацаны считают кол-во умножений, в каком веке они живут, 19? Я конечно понимаю, что некомпетентность она такая, но всё же.

повторно дал ссылку выше. пацаны запилили то же самое, а потом начали прикручивать свои скильные оптимизации.

Ещё раз - это частный случай из которого не вывести даже наивный частный не говоря уже об общем без понимания темы, ты это понимаешь?

Там тонна способов всякого разного:

https://en.wikipedia.org/wiki/Chirp_Z-transform#Bluestein.27s_algorithm https://en.wikipedia.org/wiki/Bruun's_FFT_algorithm https://en.wikipedia.org/wiki/Prime-factor_FFT_algorithm https://en.wikipedia.org/wiki/Cooley–Tukey_FFT_algorithm - что из этого. Ладно я уже не прошу реализацию - я прошу хотябы конечный алгоритм.

ты не можешь разобраться в паре сотен тысяч строк кода из-за своей анскильности.

Это не пара сотен тысяч строк, а пара сотен тысяч строк врайтонли говна, которое написано хрен знает когда.

В это можно разобраться а) зная теорию на которой всё это основано и живя в этом говне пару лет. Тогда да.

в свою очередь, я считаю тех, кто пилит такие проекты на си без крестов наркоманами, но это вопрос второй.

И какие же плюсы привнесут кресты? И да, это не си - это говно.

Давай нормально, без питухов. Не обижайся на меня - я шутя.

Но вот смотри - есть типа бфп - это какая-то не понятная штука. Из которой уже выводят алгоритма решения. Ну и вот, я тебя прошу как человека шарящего - расскажи что это такое, чем они отличаются и что юзать. Даже кода не надо - я попытаюсь разобраться.

Но тут тоже проблема - а вдруг я пойму что-то неправильно и выведу реальзацию криво - я же это не проверю. Как быть?

Я там поглядел - дискретные формулки я более-менее понимаю и там даже мне 3класснику разобраться можно, но какие юзать, что они значат и т.п.

Введи пожалуйста в курс дела, так сказать экскурс в историю запила. Там в стародавние времена пацаны юзали то-то, а потом нашли другие и стали юзать сё-то, потомучто она тем-то лучше, а щас перешли на третье, либо там есть основные направления и они отличаются тем-то.

Т.е. чтоб я хоть что-то понимал - я не могу пилить - я нихрена не понимаю.

но зачем мне это?

Просил рисовалку же. Если без освещения, просто каркасами — сделай простейший 3D вид с камеры на разные объекты своими средствами (т.е. использовать стороннего только вывод готовой картинки) с анимацией и контролем движений, вращений и т.п. всего и вся, через матрицы, тригонометрию, кватернионы. Но так тогда без перформанса, чисто для демонстрации всех этих вещей, чтобы упереться в рисовалке это нужно что-то особого делать, для чего нужно разбираться.

Я про DFT не говорил... но задача по набору семплов время-сигнал посчитать корреляции с косинусами и синусами разной периодичности, то есть в итоге график гармоника-вклад, если исходный сигнал представляет из себя суперпозицию гармоник, то мы сразу это увидим и их получим, то есть спектральное представление сигнала. То что там комплексные числа и экспонента это оно объединяет по формуле Муавра, то есть можно считать отдельно DCT и DST. Криво посчитать тут сложно, можно посчитать медленно, но в итоге нужны просто значения корреляций, то есть суммы конечных рядов.

Пример: http://en.wikipedia.org/wiki/JPEG#Discrete_cosine_transform.

Divide and conquer: http://en.wikipedia.org/wiki/Cooley–Tukey_FFT_algorithm.