Непозиционные системы счисления, кроме СОК

[AndreyS]

Просьба подсказать ссылки и поделиться знаниями о непозиционных системах
счисления кроме СОК и Римской (и прочих древних разновидностей записи).

Главное условие - чтобы эти системы счисления обладали какими-либо преимуществами
для определенных операций над целыми числами по сравнению с другими системами счисления.

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

З.Ы.
Всякие факториальные, фибоначевы и другие в виде сумм подобных структур
я отношу к позиционным.

[geomath]

Что такое СОК?

[AndreyS]

geomath писал(а):

Что такое СОК?

Ну воот, начинается Я думал новенькое узнать, а приходится о стареньком
рассказывать.
СОК - это система остаточных классов.
Обладает преимуществом в умножении и сложении (конкурирует с умножением с помощью
быстрых преобразований фурье - в чем то даже лучше (долго объснять)) по сравнению с обычной
позиционной системой счисления. Но имеет недостатки в делении и сравнении. Таким образом при
умножение по модулю (что часто нужно во многих алгоритмах теории чисел) быстрые спец. модификации
преобразований Фурье все-таки значительно быстрее. Но если нужно просто умножить, то
цены ей нет, так как возможно распараллеливание и даже использование транспьютера,
что заставляет БПФ отдыхать. Так что нетрадиционные переосмысливания основ могут
привести к ряду замечательных и неочевидных сразу преимуществ.
Вот интересно, есть ли еще такие замечательные вещи в виде других непозиционных
систем счисления?

[maxal]

Смотря, что вы относите к непозиционным системам счисления.
Например, фибоначчива, факториальная и биномиальная системы счисления.

См. Система счисления в Википедии.

[RIP]

AndreyS писал(а):

З.Ы.
Всякие факториальные, фибоначевы и другие в виде сумм подобных структур
я отношу к позиционным.

maxal писал(а):

Смотря, что вы относите к непозиционным системам счисления.
Например, фибоначчива и факториальная.

[maxal]

Не заметил ЗЫ.

Другой пример:

пусть $p_1=2, p_2=3, \dots, p_k, \dots$ - простые числа в их естественном порядке.
Будем записывать $n$ как вектор $(d_1,\dots,d_m),$ где $d_i$ - неотрицательные целые числа, причем $d_m>0,$ так что $n=\prod_{i=1}^m p_i^{d_i}.$ Согласно основной теореме арифметики, такое представление единственно, и формально является с.с.

Понятно, что такое представление ускоряет умножение чисел, заменяя его сложением "цифр". На практике его варианты используются в алгоритмах index calculus, а также факторизации больших чисел.

[AndreyS]

To maxal
Да, формально это система счисления и очень известная так сказать
со времен основной теоремы .

Но, к сожалению, она не сильно ускоряет расчеты - даже обычное умножение произвольного числа.
Тоесть умножаемые числа надо сначало либо факторизовать полностью (что при
больших числах ....), а потом умножить, либо сразу умножить обычным
способом.
В чистом виде она даже не используется в алгоритмах факторизации.
Вы видимо имели ввиду самый мощный на сегодняшний день алгоритм
факторизации решета числового поля. Но даже там число пытаются
представить в виде некоего максимально факторизованного числа в приведенном
Вами виде произведений небольших простых чисел в соответствующих степенях плюс
некоторое небольшое число (только так можно искать максимально факторизованный
фрагмент суммы). А при прямом использовании этого выражения - произвольное число,
а особенно фактор RSA, будет представлять из себя просто это простое число в первой степени
либо практически нефакторизуемые произведения. Тоесть задача предварительной
подготовки по сложности сопоставима с самой задачей умножения, если конечно теоретически не
искать произведения в поле максимально факторизованных чисел с заданным
множеством базисных простых чисел. То есть, приведенная Вами система записи через множители
-практической реализации при умножении произвольного числа с заранее неизвестными факторами
по быстроте не привосходит даже обычное умножение (ну если вдруг все факторы маленькими
не окажутся).

Спасибо что привели этот пример, так как для дискуссии он полезен и
его модификация (плюс некоторое число к произведению) действительно позволяет
построить многие полезные алгоритмы для обратных задач.

Но я ищу системы счисления, которые позволяют действительно ускорить
целочисленные вычисления с учетом времени предварительной подготовки числа.

