Pull to refresh

Comments 54

Поиграл в вашу игру. Понравилось) Вроде бы нашёл алгоритм, который можно быстренько запрограммировать (правда, лень).
1) Спускаем всё вниз
2) Нормализуем последний ряд
3) Повторяем 1-2 пока не зайдём в тупик
4) Денормализуем самую правую единицу во втором снизу ряду
5) Повторяем 1-2-3-4 пока не завершим.
Да, это должно работать на всех (конечных) входных данных.
Очень живо и интересно написано, спасибо.
Прочитал.
Вдумался в тег «курить бамбук нагибая дубы».
Можете дать этимологию слову «фиеричный»? Или все-таки, от слова «феерия»?
P.S.: Пишу здесь, а не в ЛС, может быть я просто не знаю такого слова (через «и»).
Подсказка: название греческой буквы.
Ну так он же написал

«Далее по тексту я иногда буду называть её фиеричной (по аналогии с, допустим, восьмеричной) системой счисления, а иногда не буду.»

Просто вместо цифры название буквы подставил и все, как капитан выше подсказывает
как капитан выше подсказывает

Сначала подумал про капитана Очевидность, затем поднял глаза на ник предыдущего комментатора… Нет, Флинт :-)
Интересно, а звание дважды капитана существует?
Можно по совместительству, на полставки. :-)
Лучше было бы писать фи-еричная или φ-еричная, потому что это слово упорно читается, как «фееричная».
Ну, это был такой каламбур, так что just as planned)

Каламбур удался, не слушайте их.

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

Я вырос на обозначениях, где фи малое — это величина, обратная к фи большому, т.е. как в википедии.

А факт действительно крутой, мне он был неизвестен, и я сходу не могу сообразить, как этого можно добиться. Не поделитесь ссылкой?

Не слушайте его, это неверно. В фиеричной системе при сложении вроде 1010101010101010 + 1 перенос точно так же пойдет из младшего разряда в старший на этапе нормализации.

Спасибо, мы уже разобрались) там похожая, но более хитрая система обладает этим свойством.
  • Гуглить по слову 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 (в статье ошибка, из-за которой всё заявленное работает только для рациональных оснований). В любом случае там будет полезна обзорная часть.
А, вот оно что! Нашёл статью из второго пункта, там появляется дополнительная цифра "-1". А я уж всю голову сломал, пытаясь понять, как в оригинальной бергмановской системе организовать параллельное сложение.
Спасибо за информацию, помещу ссылку на ваш комментарий в статью.

Хм, вообще-то, если я правильно помню, организовать параллельное сложение можно и с двумя цифрами {0,1}, главное, чтобы основание было меньше 2. Общее утверждение таково, что для существования поразрядного паралеллизма достаточно: (1) количество цифр (0, 1, ...) должно быть больше, чем основание, (2) основание должно быть алгебраическим числом (это требуется только для "точных" представлений, для интервальных вроде не обязательно) и (3) довольно причудливое условие на алгебраические сопряженные основания, которое для фи выполнено.

Тут говорят:
When the base β is the Golden Mean, we further refine the construction to obtain a parallel algorithm on the alphabet {−1, 0, 1}. This alphabet cannot be reduced any more.
(выделено мной).
Интересно, как это ложится на вычислительные машины с троичной логикой. Понятно, что напрямую операции не закодировать, но с учетом полного отображения базы в трит я думаю можно получить более элегантное решение чем для двоичной логики.
Насколько я успел вкурить бамбук статью, там в промежуточном представлении при сложении используются цифры от -2 до 2. Так что триты не спасут отца русской демократии.
Фиеричная

Каждый раз при прочтении этого слова рука моего внутреннего граммар-наци тянется к расстрельному "вальтеру", но в следующую секунду опускается обратно ;)


Цимес в том, что приведённая формула, если рассматривать её как уравнение, имеет единственное действительное решение.

Прочитав это, мой внутренний хакер немедленно встрепенулся и задал вопрос — "раз есть действительное решение — значит, должно быть и комплексное, нельзя ли его как-нибудь в хозяйстве применить?"

