Напечатать документ Послать нам письмо Сохранить документ Форумы сайта Вернуться к предыдущей
АКАДЕМИЯ ТРИНИТАРИЗМА На главную страницу
Институт Золотого Сечения - Дискуссии

Никитин А.В.
Компьютеры Фибоначчи
Oб авторе


 

 

Настоящая статья открывает серию статей по оригинальным математическим результатам «математики гармонии», которые не существовали в рамках «классической математики».[2]

 

Математиком я никогда не был, и вряд ли когда-нибудь буду. Кое-что понимаю в вычислительной технике, немного в процессорах…

Составить конкуренцию профессионалам я не смогу. Но…

Могу просто кое-что рассказать.

В том числе и компьютере Фибоначчи.

А вы уж сами решайте, что тут хорошо, а что … не очень.

Теперь немного о предмете разговора…

Сначала я повторю те же системы счета, изложенные в [1,2]. Там они даны хорошим математическим языком, но некоторые простые моменты при таком изложении понимаются не сразу. И потому…


Система Бергмана

Система Бергмана – полномасштабная позиционная система счисления с иррациональным основанием Ф. Она позволяет проводить с числами все арифметические действия в принятом порядке, с учетом свойств и правил счета этой системы. Складывать, вычитать, умножать и делить.

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

Основное правило роста разрядности числа 011 =100, т.е. старший разряд — это сумма двух предыдущих, а не только произведение, как во всех остальных системах счисления. Основной формой записи числа является запись единицами старших разрядов 100, а число 011 — эквивалентная, временная форма записи, которая при окончании операции вычисления должна быть переведена в основную. Пример: Число 11111, исходя из основного правила, существовать не может и может рассматриваться только как временная эквивалентная запись числа перед преобразованием его в нормальную форму, т.е. 11 111 = 100111 = 101001.

Еще одна особенность: 100+100 = 100+011 = 111= 1001.

На этой особенности мы остановимся подробнее.

При сложении одинаковых разрядных единиц мы получаем: 1+1=10,01. Как мы видим, заполняется новый разряд числа слева и… еще один разряд справа, через один от разряда сложения. Вот это движение единиц вправо от разряда сложения и отличает подобные системы счета от привычных нам систем с рациональным основанием: двоичной, десятичной…, там движение единиц идет только в одну сторону – левую. В сторону увеличения веса разряда.

Для правильного сложения одно из чисел должно быть представлено во временной эквивалентной форме..011…, как мы делаем при вычитании из пустого разряда в любой системе счета, занимая единицы из соседнего разряда. Здесь это постоянная операция и при сложении одинаковых разрядных единиц и при вычитании из пустого разряда.

Давайте посмотрим, как будет выглядеть запись первых чисел натурального ряда в этой системе счисления:


1= 1

2=10,01=1+1

3=100,01=10,01+1=11,01

4=101,01=100,01+1

5=1000,1001=101,01+1=110,1001=

6=1010,0001= 1000,1001+1=1001,1001

7=10000,0001=1010,0001+1=1011,0001

8=10001,0001=10000,0001+1 и т.д.


Видите, как быстро растет число? Такое положение возникает в результате того, что десяток не содержит целого числа единиц, т.к. он меньше 2, и сложение 1+1>Ф, дает следующий разряд с переполнением. А так как, мы складываем единицы нулевого разряда, у нас одинаково быстро нарастает как целая часть числа, так и дробная.


Коды Фибоначчи.

Эта система представления числа была предложена бельгийским врачом Эдуардом Цекендорфом в 1939 г., а теоретическое обоснование у нас она получила в работах А. П. Стахова.

Последовательность Фибоначчи: 1,1,2,3,5,8,13,…

Число Ф здесь присутствует, как предел отношения соседних членов последовательности. Общая формула этой последовательности:


С n = C n-1+ C n-2            (1)


Это означает, что каждый новый член последовательности, это сумма двух предыдущих.

Из последовательности можно сделать систему представления числа. Вот как выглядят в ней первые числа натурального ряда:


1 = 1= 0+1

2 = 10=1+1

3 = 100=10+1=11

4 = 101=100+1

5 = 1000=101+1= 110

6 = 1001=1000+1

7 = 1010=1001+1

