Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
_Ivana
3233 / 1861 / 234
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
1

Победить модификацию Фарроу для оптимизации расчета коэффициентов полинома

01.11.2014, 00:43. Просмотров 1228. Ответов 21
Метки нет (Все метки)

Рискну в очередной раз предложить интересующимся участникам форума задачку для подумать/решить.

Небольшая предыстория. Есть один популярный вид локальной интерполяции, когда по 4 точкам строится полином Лагранжа 3 степени, проходящий через эти 4 точки, и значения этого полинома берутся в качестве интерполирующей функции на среднем интервале, задаваемом второй и третьей точкой. Для соседнего интервала строится свой такой же полином по 4 точкам, и т.д. Этот вид интерполяции широко применяется во многих практических приложениях, особенно в ЦОС (сразу оговоримся, что далее везде подразумевается равномерная сетка), он настолько популярен, что ему посвящается много статей, например вот, где приведена даже модификация Фарроу для оптимизации расчета коэффициентов полинома: требуется 1 деление на 6, 2 умножения/деления на 2 (сдвига при реализации алгоритма в машинном коде) и 8 сложений/вычитаний.
А теперь, собственно, задача: реализовать алгоритм расчета коэффициентов локального сплайна, составленного именно из полиномов Лагранжа, проходящих через 4 точки (для среднего интервала на равномерной сетке), содержащий меньшее количество операций, чем выше представленная модификация Фарроу.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.11.2014, 00:43
Ответы с готовыми решениями:

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

Составить программу расчета значений полинома
Составить программу расчета значений полинома ...

Победить Фарроу
Небольшая предыстория. Есть один популярный вид локальной интерполяции, когда...

.m сценарий для расчета коэффициентов регрессии
Всем привет, давненько не заглядывал на форум, а тут вот "сел в лужу". Никак не...

Расчет коэффициентов полинома
Добрый вечер. Буду благодарен если мне кто-то поможет. Подскажите пожалуйста...

21
Tulosba
01.11.2014, 10:52
  #2

Не по теме:

_Ivana, задача может быть и интересная, но она совершенно не уместна в данной ветке форума. Логичнее было бы ее видеть где-то здесь: http://www.cyberforum.ru/programming-theory/

0
_Ivana
01.11.2014, 22:37  [ТС]
  #3

Не по теме:

Tulosba, вы конечно правы, но позволю себе оправдаться. Я хоть и не знаю С++, но активно общаюсь в этом разделе, появились многие знакомые, которые любят решать интересные задачки, хочется им подкинуть интересное. А заходят ли они в раздел теории - не факт, к тому же тут жизнь кипит. А еще когда я спросил где создать тему - мне посоветовали раздел Лиспа, но в С/С++ мы хоть как-то можем предугадать затратность каждой операции, поэтому в этом разделе ловля блох и оптимизация тактов имхо более уместна. Хотя скорее всего тема утонет без ответов, и мне не придется выкладывать свой вариант и читать именно от вас же возражения типа "современные процессоры умножают за один такт и нет смысла минимизировать операции за счет сохранения/чтения памяти" :)

0
castaway
Эксперт С++
4930 / 3037 / 453
Регистрация: 10.11.2010
Сообщений: 11,116
Записей в блоге: 10
Завершенные тесты: 1
02.11.2014, 08:38 4
_Ivana, ты бы дал не оптимизированный исходник расчета коэффициентов локального сплайна, составленного именно из полиномов Лагранжа, проходящих через 4 точки (для среднего интервала на равномерной сетке) на С++, а мы бы попробовали его оптимизировать. По-моему так было бы интереснее, по крайней мере для меня.
0
_Ivana
3233 / 1861 / 234
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
02.11.2014, 16:18  [ТС] 5
castaway, будете смеяться, но буквально сегодня ночью об этом подумал - что надо написать шаблонный код на основе алгоритма по ссылке, чтобы было примерно понятно с кем сражаться и кого побеждать. Правда, эта мысль сначала пришла ко мне в образе Haskell, но вскоре и в С++ трансформировалась, почему нет. Если в ближайшее время домашние дела не отвлекут - вскоре выложу код, если таки отвлекут - попозже сегодня вечером.

