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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.94
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
#1

Многочлены над GF(2^m) - C++

06.11.2012, 02:35. Просмотров 2050. Ответов 39
Метки нет (Все метки)

Пишу кодер Рида-Соломона.
Дано следующее:
* http://www.cyberforum.ru/cgi-bin/latex.cgi?m - количество битов в одном символе (читай, элементов поля http://www.cyberforum.ru/cgi-bin/latex.cgi?GF(2^m));
* http://www.cyberforum.ru/cgi-bin/latex.cgi?n - длина кода (в символах);
* http://www.cyberforum.ru/cgi-bin/latex.cgi?k - длина сообщения (в символах);
* http://www.cyberforum.ru/cgi-bin/latex.cgi?g(x) - неприводимый многочлен степени http://www.cyberforum.ru/cgi-bin/latex.cgi?n-k над http://www.cyberforum.ru/cgi-bin/latex.cgi?GF(2^m)
* http://www.cyberforum.ru/cgi-bin/latex.cgi?\overline m - сообщение из 0 и 1 конечной длины.
* http://www.cyberforum.ru/cgi-bin/latex.cgi?u - сообщение, полученное из http://www.cyberforum.ru/cgi-bin/latex.cgi?\overline m путём выделения блоков длины http://www.cyberforum.ru/cgi-bin/latex.cgi?m;
* А также естественное отображение http://www.cyberforum.ru/cgi-bin/latex.cgi?A:GF^n(2^m)\to P_n(GF(2^m)); (\alpha _0\alpha _1...\alpha _{n-1})\mapsto \alpha _0+\alpha _1x+...+\alpha _{n-1}x^{n-1}
На выходе нужно получить РС-код:
* http://www.cyberforum.ru/cgi-bin/latex.cgi?v - код длины http://www.cyberforum.ru/cgi-bin/latex.cgi?n (в символах), по формуле: http://www.cyberforum.ru/cgi-bin/latex.cgi?v=A^{-1}(x^{n-k}(Au)(x)+(x^{n-k}(Au)(x) \mathrm{mod} g(x)))
http://www.cyberforum.ru/cgi-bin/latex.cgi?GF(2^m)=\{0,\alpha ^0, \alpha ^1,...,\alpha ^{2^m-2}\}, где http://www.cyberforum.ru/cgi-bin/latex.cgi?g(\alpha )=0.
По теории вроди бы всё, сейчас попробую описать прототип реализации.

Добавлено через 2 часа 17 минут
Посмотрите, пожалуйста!
Кликните здесь для просмотра всего текста
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
29
30
#ifndef RS_encoder.h
 
#include <vector>
 
const int GROUP_DEGREE = 0; // = m -- порядок группы GF(2^m)
const std::vector<int> PRIMITIVE_POLYNOMIAL (0); // примитивный полином в GF(2^m)
 
class GF 
{
private:
    int alpha_power; // представление в виде степени альфа
    std::vector<int> alpha_vector; // представление в виде вектора
    bool null; // индикатор того, что вектор нулевой
 
    void power_to_vector ();
    void vector_to_power ();
 
public:
    GF ();
    GF (int power); // используем power_to_vector
    GF (std::vector<int> vector); // используем vector_to_power
    ~GF ();
 
    GF operator+ (GF right_hand_side); // сложение
    GF operator* (GF right_hand_side); // умножение
 
    void show_alpha_vector (); //вывод на экран вектора
};
 
#endif

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#ifndef GF_polynom.h
 
#include "GF.h"
 
class GF_polynom
{
private:
    std::vector<GF> polynom; // вектор из коэфициентов полинома,
                             // которые принадлежат GF(2^m)
public:
    GF_polynom ();
    GF_polynom (std::vector<GF> coefficients);
    ~GF_polynom ();
 
    GF_polynom operator+ (GF_polynom right_hand_side); // сложение 
    GF_polynom operator* (GF_polynom right_hand_side); // умножение
    GF_polynom operator% (GF_polynom right_hand_side); // остаток от деления
};
 
#endif

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#ifndef RS_encoder.h
 