Применять в хозяйстве, я думаю, будет проблематично — судя по всему, комплексные решения невыразимы в радикалах. Только численные методы, только приближенное решение, только грусть…
Нужно просто ввести мнимую цифру.
Ввести, простите, куда?
Уже писали про цифру -1, чтобы получить симметричную систему.
Я хотел написать, что чтобы получить возможность записи комплексных чисел нужно добавить ещё i и -i, но по здравому размышлению это неудачная идея.
Для записи комплексных чисел можно взять основание корень из минус фи и не париться. Но вообще изначально в этой ветке речь шла о комплексных решениях уравнения. Это, по идее, совсем другая история.

Ну есть проблема, что количество цифр в действительных числах будет расти квадратично от количества чисел в обычной системе, но для каких-то задач может оказаться полезно. Кажется, у Кнута на эту тему статьи были. Еще можно не числа, а матрицы использовать, тоже интересно получается.

Почему квадратично? Навскидку кажется, что в константу раз (примерно вдвое).

То же количество цифр описывает не отрезок на прямой, а квадрат на плоскости. Соответственно, отрезок получается короче.

Но это значит, что количество отсчётов (представимых значений) растет квадратично. А количество цифр зааисит от него логарифмически.

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

Фееричная статья про фиеричные системы счисления!
Хабр — торт!
Было бы интересно на основе этой cистемы счисления сделать фиеричный эзотерический язык программирования. Возможно, получится даже сложнее Malbolge, с его троичной с/с и операцией crazy. :)
жажду увидеть пару абзацев о практической полезности данной фисистемы
Про неё можно писать хабрапосты, набирающие неплохой рейтинг, по крайней мере один раз.
Думаю, что и на 10.01 раза материала может хватить =) Но тут нужен какой-то совсем прошаренный инженер-математик
Неплохой рейтинг также могут набрать посты про «Pi-еричную» систему, а также конвертер из «фи-еричной» системы в «pi-еричную» согласно формуле:
image
Интересно, для компрессии данных ее можно использовать? Ведь 100=11 в ней, а значит, можно кодировать три символа двумя.
Видимо, поскольку у фееричного числа может быть несколько форм, то «сжатую» информацию нельзя одназначно интерпретировать. А если исходные данные всегда в нормальной форме, то это накладывает ограничения на «несжатую» информацию.
Спасибо. Прочитал оригинальную статью Бергмана, получил истинное удовольствие от красоты этой системы. Для интересующихся темой есть также отличная книга А.П. Стахов «Коды золотой пропорции» М. Радио и связь, 1984
… в которой мимоходом «доказываются» неверные утверждения.
> таких даже больше, их континуум
Нужно будет запомнить. Хороший эвфемизм для выражения «до х#я»
Вспомнился анекдот про то, как разделить 28 танков между между 7 ротами по 13 штук.
Ведь такая система счисления тоже должна как-то называться.
Тут скорее попытка ввести на множестве целых чисел альтернативную кольцевую структуру.
Вспомнилось «в армии нет слова „украли“, есть слово „прое… л“.»

Не пойму, как так получается. В двоичной системе счисления две цифры, в троичной — три, в шестнадцатеричной — шестнадцать. Это мне понятно, и вроде этому меня и учили. А тут, мало того, что должно быть 1,62 цифры, так еще и левые цифры (-1) вводятся. Никто не пробовал вводить дробные цифры в десятичную, например? Получились бы прикольные штуки, типа, 7'36, где цифра 7' — это 7,5. Или даже (7 + 1/e).


Кто-нибудь тут может объяснить, как эти "ненатуральные" системы работают?

Целочисленные системы имеют конечное множество модулей от оснований, десятичная(-5..4), троичная(-1..1)… это все остатки по модулям. Остатков-же по дробному основанию — бесконечное множество, в том числе и целые, и отрицательные, и рациональные/иррациональные(от комплексного/матрицы остаток — комплексный/митричный), проблема-же и там, и там — большинство чисел не представимы конечным чистом не нулевых цифр.

По своей сути наша запись — апроксимация(приближение), означающая, что мы описываем число, которое: больше некоторого 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
Результат, который получается при сложении, вычитании или перемножении чисел в любом из разрядов, никак не зависит от цифр в других разрядах числа. Операции во всех разрядах можно выполнять одновременно, причем с каждым разрядом можно действовать независимо от всех остальных разрядов. Очевидно, что при этом могут быть достигнуты существенно более высокие скорости выполнения операций, чем при использовании позиционного способа изображения чисел.
Sign up to leave a comment.

Articles