Добавлено через 1 час 5 минут
Выкладываю код. Что он делает - читает из входного файла последовательно отсчеты входящих значений (вполне жизненная ситуация, часто входные данные поступают именно в виде потока по какому-нибудь каналу), и для каждого интервала рассчитывает n промежуточных значений интерполяции (Лагранж по центральному интервалу 4-х точек), и выводит эти рассчитанные значения в выходной файл - можно потом посмотреть график его значений в Матлабе/GNUplot-е или хоть в Экселе.
Повторю задачу - придумать и реализовать алгоритм, который выдает точно такой же финальный результат (массив n значений для каждого интервала), но требует меньше операций для расчета коэффициентов полинома. То есть, победить алгоритм Фарроу, который считается оптимальным.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int _tmain(int argc, _TCHAR* argv[]) 
{
    freopen("points.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    double y[4]; cin >> y[0] >> y[1] >> y[2];
    int n = 20; // количество точек для расчета значений внутри каждого интервала
    while (cin >> y[3]) {
        // Расчет коэффициентов полинома по Фарроу: 1 умножение (на 1/6), 2 сдвига, 8 сложений
        double a[4];
        a[3] = (y[3] - y[0])/6 + (y[1] - y[2])/2;
        a[1] = (y[3] - y[1])/2 - a[3];
        a[2] =  y[3] - y[2] - a[1] - a[3];
        a[0] =  y[2];
 
        // коэффициенты рассчитаны - рассчитаем n значений полинома на среднем интервале
        // полином рассчитываем по схеме Горнера, но это не принципиально
        for (int i=0; i<n; i++) {
            double x = -1.0 + (double) i/n, y=0;
            for (int j=3; j>=0; j--) y=y*x + a[j];
            cout << y << '\n';
        }
        // кривой сдвиг массива 4-х входящих значений, надо по-хорошему кольцевой буфер
        // но для целей демонстрации и так сойдет, это не принципиальный момент
        for (int i=0; i<3; i++) y[i]=y[i+1];
    }
    return 0;
}
Если есть вопросы и уточнения, готов разъяснить

ЗЫ да, кстати, если кто предложит сразу рассчитать коэффициенты полифазного фильтра для каждой заранее известной точки интервала - это НЕ ответ Считайте, что я могу запросить значение полинома в любой внутренней точке интервала.
0
castaway
Эксперт С++
4930 / 3037 / 453
Регистрация: 10.11.2010
Сообщений: 11,116
Записей в блоге: 10
Завершенные тесты: 1
02.11.2014, 16:45 6
Методы оптимизации любые приветствуются?
Буду дома - посмотрю.
0
_Ivana
3233 / 1861 / 234
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
02.11.2014, 16:54  [ТС] 7
Цитата Сообщение от castaway Посмотреть сообщение
Методы оптимизации любые приветствуются?
Даже стесняюсь спросить какие вы имеете в виду Думаю, любые. Только не полифазник Должен получиться честный полином с честными же коэффициентами, все в даблах. Вопросы типа "современные математические сопроцессоры умножают/складывают даблы за 1 такт, так что не стоит уменьшать количество операций" давайте оставим за кадром - пусть мы пишем для простейшего контроллера без математического сопроцессора, который даблы будет складывать/умножать за много тактов.
1
castaway
Эксперт С++
4930 / 3037 / 453
Регистрация: 10.11.2010
Сообщений: 11,116
Записей в блоге: 10
Завершенные тесты: 1
02.11.2014, 18:22 8
_Ivana, я просто спрошу. Именно этот пример можно оптимизировать, не вникая в сам алгоритм?
0
_Ivana
3233 / 1861 / 234
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
02.11.2014, 18:33  [ТС] 9
Если я правильно понимаю суть вашего вопроса - то нет Но это уже будет подсказка. Именно этот пример оптимизировать врядли получится, если не вникать в алгоритм. Надо придумать другой алгоритм, который будет давать тот же результат - полином 3 степени с коэффициентами, по которому можно рассчитать любое значение в интервале, работающий с потоковым входом значений.

Добавлено через 2 минуты
ЗЫ у меня есть пример решения этой задачи моим знакомым (когда я ему задал ее), у него меньше операций на расчет коэффициентов, чем у Фарроу, и при этом имхо несложное теоретическое обоснование. У моего же алгоритма количество операций еще меньше, и имхо интересное математическое обоснование

Добавлено через 4 минуты
ЗЗЫ просто сам алгоритм - решение системы линейных уравнений 4*4 на равномерной сетке - и Фарроу просто предложил одну из оптимальных реализаций, которая стала популярной - по ссылке в первом посте все написано, какая исходная задача, каково ее решение "в лоб", и что предложил Фарроу. Мы же с моим знакомым придумали 2 другие реализации, которые оптимальнее.
1
castaway
Эксперт С++
4930 / 3037 / 453
Регистрация: 10.11.2010
Сообщений: 11,116
Записей в блоге: 10
Завершенные тесты: 1
02.11.2014, 18:58 10
Вы правильно меня поняли. Но дело в том, что я плохой математик У меня больше развито логическое мышление)
Я рассчитывал увидеть алгоритм, который обычный программист может оптимизировать. Но немного подумав над вашим примером я понял,
что там оптимизировать по большому счёту нечего Ссылка из первого поста для меня - тёмный лес.
Есть возможность предоставить этот алгоритм в самом простом виде (не Фарроу) на языке C++?
0
_Ivana
3233 / 1861 / 234
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
02.11.2014, 19:13  [ТС] 11
Попробую объяснить суть задачи на пальцах у нас есть массив исходных точек, соответствующих значениям некоей функции на равномерной (!) сетке аргумента - если вам будет понятнее, считайте его wav-файлом Задача - внутри каждого интервала сетки рассчитать любое количество значений функции, которая интерполирует данный массив каким-либо образом. Например, для простейшего случая линейной интерполяции мы соединяем линиями 2 точки и промежуточные значения берем лежащие на этой линии. Но чтобы повысить точность, мы применяем интерполяцию полиномом 3 степени - для каждых 4 точек мы строим полином 3 степени, проходящий через них (этот полином единственный по известной теореме, так что как его строить - все равно!), и рассчитываем промежуточные значения по этому полиному. Остается только вопрос оптимального построения полинома, проходящего через 4 точки равномерной сетки - если решать ее в лоб, то надо решать систему линейных уравнений 4*4 для вычисления коэффициентов полинома - решать или Гауссом, или чем еще - неважно (это то, что вы просили
Цитата Сообщение от castaway Посмотреть сообщение
Есть возможность предоставить этот алгоритм в самом простом виде (не Фарроу) на языке C++?
- нет, Фарроу - это один из самых простых видов
). Но решать систему Гауссом или Зейделем - это затратно по операциям. Вот люди и задумались, как максимально уменьшить количество операций для этого, придумали разные алгоритмы. Остальное вы знаете Вроде все рассказал.
0
castaway
Эксперт С++
4930 / 3037 / 453
Регистрация: 10.11.2010
Сообщений: 11,116
Записей в блоге: 10
Завершенные тесты: 1
02.11.2014, 19:53 12
Проясните мне некоторые моменты..
Под "сеткой" вы подразумеваете дискретизацию?
Под исходными точками - ключевые значения, между которыми происходит интерполяция. В данном случае их четыре. Правильно?