8 = 10000=1010+1=1011=1100

9 = 10001=10000+1 и т.д.


Единица старшего разряда в числе – сумма единиц двух соседних младших разрядов.

А потому число этой системы счета в развернутой форме не может иметь две единицы подряд в соседних разрядах: 10+1=011= 100.

Такая система, строго говоря, системой счисления называться не может. Она не имеет дробной части. Для нее специально разрабатывались правила умножения и деления. Это система представления числа. Что и отражено в названии системы – коды Фибоначчи.

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

А так как любое число в нулевой степени равно единице, то она и принята за счетную единицу.

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

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

Единица нового разряда образуется сложением единиц двух предыдущих разрядов. И первый разряд должен отличаться от единицы, да и нулевой разряд должен быть выделен. А в нем, в нулевом разряде умещается только одна единица. И в первом тоже, но переполнения нет. Но единица у нас – десяток. Первая же счетная единица заполняет нулевой разряд, и переводится в первый разряд, т.е. в разряд десятков. Так мы это и записываем 0+1=10. Но, мы помним, что единица первоначально помещается в нулевой разряд, а лишь потом переходит в первый разряд. Полная запись такая: 00+1=01=10. Если первый разряд уже заполнен, то следующая единица задержится в нулевом разряде на период преобразования числа в основную форму записи или на период проведения счетной операции. А потому: 1 = 10, 2=100, 3= 1000 и т.д.

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

Правило сложения одинаковых разрядных единиц 100+100 = 100+011 = 111= 1001 действует и в этой системе. Правда, А.П.Стахов исключил второй единичный разряд и ввел особые правила сложения в нулевом разряде: 1+1=10. Если принять во внимание, что данная система счетной не является по определению, то решение вполне рациональное.

Кстати, данный материал[3] был опубликован в 2006 году. Тогда коды Фибоначчи1 в изложении А.П.Стахова еще имели вид показанный выше.

Идем далее.

Вот это утверждение совершенно справедливо [2]:


«В отличие от классической двоичной системы код Фибоначчи (4) является избыточным кодом. При этом его избыточность кода проявляет себя в свойстве многозначности представления натуральных чисел. Это свойство лежит в основе контроля всех арифметических операций и обеспечивает другие важные технические преимущества данного кода».


Уточним, одно и то же число, записанное в кодах Фибоначчи, может иметь несколько вариантов записи.


***

И была еще зеркально-симметричная система счета, построенная на использовании основания Ф2 с применением как положительных, так и отрицательных чисел в разрядах системного числа. Но это, так, к сведению, не более.


Последовательность Люка.

Последовательность Люка сформирована на базе округления очередного значения Фn до ближайшего целого числа по формуле:


Lnn+(-1)nФ-n            (2)


Как последовательность, она имеет вид: 1,3,4,7, ….


***

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


Переходим к технике…

Сначала подборка цитат из работы [1]:


«…Наиболее революционным предложением в современной теории систем счисления по праву можно считать систему счисления, предложенную в 1957 г. американским математиком Джорджем Бергманом.

…Хорошо известно следующее свойство «золотой пропорция»:

Фi = Фi -1i-2 = ФxФi-1 , (2)

где i = 0, ±1, ±2, ±3, … .

Рассмотрим представления чисел в системе Бергмана (1). Ясно, что сокращенная цифровая запись числа A в системе (1) имеет следующий вид:

A = anan-1 a1a0, a-1a-2a-m. (3)

Из (3) вытекает, что сокращенная запись числа A представляет собой двоичную кодовую комбинацию, разделенную запятой на две части, левую часть anan-1a1a0, соответствующую «весам»: Фnn-1,...,Ф10 = 1, и правую часть a-1a-2a-m, соответствующую «весам»: Ф-1-2,...,Ф-m. Заметим, что «веса» Фi (i =0, ±1, ±2, ±3, …) связаны между собой математическими соотношениями (2).

Например, рассмотрим двоичную кодовую комбинацию 100101. Ясно, что в системе Бергмана (1) она представляет следующее действительное число:

A =100101=Ф520.

Известно следующее тождество, связывает i-ю степень «золотой пропорции» Фi c числами Фибоначчи и Люка:

(5)