#include "GF_polynom.h"
#include <string>
 
const int CODE_LENGTH = 0; // длина кода
const int MESSAGE_LENGTH = 0; // длина сообщения
 
std::vector<int> str_to_int (std::string str_message); // строку в вектор
std::vector<GF> message_to_GF_message (std::vector<int> message); // вектор из 0 и 1 в 
                                                                  // вектор из элементов GF(2^m)
std::vector<GF> encode (std::vector<GF> GF_message, int n = CODE_LENGTH, int k = MESSAGE_LENGTH); // кодирование сообщения
 
#endif

Я пока не использовал ссылки и модификатор const. Завтра всё доделаю и буду приступать к написанию самих функций. Прокомментируйте, пожалуйста. Спасибо!!!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.11.2012, 02:35
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Многочлены над GF(2^m) (C++):

Многочлены - C++
http://s44.***********/i106/1001/93/421c17bb2f28.png Прошу помочь решить\ или хоть популярно объяснить.

Многочлены - C++
http://s003.***********/i202/1001/dc/6e8447711438.png

списки-многочлены. сложение - C++
Здравствуйте, задали сделать прогу, но я не понимаю каким образом это надо осуществить. Задача: Многочлен с целыми коэффициентами можно...

класс, моделирующий многочлены n – го порядка - C++
Разработайте класс, моделирующий многочлены n – го порядка от одной переменной. В классе должен быть конструктор копирования и оператор...

Построить интерполяционные многочлены Ньютона - C++
Построить интерполяционные многочлены Ньютона для функции F(x)=lg(x)-((x-1)/x) по следующим узлам: х=1, 2, 4, 8, 10; Проблемы возникают...

Интерполяционный многочлены по чебышевским узлам - C++
Всем здравствуйте!Столкнулся с проблемой: 1)Как находить узлы я знаю,и написал,и значения в ней нашел...Но как же строить сам многочлен я...

39
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
06.11.2012, 12:19 #2
include guard'ы написаны неверно - где define того, что проверяется в ifndef?
1
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
06.11.2012, 16:12  [ТС] #3
А я, когда пишу
C++
1
2
3
4
#ifndef prog.h
#define prog.h
/* code */
#endif
мне VS выдаёт ошибку, типа лишний раз объявлено. Или его не так писать надо?
Сейчас покушаю и напишу усовершенствованную версию=)
0
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
06.11.2012, 17:01 #4
в VS проще писать #pragma once
эта штука нестандартная, но много где работает
Меня тут - prog.h - точка смущает)
0
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
06.11.2012, 22:22  [ТС] #5
Вот (почти) финальный вариант. Гляньте одним глазком, всё ли верно? Я старался писать как можно более разборчиво
Кликните здесь для просмотра всего текста
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
29
30
31
32
33
34
#ifndef GF_h
#define GF_h
 
#include <vector>
 
const int GROUP_DEGREE = 0; // = m -- порядок группы GF(2^m)
const std::vector<int> PRIMITIVE_POLYNOMIAL (0); // примитивный полином в GF(2^m)
 
const std::vector<GF> init_GF_table (); // возвращает вектор из всех элементов GF(2^m)
const std::vector<GF> GF_table = init_GF_table ();
 
class GF 
{
private:
    int alpha_power; // представление в виде степени альфа
    std::vector<int> alpha_vector; // представление в виде вектора
    bool null; // индикатор того, что вектор нулевой
 
    void power_to_vector (); // используем 
    void vector_to_power (); // GF_table
 
public:
    GF ();
    GF (const int& power); // используем power_to_vector
    GF (const std::vector<int>& vector); // используем vector_to_power
    ~GF ();
 
    GF operator+ (const GF& right_hand_side) const; // сложение
    GF operator* (const GF& right_hand_side) const; // умножение
 
    std::vector<int> return_alpha_vector () const; // возврат элемента в виде вектора
};
 
#endif

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#ifndef GF_polynom_h
#define GF_polynom_h
 
#include "GF.h"
 