Цитата Сообщение от _Ivana Посмотреть сообщение
которая интерполирует данный массив каким-либо образом
Не каким-либо, а именно "когда по 4 точкам строится полином Лагранжа 3 степени"?

В остальном я вас понял. Решение не обещаю, но голову ломать буду в любом случае несколько дней..
0
_Ivana
3233 / 1861 / 234
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
02.11.2014, 20:02  [ТС] 13
Все правильно, но некоторые уточнения:
1) в n-й раз уточняю, что сетка равномерная
2) "их четыре" для каждого интервала. То есть, пусть у нас есть отсчеты диксретизации:
10, 30, 20, 50, 40, 70
Мы можем выделить только 3 внутренних интервала, где можем провести интерполяцию по 4 точкам, и проводим ее для каждой четверки точек, но значения по данному полиному считаем только на среднем интервале данных 4 точек, то есть по точкам
10, 30, 20, 50 считаем между 30 и 20
30, 20, 50, 40 - между 20 и 50
20, 50, 40, 70 - между 50 и 40
3) имейте в виду, что у нас потоковый вход, поэтому мы не знаем сразу весь массив отсчетов, но по приходу очередного значения (считыванию его из файла) должны рассчитать коэффициенты полинома для очередного интервала и нужное количество его значений - все как в моем примере кода.

