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

Реализовать поле Галуа - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.88
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
21.01.2014, 01:49     Реализовать поле Галуа #1
Нужно реализовать поле Галуа GF(2^m) на с++.
Хочу реализовать так:
создать класс
C++
1
2
3
4
5
6
7
8
9
10
11
class GF
{
public:
    GF();
 
    GF operator+(const GF&);
    GF operator*(const GF&);
private:
    int poly;
    int root;
}
Каждый элемент поля представляется в двух видах: root и poly. Первый удобен для умножения, а второй -- для сложения.
Также, мне нужны: генерирующий полином int genPoly две таблички int *rootTable и int *polyTable, которые я буду использовать для сложения и умножения как LookUp Table.
Нужно, чтоб genPoly можно было задать предварительно, с его помощью создать две таблички (их размер зависит от genPoly) и сделать их недоступными для дальнейшей модификации. Как это лучше реализовать?

Не по теме:

Кстати, если эта реализация плохая -- готов рассмотреть вашу. Ссылки на opensource не предлагать.



Добавлено через 3 часа 2 минуты
Напишу подробнее, что я имел ввиду.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class GF
{
public:    
    /*
    ...
    */
    void initTable(const int genPoly);
private:
    /*
    ...
    */
    static const int *rootTable; // *
};
 
/*
...
*/
void GF::initTable(const int genPoly)
{
    rootTable = new int[genPolyDegree]; // **
    // ...
}
* - const для запрещения модификации и static для запрещения создания копии при создании экземпляров.
** - в этом месте выдаёт ошибку unresolved external symbol rootTable.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.01.2014, 01:49     Реализовать поле Галуа
Посмотрите здесь:

Поле first - целое число, длительность телефонного разговора в минутах; поле second - дробное число, стоимость одной минуты в гривнах C++
Определить сможет ли белый слон расположенный на поле (a,b),одним ходом пойти на поле (e,f),не попав при этом под удар чёрного коня нах.(c,d) C++
Поле first — целое число, левая граница диапазона, включается в диапазон; поле second — целое число, правая граница диапазона, не включается в диапазо C++
C++ Только константное статическое поле НЕ МОЖЕТ быть поле членом класса !
Друзья, подскажите, как в классе создать константное поле, ссылочное поле и объектное поле? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
21.01.2014, 07:57     Реализовать поле Галуа #2
Функцию имеет смысл сделать статической:
C++
1
static void initTable(const int genPoly);
А статическое поле нужно определить вне класса:
C++
1
const int* GF::rootTable;
http://ideone.com/Yi3P8S
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
21.01.2014, 18:13  [ТС]     Реализовать поле Галуа #3
Спасибо большое!!!
Т.е., когда я пишу
C++
1
static const int *rootTable;
внутри класса -- это всего лишь даёт членам класса доступ к этой переменной, но память на неё выделять сам класс не умеет?

Добавлено через 6 минут
И ещё вопрос: чем отличается statc const от const static?
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
21.01.2014, 18:24     Реализовать поле Галуа #4
Цитата Сообщение от vlad_light Посмотреть сообщение
это всего лишь даёт членам класса доступ к этой переменной, но память на неё выделять сам класс не умеет?
это называется "переменная объявлена (declared), но не определена (defined)".
Только для интегральных типов (int,char, например) объявление в классе статической константы будет являться и определением. Хотя тут тоже есть нюансы, например если захотите взять от нее адрес, то нужно всё равно будет определить ее вне класса.
Цитата Сообщение от vlad_light Посмотреть сообщение
чем отличается static const от const static?
Ничем.
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
22.01.2014, 00:08  [ТС]     Реализовать поле Галуа #5
Цитата Сообщение от Tulosba Посмотреть сообщение
Только для интегральных типов (int,char, например)
Думал, что int* тоже к ним относится.

Добавлено через 5 часов 28 минут
Вот, я написал -- может кому будет полезно...
Можете, пожалуйста, глянуть код и по исправлять ошибки. Заранее благодарен!
Кликните здесь для просмотра всего текста
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
// GF.h
 
#pragma once
 
typedef unsigned char uint8;
typedef unsigned int uint32;
 
class GF
{
public:    
    GF();
    GF(const uint32 polynomial);
 
    static void initializeTable(const uint32 generatorPolynomial, const uint8 generatorPolynomialDegree);
    static void deleteTable();
 
    GF operator+(const GF& rhs) const; // operator- is the same as operator+
    GF operator*(const GF& rhs) const;
    GF invert() const; // a/b == a * b.invert
 
 
private:
    uint32 m_polynomial;
 
