Пифагор

В мире нет ничего, кроме Красоты.
В Красоте нет ничего, кроме Формы.
В Форме нет ничего, кроме пропорций.
В пропорциях нет ничего, кроме Числа.

Пифагор

Непозиционные системы счисления

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

Научный форум → Математика → Дискуссионные темы (М)

Предыдущая тема :: Следующая тема
Автор	Сообщение
AndreyS Зарегистрирован: 23.06.2006 Сообщения: 15	Добавлено: Вт Дек 12, 2006 19:41:47    Заголовок сообщения: Непозиционные системы счисления, кроме СОК Просьба подсказать ссылки и поделиться знаниями о непозиционных системах счисления кроме СОК и Римской (и прочих древних разновидностей записи). Главное условие - чтобы эти системы счисления обладали какими-либо преимуществами для определенных операций над целыми числами по сравнению с другими системами счисления. Заметил, что часто начинают обсуждать вопрос зачем вообще надо изощряться тем или иным способом предлагаемом в теме для обсуждения. Я не готов отстаивать точку зрения полезности рассмотрения предлагаемой проблемы, по этому отвечу просто на этот вопрос: - Для нада З.Ы. Всякие факториальные, фибоначевы и другие в виде сумм подобных структур я отношу к позиционным.
Вернуться к началу
geomath Зарегистрирован: 15.11.2006 Сообщения: 694 Откуда: Дровишки? Из лесу, вестимо!	Добавлено: Чт Дек 14, 2006 16:13:58    Заголовок сообщения: Что такое СОК? _________________ Как же я устал от этой гонки! Не успеешь решить одну математическую проблему, как тут же не успеешь решить другую...
Вернуться к началу
AndreyS Зарегистрирован: 23.06.2006 Сообщения: 15	Добавлено: Чт Дек 14, 2006 20:16:25    Заголовок сообщения: geomath писал(а): Что такое СОК? Ну воот, начинается Я думал новенькое узнать, а приходится о стареньком рассказывать. СОК - это система остаточных классов. Обладает преимуществом в умножении и сложении (конкурирует с умножением с помощью быстрых преобразований фурье - в чем то даже лучше (долго объснять)) по сравнению с обычной позиционной системой счисления. Но имеет недостатки в делении и сравнении. Таким образом при умножение по модулю (что часто нужно во многих алгоритмах теории чисел) быстрые спец. модификации преобразований Фурье все-таки значительно быстрее. Но если нужно просто умножить, то цены ей нет, так как возможно распараллеливание и даже использование транспьютера, что заставляет БПФ отдыхать. Так что нетрадиционные переосмысливания основ могут привести к ряду замечательных и неочевидных сразу преимуществ. Вот интересно, есть ли еще такие замечательные вещи в виде других непозиционных систем счисления?
Вернуться к началу
maxal Модератор Зарегистрирован: 11.01.2006 Сообщения: 1554	Добавлено: Пт Дек 15, 2006 02:03:22    Заголовок сообщения: Смотря, что вы относите к непозиционным системам счисления. Например, фибоначчива, факториальная и биномиальная системы счисления. См. Система счисления в Википедии. Последний раз редактировалось: maxal (Пт Дек 15, 2006 02:13:38), всего редактировалось 1 раз
Вернуться к началу
RIP Активный участник Зарегистрирован: 11.01.2006 Сообщения: 1467 Откуда: отсюда	Добавлено: Пт Дек 15, 2006 02:09:34    Заголовок сообщения: AndreyS писал(а): З.Ы. Всякие факториальные, фибоначевы и другие в виде сумм подобных структур я отношу к позиционным. maxal писал(а): Смотря, что вы относите к непозиционным системам счисления. Например, фибоначчива и факториальная. _________________ Nobody is perfect. I'm nobody. RIP+LynxGAV
Вернуться к началу
maxal Модератор Зарегистрирован: 11.01.2006 Сообщения: 1554	Добавлено: Пт Дек 15, 2006 03:07:21    Заголовок сообщения: Не заметил ЗЫ. Другой пример: пусть - простые числа в их естественном порядке. Будем записывать как вектор где - неотрицательные целые числа, причем так что Согласно основной теореме арифметики, такое представление единственно, и формально является с.с. Понятно, что такое представление ускоряет умножение чисел, заменяя его сложением "цифр". На практике его варианты используются в алгоритмах index calculus, а также факторизации больших чисел.
Вернуться к началу
AndreyS Зарегистрирован: 23.06.2006 Сообщения: 15	Добавлено: Пт Дек 15, 2006 13:49:41    Заголовок сообщения: To maxal Да, формально это система счисления и очень известная так сказать со времен основной теоремы . Но, к сожалению, она не сильно ускоряет расчеты - даже обычное умножение произвольного числа. Тоесть умножаемые числа надо сначало либо факторизовать полностью (что при больших числах ....), а потом умножить, либо сразу умножить обычным способом. В чистом виде она даже не используется в алгоритмах факторизации. Вы видимо имели ввиду самый мощный на сегодняшний день алгоритм факторизации решета числового поля. Но даже там число пытаются представить в виде некоего максимально факторизованного числа в приведенном Вами виде произведений небольших простых чисел в соответствующих степенях плюс некоторое небольшое число (только так можно искать максимально факторизованный фрагмент суммы). А при прямом использовании этого выражения - произвольное число, а особенно фактор RSA, будет представлять из себя просто это простое число в первой степени либо практически нефакторизуемые произведения. Тоесть задача предварительной подготовки по сложности сопоставима с самой задачей умножения, если конечно теоретически не искать произведения в поле максимально факторизованных чисел с заданным множеством базисных простых чисел. То есть, приведенная Вами система записи через множители -практической реализации при умножении произвольного числа с заранее неизвестными факторами по быстроте не привосходит даже обычное умножение (ну если вдруг все факторы маленькими не окажутся). Спасибо что привели этот пример, так как для дискуссии он полезен и его модификация (плюс некоторое число к произведению) действительно позволяет построить многие полезные алгоритмы для обратных задач. Но я ищу системы счисления, которые позволяют действительно ускорить целочисленные вычисления с учетом времени предварительной подготовки числа. Например в СОК предварительная подготовка чисел делением по модулю практически мгновенна (деление, а особенно на малые числа значительно быстрее, чем умножение больших чисел). Далее можно умножить хоть миллион таких чисел, и достаточно быстро восстановить результат (умножение малых чисел (одно-двухразрядовых) на большие тоже быстро). Сложность будет пропорционально числу чисел и разряду чисел, что значительно быстрее обычного умножения и немного даже быстрее БПФ. А БПФ имеет еще и вероятность ошибки при заниженной точности вещественных коэффициентов, а здесь этого нет. Например числа Мерсенна давно ищуться при привышении предела вероятности для отсутствия ошибки умножения из-за округления коэффициентов преобразования (ограничения компьютера на разрядность при быстрых операциях с вещественными числами). Вероятность ошибки правда еще невелика, но как знать, может несколько чисел уже пропущено из-за этого. К сожалению СОК не может сменить БПФ при поиске чисел Мерсенна, так как там нужно умножение по модулю, а СОК в этом совсем не конкурент модифицированному БПФ. Так, что поиск продолжается.
Вернуться к началу
geomath Зарегистрирован: 15.11.2006 Сообщения: 694 Откуда: Дровишки? Из лесу, вестимо!	Добавлено: Пт Дек 15, 2006 17:20:31    Заголовок сообщения: Скажите, вот когда говорят о квантовых вычислениях, квантовом компьютере и т.п., то какую систему счисления имеют в виду? Тоже квантовую? Она позиционная? _________________ Как же я устал от этой гонки! Не успеешь решить одну математическую проблему, как тут же не успеешь решить другую...
Вернуться к началу
AlexDem Активный участник Зарегистрирован: 07.08.2006 Сообщения: 553 Откуда: Рыбинск-Москва	Добавлено: Пт Дек 15, 2006 18:06:29    Заголовок сообщения: geomath писал(а): Скажите, вот когда говорят о квантовых вычислениях, квантовом компьютере и т.п., то какую систему счисления имеют в виду? Тоже квантовую? Она позиционная? По-моему, к системе счисления это имеет довольно слабое отношение - что положишь в кубиты, то и возьмешь. Просто если в реальном компьютере в одно регистре может сидеть только одно число, например "1010 1100" или "1110 1011", то в квантовом все такие 8-битовые числа одновременно. Что-то принципы получения результата подзабыл - думаю, лучше будет Вам поискать в интернете, если нужно. Только вот не все уверены в том, что масштабируемый квантовый компьютер осуществим. Мне тоже так кажется, иначе придется принимать теорию мультиверса (множества вселенных), которой придерживается Пенроуз. _________________ Алексей
Вернуться к началу
AndreyS Зарегистрирован: 23.06.2006 Сообщения: 15	Добавлено: Пт Дек 15, 2006 18:08:07    Заголовок сообщения: Честно говоря, я не сильно интересовался деталями системы счисления в квантовых компьютерах. Там больше суть в когерентном возбуждении квантовой системы. Но возможности квантовых компьютеров сильно переоценены теми кто далек от практической реализации их. Дело в том, что математики пользуются некой математической идеальной моделью квантовой системы не учитывая даже некоторых принципиальных теоретических квантовых ограничений. А в реалии такой комп может быть построен на квантовых системах состояших не меньше чем атомы. Каждый вариант когерентной неопределенности должет иметь хоть сколько то носителей стат ансамбля. Если посчитать число этих носителей умножив на варианты, которые могут быть в некоторых задачах (в частности факторизации), то окажется что атомов и в солнечной системе не хватит для расчета некоторых задач (и как собрать такой комп?). Если же учесть, что квантовые системы имеют теоретическии диссипации, релаксанции, немгновенные корреляции, и релятивистские эффекты никто не отменял, а также запрет на безвозмущенный съем информации с части системы, то дела становятся еще хуже. А если еще учесть и другие неотъемлемые свойства реальных молекул или твердых тел и физ процессов, то дела уже становятся совсем плохо. В общем насколько я знаю сейчас еще кватновый компьютер не могут уверенно заставить умножить 3 на 5. Ну возможно я ошибаюсь в перспективах- детально вопрос не исследовал. В любом случае квантовый компьютер и особая система счисления для него практически не слишком интересна при современном развитии этого хозяйства в рамках темы этой ветки. Последний раз редактировалось: AndreyS (Пт Дек 15, 2006 18:46:46), всего редактировалось 1 раз
Вернуться к началу
geomath Зарегистрирован: 15.11.2006 Сообщения: 694 Откуда: Дровишки? Из лесу, вестимо!	Добавлено: Пт Дек 15, 2006 18:45:28    Заголовок сообщения: Я вот почему спросил про кванты. Не кажется ли вам, что когда в атоме по мере роста его номера электроны заполняют свои уровни и подуровни (см. табл. Менделеева), то при этом используется какая-то другая арифметика, с непривычной нам системой счисления? _________________ Как же я устал от этой гонки! Не успеешь решить одну математическую проблему, как тут же не успеешь решить другую...
Вернуться к началу
AlexDem Активный участник Зарегистрирован: 07.08.2006 Сообщения: 553 Откуда: Рыбинск-Москва	Добавлено: Пт Дек 15, 2006 18:47:31    Заголовок сообщения: geomath писал(а): см. табл. Менделеева Кстати, какую из них? Ту, по которой нас учили в школе или современную - у нее столбцов вроде не 8, а 16... _________________ Алексей
Вернуться к началу
AndreyS Зарегистрирован: 23.06.2006 Сообщения: 15	Добавлено: Пт Дек 15, 2006 18:55:59    Заголовок сообщения: Ну вот только Бога сюда осталось приплести Суть именно такого заполнения оболочек достаточна ясна из известных уравнений, принципа паули и свойств спина. В общем загадок уже не осталось в этом почти. Если пытаться как то использовать закономерности их заполнения приминив их как систему счисления в математическом плане, то ничего хорошего не получается. Более того, если даже применить магические числа из островков стабильности ядер то тоже ничего хорошего не получается Так что Бог в этом деле не помогает
Вернуться к началу
geomath Зарегистрирован: 15.11.2006 Сообщения: 694 Откуда: Дровишки? Из лесу, вестимо!	Добавлено: Пт Дек 15, 2006 19:07:53    Заголовок сообщения: А вы могли бы привести пример современной системы счисления, одновременно позиционной и непозиционной? _________________ Как же я устал от этой гонки! Не успеешь решить одну математическую проблему, как тут же не успеешь решить другую...
Вернуться к началу
AlexDem Активный участник Зарегистрирован: 07.08.2006 Сообщения: 553 Откуда: Рыбинск-Москва	Добавлено: Пт Дек 15, 2006 19:08:10    Заголовок сообщения: Боюсь, что AndreyS спрашивает не просто так - ему вроде быстрое умножение нужно. Вот он говорит, что подобная СС на электронах не подходит. Хотя, в принципе, это тоже СС, как, например, такая - в первом разряде может храниться 0 или 1, во втором - 0, 1, 2, в третьем - 0, 1, 2, 3, и т.д. geomath писал(а): А вы могли бы превести пример современной системы счисления, непозиционной, но и не позиционной? Вот я, вроде, и привел _________________ Алексей
Вернуться к началу
AndreyS Зарегистрирован: 23.06.2006 Сообщения: 15	Добавлено: Пт Дек 15, 2006 19:22:13    Заголовок сообщения: AlexDem писал(а): в первом разряде может храниться 0 или 1, во втором - 0, 1, 2, в третьем - 0, 1, 2, 3, и т.д. ...... Вот я, вроде, и привел Ага - это к примеру пример факториальной системы счисления будет Мне нужно быстрое умножение по модулю и быстрее (с учетом достаточной точности) чем БПФ, но не только это - есть и другие мотивы так сказать
Вернуться к началу
geomath Зарегистрирован: 15.11.2006 Сообщения: 694 Откуда: Дровишки? Из лесу, вестимо!	Добавлено: Пт Дек 15, 2006 19:27:22    Заголовок сообщения: Как думаете, связана ли форма десятичных цифр с арифметическими операциями? Например, случайно ли, что цифры 6 и 9 взаимно перевернутые, а цифра 8 симметричная? Если взять старый калькулятор, как у меня, где цифры состоят из палочек-черточек (из 7 максимум) и вывести на дисплей все десять цифр (а больше и не получается), то для этого потребуется 50 черточек (кстати, подсчитайте энтропию системы этих черточек). Из них 28 будут вертикальными, а 22 - горизонтальными, т.е. у этих черточек, если хотите, есть "спин". Спрашивается, можно ли установить какую-то систему преобразования этих черточек при арифметических операциях? А если нельзя, то можно ли так переделать форму привычных нам цифр, чтобы получить разумную систему в указанном смысле? _________________ Как же я устал от этой гонки! Не успеешь решить одну математическую проблему, как тут же не успеешь решить другую...
Вернуться к началу
geomath Зарегистрирован: 15.11.2006 Сообщения: 694 Откуда: Дровишки? Из лесу, вестимо!	Добавлено: Пн Дек 18, 2006 19:35:11    Заголовок сообщения: Чем вам не понравилась идея с цифрами из палочек? По-моему, классная. Тем более что древние китайцы частично реализовали ее. Ведь как-то же они считали! Известны системы счисления сильно избыточные (непозиционные) и слабо избыточные (позиционные). Китайцы, как всегда, оказались хитрее всех. Система счисления (десятичная) у них была с контролем четности: в нечетных разрядах использовались одни цифры, а в четных - другие. Цифры состояли из одинаковых палочек. Чтобы записать одновременно все цифры от 1 до 9 нечетного разряда, нужно было 29 палочек. Чтобы записать одновременно все цифры от 1 до 9 четного разряда, нужно было еще 29 палочек. Был у китайцев и ноль (маленький кружочек), индийский видимо. И если потратить на него, скажем, пару палочек, то всего нужно 60 палочек. (На калькуляторе, напомню, 50 палочек.) Можете попробовать решить маленькую задачку - выписать самостоятельно все китайские цифры. Но это то, что было вчера. Однако есть у меня идея и того, что будет завтра. К сожалению, насколько я понял, закоперщику темы нужно было сразу готовое решение. Поэтому до свидания. _________________ Как же я устал от этой гонки! Не успеешь решить одну математическую проблему, как тут же не успеешь решить другую...
Вернуться к началу
AlexDem Активный участник Зарегистрирован: 07.08.2006 Сообщения: 553 Откуда: Рыбинск-Москва	Добавлено: Пн Дек 18, 2006 20:04:54    Заголовок сообщения: geomath писал(а): Как думаете, связана ли форма десятичных цифр с арифметическими операциями? Например, случайно ли, что цифры 6 и 9 взаимно перевернутые, а цифра 8 симметричная? С моей точки зрения, конкретное начертание цифр, их энтропия как знаков не связаны с арифметическими действиями по крайней мере в позиционной СС. Ту же восьмерку мы с Вами пишем (и произносим) немного по-разному, формально это разные знаки, но мы оба вкладываем в них один и тот же смысл, поэтому получаем одинаковый результат. geomath писал(а): Чем вам не понравилась идея с цифрами из палочек? По-моему, Ваши замечания интересны в том смысле, что дают повод подумать в несколько ином направлении. Но это прежде всего должно быть интересно автору ветки... _________________ Алексей
Вернуться к началу
нг Супермодератор Зарегистрирован: 30.11.2006 Сообщения: 1000	Добавлено: Пн Дек 18, 2006 20:34:37    Заголовок сообщения:  !  нг: geomath писал(а): Чем вам не понравилась идея с цифрами из палочек? Не занимайтесь захватом темы. Откройте свою. Если попросите ЛС — я скопирую Ваши сообщения в отдельную тему. А здесь давайте рассматривать как флуд.
Вернуться к началу
AndreyS Зарегистрирован: 23.06.2006 Сообщения: 15	Добавлено: Пн Дек 18, 2006 21:04:24    Заголовок сообщения: geomath писал(а): Однако есть у меня идея и того, что будет завтра. К сожалению, насколько я понял, закоперщику темы нужно было сразу готовое решение. Ну я как "закаперщик" (ну и названьеце ) темы имею сказать следующие. Лично меня неуниверсальные задачи не интересуют вообще и в принципе. Что я понимаю под универсальными. Это если наши братья или небратья по разуму могут прийти к такой же проблеме независимо. Вот простые числа универсальны, факторизация универсальна и т.д. А вот начертания наших цифр сугубо наше индивидуальное. Так, что энтропия начертания арабско (индийских) цифр меня мало интересует. Вот если использовать более новую формулировку geomath о создании новых форм обозначения цифр, чтобы после действий над ними появились новые дополнительные наглядные признаки правильности вычислений и/или свойств чисел, то считаю эту тему достойной и в некотором смысле универсальной. Но так как это лежит (на первый и второй взгляд) в стороне от ускорения разного рода вычислений с помощью нестандартных (вероятнее непозиционных) систем счисления, то для этого можно сроздать отдельную ветку.
Вернуться к началу
maxal Модератор Зарегистрирован: 11.01.2006 Сообщения: 1554	Добавлено: Ср Дек 20, 2006 14:24:07    Заголовок сообщения: AndreyS писал(а): Но, к сожалению, она не сильно ускоряет расчеты - даже обычное умножение произвольного числа. Тоесть умножаемые числа надо сначало либо факторизовать полностью (что при больших числах ....), а потом умножить, либо сразу умножить обычным способом. В чистом виде она даже не используется в алгоритмах факторизации. Еще как используется. Например, многие алгоритмы факторизации (вплоть до моднючего NFS, хотя там все сложнее) основаны на идее поиска соотношения из которого при легко получить нетривиальный делитель Обычно выбирается базовое число и числа типа пытаются разложить по простым не превосходящим Если это удается, то число считается "хорошим" (-гладким) и его разложение ("цифры") запоминается как строка некоторой матрицы (с количеством столбцов равным - количеству простых чисел не превосходящих ). После того как накоплено достаточное количество строк матрица рассматривается над полем (т.е. все "цифры" разложения берутся по модулю 2) и с помощью алгоритмов линейной алгебры в ней ищется линейная комбинация строк, дающая нулевой вектор. Эта же комбинация в исходной матрице дает вектор, все компоненты которого четные, а значит он соответствует некоторому квадрату Это правая часть искомого соотношения, а в левой части стоит произведение тех для которых строки их цифр участвуют в линейной комбинации дающей Примерно так это и работает в алгоритмах факторизации.
Вернуться к началу
AndreyS Зарегистрирован: 23.06.2006 Сообщения: 15	Добавлено: Чт Дек 21, 2006 13:42:09    Заголовок сообщения: To maxal Ну так NFS и есть Number Field Sieve (решето числового поля) о котором я писал в прошлом посте. Ну я написал, что в чистом виде не используется такая система счисления (как именно счисления), но я не сказал что она вообще не используется для факторизации. А под расчетами я имел ввиду прямую задачу типа умножения. Впрочем, это вопрос совсем не важной в данном случае терминологии. По существу Вы правы - нестандартная форма представления числа (в частности такого вида) позволяет получить новые и мощные методы расчета. Более того, именно для обсуждения этого я ветку и создавал. Так, что спасибо за расширение дискуссии. По большому счету основная идея в том, что переосмысления основ и разные нестандартные способы представления чисел позволяют сильно упросить некоторые методы расчета и построить мощные алгориты для извечных задач. В частности, СОК позволяет намного быстрее умножать по сравнению с обычной системой. Факториальная - имеет больше признаков деления на простые сомножители. Поиск чисел в высокофакторизованном виде с использованием факторной системы (назовем так) позволяет построить наиболее мощный алгоритм факторизации. В общем есть намек, что двигаясь в этом напралении наверное можно еще более продвинуться в скорости расчетов и решении разных обратных задач типа факторизации. Вот поиску таких новых представлений чисел этот топик по большому счету я и задумывал. Сначала было просто желание найти еще одну непозиционную систему счисления обладающую преимуществами для определенных операций над числами. В частности была тайная мысль, что фактоизация в другой системе может стать меньшей проблемой. К сожалению, в СОК проблема факторизации даже сложнее выглядит, чем обычно. NFS уже практически выжал все из представления числа в факторизованном виде. В общем предлагаю продолжить поиск. Почему я предлагаю искать непозиционные системы. Ну потому, что это нечто большее, чем просто система счисления. По большому счету (смотря на СОК) это некая серия преобразований числа приводящая к некоторому набору (серии) "разрядов". Основное свойство этих "разрядов" в том, что с помощью гораздой меньшей (чем в позиционных) комбинации действий "разрядов" одного числа с "разрядами" другого мы получаем и восстанавливаем результат. Таким образом стоит поискать еще и другие замечательные пребразования обладающие подобными свойствами, но в поле целых чисел, так как в принципе и БПФ умножение можно в некотором смысле сюда отнести, если бы не его примерность (использование действительных чисел) и невозможность поставить обратную задачу факторизовать число в его рамках. Надеюсь, что СОК не идинственно возможный пример такого вида. А может и единственный - кто знает.