ЗЫ надеюсь, вам будет интересно подумать
0
castaway
Эксперт С++
4930 / 3037 / 453
Регистрация: 10.11.2010
Сообщений: 11,116
Записей в блоге: 10
Завершенные тесты: 1
02.11.2014, 20:29 14
Всё вышеописанное понимаю кроме того, как строится этот полином Лагранжа 3-й степени.. Придётся подумать. Пытливый ум не даст мне покоя...

Не по теме:

P.S.: вы с вашим товарищем опубликовали свои методы? Общество о них знает?

0
_Ivana
3233 / 1861 / 234
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
02.11.2014, 20:34  [ТС] 15
Цитата Сообщение от castaway Посмотреть сообщение
Придётся подумать. Пытливый ум не даст мне покоя...
Ради этого и запостил задачку на форум
Цитата Сообщение от castaway Посмотреть сообщение
вы с вашим товарищем опубликовали свои методы? Общество о них знает?
Знает. Но выражает совершенное по безразличие Хуже того - я по мотивам моего метода сформулировал и доказал одну теорему, ранее нигде мною не виденную. Отношение общества такое же
0
castaway
02.11.2014, 20:55
  #16

Не по теме:

Цитата Сообщение от _Ivana Посмотреть сообщение
Знает. Но выражает совершенное безразличие
Может не там опубликовали, или предоставили "не в том виде"?

0
_Ivana
02.11.2014, 21:03  [ТС]
  #17

Не по теме:

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

Цитата Сообщение от Tulosba Посмотреть сообщение
На счет эффективности хотелось бы еще заметить, что на современных процах порой быстрее вычислить выражение по новой, чем считать его из памяти. Если не изменяет память, чуть ли не на таблице синусов такое проверялось.
- может и из-за них тоже народ так апатичен, а может и вообще как кто-то писал "на современных процах десяток-другой лишних тактов роли не играет", хотя я в корне не согласен с таким разбазариванием ресурсов :)

0
_Ivana
3233 / 1861 / 234
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
14.11.2014, 10:20  [ТС] 18
Все, завяла тема, несмотря на пытливость умов?
1
castaway
Эксперт С++
4930 / 3037 / 453
Регистрация: 10.11.2010
Сообщений: 11,116
Записей в блоге: 10
Завершенные тесты: 1
14.11.2014, 10:39 19
_Ivana, я честно сдаюсь) Увы..
0
_Ivana
3233 / 1861 / 234
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
14.11.2014, 10:46  [ТС] 20
castaway, ну если и вы сдаетесь, тогда больше воевать некому
ЗЫ если вдруг действительно интересно (а не просто из вежливости и тактичности ), могу выложить наши алгоритмы и прокомментировать.
0
14.11.2014, 10:46
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.11.2014, 10:46

Значение коэффициентов полинома
Надо найти значение коэффициентов полинома, если использовать прямое...

Определение коэффициентов полинома
Здравствуйте, подскажите пожалуйста с помощью какой функции можно определить...

Определение коэффициентов полинома
Задача. Написать определение коэффициентов полинома, заданного списком...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru