Не работает обратное преобразование Фурье над конечным полем

[Without Name]

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

Формулы. Прямое преобразование

$D_k = \sum\limits_{i=0}^{n-1}{\omega}^{ik}{d}_{i}$

Обратное преобразование:

$S_k = \frac{1}{n}\sum\limits_{i=0}^{n-1}{\omega}^{-ik}{D}_{i}$

Я взял многочлен $1+2x+3x^2+4x^3+5x^4$ со списком коэффициентов $(1, 2, 3, 4, 5)$ над полем ${Z}_{13}$ и нахожу от него преобразование Фурье:



Здесь двойка - корень из единицы степени 12 в поле ${Z}_{13}$, от 0 до 4 идет проход по коэффициентам многочлена. Преобразование Фурье равно $(2, 12,7,0,1)$

Теперь от этого полученного вектора я хочу найти обратное преобразование Фурье. Должен получиться исходный вектор коэффициентов:



Здесь число 7 - обратный элемент поля для элемента 2, нужен, чтобы избавиться от минуса в показателе степени. Число ${5}^{-1}$ - обратный для $n=5$. Видим, что получился совсем не исходный вектор. Почему так? Почему не сработало обратное преобразование Фурье?

[svv]

Давайте сначала исправим программу, а потом будем её оптимизировать.
На данном этапе любой многочлен должен задаваться вектором из 12 коэффициентов:
$[a_0,a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9,a_{10},a_{11}]$
Работаем только с такими векторами. Поэтому замените вектор $[1,2,3,4,5]$ на $[1,2,3,4,5,0,0,0,0,0,0,0]$.

Теперь в формулах везде возьмите $n=12$. Во всех циклах (как for, так и $\Sigma$) переменная цикла должна пробегать значения от $0$ до $n-1=11$ включительно.

Найдите теперь $D_k$, а потом $S_k$. Что получилось?

[Without Name]

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

${D}_{k} = [2, 12, 7, 0, 1, 3, 3, 5, 12, 6, 7, 6]$

$S_k = [5, 10, 2, 7, 12, 0, 0, 0, 0, 0, 0, 0]$

[svv]

Without Name
$D_k$ — совершенно правильно.
$S_k$ — получились такие потому, что Вам надо поставить $n=12$ везде, в том числе здесь:
$S_k = \dfrac{1}{\color{magenta}n}\sum\limits_{i=0}^{n-1}{\omega}^{-ik}{D}_{i}$
А Вы делили по-прежнему на $5$.

[Without Name]

Ого! Спасибо, все получилось! Пойду реализовывать этот алгоритм на C++

[svv]

Without Name
Это здорово! Позвольте ещё несколько замечаний.

0) Обратите внимание, что если в векторе $D_k$ после вычисления обнулить (или как-то ещё испортить) даже только $D_{11}$, уже ничего не получится. В этом, собственно, и была ошибка: исходный многочлен четвёртой степени, а его преобразование Фурье — максимальной.

1) У исходного многочлена только пять первых коэффициентов отличны от нуля. Поэтому, в принципе, первый цикл for первое суммирование можно сделать от 0 до 4. Но поскольку в будущем это, вероятно, будет библиотечная функция, я бы не советовал этого делать.

2) Всё это желательно проверить на нескольких многочленах случайной ($0...11$) степени и со случайными ($0...12$) коэффициентами.

3) Деление на $12$ есть умножение на $-1$, поскольку $12x+x=13x=0$.

4) В реализации на C++ я бы все операции реализовал в виде таблиц (lookup tables). Особенно напрашивается заранее вычислить массив $2^n$.

[Without Name]

Спасибо! Отличные замечания

[Without Name]

Что у меня не так в реализации? Почему-то вектор после преобразования получается не такой, какой получился в Maple

inline constexpr int FT_LENGTH = 12;

// Таблица для 2^n mod 13
int exp_table[13] = {
   1, 
   2, 
   4, 
   8, 
   3, 
   6, 
   12, 
   11, 
   9, 
   5, 
   10, 
   7,
   1
};

int mul_table[13][13] = {
   { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
   { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 },
   { 0, 2, 4, 6, 8, 10, 12, 1, 3, 5, 7, 9, 11 },
   { 0, 3, 6, 9, 12, 2, 5, 8, 11, 1, 4, 7, 10 },
   { 0, 4, 8, 12, 3, 7, 11, 2, 6, 10, 1, 5, 9 },
   { 0, 5, 10, 2, 7, 12, 4, 9, 1, 6, 11, 3, 8 },
   { 0, 6, 12, 5, 11, 4, 10, 3, 9, 2, 8, 1, 7 },
   { 0, 7, 1, 8, 2, 9, 3, 10, 4, 11, 5, 12, 6 },
   { 0, 8, 3, 11, 6, 1, 9, 4, 12, 7, 2, 10, 5 },
   { 0, 9, 5, 1, 10, 6, 2, 11, 7, 3, 12, 8, 4 },
   { 0, 10, 7, 4, 1, 11, 8, 5, 2, 12, 9, 6, 3 },
   { 0, 11, 9, 7, 5, 3, 1, 12, 10, 8, 6, 4, 2 },
   { 0, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }
};

void forward_transform(const int(&source)[FT_LENGTH], int(&target)[FT_LENGTH])
{
   for (int k = 0; k < FT_LENGTH; ++k)
   {
      int sum = 0;
      for (int i = 0; i < FT_LENGTH; ++i)
      {
         sum += exp_table[(i * k) % 13] * source[i];
      }
      target[k] = sum % 13;
   }
}

int main()
{
    int a[12] = {1, 2, 3, 4, 5, 0, 0, 0, 0, 0, 0, 0};
    int b[12] = { 0 };
    int c[12] = { 0 };

    forward_transform(a, b);
    inverse_transform(b, c);

    return 0;
}

[svv]

Начнём с какого-то элемента $a$ и будем прибавлять единицу. Чтобы вернуться к $a$, нам надо $13$ раз прибавить единицу.
Начнём с какого-то элемента $a\neq 0$ и будем умножать на $2$. Чтобы вернуться к $a$, нам надо $12$ раз умножить на $2$.
Почему такая разница? В процессе прибавления единицы мы переберём все 13 элементов поля. А в процессе умножения на $2$ мы не можем получить нуль (если только не начали с нуля). А если бы мы чудом нуль получили, все дальнейшие результаты умножения тоже были бы нулями.

Поэтому
sum += exp_table[(i * k) % 13] * source[i]; // ошибка! заменить 13 на 12
но
target[k] = sum % 13; // правильно

Поэтому последнее значение в exp_table является излишним (да Вы и сами видите, что это уже повтор), этот массив должен содержать лишь 12 элементов.

[Without Name]

Ааа, понятно, спасибо

[svv]

Without Name
Вам респект за то, что не ставите открывающие скобки так:

Используется синтаксис C++

   for (int k = 0; k < FT_LENGTH; ++k) {
      int sum = 0;
      for (int i = 0; i < FT_LENGTH; ++i) {
         sum += exp_table[(i * k) % 13] * source[i];
      }
      target[k] = sum % 13;
   }

А следуете моему любимому стилю Оллмана (который у меня установился как-то сам собой).