Сборник материалов Иркутск, 19 апреля 2007 г. Иркутск 2007 г

Машина Поста

Машина Поста не существует в реальной жизни; это устройство представляет собой мысленную конструкцию, существующую лишь в нашем воображении и отражающую многие существенные черты вычислений на реальных компьютерах. Её создал в 1936 году американский математик Эмиль Л. Пост с целью изучения и уточнения одного из центральных понятий математики «алгоритм» [1,2]. В том же году была изобретена ещё одна подобная абстрактная машина – машина Тьюринга. Когда несколько лет спустя появились первые ЭВМ, оказалось, что основные принципиальные черты этих машин были предвосхищены в конструкциях Поста и Тьюринга.

Машина Поста состоит из бесконечной ленты, разделенной на клетки одинакового размера и каретки, которая обозревает одну из клеток ленты (см. рис. 1, на котором каретка изображена в виде вертикальной стрелочки).


Рис. 1.
Каждая клеточка может находиться в двух состояниях: пустая (рис. 2а) и заполненная (рис. 2б).

Рис. 2.

• 
  Сдвиг каретки на клетку вправо (R или RIGHT)
  
• 
  Сдвиг каретки на клетку влево (L или LEFT)
  
• 
  Заполнение клетки (P или PUT)
  
• 
  Опустошение клетки (D или DELETE)
  
• 
  Передача управления [выбор: если клеточка, обозреваемая кареткой, заполнена, выполняется первая написанная команда, если нет – вторая] (I или IF)
  
• 
  Стоп (S или STOP)
  

1. 
   на k-ом месте в списке стоит команда с номером k (k=1, 2, …);
   
2. 
   передача управления осуществляется на одну из команд в списке.
   

• 
  Сложение натуральных чисел.
  
• 
  Умножение натуральных чисел.
  
• 
  Деление чисел (аналог команды div в Паскале).
  
• 
  Вычитание из большего натурального числа меньшего натурального числа.
  

1. 
   L 2
   
2. 
   I 3 1
   
3. 
   R 4
   
4. 
   P 5
   
5. 
   S
   

1: начальное состояние 3: сдвиг вправо на одну клеточку



2: поиск правого края массива 4: заполнение клеточки и остановка

Рис. 3.

1. 
   R 2
   
2. 
   I 3 1
   
3. 
   D 4
   
4. 
   R 5
   
5. 
   I 6 10
   
6. 
   L 7
   
7. 
   I 8 6
   
8. 
   R 9
   
9. 
   P 1
   
10. 
    S
    

В данной программе каретка подходит к правому массиву, стирает крайнюю левую клеточку и смотрит, была ли она последней (была ли она нулем) если да, то программа заканчивает работу, если нет – каретка движется к левому массиву, заполняет клеточку перед ним и идет в начало программы.

нет да

1. 
   R 2
   
2. 
   I 1 3
   
3. 
   R 4
   
4. 
   I 6 5
   
5. 
   S
   
6. 
   L 7
   
7. 
   P 8
   
8. 
   L 9
   
9. 
   I 8 10
   
10. 
    R 11
    
11. 
    D 12
    
12. 
    R 13
    
13. 
    D 1
    

1. 
   находит правую границу левого массива,
   
2. 
   сдвигается вправо и делает «проверку окончания» (если элемент был последним, то делает остановку, если нет – продолжает работу)
   
3. 
   сдвигается влево и заполняет клеточку
   
4. 
   находит левую границу массива
   
5. 
   опустошает две крайние клеточки и начинает свою работу сначала
   

1. 
   I 3 2
   
2. 
   R 1
   
3. 
   D 4
   
4. 
   R 5
   
5. 
   I 7 6
   
6. 
   S
   
7. 
   L 8
   
8. 
   I 9 7
   
9. 
   D 1
   

Нет да

1. 
   Успенский В.А. Машина Поста. Популярные лекции по математике, № 64 – М.: Наука. 1988. – 96 с.
   
2. 
   Гусев В.А., Орлов А.И., Розенталь А.Л. Внеклассная работа по математике в 6–8 классах. /Под редакцией С.И. Швацбурда - М.: Просвещение. 1977. – с. 48-60.
   

