Benchmark 8 ферзей

| рубрика «Испытания» | автор st
Метки: ,

Поиск расстановки 8 ферзей на шахматной доске используется для измерения скорости вычислений ПМК. Результаты зарубежных моделей можно увидеть, например, на странице Calculator Benchmark.

В журнале "НиЖ" №10 за 1988 год был объявлен конкурс на создание подобной программы. Время счета измерялось часами, альтернативой перебору вариантов предлагался даже метод Монте-Карло. Впрочем, на времени ожидания результата это сказывалось незначительно.

Нас же интересует, насколько быстро справится с задачей новый МК-152

Пишем программу

За основу был взять вариант на Паскале по упомянутой выше ссылке.

Немного об алгоритме, который уже оптимизирован по числу вариантов перебора. Задачу решил больше 200 лет тому назад Леонард Эйлер. При отсутствии компьютера, он, тем не менее, нашел все 92 расстановки. Перед ПМК стоит задача попроще - найти первую подходящую расстановку.

Очевидно, на каждой из 8 вертикалей должно стоять по ферзю. Каждую такую расстановку можно закодировать одномерным массивом X[1],...,X[8], где X[i] - номер горизонтали для i-го ферзя.

Поскольку никакие два ферзя не могут стоять на одной горизонтали (тогда они бьют друг друга), то все X[i] различны, т.е. образуют перестановку из чисел 1..8.

procedure qbench;
var
    a: array[1..8] of integer;
    r, s, t, x, y: integer;
begin
    r := 8;
    s := 0;
    x := 0;
    repeat
        inc(x);
        a[x] := r;
        repeat
            inc(s);
            y := x;
            while y > 1 do begin
                dec(y);
                t := a[x] - a[y];
                if (t = 0) or (x - y = abs(t)) then begin
                    y := 0;
                    dec(a[x]);
                    while a[x] = 0 do begin
                        dec(x);
                        dec(a[x]);
                    end;
                end;
            end;
        until y = 1;
    until x = r;
    writeln(s);
end;

Если добавить процедуру вывода, то получаем найденную позицию:

a8 b4 c1 d3 e6 f2 g7 h5

Хотя Паскаль хорош тем, что алгоритм "читается", но к сожалению, перевод паскаль-кода в ПМК-шный совершенно неоднозначен, поэтому пришлось создать промежуточный вариант на "неструктурированном псевдопаскале". Вот он (надеюсь, профессор Вирт сейчас крепко сидит на стуле)

begin
    RA := 8;
    RB := 0;
    RC := 0;
    repeat
        inc(RC);
        a[RC] := RA;
        repeat
            inc(RB);
            RD := RC;
            L2:
            if RD - 1 <= 0 goto L1;
                dec(RD);
                R9 := a[RC] - a[RD];
                if (R9 <> 0) and (RC - RD <> abs(R9)) goto L2;
                    RB := 0;
                    dec(a[RC]);
                    L5:
                    if a[RC] <> 0 goto L2;
                        dec(RC);
                        dec(a[RC]);
                    goto L5;
                L1:
            until RB = 1;
        until RC = RA;
    stop;
end;

Теперь достаточно легко перейти к программе для МК-61/52, не претендующей на краткость. На эмуляторе МК-52 счет в реальном масштабе времени занял около получаса, после чего ПМК "завис". К счастью, у эмулятора есть "быстрый" режим, позволяющий получить результат практически мгновенно. Программа подойдет и для старых моделей МК-54/56 и Б3-34. Файл с программой для эмулятора можно скачать по ссылке в конце статьи.

00.Cx 10.ПВ  20.ИПВ  30.64   40.К|х|  50.1    60.1    70.ИПА
01.ПО 11.ПС  21.1    31.FxO 41.ИПС   51.-    61.-    71.-
02.П1 12.8   22.+    32.64   42.ИПД   52.КПС  62.БП   72.Fx=0
03.П2 13.ПА  23.ПВ   33.ПД   43.-     53.Fx=0 63.52   73.14
04.ПЗ 14.ИПС 24.ИПС  34.КИПС 44.-     54.26   64.ИПВ  74.С/П
05.П4 15.1   25.ПД   35.КИПД 45.Fx=0  55.ИПС  65.1
06.П5 16.+   26.ИПД  36.-    46.26    56.1    66.-
07.П6 17.ПС  27.1    37.П9   47.0     57.-    67.Fx=0
08.П7 18.ИПА 28.-    38.Fx0 48.ПВ    58.ПС   68.20
09.П8 19.КПС 29.Fx0 39.47   49.КИПС  59.КИПС 69.ИПС

Инструкции по запуску: В/0, С/П

После останова в регистрах Р1..Р8 координаты по вертикали i-го ферзя (стоящего на i-й горизонтали).

Контрольный запуск на эмуляторе выдает следующую комбинацию: Р1=8, Р2=4, Р3=1, Р4=3, Р5=6, Р6=2, Р7=7, Р8=5, что соответствует расстановке на шахматной доске: Фa8, Фb4, Фc1, Фd3, Фe6, Фf2, Фg7, Фh5

Программу, видимо, можно подсократить в теле циклов, но вряд ли это заметно скажется на времени счета для МК-52.

Тестируем МК-152

Испытания провел AtH на своём МК-152.