class GF_polynom
{
private:
    std::vector<GF> polynom; // вектор из коэфициентов полинома,
                             // которые принадлежат GF(2^m)
public:
    GF_polynom ();
    GF_polynom (const std::vector<GF>& coefficients);
    ~GF_polynom ();
 
    GF_polynom operator+ (const GF_polynom& right_hand_side) const; // сложение 
    GF_polynom operator* (const GF_polynom& right_hand_side) const; // умножение
    GF_polynom operator% (const GF_polynom& right_hand_side) const; // остаток от деления
 
    std::vector<GF> return_coefficients () const; // возвращает коэффициенты многочлена
};
 
#endif

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#ifndef RS_encoder_h
#define RS_encoder_h
 
#include "GF_polynom.h"
#include <string>
 
const int CODE_LENGTH = 0; // длина кода
const int MAX_ERRORS = 0; // количество исправляемых ошибок
const int MESSAGE_LENGTH = 0; // длина сообщения
 
std::vector<int> str_to_int (const std::string& str_message); // строку в вектор
std::vector<GF> message_to_GF_message (const std::vector<int>& message); // вектор из 0 и 1 в 
                                                                         // вектор из элементов GF(2^m)
std::vector<GF> encode (const std::vector<GF>& GF_message, const int& n = CODE_LENGTH, 
                        const int& k = MESSAGE_LENGTH); // кодирование сообщения
std::vector<int> GF_code_to_vector (const std::vector<GF>& code);
 
#endif


Добавлено через 4 часа 36 минут
Написал такое, выдаёт ошибку "vector out of range". Подскажите, где оно вылзит. Спасибо!
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef GF_table_h
#define GF_table_h
 
#include <vector>
 
extern const int GROUP_DEGREE; 
 
const std::vector<int> init_primitive_polynomial (const int& degree); 
                        
 
struct GF_table
{
    int power;
    std::vector<int> vector;
};
 
std::vector<GF_table> init_GF_table (const std::vector<int>& primitive_polynomial);
 
extern const std::vector<GF_table> table;
 
#endif

Кликните здесь для просмотра всего текста
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include "GF_table.h"
 
const int GROUP_DEGREE = 3;
 
const std::vector<int> init_primitive_polynomial (const int& degree = GROUP_DEGREE)
{
    std::vector<int> polynom;
    polynom.reserve (degree);
 
    switch (degree)
    {
    case 2:
        for (int i = 0; i < 3; ++i)
            polynom.push_back (1);
        return polynom;
    case 3:
        polynom.push_back (1);
        polynom.push_back (1);
        polynom.push_back (0);
        polynom.push_back (1);
        return polynom;
    case 4:
        polynom.push_back (1);
        polynom.push_back (1);
        polynom.push_back (0);
        polynom.push_back (0);
        polynom.push_back (1);
        return polynom;
    /* case 5, 6,...*/
    }
}
 
std::vector<GF_table> init_GF_table (const std::vector<int>& primitive_polynomial = init_primitive_polynomial ())
{
    std::vector<GF_table> table;
    table.reserve (int (std::pow (2.0, GROUP_DEGREE) - 1));
 
    std::vector<int> temp_vec (GROUP_DEGREE, 0);
    temp_vec.reserve (GROUP_DEGREE + 1);
 
    temp_vec.at(0) = 1;
 
    table.at(0).power = 0;
    table.at(0).vector = temp_vec; 
 
    for (int i = 1; i < int (std::pow (2.0, GROUP_DEGREE) - 1); ++i)
    {
        table.at(i).power = i;
 
        temp_vec = table.at(i - 1).vector;
        temp_vec.insert (temp_vec.begin (), 0);
        temp_vec.pop_back ();
 
        table.at(i).vector = temp_vec;
 
        if (table.at(i).vector.at(GROUP_DEGREE - 1) = 1)
            for (int j = 0; j < GROUP_DEGREE; ++j)
                table.at(i).vector.at(j) = (table.at(i).vector.at(j) + primitive_polynomial.at(j)) % 2;
    }
 
    return table;
}
 
