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