Вышеприведенная программа для ПМК без изменений выполняется на МК-152 ровно 9 секунд. Любопытно было бы её переписать с учётом особенностей компактного языка (циклы по FL0/FL1, автоинкремент по КИП5/6) и огромного количества регистров памяти в МК-152.

А пока AtH подсократил программу на восемь шагов (с регистром B также имеет смысл разобраться, он из счётчика превратился во флаг) и вот, что получилось:

00.Cx   01.ПB   02.9   03.П0   04.Cx   05.КП0  06.ИП0 07.Fx=0 08.04   09.ПС
10.ИПС  11.1    12.+   13.ПС   14.8    15.КПС  16.ИПВ 17.1    18.+    19.ПВ
20.ИПС  21.ПД   22.ИПД 23.1    24.-    25.Fx0 26.56  27.Fx0 28.56   29.ПД
30.КИПС 31.КИПД 32.-   33.Fx0 34.42   35.К|x| 36.ИПС 37.ИПД  38.-    39.-
40.Fx=0 41.22   42.0   43.ПВ   44.КИПС 45.1    46.-   47.КПС  48.Fx=0 49.22
50.ИПС  51.1    52.-   53.ПС   54.БП   55.44   56.ИПВ 57.1    58.-    59.Fx=0
60.16   61.ИПС  62.8   63.-    64.Fx=0 65.10   66.С/П

Время счёта по новой версии программы на МК-152 — 8 секунд.

Буквальный перевод кода для калькулятора Casio FX-4500PA (программа по первой ссылке, переменные S, Y и X хранятся в регистрах 9, A и B) без оптимизации под МК-152 даёт результат 876 (количество перебранных узлов дерева вариантов, это же число показывает и программа на бейсике - самая первая в списке программ по упомянутой в начале ссылке) и требует 13 секунд:

00.Cx   01.1  02. 2   03.П0   04.Cx   05.КП0  06.ИП0 07.Fx=0 08.04   09.8
10.ИПB  11.-  12.Fx0 13.56   14.ИПB  15.1    16.+   17.ПB   18.8    19.КПB
20.ИП9  21.1  22.+    23.П9   24.ИПB  25.ПA   26.ИПA 27.1    28.-    29.ПA
30.Fx0 31.09 32.КИПB 33.КИПA 34.-    35.Fx0 36.44  37.K|x| 38.ИПB  39.ИПA
40.-    41.-  42.Fx=0 43.26   44.КИПB 45.1    46.-   47.КПB  48.Fx=0 49.20
50.ИПB  51.1  52.-    53.ПB   54.Fx=0 55.44   56.ИП9 57.С/П

Но на этом тесты не закончились. AtH воспользовался своим старинным другом - МК-56, заменил в нашей первой программе для МК-52 оператор K|x| на Fx<0 nn /—/ и запустил программу. ПМК так надолго "ушел в себя", что даже появились опасения, не зациклился ли он? Но вот и всё, ПМК досчитал! Три часа девять минут (189 минут, то есть 11340 секунд).

Получается, что МК-152 быстрее МК-56 примерно в 1300 раз (та же версия программы выполнялась на МК-152 за девять секунд). То же самое можно сказать и относительно всех старых моделей.

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

Результаты

Итак, время счета - 8 секунд. Это означает, что МК-152:

  • примерно в 1300 раз быстрее старых моделей (Б3-34, МК-54/56, МК-61/52)
  • находится на уровне следующих зарубежных моделей:
    • 9.07 сек: FX-9860G Formula / Structured / Matrix / Fast Mode x1.9 (20->80 MHz)
    • 8.80 сек: FX-9860GS Formula / Structured / Matrix / Fast Mode x1.9 (20->80 MHz)
    • ~8.3 сек: TI-Nspire Formula / Structured / List / Ver.1.2 CAS
  • оставил далеко позади такие популярные модели, как:
    • 34.2 сек: TI-85 Formula / List / Turbo x3.3
    • 53.1 сек: TI-89 Formula / Structured / List / HW2 / Turbo x2.0
    • ~67 сек: HP-50G UserRPL / Fast Mode x1.3 (75->203 MHz)

Результат по маркам TI и HP несколько неожиданный. TI-89 - современная популярная марка, а HP-50g - практически новая модель (при частоте процессора 203 МГц). Наиболее очевидное объяснение - язык ПМК низкоуровневый, близок к ассемблерам (но фактически выполняется в рамках встроенного интерпретатора), тогда как входные языки вышеназванных флагманов - интерпретируемые и высокого уровня.

Обновление от 16/12/2007.

По итогам обсуждения на форуме HP, наш результат включен в общий список. Как можно видеть, результат находится на пределе возможностей основных входных языков других ПМК. Быстрее исполняются разве что скомпилированные C/Pascal/Assembler-программы и скомпилированный байткод для OPL/Lua на более мощных устройствах, например, Psion, близких уже к КПК, а не к ПМК.

Спасибо всем участникам теста!

Обновление от 23/10/2013.

Новый ПМК HP Prime с программой на встроенном языке типа "паскаль-скрипт" проходит тест всего за 0,4 сек! Впечатляющая скорость языка высокого уровня на уровне мнемокода и ассемблеров старых моделей.

  • 0.55 HP-41CL Mcode / Turbo20 Mode x19.6
  • 0.4 HP-Prime Formula / List
  • 0.385 PC-1360 Assembly / SC61860 @ 1.6 MHz / Turbo x2.1