Остаточные классы
Продолжаем выковыривать изюм из лекций. Самое красивое, интересное, бесполезное :) В этот раз речь про очень простой, очень красивый и неожиданный способ представления чисел, подававший большие надежды где-то в 60-х, но благополучно померший впоследствии: не смогли преодолеть критический недостаток. Но сама идея!
А идея такая:
5 * 7 * 9 = 315
42 --> 42 mod 5 / 42 mod 7 / 42 mod 9 = 2 / 0 / 6
126 --> 128 mod 5 / 128 mod 7 / 128 mod 9 = 3 / 2 / 2
На виндовом калькуляторе в "инженерном" режиме есть кнопка Mod, это оно.
Теперь вспоминаем свойства остатков:
(a + b) mod c = ([a mod c] + [b mod c]) mod c
(a * b) mod c = ([a mod c] * [b mod c]) mod c
то есть, сложение, вычитание, умножение можно производить по частям.
2 / 0 / 6 + 3 / 2 / 2 = 0 / 2 / 8
128 + 42 = 170 --> 170 mod 5 / 170 mod 7 / 170 mod 9 = 0 / 2 / 8 -- всё правильно
Для того, чтобы понять, почему это круто, нужно немного понимать как работают железки и немного знать, как устроены сумматоры и умножители. Именно для этого был написан предыдущий пост :)
Про умножители там ничего нет, но с ними всё так же, только гораздо хуже, в подробности вдаваться не будем.
Какие из него можно сделать выводы:
Но... К сожалению, операция деления за разумное время не реализуется, никак. И перевести число из вида a/b/c в какой-нибудь "обычный" -- очень сложно. А без этого использовать такие числа вряд ли кто-нибудь когда-нибудь будет. Вот так вот.
Upd: В обсуждении всплыло. Так же непонятно, как делать сравнение больше-меньше и проверку на переполнение при сложении/умножении.
А идея такая:
- берём несколько взаимно простых чисел, для конкретности пусть их будет 3: p, q, g
- для любого числа x можно вычислить тройку остатков от деления: [x mod p], [x mod q], [x mod g]
- так как числа взаимно простые, остатки независимы, т.е. любому остатку от деления на p может соответствовать любой остаток от деления на q. Значит таких троек ровно pqg штук
- так как иксов от 0 до pqg (включая 0, исключая pqg) столько же, то более-менее понятно, что разным x в этом диапазоне соответствуют разные тройки. Т.е. можно установить взаимно-однозначное соответствие, а значит можно использовать тройку остатков для представления числа x.
5 * 7 * 9 = 315
42 --> 42 mod 5 / 42 mod 7 / 42 mod 9 = 2 / 0 / 6
126 --> 128 mod 5 / 128 mod 7 / 128 mod 9 = 3 / 2 / 2
На виндовом калькуляторе в "инженерном" режиме есть кнопка Mod, это оно.
Теперь вспоминаем свойства остатков:
(a + b) mod c = ([a mod c] + [b mod c]) mod c
(a * b) mod c = ([a mod c] * [b mod c]) mod c
то есть, сложение, вычитание, умножение можно производить по частям.
2 / 0 / 6 + 3 / 2 / 2 = 0 / 2 / 8
128 + 42 = 170 --> 170 mod 5 / 170 mod 7 / 170 mod 9 = 0 / 2 / 8 -- всё правильно
Для того, чтобы понять, почему это круто, нужно немного понимать как работают железки и немного знать, как устроены сумматоры и умножители. Именно для этого был написан предыдущий пост :)
Про умножители там ничего нет, но с ними всё так же, только гораздо хуже, в подробности вдаваться не будем.
Какие из него можно сделать выводы:
- Железо по своей природе работает параллельно, независимые части выполняются одновременно. Применительно к нашему случаю: все три остатка можно складывать/умножать одновременно.
- Чем меньше разрядов, тем быстрее сложение и умножение. Так как каждый остаток примерно в три раза короче "нормального" числа, сложение/умножение займёт примерно в три раза меньше времени.
Но... К сожалению, операция деления за разумное время не реализуется, никак. И перевести число из вида a/b/c в какой-нибудь "обычный" -- очень сложно. А без этого использовать такие числа вряд ли кто-нибудь когда-нибудь будет. Вот так вот.
Upd: В обсуждении всплыло. Так же непонятно, как делать сравнение больше-меньше и проверку на переполнение при сложении/умножении.