Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
_Ivana
3227 / 1855 / 156
Регистрация: 01.03.2013
Сообщений: 5,080
Записей в блоге: 5
#1

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

01.11.2014, 00:43. Просмотров 1172. Ответов 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
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Победить модификацию Фарроу для оптимизации расчета коэффициентов полинома (C++):

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

Составить программу расчета значений полинома - C++
Составить программу расчета значений полинома P(x)=a0+a1x+a2x^2+...+anx^n где n – порядок полинома,...

Победить Фарроу - Haskell
Небольшая предыстория. Есть один популярный вид локальной интерполяции, когда по 4 точкам строится полином Лагранжа 3 степени, проходящий...

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

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

Определение коэффициентов полинома - Prolog
Задача. Написать определение коэффициентов полинома, заданного списком действительных корней. Помогите пожалуйста.

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
Эксперт С++
4924 / 3032 / 372
Регистрация: 10.11.2010
Сообщений: 11,085
Записей в блоге: 10
Завершенные тесты: 1
02.11.2014, 08:38 #4
_Ivana, ты бы дал не оптимизированный исходник расчета коэффициентов локального сплайна, составленного именно из полиномов Лагранжа, проходящих через 4 точки (для среднего интервала на равномерной сетке) на С++, а мы бы попробовали его оптимизировать. По-моему так было бы интереснее, по крайней мере для меня.
0
_Ivana
3227 / 1855 / 156
Регистрация: 01.03.2013
Сообщений: 5,080
Записей в блоге: 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
Эксперт С++
4924 / 3032 / 372
Регистрация: 10.11.2010
Сообщений: 11,085
Записей в блоге: 10
Завершенные тесты: 1
02.11.2014, 16:45 #6
Методы оптимизации любые приветствуются?
Буду дома - посмотрю.
0
_Ivana
3227 / 1855 / 156
Регистрация: 01.03.2013
Сообщений: 5,080
Записей в блоге: 5
02.11.2014, 16:54  [ТС] #7
Цитата Сообщение от castaway Посмотреть сообщение
Методы оптимизации любые приветствуются?
Даже стесняюсь спросить какие вы имеете в виду Думаю, любые. Только не полифазник Должен получиться честный полином с честными же коэффициентами, все в даблах. Вопросы типа "современные математические сопроцессоры умножают/складывают даблы за 1 такт, так что не стоит уменьшать количество операций" давайте оставим за кадром - пусть мы пишем для простейшего контроллера без математического сопроцессора, который даблы будет складывать/умножать за много тактов.
1
castaway
Эксперт С++
4924 / 3032 / 372
Регистрация: 10.11.2010
Сообщений: 11,085
Записей в блоге: 10
Завершенные тесты: 1
02.11.2014, 18:22 #8
_Ivana, я просто спрошу. Именно этот пример можно оптимизировать, не вникая в сам алгоритм?
0
_Ivana
3227 / 1855 / 156
Регистрация: 01.03.2013
Сообщений: 5,080
Записей в блоге: 5
02.11.2014, 18:33  [ТС] #9
Если я правильно понимаю суть вашего вопроса - то нет Но это уже будет подсказка. Именно этот пример оптимизировать врядли получится, если не вникать в алгоритм. Надо придумать другой алгоритм, который будет давать тот же результат - полином 3 степени с коэффициентами, по которому можно рассчитать любое значение в интервале, работающий с потоковым входом значений.

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

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

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

В остальном я вас понял. Решение не обещаю, но голову ломать буду в любом случае несколько дней..
0
_Ivana
3227 / 1855 / 156
Регистрация: 01.03.2013
Сообщений: 5,080
Записей в блоге: 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
Эксперт С++
4924 / 3032 / 372
Регистрация: 10.11.2010
Сообщений: 11,085
Записей в блоге: 10
Завершенные тесты: 1
02.11.2014, 20:29 #14
Всё вышеописанное понимаю кроме того, как строится этот полином Лагранжа 3-й степени.. Придётся подумать. Пытливый ум не даст мне покоя...

Не по теме:

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

0
_Ivana
3227 / 1855 / 156
Регистрация: 01.03.2013
Сообщений: 5,080
Записей в блоге: 5
02.11.2014, 20:34  [ТС] #15
Цитата Сообщение от castaway Посмотреть сообщение
Придётся подумать. Пытливый ум не даст мне покоя...
Ради этого и запостил задачку на форум
Цитата Сообщение от castaway Посмотреть сообщение
вы с вашим товарищем опубликовали свои методы? Общество о них знает?
Знает. Но выражает совершенное по безразличие Хуже того - я по мотивам моего метода сформулировал и доказал одну теорему, ранее нигде мною не виденную. Отношение общества такое же
0
02.11.2014, 20:34
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.11.2014, 20:34
Привет! Вот еще темы с ответами:

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

Нахождение коэффициентов полинома - C#
//Вычисляем коэффициенты полинома первой степени a= 1; a = -x; //цикл по числу полиномов for(int k=2;k&lt;=n; k++) { //Вычисляем...

Определение коэффициентов полинома - Matlab
Здравствуйте, подскажите пожалуйста с помощью какой функции можно определить коэффицикнты полинома в матлаб?:(

Задача на определение коэффициентов полинома - Matlab
Здравствуйте, помогите с задачкой, не знаю как по таким данным определить коэффициенты полинома...Текст задачи прилагаю, задача номер 2


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

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

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