Исчисление можно проводить разными методами. Позиционные системы счисления отличаются от непозиционных тем, что для кодирования чисел используется не сумма: A = a₀*P⁰+a₁*P¹+…+a_n*Pⁿ, где P-основание системы счисления, а другие различные способы.

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

Система остаточных классов (СОК) – это непозиционная система счисления, числа в которой представляются остатками от деления на выбранную систему оснований Р₁, Р₂,...,Р_n и являются взаимно простыми числами. Операции сложения, вычитания и умножения над числами в СОК производятся независимо по каждому основанию без переносов между разрядами (основаниями). Диапазон представимых чисел от 0 до P = P₁*P₂*...*P_n.

Если задан ряд положительных взаимно простых чисел Р₁, Р₂,...,Р_n, то целое положительное число A, представленное в виде набора наименьших положительных остатков (вычетов) от деления числа А на выбранные основания Р₁, Р₂,...,Р_n, можно записать в виде А =(a₁, a₂, ... ,a_n), где а_i =A(mod p_i).
Операции сложения/вычитания в общем виде выглядят так:

Здесь B – базис, X,Y – исходные числа, а Z – их сумма. При сложении каждый остаток складывается с соответствующим, а затем берется остаток от суммы при делении на соответствующее число в базисе.

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

Если исходные числа А, В, их сумма А+В и их произведение А*В находятся в диапазоне [0,P), то результаты операций сложения А+В и умножения АВ могут быть однозначно представлены соответственно остатками g_i и r_i по тем же основаниям Р_i, т.е.

А = (a₁, a₂,...,a_n), B = (b₁, b₂,...,b_n)
А+В = (g₁, g₂,...,g_n), АВ = (r₁, r₂,..., r_n), где g_i = a_i+b_i, r_i = a_i*b_i.
Такие операции, как деление, сравнение и др., требующие информации о величине всего числа, в СОК выполняются по более сложным алгоритмам. И в этом заключается существенный недостаток данной системы счисления, сдерживающий ее широкое применение в качестве компьютерной арифметики. Однако сегодня даже в самых современных компьютерах при работе с большими и очень большими числами используют СОК, ибо только эта арифметика позволяет получать результаты вычислений в реальном времени. В таких случаях в качестве оснований СОК применяют величины, близкие к 2^m (m – двоичная разрядность компьютера), например 2^{m –1}-1, 2^m-1, 2^{m –1}+1 и т.д. Компьютер вычисляет результат по одному из модулей за один проход. Другие области применения СОК – помехоустойчивое кодирование, криптография и т.п.

Начиная с 1952 года, специалисты многих стран мира, включая и СССР, занимались проблемой повышения скорости выполнения “неудобных” операций в СОК [3]. Особую роль в решении данной проблемы сыграл Израиль Яковлевич Акушский [4]. Немалый вклад в эту область науки внесли также Д.И. Юдицкий, В.М. Амербаев, А.А. Коляда [1,2].

Целью данной работы было исследование возможности использования СОК для реальных вычислений. Для выполнения поставленной задачи необходимо было написать:

• 
  Средства для организации системы остаточных классов и работы с нею, то есть создание базиса и средств для перевода из позиционного представления в остаточное и обратно, а также арифметические операции (сложение, вычитание, умножение).
  
• 
  Позиционную арифметику, способную работать с длинными числами, так называемую «длинную арифметику».
  
• 
  Средства для перевода из СОК в «длинную арифметику» и обратно.
  
• 
  Создание системы рациональных чисел, то есть чисел представленных как натуральная дробь, у которой числитель и знаменатель – числа в СОК.
  
• 
  Оценка быстродействия отдельных частей и всей программы в целом.
  

Программа может переводить числа из позиционной системы в систему СОК и обратно. Представление чисел в СОК было показано выше, в разделе «Введение». В теле программы число – это одномерный массив, содержащий в каждой своей ячейке остаток от деления на соответствующее основание. Основаниями в моей программе выбраны последовательные простые числа, начиная с 65521, и кончая 49117. Всего таких чисел 1500. Такие большие числа не случайны, ведь максимальным числом, используемым в программе, является произведение оснований, а большие остатки дают большую верхнюю границу.

