Остаточные классы

[fat_crocodile]

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

А идея такая:

• берём несколько

Comments

[scavenger_spb]

На самом деле эти тройки соответствуют классам эквивалентности обычных чисел, т.е. одной тройке соответствует множество чисел. А взаимно однозначное соответствие как-нить реализуется? Т.е. меня интересует представление чисел больше pqg.

Да, и еще... Алгоритм деления существует? И есть ли вообще однозначный результат такой операции?

ЗЫ А почему g, а не r?

[fat_crocodile]

Да, конечно класс эквивалентности, понятно, что все три остатка для (pqg + 1) и для просто 1 совпадают. С этим, по-моему, ничего не поделать.

Но точно такое же ограничение накладывает любое представление ограниченной разрядности.

Алгоритмов деления в те времена было придумано много, но я ни одного не знаю :) Там всё действительно сложно. Если бы реализовать деление, то можно было бы привести и к стандартному 10-му или 2-му виду.

Однозначный результат, конечно, есть. Возможно преобразовать делимое и делитель к "нормальной" форме, а потом преобразовать результат к "остаточной" -- вот тебе и однозначный результат.

Но преобразование к нормальной форме это решение системы уравнений в целых числах... И это тот ещё геморрой. Общей формулы, видимо, просто нет. Как говорил мне преподаватель, которому я помогаю вести лабы и который поручил мне провести эти лекции, есть решение в частном случае: для двух специально подобранных взаимно простых чисел. Вроде бы 2n-1 и 2n+1. Но я не вдавался в подробности.

Как-то g пришло в голову первым :)

[scavenger_spb]

Нормальная форма - это ты имеешь в виду обычные числа? Так тут накладка ;) Я могу взять любое число из класса эквивалентности... а это этого зависит результат. Да и возможно их несколько.

А вообще вещь занятная... немного поломал голову по этому поводу :)

[fat_crocodile]

Ты можешь взять любое, но зная его и значение pqg, можно вычислить минимальное. Всегда имеется ввиду именно минимальное.

Да, вещь немного "вскрывающая мозг". Позиционные системы счисления настолько привычны, что кажутся безальтернативными. Ну, тупые римляне не знали, но что с них взять... А тут -- такое.

[ran_dom]

Серж - а остатки от каких чисел предполагается использовать? точнее - сколько чисел предполагается использовать?
те если нам нужно представлять числа порядка 32 бит в двоичной позиционной, то можно использовать 2^16+1, 2^16-1.
перевод (и другие унарные) можно делать по таблице...

[fat_crocodile]

Можно и от двух.
Про таблицу я не понял, объясни.

[fat_crocodile]

Я, как обычно, демонстрирую идею :)
Время для неё уже солидно упущено, так что широкомасштабные практические реализации вряд ли будут. Но вот чтобы ложное ограничение о единственности и истинности позиционного представления не довлела в головах молодых инженеров...

[beroal]

Да, когда-то читал про арифметику вычетов. А теперь вот узнал, почему её не используют. :-) А ведь вычет от большого простого числа можно опять разложить на несколько вычетов, если уметь определять перенос, конечно.

[fat_crocodile]

Последнее предложение не понял...

[beroal]

Ну, например, числа от 0 до 32589158477190044729 (чуть больше 2^64) представляются списком вычетов mod 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53. Сложение вычетов mod 53 реализовано как традиционное бинарное сложение. Но вычет mod 53 можно разложить на mod 2, 5, 7 и распараллелить вычисления ещё раз. Или я чего-то не понял?

[fat_crocodile]

Ага, теперь понял :)

Да, эта мысль мне тоже приходила в голову, но действительно нужно как-то определить, когда вычет 53, записанный в виде вычетов 2/5/7 перейдёт через 53.

И как-то не понятно, как этого добиться. Из-за той же "распределённости", которая позволяет складывать по частям, всё вместе не собрать.