const std::vector<GF_table> table (init_GF_table ());
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.11.2012, 23:04 #6
Для table вижу reserve, но не вижу увеличения размера, собсно получается вектор с нулевым размером и затем идет попытка получить его первый элемент.
И еще, глаз режет:
C++
1
std::pow (2.0, GROUP_DEGREE)
Используйте
C++
1
1 << GROUP_DEGREE
1
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
07.11.2012, 00:11 #7
C++
1
2
std::vector<GF> encode (const std::vector<GF>& GF_message, const int& n = CODE_LENGTH, 
                        const int& k = MESSAGE_LENGTH);
стандартные типы, такие как int, можно передавать по значению, а не по ссылке. Для них в случае ссылки никакого ускорения не будет
И еще, я вижу в классах деструктор, но не вижу конструктора копирования и оператора присваивания
2
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
07.11.2012, 02:55  [ТС] #8
Пока написал 2 штуки, но они не работают: выдаёт какую-то непонятную ошибку

Не по теме:

GF.obj : error LNK2019: ссылка на неразрешенный внешний символ "public: __thiscall GF::~GF(void)" (??1GF@@QAE@XZ) в функции "public: class GF __thiscall GF::operator+(class GF const &)const " (??HGF@@QBE?AV0@ABV0@@Z)


Вот, что я пока накатал...
Кликните здесь для просмотра всего текста
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF_table.h
* * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef GF_table_h
#define GF_table_h
 
#include <vector>
 
extern const int GROUP_DEGREE; 
 
const std::vector<int> init_primitive_polynomial (const int& degree); 
 
struct GF_table
{
    GF_table ();
    GF_table (const GF_table& GF_element);
    ~GF_table ();
 
    GF_table& operator= (const GF_table& right_hand_side);
 
    int power;
    std::vector<int> vector;    
};
 
std::vector<GF_table> init_GF_table (const std::vector<int>& primitive_polynomial);
 
extern const std::vector<int> null_vector;
extern const std::vector<GF_table> table;
 
#endif
 
 
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF_table.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "GF_table.h"
 
const int GROUP_DEGREE = 3;
 
const std::vector<int> init_primitive_polynomial (const int degree = GROUP_DEGREE)
{
    std::vector<int> polynom (degree + 1, 0);
    polynom.resize (degree + 1);
 
    switch (degree)
    {
    case 2:
        for (int i = 0; i < 3; ++i)
            polynom.at(i) = 1;
        return polynom;
 
    case 3:
        for (int i = 0; i < 4; ++i)
            polynom.at(i) = 1;
        polynom.at(2) = 0;
        return polynom;
 
    case 4:
        for (int i = 0; i < 5; ++i)
            polynom.at(i) = 1;
        polynom.at(2) = 0;
        polynom.at(3) = 0;
        return polynom;
 
    /* case 5, 6,...*/
    }
}
 
GF_table::GF_table ()
{
    power = 0;
    vector.resize (GROUP_DEGREE);
}
 
GF_table::GF_table (const GF_table& GF_element)
{
    power = GF_element.power;
    vector = GF_element.vector;
}
 
GF_table& GF_table::operator= (const GF_table& right_hand_side)
{
    power = right_hand_side.power;
    vector = right_hand_side.vector;
 
    return *this;
}
 
std::vector<GF_table> init_GF_table (const std::vector<int>& primitive_polynomial = init_primitive_polynomial ())
{
    std::vector<GF_table> table;
    table.resize ((1 << GROUP_DEGREE) - 1);
 
    std::vector<int> temp_vec (GROUP_DEGREE, 0);
    temp_vec.resize (GROUP_DEGREE);
 
    temp_vec.at(0) = 1;
 
    table.at(0).power = 0;
    table.at(0).vector = temp_vec; 
    
 
    for (int i = 1; i < (1 << GROUP_DEGREE - 1); ++i)
    {
        table.at(i).power = i;
 
        temp_vec = table.at(i - 1).vector;
        temp_vec.insert (temp_vec.begin (), 0);
 
        if (*(table.at(i).vector.end ()) = 1)
            for (int j = 0; j < GROUP_DEGREE; ++j)
                table.at(i).vector.at(j) = (table.at(i).vector.at(j) + primitive_polynomial.at(j)) % 2;
        
        temp_vec.pop_back ();
 
        table.at(i).vector = temp_vec;      
    }
 
    return table;
}
 