    static uint32 m_generatorPolynomial;    
    static const uint32* m_polynomialTable;
    static const uint32* m_rootTable;
    static uint32 m_tableSize;
};
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
// GF.cpp
 
#include "GF.h"
 
const uint32* GF::m_polynomialTable = nullptr;
const uint32* GF::m_rootTable = nullptr;
uint32 GF::m_generatorPolynomial = 0;
uint32 GF::m_tableSize = 0;
 
GF::GF()
{
 
}
 
GF::GF(const uint32 polynomial)
{
    m_polynomial = polynomial;
}
 
void GF::initializeTable(const uint32 generatorPolynomial, const uint8 generatorPolynomialDegree)
{
    deleteTable();
 
    m_generatorPolynomial = generatorPolynomial;
 
    m_tableSize = (1 << generatorPolynomialDegree) - 1;
    uint32* table = new uint32[m_tableSize];
 
    // construct root table
    for(uint8 i = 0; i < generatorPolynomialDegree; ++i)
        table[i] = 1 << i;
 
    uint32 tableMask = (1 << generatorPolynomialDegree) - 1;
    for (uint32 i = generatorPolynomialDegree; i < m_tableSize; ++i)
    {
        table[i] = table[i - 1] << 1;
 
        if(table[i - 1] >> (generatorPolynomialDegree - 1))
        {
            table[i] ^= m_generatorPolynomial;
            table[i] &= tableMask;
        }
    }
 
    m_rootTable = table;
    
    // construct polynomial table
    table = new uint32[++m_tableSize];
    table[0] = 0;
    for(uint32 i = 0; i < m_tableSize - 1; ++i)
        table[m_rootTable[i]] = i;
 
    m_polynomialTable = table;
}
 
void GF::deleteTable()
{
    if((m_polynomialTable != nullptr) && (m_rootTable != nullptr))
    {
        delete[] m_polynomialTable;
        delete[] m_rootTable;
        m_polynomialTable = nullptr;
        m_rootTable = nullptr;
    }
}
 
GF GF::operator+(const GF& rhs) const
{
    return GF(m_polynomial ^ rhs.m_polynomial);
}
 
GF GF::operator*(const GF& rhs) const
{
    if(this->m_polynomial == 0)
        return *this;
    if(rhs.m_polynomial == 0)
        return rhs;
 
    return GF(m_rootTable[(m_polynomialTable[m_polynomial] + m_polynomialTable[rhs.m_polynomial]) % (m_tableSize - 1)]);
}
 
GF GF::invert() const
{
    if(m_polynomial == 0)
        throw "Division by zero";
 
    return GF(m_rootTable[m_tableSize - 1 - m_polynomialTable[m_polynomial]]);
}
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,419
22.01.2014, 00:14     Реализовать поле Галуа #6
Память, выделенную new[] необходимо освободить.
Используйте список инициализации в конструкторе
C++
1
2
GF::GF(const uint32 polynomial) :
    m_polynomial(polynomial) {}
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
22.01.2014, 00:17  [ТС]     Реализовать поле Галуа #7
Используйте список инициализации в конструкторе
У меня почему-то в msvs 2010 express оно не хочет так делать. Это, наверное, начиная с с++11 так можно делать.
Память, выделенную new[] необходимо освободить.
У меня это делает функция static void deleteTable();. Можно как-то сделать выделение и освобождение памяти автоматически?
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,419
22.01.2014, 00:19     Реализовать поле Галуа #8
Цитата Сообщение от vlad_light Посмотреть сообщение
Это, наверное, начиная с с++11 так можно делать.
нет, это можно было делать еще до него. Видимо вы что-то неверно делаете.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.01.2014, 00:22     Реализовать поле Галуа
Еще ссылки по теме:

Реализовать игровое поле в игре "Тетрис" C++
C++ Необходимо реализовать шаблонный класс Array, и грамотно реализовать push_back
C++ Поле чудес С++

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

Или воспользуйтесь поиском по форуму:
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
22.01.2014, 00:22     Реализовать поле Галуа #9
Цитата Сообщение от vlad_light Посмотреть сообщение
Можно как-то сделать выделение и освобождение памяти автоматически?
Создать тип, который будет в конструкторе выделять память, в деструкторе освобождать. И сделать статическую переменную этого типа в классе.
С другой стороны, так как статическая переменная существует все время работы программы, можно особо не заморачиваться с удалением. Все равно система почистит после завершения процесса.
Yandex
Объявления
22.01.2014, 00:22     Реализовать поле Галуа
Ответ Создать тему
Опции темы

Текущее время: 11:39. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru