Учебные модели компьютера

Мы знаем тысячи разрозненных фактов, и часто рассматриваем их изолированно друг от друга, не задумываясь о том, что все они должны быть как-то связаны, поскольку мир вокруг нас един. Например, любому ребенку известно (факт А), что летом тепло, а зимой холодно. Кроме того, не менее очевидно (факт Б), что чем ближе к Солнцу, тем теплее. Каждый из тезисов очевиден и неоспорим, оба, вроде бы, об одном и том же, но при попытке объединить А и Б вместе вдруг возникают трудности: а почему же тогда сейчас, когда у нас в северном полушарии зима, в Австралии лето?

По данным статьи [1], которая представляет собой стенограмму выступления А. Кэя¹ в Конгрессе США, почти 95% старшекурсников и профессоров некоторых ведущих университетов этой страны в ходе проведенного опроса уверенно утверждали, что «Земля летом ближе к Солнцу, чем зимой». А на последующий вопрос «Знаете ли вы, какое время года настает в Южной Америке и Австралии, когда у нас в Штатах приходит лето?» давали не менее уверенный ответ «Зима, разумеется». Причем противоречие нового названного факта предыдущим двум мало кто замечал… А. Кэй пишет, что “мы столкнулись с отсутствием у этих ребят самых элементарных навыков критического мышления. Ведь и им, и их наставникам, не выдержавшим испытания, были известны факты, противоречащие невразумительным догадкам. Почему же никто из них не спохватился: «Эй, послушайте, как же так?..» Все, что нужно для правильного ответа, было им известно! Однако сопоставить факты, сложить из них мозаику, которая станет правильным ответом, большинству участников испытания не удалось.”

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

А нет ли в информатике подобных примеров, когда сопоставление фактов первоначально приводит к противоречию, а последующий анализ позволяет лучше разобраться в сути проблемы?

двоичная книга

Рассмотрим следующий, казалось бы, избитый, классический вопрос о переводе из десятичной системы в двоичную и обратно (договоримся для краткости записи называть эти процедуры «10 в 2» и «2 в 10»). Редкая книга по информатике, исключая, может быть, самоучители для «чайников» или «полных идиотов», не рассказывает о том, как это делается. Трудно противостоять напору информации и не знать (факт А): для перевода «10 в 2» необходимо число последовательно делить на два, а «2 в 10» выполняется путем сложения соответствующих степеней двойки. Мне просто не хочется писать об этом подробнее, чтобы не вызвать зевоту у читателей. Что касается факта Б, то он, видимо, менее известен широкой аудитории, но для меня он не менее очевиден, чем факт А. Речь идет о том, по какому алгоритму в компьютере на практике осуществляется перевод. О деталях поговорим чуть позднее, а сейчас подумаем, как должны быть связаны факты А и Б? Иначе говоря, использует ли компьютер те же самые алгоритмы, которые мы так старательно изучали на уроках?

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

Причин тому несколько. Во-первых, компьютер приводит к двоичному виду не десятичное число, а его введенное с клавиатуры текстовое отображение². Во-вторых, при проведении расчетов мы пользуемся десятичной системой, а компьютер двоичной (чуть позднее мы увидим, что это приводит к весьма существенным последствиям при выборе алгоритма). Наконец, в третьих, мы производим перевод чисел редко, поэтому не заботимся об оптимальности вычислительного процесса, а для компьютера ситуация другая. Таким образом, задачи «10 в 2» и «2 в 10» для человека и для компьютера выглядят весьма по-разному.

Рассмотрим теперь реализацию процесса перевода в компьютере подробнее. В основе перевода из одной системы счисления в другую лежит следующая общая теорема (см., например, [2]).

Для перевода целого числа A_p из p-ичной системы счисления в систему счисления с основанием d, необходимо A_p последовательно делить с остатком на число d, записанное в той же p-ичной системе, до тех пор, пока полученное частное не станет равным нулю. Остатки от деления при этом будут являться d-ичными цифрами числа A_d, начиная от младшего разряда к старшему. Все действия необходимо проводить в p-ичной системе счисления.

Если формулировка кажется вам запутанной и устрашающей, положите везде p = 10 и d = 2 (слова «записанное в той же p-ичной системе» в данном случае становятся излишними), в результате чего получится известное всем правило перевода «10 в 2». Необычайно важно понять, что данный алгоритм в принципе пригоден для перевода между абсолютно произвольными системами счисления. Проблема заключается в последней фразе – действия необходимо производить в той же системе, в которой представлено исходное число. Отсюда следует важный для нас сейчас вывод, что для человека данное правило удобно лишь при p = 10, т.е. при переводе из десятичной системы. Поэтому, хотя теорему можно применять и для «2 в 10», осуществляя все расчеты в двоичной системе, но делать это гораздо проще, используя другой (известный из школы) алгоритм.

Что касается компьютера, то ему, напротив, удобнее производить вычисления в двоичной системе. Поэтому для перевода «2 в 10» используется последовательное деление на десять в двоичной системе, а «10 в 2» – сложение степеней десятки. Таким образом, в компьютере уже известные нам методы применяются «зеркальным» образом по сравнению с тем, как их использует человек.

И еще об одной особенности перевода «10 в 2» в компьютерной реализации. Рассмотрим ее на примере конкретного числа 1234.

1234 = 1 х 10³ + 2 х 10² + 3 х 10¹ + 4 х 10⁰ (1)

Для упрощения вычислений данное выражение удобно преобразовать путем вынесения множителя 10 за скобки. Получим:

1234 = (1 х 10² + 2 х 10¹ + 3) х 10 + 4

Повторим процедуру еще раз.

1234 = ((1 х 10 + 2) х 10 + 3) х 10 + 4

Присмотревшись повнимательнее, увидим, что получившаяся формула описывает последовательное умножение предыдущего результата R_k-1 на 10 и прибавление очередной цифры c_k:

R_k = 10 R_k-1 + c_k (2)

Заметим, что в качестве начального условия удобно принять R₀ = 0.

Формула (2) по сравнению с исходным выражением (1) имеет существенные преимущества. Во-первых, она не требует запоминания промежуточного результата, а сразу использует его для дальнейших вычислений. Во-вторых, как доказали математики, такая схема вычислений, называемая схемой Горнера, содержит минимально возможное число арифметических операций. Наконец, в-третьих, формула (2) корректно обрабатывает число по мере ввода, тогда как (1) требует, чтобы все цифры были уже известны (иначе нельзя расставить степени!); в некоторых программах такое свойство оказывается полезным.

Примечание. Схема Горнера оказывается удобной и при традиционном «ручном» переводе «2 в 10». Более того, из ее записи немедленно видно, почему последовательное деление на 2 при обратной процедуре «10 в 2» дает именно двоичные цифры (подробнее см. главу 6 в [3]).

Напомнив читателям еще раз о том, что процедура «10 в 2» переводит текстовую строку с десятичным представлением числа в двоичное число, а «2 в 10» наоборот, приведем текст программ перевода, для наглядности реализованных на Паскале. Они настолько просты, что в дополнительных комментариях не нуждаются.

Листинг 1.

{10 в 2}
CONST baza=ord('0'); {код символа '0'}
VAR   s: STRING; r, i: INTEGER;
BEGIN READLN(s); {строка с десятичным числом (без ошибок!)}
      i:=1;{номер символа} r:=0;{очистим будущий результат}
      WHILE i<=LENGTH(s){до конца строки} DO
            BEGIN r:=10*r+(ord(s[i])-baza); {добавим цифру к результату}
                  i:=i+1; {к следующему символу}
            END;
      WRITELN(r); {вывод результата – должен совпасть со введенным}
END.

Листинг 2.

{2 в 10}
CONST baza=ord('0'); {код символа '0'}
VAR   s: STRING; n, i: INTEGER;
BEGIN READLN(n); {в переменной n - двоичное число}
      s:=''; {пока пусто}
      WHILE n>0 DO
            BEGIN i:=n MOD 10; s:=CHR(i+baza)+s; {очередная цифра}
                  n:=n DIV 10; {оставшиеся цифры}
            END;
      WRITELN(s); {вывод результата – должен совпасть со введенным}