const std::vector<int> null_vector (GROUP_DEGREE, 0);
 
const std::vector<GF_table> table (init_GF_table ());

Кликните здесь для просмотра всего текста
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF.h
* * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef GF_h
#define GF_h
 
#include "GF_table.h"
 
class GF 
{
private:
    int alpha_power; // представление в виде степени альфа
    std::vector<int> alpha_vector; // представление в виде вектора
    int null; // индикатор того, что вектор нулевой
 
    int ifnull ();
    void power_to_vector (); // используем 
    void vector_to_power (); // GF_table
 
public:
    GF ();
    GF (const GF& GF_element);
    GF (const std::vector<int> vector);
    ~GF ();
    
    GF& operator= (const GF& right_hand_side);
 
    GF operator+ (const GF& right_hand_side) const; // сложение
    GF operator* (const GF& right_hand_side) const; // умножение
 
    std::vector<int> return_alpha_vector () const; // возврат элемента в виде вектора
};
 
#endif
 
 
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "GF.h"
 
GF::GF ()
{
    alpha_power = 0;
    alpha_vector.resize (GROUP_DEGREE);
    null = 1;
}
 
GF::GF (const GF& GF_element)
{
    alpha_power = GF_element.alpha_power;
    alpha_vector = GF_element.alpha_vector;
    null = GF_element.null;
}
 
GF::GF (const std::vector<int> vector)
{
    alpha_vector = vector;
    vector_to_power ();
}
 
GF& GF::operator= (const GF& right_hand_side)
{
    alpha_power = right_hand_side.alpha_power;
    alpha_vector = right_hand_side.alpha_vector;
    null = right_hand_side.null;
 
    return *this;
}
 
void GF::power_to_vector ()
{
    alpha_vector = table.at(alpha_power).vector;
}
 
void GF::vector_to_power ()
{
    if (alpha_vector != null_vector)
    {
        int i = 0;
        while (table.at(i).vector != alpha_vector)
            ++i;
 
        alpha_power = i;
    }
    else
        null = 1;   
}
 
GF GF::operator+ (const GF& right_hand_side) const
{
    if (null == 1) 
        return right_hand_side;
    if (right_hand_side.null == 1)
        return *this;
 
    GF sum;
 
    for (int i = 0; i < GROUP_DEGREE; ++i)
        sum.alpha_vector.at(i) = (alpha_vector.at (i) + right_hand_side.alpha_vector.at (i)) % 2;
    
    if (sum.alpha_vector == null_vector)
    {
        sum.null = 1;
        return sum;
    }
 
    sum.vector_to_power ();
 
    return sum;
}
 
GF GF::operator* (const GF& right_hand_side) const
{
    if (null == 1)
        return *this;
    if (right_hand_side.null == 1)
        return right_hand_side;
 
    GF prod;
 
    prod.alpha_power = (alpha_power + right_hand_side.alpha_power) % ((1 << GROUP_DEGREE) - 1);
    
    prod.power_to_vector ();
    
    return prod;
}
 
std::vector<int> GF::return_alpha_vector () const
{
    return alpha_vector;
}

Всем большое спасибо за помощь! Я уже не дописывал комментарии в последнем коде, надеюсь, там и так всё понятно (или ничего не понятно ).
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 1
07.11.2012, 04:31 #9
всё проще чем кажется. деструктор ~GF_table вообще отсутствует. Т.е. Объявлен и Не реализован.
Вот например строки 77-81 - это конструктор. Почему деструктор не написали примерно после конструктора?
2
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
08.11.2012, 02:44  [ТС] #10
Т.е. Объявлен и Не реализован.
Я думал, что если его объявить и не реализовать, то он реализуется сам по себе. А что в нём написать? Или лучше его пустым оставить?
Поправил первые два файлика, вроди всё работает. Гляньте ещё разок, на всякий.
Кликните здесь для просмотра всего текста
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF_table.h
* * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef GF_table_h
#define GF_table_h
 
