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

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

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

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

21.01.2014, 01:49. Просмотров 1212. Ответов 9
Метки нет (Все метки)

Нужно реализовать поле Галуа 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     Реализовать поле Галуа
Посмотрите здесь:

Написать класс для реализации полей Галуа - C++
Здравствуйте! Нужно реализовать поля Галуа GF (2^n). 1. Запросить у пользователя ввести число n. 2. Представить результат в виде...

Реализовать проверку типа вводимого пользователем значения, которым будет инициализировано поле структуры - C++
Товарищи, поомогите пожалста. есть код, проблема в том что если в переменную code вводят НЕ число, программа зацикливается. вопрос -...

Реализовать игровое поле в игре "Тетрис" - C++
Добрый вечер, писал программу тетрис, и ни как не могу исправить некоторые ошибки Что нужно: 1. Нужно поле игровое по центру консоли...

Определить сможет ли белый слон расположенный на поле (a,b),одним ходом пойти на поле (e,f),не попав при этом под удар чёрного коня нах.(c,d) - C++
ребята помогите пожалуйста!я в с++ вообще не бум-бум! у меня 2-е задачи с шахматами!а я даже играть не умею в них!помогите пожалуйста!я...

Поле first - целое число, длительность телефонного разговора в минутах; поле second - дробное число, стоимость одной минуты в гривнах - C++
Поле first - целое число, длительность телефонного разговора в минутах; поле second - дробное число, стоимость одной минуты в гривнах....

Поле first — целое число, левая граница диапазона, включается в диапазон; поле second — целое число, правая граница диапазона, не включается в диапазо - C++
8. Поле first — целое число, левая граница диапазона, включается в диапазон; поле second — целое число, правая граница диапазона, не...

Поле Галуа - Алгебра
1)Построить поле GF(2^5) по модулю p(x) = x^5 + x +1. 2)Операции в этом поле. Прошу помощи совершенно не понимаю как это делать.

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tulosba
:)
Эксперт С++
4393 / 3236 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
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
:)
Эксперт С++
4393 / 3236 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
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
Модератор
Эксперт CЭксперт С++
7153 / 4319 / 630
Регистрация: 29.11.2010
Сообщений: 11,739
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
Модератор
Эксперт CЭксперт С++
7153 / 4319 / 630
Регистрация: 29.11.2010
Сообщений: 11,739
22.01.2014, 00:19     Реализовать поле Галуа #8
Цитата Сообщение от vlad_light Посмотреть сообщение
Это, наверное, начиная с с++11 так можно делать.
нет, это можно было делать еще до него. Видимо вы что-то неверно делаете.
Tulosba
:)
Эксперт С++
4393 / 3236 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
22.01.2014, 00:22     Реализовать поле Галуа #9
Цитата Сообщение от vlad_light Посмотреть сообщение
Можно как-то сделать выделение и освобождение памяти автоматически?
Создать тип, который будет в конструкторе выделять память, в деструкторе освобождать. И сделать статическую переменную этого типа в классе.
С другой стороны, так как статическая переменная существует все время работы программы, можно особо не заморачиваться с удалением. Все равно система почистит после завершения процесса.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.04.2017, 19:11     Реализовать поле Галуа
Еще ссылки по теме:

Поле Галуа. Решить систему - Дискретная математика
необходимо решить в GF(23) систему 2х+2у=3 х+2у=2

Поле Галуа из 256 элементов (умножение) - Алгебра
Здравствуйте. В универе задали реализовать умножение в поле Галуа из 256 элементов. Прочёл статью Касперского о кодах Рида-Соломона, в...

Поля Галуа - C++ Builder
Задача состоит в том, что есть некое поле Галуа GF*(p), где р (простое число) - характеристика поля, которую мы вводим, {1, а, a^2,...

Вопрос по полю Галуа - Алгебра
Здравствуйте.Созрел вопрос по конечному полю - полю Галуа.Разъясните пож-та как находится обратный элемент в поле GF (28) ????? По моему...

Насколько сложна теория Галуа? - Алгебра
Если взять всю алгебру и оценивать от 1 до 10?


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

Или воспользуйтесь поиском по форуму:
ONEJI
4 / 4 / 4
Регистрация: 13.11.2015
Сообщений: 86
01.04.2017, 19:11     Реализовать поле Галуа #10
а как здесь выводить поле Галуа? я имеюю ввиду в виде таблицы
Yandex
Объявления
01.04.2017, 19:11     Реализовать поле Галуа
Ответ Создать тему
Опции темы

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