2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Оптимальная по размеру спиральная матрица
Сообщение24.12.2017, 02:26 


24/12/17
16
Здравствуйте. Возможно мой вопрос на фоне остальных тем выглядит, крайне несерьёзным и мелким, но всё же. Есть задача - написать на паскале программу(без использования ассемблерных вставок, но прерывания дозволены) для заполнения матрицы размерностью от 2 до 9 по спирали, да не просто написать(это было бы слишком легко), а чтоб исполняемый файл(один из компиляторов паскаля под DOS) вышел как можно меньше по размеру. Меньше 3000 байт. Рекорд говорят был где-то в районе 1200 байт. Я написал самый оптимизированный алгоритм по размерам, какой только мог придумать. Сейчас с настроенными не по дефолту опциями компилятор выходит 2704 байта. И... вот тут я не знаю, что делать дальше. То ли в алгоритме что-нибудь ещё поупрощать и позаменять(есть мысль использовать одну переменную типа word для координат матрицы и обращаться к ним через функции Lo и Hi), То ли я что-то не знаю на счёт компилятора(может есть более эффективный что работает под DOS?) или уже как-то пытаться ввод заменить(Препод сказал, что можно использовать прерывания, но с ними при замене ввода и вывода программа становится больше. Подумываю об использовании процедуры interrupt, но нигде не могу найти толковой документации с примерами, как ей пользоваться этой директивой)? Вообще есть ли возможность имея в руках лишь DOSbox, компилятор и редактор кода - настрочить программу на паскале, чей исполняемый файл будет хотя бы меньше 2000 байт?
код: [ скачать ] [ спрятать ]
Используется синтаксис Pascal
program spiral;
var
 m: array [1..9, 1..9] of word;
 n: byte;
 i: byte;
 j: byte;
 c: byte;
 l: byte;
 s: shortint;
 t: byte;
 p: ^byte;
begin
 readln(n);
 l := n;
 t := n;
 s := 1;
 i := 1;
 p := @j;
 repeat
  p^ := p^ + s;
  c := c + 1;
  if p^ = t then begin
   if p = @j
    then begin
     p := @i;
     l := l - 1;
    end else begin
     p := @j;
     s := -s;
    end;
   t := p^ + s*(l);
  end;
  m[i,j] := c;
 until l = 0;
 for i:=1 to n do begin
  for j:=1 to n do write(m[i,j]:3);
  writeln;
 end;
end.
 

 Профиль  
                  
 
 Re: Оптимальная по размеру спиральная матрица
Сообщение24.12.2017, 06:49 


24/12/17
16
Немного подумал над прерываниями и опциями компилятора, так что смог ужать до 2080 байт, но всё ещё не преодолён порог в 2000 байт. Есть какие-нибудь идеи, что в обновлённом коде можно сделать, чтобы его исполняемый файл на выходе ещё сильнее ужать?
код: [ скачать ] [ спрятать ]
Используется синтаксис Pascal
program spiral;
uses dos;
var
 m: array [1..9, 1..9] of word;
 n: word;
 i: word;
 j: word;
 c: word;
 l: word;
 s: integer;
 t: word;
 p: ^word;
 r: registers;
begin
 with r do begin
  ah := 8;
  msdos(r);
  n := r.al - 48;
  ah := 2;
 end;
 l := n;
 t := n;
 s := 1;
 i := 1;
 p := @j;
 repeat
  p^ := p^ + s;
  c := c + 1;
  if c = t then begin
   if p = @j
    then begin
     p := @i;
     l := l - 1;
    end else begin
     p := @j;
     s := -s;
    end;
   t := c + l;
  end;
  m[i,j] := c;
 until l = 0;
 for i:=1 to n do begin
  for j:=1 to n do with r do begin
   dl := m[i,j] div 10 + 48;
   msdos(r);
   dl := m[i,j] mod 10 + 48;
   msdos(r);
   dl := 32;
   msdos(r);
  end;
  with r do begin
   dl := 13;
   msdos(r);
   dl := 10;
   msdos(r);
  end;
 end;
end.
 

 Профиль  
                  
 
 Re: Оптимальная по размеру спиральная матрица
Сообщение24.12.2017, 11:43 
Заслуженный участник


26/05/14
981
1. Найдите компилятор паскаля с поддержкой формата COM (Turbo 1? Turbo 3?). Обычный формат исполнимых файлов в DOS/Window - EXE. Ранние компиляторы умели компилировать в COM. Вы выиграете на размере заголовка исполнимого файла - у формата COM он отсутствует. Кроме того в COM нет разделения на сегменты - не будет потерь на их выравнивание.
2. Получите ассемблерный код того что вы скомпилировали. Или при помощи опций компилятора или при помощи декомпилятора. Посмотрите на ассемблер, могут возникнуть идеи.
3. Добавьте в массив нулевые индексы. Они не будут использоваться, а код адресации может стать компактней.
4. Замените массив на одномерный с адресной арифметикой. Выиграете на адресации.
5. Чтобы вписать спираль нужно только 81 операция. Может их записать напрямую без циклов и т.п.
6. Нужна ли вам спираль в памяти? Сразу печатайте нужный выход. Вариантов выходов только девять. Их можно вложить друг в друга матрёшкой.

 Профиль  
                  
 
 Re: Оптимальная по размеру спиральная матрица