#include <vector>
 
extern const int GROUP_DEGREE; 
 
const std::vector<int> init_primitive_polynomial (const int degree); 
 
struct GF_table
{
    GF_table ();
    GF_table (const GF_table& GF_element);
    ~GF_table ();
 
    GF_table& operator= (const GF_table& right_hand_side);
 
    int power;
    std::vector<int> vector;    
};
 
std::vector<GF_table> init_GF_table (const std::vector<int>& primitive_polynomial);
 
extern const std::vector<GF_table> table;
 
extern const std::vector<int> null_vector;
extern const std::vector<int> unit_vector;
 
#endif
 
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF_table.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "GF_table.h"
 
const int GROUP_DEGREE = 3;
 
const std::vector<int> init_primitive_polynomial (const int degree = GROUP_DEGREE)
{
    std::vector<int> polynom (degree, 0);
    polynom.resize (degree);
 
    switch (degree)
    {
    case 2:
        for (int i = 0; i < 2; ++i)
            polynom.at(i) = 1;
 
        return polynom;
 
    case 3:
        for (int i = 0; i < 3; ++i)
            polynom.at(i) = 1;
 
        polynom.at(2) = 0;
        return polynom;
 
    case 4:
        for (int i = 0; i < 4; ++i)
            polynom.at(i) = 1;
 
        polynom.at(2) = 0;
        polynom.at(3) = 0;
        return polynom;
 
    /* case 5, 6,...*/
    }
}
 
GF_table::GF_table ()
{
    power = 0;
    vector.resize (GROUP_DEGREE);
}
 
GF_table::GF_table (const GF_table& GF_element)
{
    power = GF_element.power;
    vector = GF_element.vector;
}
 
GF_table::~GF_table ()
{
 
}
 
GF_table& GF_table::operator= (const GF_table& right_hand_side)
{
    power = right_hand_side.power;
    vector = right_hand_side.vector;
 
    return *this;
}
 
std::vector<GF_table> init_GF_table (const std::vector<int>& primitive_polynomial = init_primitive_polynomial ())
{
    std::vector<GF_table> table;
    table.resize ((1 << GROUP_DEGREE) - 1);
 
    std::vector<int> temp_vec (GROUP_DEGREE, 0);
 
    temp_vec.at(0) = 1;
    table.at(0).vector = temp_vec;
 
    for (int i = 1; i < (1 << GROUP_DEGREE) - 1; ++i)
    {
        table.at(i).vector.at(0) = 0;
 
        for (int j = 1; j < GROUP_DEGREE; ++j)
            table.at(i).vector.at(j) = table.at(i - 1).vector.at(j - 1);
 
        if (table.at(i - 1).vector.at(GROUP_DEGREE - 1) == 1)
            for (int j = 0; j < GROUP_DEGREE; ++j)
                table.at(i).vector.at(j) = (table.at(i).vector.at(j) + primitive_polynomial.at(j)) % 2;
    }
 
    return table;
}
 
const std::vector<GF_table> table (init_GF_table ());
 
const std::vector<int> null_vector (GROUP_DEGREE, 0);
const std::vector<int> unit_vector (table.at(0).vector);

Кликните здесь для просмотра всего текста
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF.h
* * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef GF_h
#define GF_h
 
#include "GF_table.h"
 
class GF 
{
private:
    int alpha_power; // представление в виде степени альфа
    std::vector<int> alpha_vector; // представление в виде вектора
    int null; // индикатор того, что вектор нулевой
 
    void power_to_vector (); // используем 
    void vector_to_power (); // GF_table
 
public:
    GF ();
    GF (const GF& GF_element);
    GF (const int power);
    GF (const std::vector<int> vector);
    ~GF ();
    
    GF& operator= (const GF& right_hand_side);
 
    GF operator+ (const GF& right_hand_side) const; // сложение
    GF operator* (const GF& right_hand_side) const; // умножение
 
    int return_power () const;
    std::vector<int> return_alpha_vector () const; // возврат элемента в виде вектора
};
 