Используя тождество (5), мы можем установить, что число A, задаваемое кодовой комбинацией (4), равно:

A =100101=+ 1= (6)

Существенно подчеркнуть, что число (6) является иррациональным числом.

Это означает, что мы представили иррациональное число (6) в системе Бергмана (1), в виде кодовой комбинации 100101, состоящей из конечного числа бит!


Именно поэтому возможность представления некоторых иррациональных чисел (степеней «золотой пропорции» и их сумм), а также, как будет показано ниже, всех натуральных чисел с использованием конечной совокупности двоичных цифр есть первый неожиданный результат системы Бергмана (1), который вступает в противоречие с нашими традиционными представлениями о системах счисления.


С точки зрения математики всё совершенно справедливо. Теперь попробуем понять то, что сказано. С технической точки зрения.

Есть последовательность Фибоначчи: 1, 1, 2, 3, 5, 8, …

И последовательность Люка: 0, 1, 3, 4, 7, 11, …

Еще надо учесть множитель: к = √5 и коэффициент: а = 1/2

Преобразовать любое число в код Бергмана предлагается по формуле (5).

Для этого надо взять какое-то число из последовательности Люка, прибавить к нему произведение какого-то числа из последовательности Фибоначчи, умноженного на постоянный коэффициент к = √5. Потом сумму этих слагаемых умножить на коэффициент а = 1/2 . Произвести необходимые вычисления и преобразования. И только тогда мы получим число в системе Бергмана, записанное бинарной записью, т.е. с использованием 0 и 1.

Может быть несколько тяжеловато, но … математически верно. Правда, пока не ясно, где мы будем брать исходные числа из указанных последовательностей…

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


Ввод и хранение информации.

Как мы понимаем, ввод данных в компьютер любой системы и архитектуры, так или иначе, пока возможен в трех вариантах: с клавиатуры, с носителя и с линии связи.

Данные с носителя записываются в память массивом, а ручной ввод производится последовательным нажатием набора клавиш. С линией связи обмен информации идет непрерывно. Это принципиально разные вводы информации. Как по форме, так и по содержанию.

Данные с клавиатуры сегодня вводятся, скорее всего, в двоично-десятичном коде. Каждой клавише дан набор нескольких двухбайтовых комбинаций. Всего таких комбинаций 128. И их число растет каждый день. Но… нас интересуют пока только цифры. От 0 до 9.

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

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

Пусть это останется предметом дальнейшего обсуждения, а мы пойдем дальше.

Ввод массива данных в кодах системы Бергмана увеличивает объем хранимой информации в 1,44 раза. Это только, как мы выяснили, для целых чисел системы Бергмана. Но наши данные изначально записывались из десятичной системы счисления, и потому результирующий объем, с учетом дробной части, будет больше уже в разы…

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

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

Принцип её прост: Две единицы рядом в числе стоять не могут. И если такое случится при любой операции движения информации, то это автоматически прервет операцию, как ошибка ввода-вывода.

Эффективность этого принципа проверки достоверности информации очень высока. И здесь надо согласиться с выводами А.П.Стахова.

А мы идем дальше.

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

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

При одном и том же исходном объеме введенной полезной информации с использованием системы Бергмана в кодировании адресов ячеек памяти объем общей хранимой информации в компьютере увеличивается уже многократно. Это, как мы понимаем, уменьшит полезный объем всех постоянных и временных носителей информации.

При сохранении той же тактовой частоты процессора соответственно этому упадет и скорость обработки информации.

При работе компьютера в режиме приема-передачи информации с линией связи применение системы Бергмана в качестве основной наиболее эффективно. В этом режиме в полную силу используется помехоустойчивость этого кодирования. Здесь, как мне кажется, нужно уже очень внимательно оценить все факторы. А не только формальные, как изменение объемов информации или время, но и затраты на дополнительные проверки достоверности информации другими способами и программами. Вопрос сложный и трудный, но и затраты на это сегодня - большие.

До процессора мы еще так и не добрались, а проблем уже целый ворох…

Я в процессорах не очень, но … немного коснемся и их.


Процессоры.

Сегодняшние многоядерные процессоры работают уже на принципах конвейерной обработки информации. Это уже сложнейшие системы со своей сложной архитектурой и развитым языком программирования команд. Тут должен говорить профессионал.

