Comments 39
В школе был шокирован этой системой. Кстати по-русски она называется Система Остаточных Классов (СОК). И опять же в школе говорили что электроника основанная на СОК использовалась в системе наведения какой-то ракеты.
Спасибо, добавил во введение наиболее распрастраненное в русском языке название.
Через 10 лет в школе уже этого не было, а жаль.
UFO just landed and posted this here
Жаль, что сейчас к модулярной арифметике в основном академический интерес. Компьютеры, работающие в СОК — , СуперЭВМ 41-50, «Лидер». Также советские ученые, внесшие огромнейший вклад по сабжу — Акушский и Юдицкий. Спасибо огромнейшее за статью, очень интересно, в свое время начал писать диссертацию по производной от этой, теме, но потом решил уйти из аспирантуры.
мне одному кажется, что я ничего не понял?
А какая практическая польза от этой системы, кроме доказательства делимости? Есть ли применение?
Переводишь данные из позиционного представления в модулярный вид и можно параллельно делать быстрые арифметически операции на маленьких числах.
Допустим умножение двух 32-битных чисел заменяется параллельным умножением 8-ми 5-битных чисел. Умножение мелких чисел вообще можно делать табличным способом, если площадь на кристалле не критична.
Допустим умножение двух 32-битных чисел заменяется параллельным умножением 8-ми 5-битных чисел. Умножение мелких чисел вообще можно делать табличным способом, если площадь на кристалле не критична.
Особенно с учетом того что операции независимы по данным (нет переноса между разрядами). Поэтому это очень хорошо можно параллелить на кристалле.
А еще Китайская теорема об остатках используется для быстрой дешифрации шифртекстов в алгоритме RSA.
UFO just landed and posted this here
А про реализацию чисел с плавающей точкой(запятой) что-нибудь есть? Например, каково будет их распределение на числовой прямой? Хотя, собственно, это единственный вопрос, все остальные фокусы будут зависеть от ответа на него :)
Смущает то, что хранение числа в остатках занимает больше памяти, чем хранение в двоичном виде. Да еще и для хранения каждого остатка требуется различное число бит.
Другой недостаток — позиционная система может представлять бесконечно большие числа. А система с остатками — нет. Да к тому же и сами основания можно выбирать произвольно, а это значит что может быть несовместимость с другими девайсами.
В общем, для сугубо специализированных устройств может эта система и имеет преимущества, но для универсальных устройств — наврядли подходит.
Другой недостаток — позиционная система может представлять бесконечно большие числа. А система с остатками — нет. Да к тому же и сами основания можно выбирать произвольно, а это значит что может быть несовместимость с другими девайсами.
В общем, для сугубо специализированных устройств может эта система и имеет преимущества, но для универсальных устройств — наврядли подходит.
UFO just landed and posted this here
>На счет бесконечных чисел вообще не понял. Вы про числа с плавающей запятой? Ну так то отдельная история.
Для представления произвольного числа в СОК требуется набор простых чисел. Но этот набор в общем случае неизвестен, поскольку неизвестны все простые числа и нет формулы для их вычисления. Поэтому нельзя говорить, что в СОК представимы все числа.
Ну это я немного занудствую конечно, потому что на практике известно достаточно большое количество простых чисел, тем не менее… :)
>Для совместимости устройств есть достаточно быстрое прямое и обратное преобразование в двоичные числа.
Оно то да, только это не удобно. Кроме того теряется такое преимущество как помехоустойчивость.
Для представления произвольного числа в СОК требуется набор простых чисел. Но этот набор в общем случае неизвестен, поскольку неизвестны все простые числа и нет формулы для их вычисления. Поэтому нельзя говорить, что в СОК представимы все числа.
Ну это я немного занудствую конечно, потому что на практике известно достаточно большое количество простых чисел, тем не менее… :)
>Для совместимости устройств есть достаточно быстрое прямое и обратное преобразование в двоичные числа.
Оно то да, только это не удобно. Кроме того теряется такое преимущество как помехоустойчивость.
Позиционная система в электронике давным давно уже ограничена сверху. Вы часто писали программы для манипулирования целыми числами больше 32 или 64 бит?
Выглядит как редкостное извращение. Для того, чтобы воспринять его серьёзно, хотелось бы практического доказательства.
Условно говоря: конструируем виртуальный процессор с подобием ARM архитектуры и вот это чудо. Запускаем на симуляторе, запускаем код (допустим, что-то похожее на жизнь, т.е., например, получение и декодирование видео), смотрим, у кого выше энергопотребление (дальше долгий флуд и оптимизация, а на выходе таки ответ).
Условно говоря: конструируем виртуальный процессор с подобием ARM архитектуры и вот это чудо. Запускаем на симуляторе, запускаем код (допустим, что-то похожее на жизнь, т.е., например, получение и декодирование видео), смотрим, у кого выше энергопотребление (дальше долгий флуд и оптимизация, а на выходе таки ответ).
Ну как пример в этой статье, приводятся графики потребления энергии:
http://www2.imm.dtu.dk/~an/pubs/asil07b.pdf
Вообще очень часто модулярная арифметика применяется в специализированных DSP, где главное это скорость работы.
http://www2.imm.dtu.dk/~an/pubs/asil07b.pdf
Вообще очень часто модулярная арифметика применяется в специализированных DSP, где главное это скорость работы.
Сначала не понял, потом перечитал — классная идея, понятно что ТСР не сделают на ней в ближайжшее время, но красиво, блин!
По поводу оформления:
статья про математику, поэтому лучше использовать формулы, ( mod вместо %, dot вместо *)
ссылки на вики. (теорема остатка, операция modulu)
По поводу оформления:
статья про математику, поэтому лучше использовать формулы, ( mod вместо %, dot вместо *)
ссылки на вики. (теорема остатка, операция modulu)
Сам занимаюсь соком и его применением. В кратце скажу чего нет в статье, но это очень интересно с моей точки зрения:
1. Модель вычисления в СОК очень близка к модели нейрона, поэтому удобно строить вычислительные нейросети работающие в СОК.
2. Один из главных плюсов это возможность работы с очень большими числами, которые не помещаются в память машины.
1. Модель вычисления в СОК очень близка к модели нейрона, поэтому удобно строить вычислительные нейросети работающие в СОК.
2. Один из главных плюсов это возможность работы с очень большими числами, которые не помещаются в память машины.
В детстве, году так в 1996-1997, когда познакомился с СОК писал на Basic для Спектрума реализацию быстрого вычисления факториалов (длинная арифметика) и возведения в степени. Считать получалось гораздо быстрее, чем использовать строку или массив. Была книжка детская о Basic, там и познакомился с такой системой. Жаль исходники потеряны…
Sign up to leave a comment.
Введение в модулярную арифметику