Например в СОК предварительная подготовка чисел делением по модулю практически
мгновенна (деление, а особенно на малые числа значительно быстрее, чем умножение больших
чисел). Далее можно умножить хоть миллион таких чисел, и достаточно быстро
восстановить результат (умножение малых чисел (одно-двухразрядовых) на большие тоже быстро). Сложность будет
пропорционально числу чисел и разряду чисел, что значительно быстрее обычного умножения и
немного даже быстрее БПФ. А БПФ имеет еще и вероятность ошибки при заниженной точности
вещественных коэффициентов, а здесь этого нет. Например числа Мерсенна давно ищуться
при привышении предела вероятности для отсутствия ошибки умножения из-за округления коэффициентов
преобразования (ограничения компьютера на разрядность при быстрых операциях с вещественными числами). Вероятность
ошибки правда еще невелика, но как знать, может несколько чисел уже пропущено из-за этого.
К сожалению СОК не может сменить БПФ при поиске чисел Мерсенна, так как там нужно умножение по
модулю, а СОК в этом совсем не конкурент модифицированному БПФ.


Так, что поиск продолжается.

[geomath]

Скажите, вот когда говорят о квантовых вычислениях, квантовом компьютере и т.п., то какую систему счисления имеют в виду? Тоже квантовую? Она позиционная?

[AlexDem]

geomath писал(а):

Скажите, вот когда говорят о квантовых вычислениях, квантовом компьютере и т.п., то какую систему счисления имеют в виду? Тоже квантовую? Она позиционная?

По-моему, к системе счисления это имеет довольно слабое отношение - что положишь в кубиты, то и возьмешь. Просто если в реальном компьютере в одно регистре может сидеть только одно число, например "1010 1100" или "1110 1011", то в квантовом все такие 8-битовые числа одновременно. Что-то принципы получения результата подзабыл - думаю, лучше будет Вам поискать в интернете, если нужно. Только вот не все уверены в том, что масштабируемый квантовый компьютер осуществим. Мне тоже так кажется, иначе придется принимать теорию мультиверса (множества вселенных), которой придерживается Пенроуз.

[AndreyS]

Честно говоря, я не сильно интересовался деталями системы счисления в квантовых
компьютерах. Там больше суть в когерентном возбуждении квантовой системы.
Но возможности квантовых компьютеров сильно переоценены теми кто далек
от практической реализации их. Дело в том, что математики пользуются
некой математической идеальной моделью квантовой системы не учитывая
даже некоторых принципиальных теоретических квантовых ограничений.
А в реалии такой комп может быть построен на квантовых системах состояших не
меньше чем атомы. Каждый вариант когерентной неопределенности должет
иметь хоть сколько то носителей стат ансамбля. Если посчитать
число этих носителей умножив на варианты, которые могут быть в некоторых
задачах (в частности факторизации), то окажется что атомов и в солнечной
системе не хватит для расчета некоторых задач (и как собрать такой комп?). Если же
учесть, что квантовые системы имеют теоретическии диссипации, релаксанции, немгновенные корреляции, и
релятивистские эффекты никто не отменял, а также запрет на безвозмущенный съем информации
с части системы, то дела становятся еще хуже. А если еще учесть и другие неотъемлемые
свойства реальных молекул или твердых тел и физ процессов, то дела уже становятся совсем плохо. В общем
насколько я знаю сейчас еще кватновый компьютер не могут уверенно заставить умножить 3 на 5.
Ну возможно я ошибаюсь в перспективах- детально вопрос не исследовал.

В любом случае квантовый компьютер и особая система счисления для него
практически не слишком интересна при современном развитии этого хозяйства
в рамках темы этой ветки.

[geomath]

Я вот почему спросил про кванты. Не кажется ли вам, что когда в атоме по мере роста его номера электроны заполняют свои уровни и подуровни (см. табл. Менделеева), то при этом используется какая-то другая арифметика, с непривычной нам системой счисления?

[AlexDem]

geomath писал(а):

см. табл. Менделеева

Кстати, какую из них? Ту, по которой нас учили в школе или современную - у нее столбцов вроде не 8, а 16...

[AndreyS]

Ну вот только Бога сюда осталось приплести
Суть именно такого заполнения оболочек достаточна ясна из известных уравнений, принципа
паули и свойств спина. В общем загадок уже не осталось в этом почти.
Если пытаться как то использовать закономерности их заполнения приминив их
как систему счисления в математическом плане, то ничего хорошего не получается.
Более того, если даже применить магические числа из островков стабильности
ядер то тоже ничего хорошего не получается

Так что Бог в этом деле не помогает

[geomath]

А вы могли бы привести пример современной системы счисления, одновременно позиционной и непозиционной?

[AlexDem]

Боюсь, что AndreyS спрашивает не просто так - ему вроде быстрое умножение нужно. Вот он говорит, что подобная СС на электронах не подходит. Хотя, в принципе, это тоже СС, как, например, такая - в первом разряде может храниться 0 или 1, во втором - 0, 1, 2, в третьем - 0, 1, 2, 3, и т.д.

geomath писал(а):

А вы могли бы превести пример современной системы счисления, непозиционной, но и не позиционной?

Вот я, вроде, и привел