Comments 54
1) Спускаем всё вниз
2) Нормализуем последний ряд
3) Повторяем 1-2 пока не зайдём в тупик
4) Денормализуем самую правую единицу во втором снизу ряду
5) Повторяем 1-2-3-4 пока не завершим.
Вдумался в тег «курить бамбук нагибая дубы».
«Далее по тексту я иногда буду называть её фиеричной (по аналогии с, допустим, восьмеричной) системой счисления, а иногда не буду.»
Просто вместо цифры название буквы подставил и все, как капитан выше подсказывает
для обозначения золотого сечения принято использовать малую фи, а не заглавную
Я вырос на обозначениях, где фи малое — это величина, обратная к фи большому, т.е. как в википедии.
А факт действительно крутой, мне он был неизвестен, и я сходу не могу сообразить, как этого можно добиться. Не поделитесь ссылкой?
- Гуглить по слову beta-expansion
- Серия статей за авторством Ch. Frougny, E. Pelantova, M. Svobodova, например, "Parallel addition in non-standard numeration systems"
- По-русски могу предложить свою статью http://psta.psiras.ru/read/psta2015_2_101-117.pdf (в статье ошибка, из-за которой всё заявленное работает только для рациональных оснований). В любом случае там будет полезна обзорная часть.
Спасибо за информацию, помещу ссылку на ваш комментарий в статью.
Хм, вообще-то, если я правильно помню, организовать параллельное сложение можно и с двумя цифрами {0,1}, главное, чтобы основание было меньше 2. Общее утверждение таково, что для существования поразрядного паралеллизма достаточно: (1) количество цифр (0, 1, ...) должно быть больше, чем основание, (2) основание должно быть алгебраическим числом (это требуется только для "точных" представлений, для интервальных вроде не обязательно) и (3) довольно причудливое условие на алгебраические сопряженные основания, которое для фи выполнено.
Ага, спасибо.
Фиеричная
Каждый раз при прочтении этого слова рука моего внутреннего граммар-наци тянется к расстрельному "вальтеру", но в следующую секунду опускается обратно ;)
Цимес в том, что приведённая формула, если рассматривать её как уравнение, имеет единственное действительное решение.
Прочитав это, мой внутренний хакер немедленно встрепенулся и задал вопрос — "раз есть действительное решение — значит, должно быть и комплексное, нельзя ли его как-нибудь в хозяйстве применить?"
Я хотел написать, что чтобы получить возможность записи комплексных чисел нужно добавить ещё i и -i, но по здравому размышлению это неудачная идея.
Ну есть проблема, что количество цифр в действительных числах будет расти квадратично от количества чисел в обычной системе, но для каких-то задач может оказаться полезно. Кажется, у Кнута на эту тему статьи были. Еще можно не числа, а матрицы использовать, тоже интересно получается.
Почему квадратично? Навскидку кажется, что в константу раз (примерно вдвое).
То же количество цифр описывает не отрезок на прямой, а квадрат на плоскости. Соответственно, отрезок получается короче.
Но это значит, что количество отсчётов (представимых значений) растет квадратично. А количество цифр зааисит от него логарифмически.
Хабр — торт!
Нужно будет запомнить. Хороший эвфемизм для выражения «до х#я»
Ведь такая система счисления тоже должна как-то называться.
Не пойму, как так получается. В двоичной системе счисления две цифры, в троичной — три, в шестнадцатеричной — шестнадцать. Это мне понятно, и вроде этому меня и учили. А тут, мало того, что должно быть 1,62 цифры, так еще и левые цифры (-1) вводятся. Никто не пробовал вводить дробные цифры в десятичную, например? Получились бы прикольные штуки, типа, 7'36, где цифра 7' — это 7,5. Или даже (7 + 1/e).
Кто-нибудь тут может объяснить, как эти "ненатуральные" системы работают?
По своей сути наша запись — апроксимация(приближение), означающая, что мы описываем число, которое: больше некоторого A, но меньше или равно некоторому B, которые выразимы в наших числах, и на систему счисления должны быт наложены ограничения: минимализм(все числа вызаримы только одним образом, например, если -0 и 0 есть в системе — это дефект), адитивность( все представимые числа можно собрать через сложение, ваша система не удовлетворяет этому условию, сумма двух иррациональных чисел не факт, что даст число в вашей системе), и мультипликативность (все представимые числа должны быть либо «простыми» в этой системе, либо быть суммой произведений, и чем меньше «простых», отличных от 0 и 1, тем лучше[флоаты и даблы этому условию не удовлетворяют, они вносят в алгебру дефекты округления и потери точности]), и конечно должны быть представимы 0 и 1, и както отрицательные числа… все это вместе позволяет представить рациональные числа над множеством представимых чисел. Т.е. Вы можете ввести систему по рациональному основанию, которая даст ту же систему, что и отношение двух целочисленных, т.е. без какого-то профита. Но введение иррациональной системы сложно, или вообще не возможно( из-за невозможности построения замкнутой алгебры с конечным числом чисел ), но если потеря алгебраичности приемлема, то возможно создания и вашей системы.
Кстати, на некоторых ЭВМ использовалась система записи чисел в остатках, а «основанием» системы служили не взаимнопростые, а обычные наши простые числа
Пусть для примера N = 30 (В действительности, конечно, количество различных чисел, с которыми должна оперировать вычислительная машина, обычно во много раз больше.) Тогда в качестве взаимно простых чисел s1, s2,… могут быть выбраны наименьшие простые числа 2, 3 и 5.
Запись десятичных чисел в остатках отделения на 2, 3 и 5 приведена далее. Правая цифра в записи числа дает остаток от деления на 2, средняя — остаток от деления на 3, а левая цифра — остаток от деления на 5
Десятичное число = Число в остатках
0 = 000
1 = 111
2 = 220
3 = 301
4 = 410
5 = 021
6 = 100
7 = 211
8 = 320
9 = 401
Результат, который получается при сложении, вычитании или перемножении чисел в любом из разрядов, никак не зависит от цифр в других разрядах числа. Операции во всех разрядах можно выполнять одновременно, причем с каждым разрядом можно действовать независимо от всех остальных разрядов. Очевидно, что при этом могут быть достигнуты существенно более высокие скорости выполнения операций, чем при использовании позиционного способа изображения чисел.
Фиеричная система счисления, или почему 1 + 10 = 100