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

[AndreyS]

AlexDem писал(а):

в первом разряде может храниться 0 или 1, во втором - 0, 1, 2, в третьем - 0, 1, 2, 3, и т.д. ...... Вот я, вроде, и привел

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

[geomath]

Как думаете, связана ли форма десятичных цифр с арифметическими операциями? Например, случайно ли, что цифры 6 и 9 взаимно перевернутые, а цифра 8 симметричная?

Если взять старый калькулятор, как у меня, где цифры состоят из палочек-черточек (из 7 максимум) и вывести на дисплей все десять цифр (а больше и не получается), то для этого потребуется 50 черточек (кстати, подсчитайте энтропию системы этих черточек). Из них 28 будут вертикальными, а 22 - горизонтальными, т.е. у этих черточек, если хотите, есть "спин". Спрашивается, можно ли установить какую-то систему преобразования этих черточек при арифметических операциях? А если нельзя, то можно ли так переделать форму привычных нам цифр, чтобы получить разумную систему в указанном смысле?

[geomath]

Чем вам не понравилась идея с цифрами из палочек? По-моему, классная. Тем более что древние китайцы частично реализовали ее. Ведь как-то же они считали!

Известны системы счисления сильно избыточные (непозиционные) и слабо избыточные (позиционные). Китайцы, как всегда, оказались хитрее всех. Система счисления (десятичная) у них была с контролем четности: в нечетных разрядах использовались одни цифры, а в четных - другие. Цифры состояли из одинаковых палочек. Чтобы записать одновременно все цифры от 1 до 9 нечетного разряда, нужно было 29 палочек. Чтобы записать одновременно все цифры от 1 до 9 четного разряда, нужно было еще 29 палочек. Был у китайцев и ноль (маленький кружочек), индийский видимо. И если потратить на него, скажем, пару палочек, то всего нужно 60 палочек. (На калькуляторе, напомню, 50 палочек.) Можете попробовать решить маленькую задачку - выписать самостоятельно все китайские цифры.

Но это то, что было вчера. Однако есть у меня идея и того, что будет завтра. К сожалению, насколько я понял, закоперщику темы нужно было сразу готовое решение. Поэтому до свидания.

[AlexDem]

geomath писал(а):

Как думаете, связана ли форма десятичных цифр с арифметическими операциями? Например, случайно ли, что цифры 6 и 9 взаимно перевернутые, а цифра 8 симметричная?

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

geomath писал(а):

Чем вам не понравилась идея с цифрами из палочек?

По-моему, Ваши замечания интересны в том смысле, что дают повод подумать в несколько ином направлении. Но это прежде всего должно быть интересно автору ветки...

[нг]

нг:

geomath писал(а):

Чем вам не понравилась идея с цифрами из палочек?

Не занимайтесь захватом темы. Откройте свою. Если попросите ЛС — я скопирую Ваши сообщения в отдельную тему. А здесь давайте рассматривать как флуд.

[AndreyS]

geomath писал(а):

Однако есть у меня идея и того, что будет завтра. К сожалению, насколько я понял, закоперщику темы нужно было сразу готовое решение.

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

[maxal]

AndreyS писал(а):

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

Еще как используется.
Например, многие алгоритмы факторизации (вплоть до моднючего NFS, хотя там все сложнее) основаны на идее поиска соотношения $X^2\equiv Y^2\pmod{n},$ из которого при $X\ne\pm Y$ легко получить нетривиальный делитель $n.$
Обычно выбирается базовое число $B,$ и числа типа $X^2\bmod n$ пытаются разложить по простым не превосходящим $B.$ Если это удается, то число считается "хорошим" ($B$-гладким) и его разложение ("цифры") запоминается как строка некоторой матрицы (с количеством столбцов равным $\pi(B)$ - количеству простых чисел не превосходящих $B$). После того как накоплено достаточное количество строк матрица рассматривается над полем $F_2$ (т.е. все "цифры" разложения берутся по модулю 2) и с помощью алгоритмов линейной алгебры в ней ищется линейная комбинация строк, дающая нулевой вектор. Эта же комбинация в исходной матрице дает вектор, все компоненты которого четные, а значит он соответствует некоторому квадрату $Y^2.$ Это правая часть искомого соотношения, а в левой части стоит произведение тех $X^2,$ для которых строки их цифр участвуют в линейной комбинации дающей $Y.$ Примерно так это и работает в алгоритмах факторизации.

[AndreyS]

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

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