#endif
 
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "GF.h"
 
GF::GF ()
{
    alpha_power = 0;
    alpha_vector.resize (GROUP_DEGREE);
    null = 1;
}
 
GF::GF (const GF& GF_element)
{
    alpha_power = GF_element.alpha_power;
    alpha_vector = GF_element.alpha_vector;
    null = GF_element.null;
}
 
GF::GF (const int power)
{
    alpha_power = power;
    power_to_vector ();
}
 
GF::GF (const std::vector<int> vector)
{
    alpha_vector = vector;
    vector_to_power ();
}
 
GF::~GF ()
{
 
}
 
GF& GF::operator= (const GF& right_hand_side)
{
    alpha_power = right_hand_side.alpha_power;
    alpha_vector = right_hand_side.alpha_vector;
    null = right_hand_side.null;
 
    return *this;
}
 
void GF::power_to_vector ()
{
    alpha_vector = table.at(alpha_power).vector;
}
 
void GF::vector_to_power ()
{
    if (alpha_vector != null_vector)
    {
        int i = 0;
        while (table.at(i).vector != alpha_vector)
            ++i;
 
        alpha_power = i;
        null = 0;
    }
    else
        null = 1;   
}
 
GF GF::operator+ (const GF& right_hand_side) const
{
    if (null == 1) 
        return right_hand_side;
    if (right_hand_side.null == 1)
        return *this;
 
    GF sum;
 
    for (int i = 0; i < GROUP_DEGREE; ++i)
        sum.alpha_vector.at(i) = (alpha_vector.at (i) + right_hand_side.alpha_vector.at (i)) % 2;
    
    if (sum.alpha_vector == null_vector)
    {
        sum.null = 1;
        return sum;
    }
 
    sum.vector_to_power ();
 
    return sum;
}
 
GF GF::operator* (const GF& right_hand_side) const
{
    if (null == 1)
        return *this;
    if (right_hand_side.null == 1)
        return right_hand_side;
 
    GF prod;
 
    prod.alpha_power = (alpha_power + right_hand_side.alpha_power) % ((1 << GROUP_DEGREE) - 1);
    
    prod.power_to_vector ();
    
    return prod;
}
 
int GF::return_power () const
{
    return alpha_power;
}
 
std::vector<int> GF::return_alpha_vector () const
{
    return alpha_vector;
}