Возьмем некоторое число, например, 27 и систему оснований из 3,5 и 7. Остаток от деления на 3 равен 0, на 5 равен 2, на 7 равен 6. Отсюда 27=(0,2,6).

Затем над представленными таким образом числами можно производить различные действия: сложение, вычитание, умножение и проверять на равенство. Из-за сложности операций деления и сравнения потребовалось реализовать «длинную арифметику». Деление представляет собой, так сказать, «отложенную операцию». Т.е. в процессе вычислений число представляет собой дробь , где a и b – представленные в СОК числа. После конца вычислений они будут переведены во внутреннее представление «длинной арифметики», поделены, и результат будет получен.

Из-за представления чисел в виде дробей арифметические операции над числами претерпели незначительные изменения, выраженные в том, что теперь они представляют собой действия над дробями. Например, сложение: . Затем над числителем и знаменателем проводятся вычисления по отдельности, как над числами в СОК.

Преимущество системы остаточных классов в том, что при росте числа знаков само представление чисел растет намного медленнее, т.е. число остатков растет очень медленно. Так, например, для примерно 9 тысяч знаков требуется всего 1500 остатков. Каждый остаток – 2 байта. Всего 3000 байтов. Для представления в позиционной двоичной системе требуется 4096 байт. Экономия в 4096/3000 = 1,365 раз; при вычислениях это дает еще больший выигрыш; например, сложим два числа, представленными 3000 байтами, что потребует по 3000 операций сложения и проверки переноса, а также сколько-то самих переносов, всего – более 6000 операций; и это только сложение. А сколько займет умножение, даже и сказать трудно. И это без учета вспомогательных операций. А в системе остаточных классов то же сложение займет чуть больше 3000 операций (по 1500 сложений и взятий остатков). Экономия примерно в 2 раза. А при умножении данные показатели еще лучше, потому как на перемножение остатков требуется так же 3000 операций, а умножение в позиционной системе потребует множество сложений. По меньшей мере, одно, если, конечно, не на ноль умножать. В результате умножения на ноль потребуется обнулить больший объем памяти (4096 байт против 3000). А в общем, количество равно сумме всех цифр у какого-нибудь из чисел. Хорошо еще, если она будет меньшей из двух возможных. А если нет, то что делать? Сравнивать их тоже очень долго.

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

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

Оптимизация в «длинной арифметике» ведется в основном благодаря тому, что в самом числе хранится информация о его длине. Благодаря этому свойству происходит меньше операций, потому что работа ведется на меньшем массиве данных. Похожая система применена в СОК. Но число остатков там для всех чисел одинаково и меняется только одновременно: либо увеличивается при повышении разрядности чисел, либо уменьшается, если не требуется столько оснований. Но процесс изменения количества долог и не может применяться часто. Поэтому приходится делать достаточный запас для того, чтобы избежать ошибок переполнения, которые достаточно трудно отследить по той причине, что при выходе за границы представления числа переходят через 0 в начало, ведь остатки и числа, ими заданные, повторяются циклически, длина этого цикла равна произведению всех оснований.

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

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

Сама программа сравнивает производительность при различных действиях, при расчете нескольких медленно сходящихся рядов, а также способна производить действия над введенными числами. Все это реализовано в среде Delphi 7. Сравнение ведется между «длинной арифметикой», системой остаточных классов и процессорными действиями. Быстрее всего считает, конечно, процессор, но при увеличении длины чисел он первым и перестает считать.

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

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

1. 
   Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах.- М.; Сов.Радио. 1968. - 439 с.
   
2. 
   Акушский И.Я., Амербаев В.М., Пак И.Т. Основы машинной арифметики комплексных чисел. Алма-Ата: Наука. 1973. - 192 с.
   
3. 
   Синьков М.В., Губарени Н.М. Непозиционные представления многомерных числовых систем. Киев. - Наукова думка. 1977. - 149 с.
   
4. 
   Синьков М.В., Синькова Т.В., Федоренко А.В., Чапор А.А. Нетрадиционная система остаточных классов и ее основоположник И. Я. Акушский.- www.icfcst.kiev.ua,10.02.1999.