Проверка функции на линейность, реализация в си

[inky]

Здравствуйте! Пишу программу на си которая проверяет булевую функцию на линейность. Я знаю как это сделать, но не знаю как обосновать мой метод.
Входные параметры это количество переменных и таблица значений. Я нахожу коэффициенты полинома Жегалкина и по ним определяю линейность функции. Для этого я использую алгоритм сортировки слиянием, только функция которая занимается "слиянием" работает следующим образом: первую часть записывает без изменений, а вторую часть записывает как сумма (по модулю два естественно) первой и второй частей (поэлементно). В результате, мы получаем коэффициенты полинома Жегалкина.
Этот алгоритм я узнал через друга, который в свою очередь узнал его у кого-то еще и не смог объяснить мне на чем это основывается. Начал копаться в гугле и нашел похожий способ, в википедии он назывется "методом треугольника". Я подозреваю что именно он лежит в основе моего алгоритма, только как это понять?

[arseniiv]

(Моё нескромное мнение.)

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

[inky]

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

[inky]

Возникла другая проблема...код который я использую выдает не тот результат. Вот сам код:

int Merge(int *a, int start, int end)
{
 int half=(start+end)/2, i;
 for(i=0;i<=half;i++)
 {
  a[half+1+i]+=a[i];
  a[half+1+i]=a[half+1+i] % 2; 
 }
 return 0;
}

int Coefficients(int *a, int mStart, int mEnd)
{
 if(mStart<mEnd)
 {
  Coefficients(a, mStart, (mStart+mEnd)/2); 
  Coefficients(a, (mStart+mEnd)/2+1, mEnd);
  Merge(a, mStart, mEnd);
 }
 return 0;
}

Главная функция вызывает функцию Coefficients, задавая массив значений, начало и конец массива.
Я тестировал код на наборе "0110"=>получалось "0111" (должно было получится "0110")
на "0111"=>"0110" (должно было получится "0111")
на "11111111"=>"10000100" (должно было получится "10000000")

Можете подсказать где я ошибся?
Ps Алгоритм работает по принципу описанному в первом сообщении

-- 23.04.2014, 10:26 --

Уже нашел ответ почему: цикл не с того элемента начинается