END.

Хочу особо подчеркнуть, что описанная в статье картина распространяется не только на языки программирования; все сказанное выше, например, целиком и полностью относится ко вводу числовой информации в ячейки электронной таблицы Excel.

Кстати говоря, при достаточном знании строковых функций, листинги 1 и 2 можно переделать для имитации рассматриваемых алгоритмов в Excel. Ниже в таблицах 1 и 2 кратко описано, как заполнить ячейки таблицы для того, чтобы проанализировать ход перевода для случая, когда количество десятичных цифр не превышает четырех. Заметим, что столбец A оставлен для нумерации цифр числа (в таблице не отражено).

Таблица 1.

Ячейки Формулы Комментарии
B1 "9876" Строка с переводимым десятичным числом (s)
B2 ПСТР($B$1;2;1) Первый символ-цифра (кавычки имеют номер 1)
B3 ПСТР($B$1;3;1) Второй символ-цифра

B4 ПСТР($B$1;4;1) Третий символ-цифра
B5 ПСТР($B$1;5;1) Четвертый символ-цифра
C1 КОДСИМВ(“0”) Код ‘0’ (baza)
C2 КОДСИМВ(B2)-$C$1 Первая цифра
C3-C5 размножить C2 Остальные цифры
D1 0 R₀
D2 10*D1+C2 R₁
D3-D5 размножить D2 R_k

Таблица 2.

Ячейки Формулы Комментарии
B1 9876 Переводимое число (в памяти – двоичное!)
B2 ЦЕЛОЕ(B1/10) n DIV 10
B3-B5 размножить B2 — . — . —
C2 ОСТАТ(B1;10) n MOD 10
C3-C5 размножить C2 — . — . —
D1 КОДСИМВ(“0”) Код ‘0’ (baza)
D2 СИМВОЛ(C2+$D$1) Последняя цифра
D3-D5 размножить D2 Очередные цифры
D6 СЦЕПИТЬ(D5;D4;D3;D2) Результат (s)

Тем читателям, которые захотят взглянуть на реализацию проблемы перевода чисел в компьютере IBM PC на языке процессора, могу порекомендовать доступную начинающим книгу [4].

его величество компьютер

Подведем итоги. Как оказалось, алгоритмы перевода «10 в 2» и «2 в 10» в компьютере реализуются на практике не так (или, выражаясь мягче, не совсем так), как нас учат в книгах. Но это имеет под собой вполне логичное объяснение: нас учат, как удобнее выполнять действия человеку. Что же касается компьютера, то у него «своя информатика» – двоичная, и «человеческие» десятичные алгоритмы ему не всегда подходят. С моей точки зрения, это один из примеров, который наглядно демонстрирует тот факт, что попытки «умозрительно» описывать поведение компьютера на основе повседневного (десятичного и неформального) человеческого опыта без знания фундаментальных технических подробностей могут приводить к абсолютно неправильным представлениям. К сожалению, повсеместный переход к «юзеровскому» способу обучения делает последний тезис все более актуальным.

Примечание. Кстати говоря, в учебниках все делается аккуратно и хитро: сначала идет глава с абстрактной математической теорией систем счисления, где компьютер вообще не упоминается, а затем следует глава об устройстве компьютера, в которой говорится, что методы перевода базируются на изложенной ранее теории, и поэтому мы их не рассматриваем. А что получается при формальном применении «изложенной ранее теории», мы с вами сегодня видели!

В заключение сформулируем выводы.

Компьютер реализует не перевод из одного числа в другое, а перевод строки с десятичным представлением числа в двоичное число и наоборот.
Компьютер, в основе которого лежит двоичная арифметика, использует для перевода «10 в 2» разложение по степеням числа 10, а для «2 в 10» – последовательное деление на 10. Человек поступает по-другому: для «10 в 2» пользуется делением на основание системы счисления 2, а для «2 в 10» – суммированием разложения по степеням двойки.
Для оптимизации вычислений процедуры «10 в 2» компьютер использует экономичную вычислительную схему Горнера.
(Для учителей) Всякая абстрактная теория, будучи приложенной к практике, оказывается богаче и интереснее. При этом автоматически исчезает вопрос «Зачем все это нужно?» Гармоничное единство фундаментальной теории и ее практического применения³ – не в этом ли правильный путь к построению хорошего фундаментального курса информатики?