Сообщение25.12.2017, 20:09 


24/12/17
16
Последовав некоторым вашим советам , я смог сжать программу до 1952 байт. Что ещё можно сделать с этим кодом? Может есть способ от этого флага избавиться без увеличения кода? Или mod с divом убрать? Я просто пока больше способов уменьшить не вижу... Может я вообще не тот алгоритм использую. Всё ещё не понятно, как можно было получить 1200 байт на паскаел в екзешнике.
код: [ скачать ] [ спрятать ]
Используется синтаксис Pascal
uses dos;
var
 m: array [1..81] of word;
 s: integer;
 r: registers;
 f: boolean;
begin
 with r do begin
  ah := 7;
  msdos(r);
  di := al - 48;
  ah := 2;
  bx := di;
  es := di;
  s := 1;
  repeat
   cx := cx + 1;
   si := si + s;
   if cx = es then begin
     if abs(s) = 1
      then begin
       s := di;
       bx := bx - 1;
      end else begin
       s := 1;
       f := not f;
      end;
    if f then s := -s;
    es := cx + bx;
   end;
   m[si] := cx;
  until bx = 0;
  repeat
   bx := bx + 1;
   dl := m[bx] div 10 + 48;
   msdos(r);
   dl := m[bx] mod 10 + 48;
   msdos(r);
   dl := 32;
   msdos(r);
   if bx mod di = 0 then begin
   dl := 10;
   msdos(r);
   end;
 until bx = cx;
 end;
end.
 

 Профиль  
                  
 
 Re: Оптимальная по размеру спиральная матрица
Сообщение25.12.2017, 20:21 
Заслуженный участник


26/05/14
981
1, 2, 5 и 6 пробовали?

 Профиль  
                  
 
 Re: Оптимальная по размеру спиральная матрица
Сообщение25.12.2017, 20:28 


24/12/17
16
slavav в сообщении #1278676 писал(а):
1, 2, 5 и 6 пробовали?

1 - Нужен имеено exe. Но попробую первой или третьей версией turbo скомпилировать. Может меньше выйдет)
2 - Дизассемблерировать ещё не пробовал. Надо будет попробовать
5 - Это мне ничего не даст, только разве, чтобы матрица 9 лишь на экран выводилась или меньшего порядка, а так если писать то if выйдет куда больше чем в нынешнем коде и программа точно будет за 2000 байт.
6 - Да. Спираль в памяти нужна. Препод чётко указала на это и даже тип определил чтобы равны были все. Массив word. В адресации полная свобода действий, ведь два индекса или один сути не меняет.

 Профиль  
                  
 
 Re: Оптимальная по размеру спиральная матрица
Сообщение25.12.2017, 21:02 
Заслуженный участник


26/05/14
981
1 - отменяется. Ранние компиляторы только COM и умеют. Вам нужен самый первый который будет выдавать EXE. Это, вероятно, 5.5. Нужно пересмотреть опции компилятора и директивы в коде. Turbo Pascal понимает такие штуки: {$R-}.
2 - обязательно. Сейчас вы не знаете сколько занимает код, сколько накладные расходы. А это нужно знать чтобы знать куда нажимать.
7. Попытайтесь придумать явную функцию, которая по индексу с массиве (или по паре индексов в двумерном массиве) явно вычисляет число для этой ячейки. Это сложно (квадратные уравнения), но может дать эффект.
8. Не уверен, но ваш массив может занимать место в EXE. Выделите его динамически (GetMem какой-нибудь). Или поместите на стек.

 Профиль  
                  
 
 Re: Оптимальная по размеру спиральная матрица
Сообщение25.12.2017, 21:06 
Заслуженный участник


09/05/12
25179
slavav в сообщении #1278686 писал(а):
1 - отменяется. Ранние компиляторы только COM и умеют. Вам нужен самый первый который будет выдавать EXE. Это, вероятно, 5.5.
Нет, первый - 4.0.

 Профиль  
                  
 
 Re: Оптимальная по размеру спиральная матрица
Сообщение25.12.2017, 21:11 


24/12/17
16
slavav в сообщении #1278686 писал(а):
1 - отменяется. Ранние компиляторы только COM и умеют. Вам нужен самый первый который будет выдавать EXE. Это, вероятно, 5.5. Нужно пересмотреть опции компилятора и директивы в коде. Turbo Pascal понимает такие штуки: {$R-}.
2 - обязательно. Сейчас вы не знаете сколько занимает код, сколько накладные расходы. А это нужно знать чтобы знать куда нажимать.
7. Попытайтесь придумать явную функцию, которая по индексу с массиве (или по паре индексов в двумерном массиве) явно вычисляет число для этой ячейки. Это сложно (квадратные уравнения), но может дать эффект.
8. Не уверен, но ваш массив может занимать место в EXE. Выделите его динамически (GetMem какой-нибудь). Или поместите на стек.