Сейчас дописываю третий файлик. Подскажите, как лучше реализовать деление с остатком? И пустой конструктор по умолчанию сгодится?
Кликните здесь для просмотра всего текста
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/* * * * * * * * * * * * * * * * * * * * * * *
                GF_polynom.h
* * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef GF_polynom_h
#define GF_polynom_h
 
#include "GF.h"
 
class GF_polynom
{
private:
    std::vector<GF> polynom; // вектор из коэфициентов полинома,
                             // которые принадлежат GF(2^m)
public:
    GF_polynom ();
    GF_polynom (const GF_polynom& GF_polynom_element);
    GF_polynom (const std::vector<GF>& coefficients);
    ~GF_polynom ();
 
    GF_polynom& operator= (const GF_polynom& right_hand_side);
 
    GF_polynom operator+ (const GF_polynom& right_hand_side) const; // сложение 
    GF_polynom operator* (const GF_polynom& right_hand_side) const; // умножение
    GF_polynom operator% (const GF_polynom& right_hand_side) const; // остаток от деления
 
    std::vector<GF> return_coefficients () const; // возвращает коэффициенты многочлена
};
 
#endif
 
/* * * * * * * * * * * * * * * * * * * * * * *
                GF_polynom.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "GF_polynom.h"
 
GF_polynom::GF_polynom ()
{
 
}
 
GF_polynom::GF_polynom (const GF_polynom& GF_polynom_element)
{
    polynom.resize (GF_polynom_element.polynom.size());
    polynom = GF_polynom_element.polynom;
}
 
GF_polynom::GF_polynom (const std::vector<GF>& coefficients)
{
    polynom.resize (coefficients.size ());
    polynom = coefficients;
}
 
GF_polynom::~GF_polynom ()
{
 
}
 
GF_polynom& GF_polynom::operator= (const GF_polynom& right_hand_side)
{
    polynom.resize (right_hand_side.polynom.size());
    polynom = right_hand_side.polynom;
 
    return *this;
}
 
GF_polynom GF_polynom::operator+ (const GF_polynom& right_hand_side) const
{
    GF_polynom sum;
    sum.polynom.resize (std::max(polynom.size(), right_hand_side.polynom.size()));
 
    for (int i = 0; i < std::min(polynom.size(), right_hand_side.polynom.size()); ++i)
        sum.polynom.push_back (polynom.at(i) + right_hand_side.polynom.at(i));
 
    if (polynom.size() < right_hand_side.polynom.size())
        for (int i = polynom.size(); i < right_hand_side.polynom.size(); ++i)
            sum.polynom.push_back (right_hand_side.polynom.at(i));
    else
        for (int i = right_hand_side.polynom.size(); i < polynom.size(); ++i)
            sum.polynom.push_back (polynom.at(i));
    
    return sum;
}
 
GF_polynom GF_polynom::operator* (const GF_polynom& right_hand_side) const
{
    GF_polynom prod;
    prod.polynom.resize (polynom.size() + right_hand_side.polynom.size());
 
    for (int i = 0; i < prod.polynom.size(); ++i)
    {
        GF sum (null_vector);
 
        for (int j = 0; j < i + 1; ++j)
            if ((j < polynom.size()) && (i - j < right_hand_side.polynom.size()))
                sum = sum + (polynom.at(j) * right_hand_side.polynom.at(i - j));
        
        prod.polynom.push_back (sum);
    }
 
    return prod;
}
 
GF_polynom GF_polynom::operator% (const GF_polynom& right_hand_side) const
{
 
}
 
std::vector<GF> GF_polynom::return_coefficients () const
{
    return polynom;
}
0
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
08.11.2012, 13:38 #11
Все конструкции такого вида
C++
1
2
3
4
5
GF_polynom::GF_polynom (const GF_polynom& GF_polynom_element)
{
    polynom.resize (GF_polynom_element.polynom.size());
    polynom = GF_polynom_element.polynom;
}
лучше заменить на
C++
1
2
3
4
GF_polynom::GF_polynom (const GF_polynom& GF_polynom_element):
polynom(GF_polynom_element.polynom)
{
}
Добавлено через 17 минут
в 71 строке вы создаете вектор определенной длины, заполненный нулями. А затем вы эти нули нигде не используете - только пушаете новые значения. Так и задумано?
1
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
08.11.2012, 17:08  [ТС] #12
ок, заменю. А что за 71 строка? Эта?
C++
1
sum.polynom.resize (std::max(polynom.size(), right_hand_side.polynom.size()));
0
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
08.11.2012, 17:21 #13
vlad_light, да, она. Я просто забыл дописать, из какого она листинга
0
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
08.11.2012, 17:23  [ТС] #14
т.е. там нужно вместо push_back везде написать at(i) верно?
Либо перед циклом написать clear.
0
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
08.11.2012, 17:32 #15
Лучше заменить resize на reserve. пушбеки оставить
Кстати вместо at(i) можно писать [i]
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.11.2012, 17:32
Привет! Вот еще темы с ответами:

Как запрограммировать математические многочлены, формулы? - C++
Каким образом запрограммировать математические вычисления вида: (a1+a2+… + an)/n ( a1+(a2+a3)/2+(a4+a5+a6)/3+… +(a'n-k'+...+an)/k ) / p...

Алгоритм генерации типовых задач по теме "Многочлены" - C++
Помогите с алгоритмом) никак не могу написать алгоритм генерации((( Например, деление многочленов

Выразить через основные симметрические многочлены моногенные многочлены - Алгебра
Здравствуйте. помогите пожалуйста понять как делать следующее задание &quot;Выразить через основные симметрические многочлены моногенные...

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


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
08.11.2012, 17:32
Ответ Создать тему
Опции темы

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