Литература

Кэй А. Идеям тоже нужна любовь. Компьютер в школе. 1998, N 1, с.11-15.
Акулов О.А., Медведев Н.В. Информатика: базовый курс. М.: Омега-Л, 2005, 552 с.
Гейн А.Г. Информатика: Кн. для учителя: Метод. рекомендации к учеб. 10-11 кл. / А.Г. Гейн, Н.А. Юнерман. М.: Просвещение, 2001, 207 с.
Нортон П., Соухэ Д. Язык ассемблера для IBM PC. М.: Компьютер, 1992, 352 с. (См. также Приложение 2 ниже.)

¹ автор первой объектно-ориентированной среды программирования Smalltalk; многие годы Кэй работал преподавателем в школах Калифорнии

² кто не видит разницы, путь вспомнит, что 12 + 34 = 46, а «12» + «34» = «1234»!

³ современный курс информатики в школе чаще всего строится по принципу фундаментальная теория (информация, системы счисления и т.д.) – отдельно, практика (MS Office) – отдельно; в то же время, принципы работы компьютера, которые во многом являются связующим звеном того и другого – 16 часов с 7 по 11 класс, включая правила ТБ, ОС и основы ПО

Приложения

1. Файл Excel с таблицами 1 и 2.

2. Ниже приведены программы перевода на ассемблере Intel, "обернутые" в Turbo Pascal
(чтобы легче было организовать ввод/вывод).

На Free Pascal тоже так можно делать. Важно только не забыть указать, что ассемблер Intel.

Листинг 1

program p10v2_asm;
uses wincrt;
var s:string; n:integer;
begin readln(s);
      ASM LEA BX,s     {адрес переменной s в BX}
          MOV CL,[BX]  {s[0]=length(s)   }
          MOV CH,0     {    поместим в CX}
          INC BX       {BX на первый символ}
          XOR AX,AX    {0 ==> AX (результат)}
      @1: MOV DX,0Ah   {10 ==> DX}
          MUL DX       {*10}
          MOV DL,[BX]  {извлечь очередной символ}
          SUB DL,30h   {преобразовать его в число}
          ADD AX,DX    {прибавить к результату}
          INC BX       {BX + 1 - к следующему символу}
          LOOP @1      {CX - 1; если не 0 - к повторению цикла}
          MOV n,AX     {результат в переменную n}
      END;
      writeln(n)
end.

Листинг 2

program p2v10_asm;
uses wincrt;
var n:integer; s:string;
begin readln(n);
      ASM MOV AX,n     {значение переменной n в AX}
          XOR CX,CX    {0 ==> CX (счетчик цифр)}
          MOV BX,0Ah   {10 ==> BX}
      @1: XOR DX,DX    {0 ==> DX (особенности деления процессора Intel
                        см., например, Нортон П., Соухэ Д.
                        Язык ассемблера для IBM PC. М.: Компьютер, 1992)}
          IDIV BX      {AX div BX ==> AX (остаток - в DX!)}
          PUSH DX      {запомним в стек, т.к. цифры получаются "с конца"}
          INC CX       {CX + 1 - еще одна цифра}
          AND AX,AX    {результат деления в AX нулевой?}
          JNZ @1       {если нет - продолжать деление}
          LEA BX,s     {адрес переменной s в BX}
          MOV [BX],CL  {количество символов в s[0]=length(s)}
      @2: INC BX       {адрес следующего символа}
          POP AX       {достать очередной остаток из стека}
          ADD AL,30h   {сформировать цифру}
          MOV [BX],AX  {записать в переменную}
          LOOP @2      {CX - 1; если не 0 - повторять цикл}
      END;
      writeln(s);
end.

У компьютера своя информатика

Литература

Приложения