Не подскажите где можно взять хороший дизассемблер под dos? А то гугление мне выдало только нерабочие версиии IDA)

 Профиль  
                  
 
 Re: Оптимальная по размеру спиральная матрица
Сообщение25.12.2017, 21:25 
Заслуженный участник


26/05/14
981
Turbo Debugger
TPU2ASM

 Профиль  
                  
 
 Re: Оптимальная по размеру спиральная матрица
Сообщение25.12.2017, 21:32 


24/12/17
16
slavav в сообщении #1278703 писал(а):
Turbo Debugger
TPU2ASM

Спасибо. Сейчас попробую

 Профиль  
                  
 
 Re: Оптимальная по размеру спиральная матрица
Сообщение25.12.2017, 22:46 
Заслуженный участник


20/08/14
11798
Россия, Москва
Вы меня простите, но компиляция в TP7 следующей простейшей программы
Используется синтаксис Pascal
program test;
begin
end.
даёт 1504 байта. С отключенной отладкой и прочим. Т.е. разбираться что там не так со спиралью или вызовом функций вывода символов нет смысла, сначала надо добиться от компилятора малого размера пустой программы.
Просмотр кода удобно делать HIEW. Она есть бесплатная в деморежиме (коего хватает за глаза).

 Профиль  
                  
 
 Re: Оптимальная по размеру спиральная матрица
Сообщение25.12.2017, 23:39 


24/12/17
16
Dmitriy40 в сообщении #1278730 писал(а):
Вы меня простите, но компиляция в TP7 следующей простейшей программы
Используется синтаксис Pascal
program test;
begin
end.
даёт 1504 байта. С отключенной отладкой и прочим. Т.е. разбираться что там не так со спиралью или вызовом функций вывода символов нет смысла, сначала надо добиться от компилятора малого размера пустой программы.
Просмотр кода удобно делать HIEW. Она есть бесплатная в деморежиме (коего хватает за глаза).


Я изучив exe-шник - обнаружил длиннющую строку с информацией о borland pascal, права, копирайт и т.д. Она же в принципе не нужна, но при этом я не могу её безболезненно напрямую удалить. Есть какой-то способ от неё избавиться?

 Профиль  
                  
 
 Re: Оптимальная по размеру спиральная матрица
Сообщение26.12.2017, 00:20 
Заслуженный участник


20/08/14
11798
Россия, Москва
Ну прям уж длиннющую, у меня она меньше 80 байтов, это погоды не сделает.
Гораздо интереснее как заставить компилятор не подключать код разбора строки параметров и перехвата векторов прерываний (если я правильно понял что это), это буквально первый же CALL прямо по Entry point.
Я пока не знаю.

-- 26.12.2017, 00:42 --

Между прочим эта задача уже решалась 6 лет назад, получили 1826 байтов - http://www.cyberforum.ru/turbo-pascal/thread420145.html

 Профиль  
                  
 
 Re: Оптимальная по размеру спиральная матрица
Сообщение26.12.2017, 00:53 


24/12/17
16
[quote="Dmitriy40 в [url=http://dxdy.ru/post1278755.html#p1278755]
Между прочим эта задача уже решалась 6 лет назад, получили 1826 байтов - http://www.cyberforum.ru/turbo-pascal/thread420145.html[/quote]
Только там ассемблерные вставки) А их использовать нельзя. только модуль dos, только хардкор. Если бы их можно было бы использовать я бы давно программу меньше 1900 написал бы.

-- 26.12.2017, 01:02 --

Последние вести с полей. Исправив немного условие в выводе я уменьшил программу до 1939 байт.
код: [ скачать ] [ спрятать ]
Используется синтаксис Pascal
{$S-}
uses dos;
var
 m: array [1..81] of word;
 s: integer;
 r: registers;
 f: boolean;
begin
 with r do begin
  ah := 7;
  msdos(r);
  di := al - 48;
  ah := 2;
  bx := di;
  es := di;
  s := 1;
  repeat
   cx := cx + 1;
   si := si + s;
   if cx = es then begin
     if abs(s) = 1
      then begin
       s := di;
       bx := bx - 1;
      end else begin
       s := 1;
       f := not f;
      end;
    if f then s := -s;
    es := cx + bx;
   end;
   m[si] := cx;
  until bx = 0;
  repeat
   bx := bx + 1;
   dl := m[bx] div 10 + 48;
   msdos(r);
   dl := m[bx] mod 10 + 48;
   msdos(r);
   if bx mod di = 0
    then dl := 10
    else dl := 32;
   msdos(r);
 until bx = cx;
 end;
end.
 

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 30 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group