Мы же поговорим только об общих понятиях и основном компоненте процессора – параллельном сумматоре.

Сумматор «заточен» под двоичную систему. Мы это понимаем. Для применения системы Бергмана нужен новый сумматор. С новой архитектурой и системой связей. С новой системой разрядного сложения.

И сначала, видимо, придется вернуться обратно к триггерным счетным линейкам параллельной загрузки. Начинать придется опять с них. И с обратных связей. Как вперед, так и назад. Потому, что 1+1=10,01; мы же это помним…

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

И от этого нам никуда не уйти. Дробная часть составляет единый комплекс с целой частью обрабатываемого числа. Потому, что в основе системы Бергмана иррациональное число. Кроме системы Бергмана в процессоре никакой другой быть не может. Это единственная полномасштабная система счисления, из предлагаемых в [1, 2] для компьютера Фибоначчи.

Все остальные, пока только системы представления или отображения числа.

Таким образом, применение системы Бергмана в качестве основной системы счисления компьютера сразу увеличивает в два раза количество разрядов процессора, а при увеличении значности целого числа в 1,44 раза, количество разрядов процессора возрастает почти в 3 раза по сравнению с существующим.

Если современный процессор работает с машинным словом в 64 разряда, то процессор Фибоначи для обеспечения той же точности вычислений должен имеет около 200 разрядов в машинном слове.

Теперь вернем это машинное слово в память машины и пересчитаем эффективность использования памяти компьютера. Как постоянной, так и временной, оперативной. Всех видов. Картина получится интересная…

Правда, мы об этом уже говорили ранее, но, как мы видим, ситуация еще более усложняется.

Это только первые оценки применения системы Бергмана. Очень примерные.

Но сложности выявляются уже очень конкретные.


И на последок…

Есть еще и очень общие вопросы, влияющие на вопрос применения системы Бергмана и кодов Фибоначчи в компьютерной технике. Какие?

Например, логика этих систем. Это уже не двоичная булева логика. Другая. И программы с применением булевой логики тут будут работать некорректно.

И троичная логика Брусенцова тут неприменима. Нужна своя.

Мы не добрались до многозначности представления чисел в кодах Фибоначчи для обеспечения надежности хранения и передачи информации, об это разговор еще впереди…

Пока бы с этими вопросами разобраться.


 

1Музей Гармонии и Золотого Сечения http://www.goldenmuseum.com/index_rus.html

Раздел: Математика Гармонии – коды Фибоначчи.


Литература:


  1. А.П. Стахов, Системы счисления с иррациональными основаниями и новые свойства натуральных чисел // «Академия Тринитаризма», М., Эл № 77-6567, публ.16778, 24.08.2011 http://www.trinitas.ru/rus/doc/0232/009a/02321216.htm
  2. А.П. Стахов, Микропроцессоры Фибоначчи - как одна из базисных инноваций будущего технологического уклада, изменяющих уровень информационной безопасности систем // «Академия Тринитаризма», М., Эл № 77-6567, публ.16759, 16.08.2011 http://www.trinitas.ru/rus/doc/0232/009a/02321212.htm
  3. Никитин А.В. На пути к Машинному Разуму. Круг третий. (Часть 3) // «Академия Тринитаризма», М., Эл № 77-6567, публ.12907, 03.02.2006 http://trinitas.ru/rus/doc/0023/001a/00230030.htm


 


Никитин А.В., Компьютеры Фибоначчи // «Академия Тринитаризма», М., Эл № 77-6567, публ.16780, 25.08.2011

[Обсуждение на форуме «Публицистика»]

В начало документа

© Академия Тринитаризма
info@trinitas.ru

Warning: include(/home/trinita2/public_html/footer.php) [function.include]: failed to open stream: No such file or directory in /home/trinita2/public_html/rus/doc/0232/009a/02321217.htm on line 488

Warning: include() [function.include]: Failed opening '/home/trinita2/public_html/footer.php' for inclusion (include_path='.:/opt/alt/php53/usr/share/pear:/opt/alt/php53/usr/share/php') in /home/trinita2/public_html/rus/doc/0232/009a/02321217.htm on line 488