Полигон-2

xoiss написал:

[q]

всё понятно?

[/q]

Спасибо, почти.

xoiss написал:

[q]

в общем, чтобы "разделить полином A на полином B по модулю P", надо сделать вот что:

[/q]

Что такое разделить, понимаю.
Что значит "по модулю P"?

Rio444 написал:

[q]

Что такое разделить, понимаю.
Что значит "по модулю P"?

[/q]

множества чисел (или множества "объектов", в общем случае) бывают бесконечными и конечными
и те и другие — "мамы всякие нужны, мамы всякие важны"

арифметические операции на бесконечных множествах — это обычные сложение, умножение и пр.

на КОНЕЧНЫХ же множествах (на интервалах целых чисел, например) так вот просто операцию сложения не введёшь, т.к. результат может оказаться за пределами множества
// например, на множестве чисел 0..9 если сложить 5+5, то результат 10 не будет принадлежать этому множеству, хотя слагаемые принадлежат
такая "недоделанная" операция сложения на конечных множествах не имеет практического смысла

поэтому придумали операцию сложения по модулю — ну, а почему бы и не придумать
её основное свойство в том, что результат сложения-по-модулю всегда принадлежит тому же множеству
// обычную операцию сложения на бесконечных множествах можно, кстати, рассматривать как "сложение по модулю бесконечности"

короче, сложение-по-модулю — это как бы "просто сложение", но только на конечных множествах целых чисел
никакой особой супер магии в нём нет — просто это ЕДИНСТВЕННЫЙ вариант, как ещё адекватно прикрутить операцию сложения чисел к конечным множествам чисел

для множества { 0 ... (N-1) } сложение по модулю — это будет сложение по модулю N — ну, по определению
например, если N=12, а множество будет 0..11, то сложение по модулю (7 + 8) mod 12 = 3
// см. "остаток от деления" — это суть то же самое в данном случае

если на множестве (чисел, полиномов, объектов) определена операция сложения (сложения по модулю), то можно определить объект-ноль — это такой, который будучи прибавленным к любому объекту множества даёт тот же самый объект
// не каждое множество имеет объект-ноль... например, множество 2..9 не имеет

далее, на множестве можно определить операцию умножения по модулю
ну, она определяется, как и обычно, как многократное сложение по модулю

в множестве можно определить объект-единицу — это такой, который будучи умноженным на любой объект из множества даёт его же

// ... пытаюсь объяснять "на пальцах", поэтому не буду использовать мат.термины типа группы, кольца и пр. — но если есть желание, то посмотрите их сами
https://ru.wikipedia.org/wiki/Кольцо_(математика)

// понятно, что примеры с числами - это лишь частный случай

далее можно определить обратный элемент к данному — это такой, который будучи умноженным по модулю на данный элемент (на элемент, которому он обратен) даёт объект-единицу

умножение-по-модулю на обратный-по-модулю элемент к данному можно считать делением-по-модулю на данный элемент, в каком-то смысле
// один пример деления-по-модулю я приводил в пред. комменте
ещё раз обращаю внимание, что деление-по-модулю в общем случае даёт совсем не такой результат, как обычное деление

... далее... интересные свойства наблюдаются в том случае, если модуль N является простым числом — поэтому я и обозначил его P в пред. комменте
что за интересные свойства? ну, долго перечислять и даже не знаю, с чего начать — не столько интересные они, сколько полезные в плане массы практических приложений
например, там всегда существует объект, обратный к данному, — а значит вполне определена операция деления-по-модулю, что офигительно полезно в ряде прикладных задач теории чисел

ещё один пример деления по модулю:
пусть модуль будет P=13 (простое число)
множество тогда будет 0..12
поделим 6 на 3 по модулю 13 в этом множестве
для этого надо сначала найти элемент, обратный 3 по модулю 13
// сразу скажу, что (1) он существует, и (2) он определён единственным образом!
не вдаваясь в детали, элемент обратный 3 по модулю 13, — это 9 // проверим: (9*3) mod 13 = (27) mod 13 = 27-13-13 = 1 — действительно, получилась единица
теперь умножаем 6 на 9 по модулю 13: (6*9) mod 13 = (54) mod 13 = 54-13-13-13-13 = 2
итак, частное от деления 6 на 3 по модулю 13 равно, как ни странно, 2

другой пример:
пусть модуль будет P=13 (простое число)
множество тогда будет 0..12
поделим 5 на 3 по модулю 13 в этом множестве
ну, обратный элемент к 3 мы уже знаем — это 9
теперь умножаем 5 на 9 по модулю 13: (5*9) mod 13 = (45) mod 13 = 45-13-13-13 = 6
итак, частное от деления 5 на 3 по модулю 13 равно ... 6 --- внезапно

то есть вывод: деление по модулю на конечных множествах чисел (ну, не хочу я использовать официальные мат.термины) в общем случае даёт непривычные числовые результаты
ну, как прибили — так и держится, что тут скажешь ---- зато профит в том, что результат получается целым числом и никаких "остатков от деления"!!! (ну, если модуль P - это простое число)


стало ли хоть как-то понятней, что такое "модуль" ?
... и что такое "разделить по модулю" ??

xoiss написал:

[q]

[/q]

Большое спасибо!
Стало всё понятно об операциях "по модулю".
Более того, есть очень понятная для программистов интерпретация - арифметические операции с байтами без учета переполнения.
Например, если мы сложим два однобайтовых числа 0b1000 0000 и 0b1000 0001 (десятичные 128 и 129, шестнадцатиричные 80h и 81h) то должны получить 0b1 0000 0001 (257, 101h). Но если операция производится с 8-битными регистрами, то на выходе будет "1", а старший бит уйдет в флаг переполнения. Если его не учитывать, получится "сложение по модулю 256", верно?


Rio444 написал:

[q]

Оффтопик: ...всегда ненавидел математику, а высшую, так абсолютно.

[/q]

В преподавателями не повезло. До ВУЗа математика мне нравилась. Всё было понятно.
В ВУЗе всё было скучно. Изучали матрицы, оператор Лапласа и прочую "хрень".
Уже после окончания ВУЗа узнал, что матрицы - это коэффициенты линейных уравнений и используются для их решения.
Оператор Лапласа - для расчета электрических цепей.
Преподавательница математики то ли забыла об этом сказать, то ли сделала это очень невнятно.
А отношение уже совсем другое.
Её, понятно, эти электрические цепи нафиг не сдались, она чисто теоретик. А для нас, студентов электромеханического факультета, это был принципиальный вопрос.

И в финале посмотрите алгоритм быстрого табличного вычисления CRC по значению очередного байта

искать lookup table crc algorithm

xoiss написал:

[q]

На микроконтроллерах же лимитирующий фактор обычно - это объём памяти (особенно если это быстрый и дорогущий он-чип SRAM, в который при старте заливается прошивка из медленного флеш-хранилища). Если так, то выгоднее использовать 1-битный чисто сдвиговый алгоритм, описанный здесь выше.

[/q]

Интересно для AVR. Разве 16-байтовая таблица существенно займёт память контроллера?