Оберон-клуб «ВЄДАsoft»

Твердыня модульных языков
Текущее время: 28 мар 2024, 18:30

Часовой пояс: UTC + 2 часа




Начать новую тему Ответить на тему  [ Сообщений: 72 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8  След.
Автор Сообщение
СообщениеДобавлено: 01 июн 2013, 05:39 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
А вот и способ вычислить NumIters = (B - A) DIV Step +1 без перехода к большей разрядности.

Сначала пусть будет шаг положительный и A<=B. В каких случаях возникает переполнение? Только если А и В имеют разные знаки (это необходимое условие переполнения, но не достаточное). Поэтому проводим дальнейшие рассуждения для A<0 и B>=0.
Что можно сказать о величине NumIters1= (B DIV Step) – (A DIV Step) ? Насколько она отличается от NumIters? Можно записать NumIters = (B + (-A)) DIV Step +1, где (–А) величина положительная (неважно что ( –А) может не оказаться в диапазоне Т, мы не собираемся программировать (-А), мы пока рассуждаем математически).

NumIters может либо совпадать с NumIters1, либо быть на 1 или 2 больше. Потому что +1 есть по формуле, при вычислении NumIters в самом крайнем случае остатки B MOD Step и (-A) MOD Step в сумме дадут Step-1+Step-1=2*Step-2, что при делении DIV Step дает лишнюю единицу, но не более. Если А MOD Step=0, то NumIters= NumIters1+1, потому что максимум, что даст B MOD Step = Step-1 (при делении DIV Step этот остаток отбросится и нужно добавить только +1 по формуле).
Если А MOD Step #0 (на самом деле >0), то A DIV Step преобразует этот остаток в лишнюю отрицательную единицу, потому что DIV в Обероне округляет всегда влево. А вот нужна ли еще какая-то коррекция нужно вычислить.
Для А не кратного Step имеем (-A) MOD Step+A MOD Step=Step, поэтому при вычислении NumIters остатки B MOD Step и (-A) MOD Step в сумме равны B MOD Step+(Step- А MOD Step), что является величиной положительной и даст лишнюю единицу, только если B MOD Step+(Step - А MOD Step)>=Step. Сокращаем обе части последнего неравенства на Step, переносим одно из слагаемых в другую часть, получаем В MOD Step >= A MOD Step. При выполнении этого условия NumIters = NumIters1+1.
Заметим ,что если А MOD Step=0, то условие В MOD Step >= A MOD Step заведомо выполняется, так что можно не рассматривать отдельно А MOD Step=0 (ведь в этом случае тоже нужно прибавить 1 ). Окончательно имеем:
Код: "OBERON"
  1. (* A < 0 , B >=0, Step > 0 *)
  2. NumIters1 := (B DIV Step)(A DIV Step);
  3. IF В MOD Step >= A MOD Step THEN
  4. NumIters := NumIters1+1
  5. ELSE
  6. NumIters := NumIters1
  7. END;
Переполнения при таком вычислении не возникает. Вернее оно может возникнуть при вычислении суммы или прибавлении 1, но это не страшно, ведь мы не делим переполненное.
Аналогично получим для отрицательного шага
Код: "OBERON"
  1. (* A >= 0 , B <0, Step < 0 *)
  2. NumIters1 := (A DIV (-Step))(B DIV (-Step));
  3. IF A MOD (-Step) >= B MOD (-Step) THEN
  4. NumIters := NumIters1+1
  5. ELSE
  6. NumIters := NumIters1
  7. END;
Но здесь есть одна тонкость. Если Step=MIN(T), то противоположной ему величины в данном типе нет. Значит случай Step = MIN(T) нужно рассмотреть отдельно, предыдущий фрагмент программы только для случая Step # MIN(T) . Поскольку у нас при отрицательном шаге A>=B, то цикл выполнится хотя бы 1 раз для id=A. После этого он либо завершится, либо выполнится еще 1 раз, но не более. И этот дополнительный раз возможен только при А>=0. Получим такой фрагмент
Код: "OBERON"
  1. (* A >= B , Step = MIN(T) *)
  2. IF (A>=0) & (A + Step >=B) THEN NumIters :=2 ELSE NumIters := 1 END;
Но на самом деле тут даже и не понадобится вычислять количество итераций. Сравнение с нулем мы считаем эффективной операцией (а так ли это для всех разрядностей?), даже при сравнении на неравенство. Поэтому не вводим в этом случае вспомогательную переменную, а просто прекращаем цикл UNTIL id < 0.

Это пока только теоретические (математические) рассуждения, на практике не тестировал.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 04 июн 2013, 00:40 
Не в сети
Аватара пользователя

Сообщения: 1019
Откуда: Днепропетровская обл.
Олег, посмотри, пожалуйста, может это пригодится.

В сборке XDev в подсистеме Multi есть модули CardAsm и Cardinals, которые реализуют элементарные операции над типами Cardinal (32 бит) и LongCard (64 бит). В Cardinals есть процедуры:
Код: "OBERON"
  1. PROCEDURE Div (c, m: LongCard): LongCard;
  2. PROCEDURE Div128 (cLo, cHi, m: LongCard; OUT qLo, qHi: LongCard);
которые реализуют беззнаковое деление 64-битных чисел, а также 128-битного на 64-битное.

Вот. А я эти процедуры сперва и не заметил. :oops:

У модуля Cardinals есть зависимость от модуля LibFmtrs, на котором завязаны некоторые процедуры. Я убрал эту зависимость и пересобрал модуль, чтобы не тянуть в XDev новую подсистему, для реализации FOR возможностей должно хватить вплоть до 64-битных типов. :)


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 08 июн 2013, 14:17 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
Zorko писал(а):
Олег, посмотри, пожалуйста, может это пригодится.
В сборке XDev в подсистеме Multi есть модули CardAsm и Cardinals, которые реализуют элементарные операции над типами Cardinal (32 бит) и LongCard (64 бит). В Cardinals есть процедуры:
Код: "OBERON"
  1. PROCEDURE Div (c, m: LongCard): LongCard;
  2. PROCEDURE Div128 (cLo, cHi, m: LongCard; OUT qLo, qHi: LongCard);
которые реализуют беззнаковое деление 64-битных чисел, а также 128-битного на 64-битное.
Прекрасно, Олег! Это действительно пригодится.
В случае положительного шага (в обозначениях процедуры OPP.StatSeq z^.conval^.intval > 0) можно вычислить количество итераций как
Код: "OBERON"
  1. L := MC.Div (y^.conval^.intval - apar^.conval^.intval, z^.conval^.intval)+1; (* NumIters := (B-A) DIV Step +1 *)
где MC - алиас модуля MultiCardinals, переменная L : LONGINT (а лучше объявить L : MC.LongCard).
При любых значениях величин А и В (даже когда они станут 64-битными), мы не получим переполнение в y^.conval^.intval - apar^.conval^.intval. Вернее получим, но отрицательное число, возникшее в результате такого переполнения, будет воспринято процедурой MC.Div как соответствующее положительное беззнаковое и результат деления будет верным (если параметры 64-разрядные, сейчас для этого требуется LONG). Процедура вернет частное в виде 64-разрядного числа, потом прибавим 1 и получим количество итераций.
Если рассматривать L как 64-разрядное знаковое (тип LONGINT BlackBox'a), L <=0 "кодирует" количество итераций 2^64 + L (в частности L=0 означает количество повторений 2^64, что вряд ли кому понадобится на практике, но теоретически возможно). Такое большое количество повторений (в диапазоне MAX(LONGINT)+1..2^64 ) возможно только для 64-битной переменной цикла.
Положительное L задает количество итераций непосредственно (L="количество итераций", без всякого кодирования). Для 1, 2, 4-байтовых параметров цикла возможен только этот случай. Но для генерации программы на Си необходимо "втиснуть" значение L в то же количество байтов, что и переменная цикла FOR. А для этого нужно "закодировать" слишком большие для данного типа положительные величины L как отрицательные числа этого типа (а значения 2^8, 2^16,2^32 для соответствующего типа "закодировать" нулем). К счастью, это легко сделать - нужно только взять 1,2 или 4 младших байта, отбросив всё остальное.
Как видим, преобразование L для размещения в дереве зависит от разрядности параметра цикла, а не только от самого значения L. Так, например, 255 должно превратиться в "-1" для 8-битного параметра, но остаться неизменным для больших типов. В предлагаемых ранее процедурах OPB.NewUnsignedConst и SetUnsignedType это не учтено! :oops:
Поэтому необходимы другие процедуры. Введем, например, процедуру NewShortConst (uintval:LONGINT;size:INTEGER). Она должна создать в дереве новую константу, втиснув ее в size байтов. А непосредственно само "отбрасывание лишних битов" будет делать процедура SetShortType(node: OPT.Node;size:INTEGER). Может быть кто-то предложит более удачные имена.
Итак, в модуле Ofront.OPB создадим
Код: "OBERON"
  1. PROCEDURE SetShortType(node: OPT.Node;size:INTEGER);
  2. (* превращает беззнаковую константу в знаковую размером size байтов *)
  3. VAR v: LONGINT;
  4. BEGIN v := node^.conval^.intval;
  5. (* наибольший случай рассмотрим первым, чтобы не возникло
  6. переполнение в (2*OPM.MaxLInt+2), когда LInt - 64битный *)
  7. (* SHORT (v...) и LONG уберем, когда будут 64битные типы*)
  8. IF size = 8 THEN
  9. (* ничего кодировать не нужно*)
  10. (* node^.typ := тип 64-разрядный, пока такой константы нет *)
  11. ELSIF size = OPM.LIntSize THEN
  12. IF size =4 THEN (* ничего не надо делать, т.к. уже выполнили SHORT(uintval) *)
  13. (* это условие уберем, когда будут 64битные типы *)
  14. ELSE node^.conval^.intval := SHORT(v MOD (2*LONG(OPM.MaxLInt)+2));
  15. END;
  16. node^.typ := OPT.linttyp;
  17. ELSIF size = OPM.IntSize THEN
  18. node^.conval^.intval := SHORT(v MOD (2*OPM.MaxInt+2));
  19. node^.typ := OPT.inttyp;
  20. ELSIF size = OPM.SIntSize THEN
  21. node^.conval^.intval := SHORT(v MOD (2*OPM.MaxSInt+2));
  22. node^.typ := OPT.sinttyp;
  23. ELSE err(203); node^.typ := OPT.sinttyp; node^.conval^.intval := 1
  24. END;
  25. END SetShortType;
  26.  
  27. PROCEDURE NewShortConst*(uintval: LONGINT;size:INTEGER): OPT.Node;
  28. (* создание новой знаковой константы длиной size байтов, по соответствующей
  29. (кодируемой той же комбинацией битов) беззнаковой константе uintval *)
  30. VAR x: OPT.Node;
  31. BEGIN
  32. x := OPT.NewNode(Nconst); x^.conval := OPT.NewConst();
  33. x^.conval^.intval := SHORT(uintval); (* пока ставим SHORT. Уберем, когда введем 64битность *)
  34. SetShortType(x,size); RETURN x
  35. END NewShortConst;
Пока нужны всевозможные "подпорки" SHORT и LONG, т.к. Ofront для хранения целых в узлах дерева (навроде x^.conval^.intval ) использует 32-битные поля. Когда эти поля станут 64битными, "подпорки" уберем, но, возможно, при этом понадобится что-то дополнительно ввести, т.к. работа будет на границе типа.
Теперь вычисление количества итераций будем производить так:
Код: "OBERON"
  1. IF z^.conval^.intval > 0 THEN (* подготовим выражение "кол-во повторений" *)
  2. IF e THEN
  3. L:=MC.Div (LONG(y^.conval^.intval) -apar^.conval^.intval, z^.conval^.intval)+1;
  4. x := OPB.NewShortConst( L,id^.typ^.size);
А при отрицательном шаге так:
Код: "OBERON"
  1. ELSIF z^.conval^.intval < 0 THEN (* в зависимости от знака Step*)
  2. IF e THEN
  3. L:=MC.Div (LONG(apar^.conval^.intval) - y^.conval^.intval, -LONG(z^.conval^.intval))+1;
  4. x := OPB.NewShortConst( L,id^.typ^.size);
Обратите внимание на LONG, необходимый для приведения параметров к 64-битной разрядности. Если шаг положительный, то LONG(z^.conval^.intval) не нужно, z^.conval^.intval будет расширено нулями при передаче параметра само собой. А вот "-LONG(z^.conval^.intval)" необходимо писать именно так, потому что (-z^.conval^.intval = z^.conval^.intval), если z^.conval^.intval = MIN(INTEGER). Когда у нас будет 64-битный тип, случай шаг=MIN(LONGINT) нужно будет учесть особо, способом, указанным в конце предыдущего сообщения.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 25 авг 2013, 20:35 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
Вернувшись к фористике после почти 3-х месячного перерыва, обнаружил, что с ходу в тему не «въехать» :( Перечитал свои посты (как хорошо, что писал подробно!), но тонкости работы Ofront пока не вспомнил. Что же, пока напишу про классификацию FOR, напишу что на основе этой классификации я собираюсь реализовать в ближайшее время. Возможно у кого-то будут полезные мысли уже на этом этапе.

Итак, в процедуре OPP.StatSeq необходимо сначала прочитать заголовок цикла FOR n:= A TO B BY Step , проанализировать «константность» и диапазоны величин A,B, их соотношение со Step. Также сразу расчитаем точное количество итераций NumIters = (B - A) DIV Step +1, если А и В — константы. Если же это не константы, то расчитаем точную верхнюю границу количества итераций MaxIters по этой же формуле, взяв вместо А величину MIN(T), а вместо B величину MAX(T). На основании всего этого установим флажки. А вот потом, по флажкам и по значению NumIters и MaxIters будем генерировать тот или иной вариант цикла.

Какие же случаи циклов возможны? По количеству итераций получим такие важные варианты:

1) Цикл не выполняется ни разу , т.е. NumIters =0 . Это можно заключить только в случае, когда A и B -константы. Весь оператор цикла при этом обращается в ничто, не нужно даже присваивания n:=A, поэтому флажок будет id=NIL. Во всех иных случаях id указывает на переменную цикла, т. е. id # NIL.

2)Цикл выполнится ровно 1 раз, т.е. NumIters=1 . Это тоже можно заранее определить только если A и B - константы. В этом случае оператор цикла превращается в «n:=A; тело цикла». Флажками пусть будет e & (L=1).
Вообще, пусть e=TRUE означает, что в L закодировано точное количество итераций. «Закодировано» в том смысле, как это указано в предыдущем посте— в знаковой 64-битной переменной L закодировано беззнаковое значение из диапазона 1..2^64. В частности L=0 означает 2^64 итераций. Понимаю, что это очень много и на практике фактически означает зацикливание. Но пусть тот, кто напишет такой диапазон для FOR, и получит зацикливание, а не пропуск цикла (для пропуска есть флажок из предыдущего пункта).
А вот e=FALSE пусть значит, что в L закодировано число MaxIters.

3)Цикл выполнится не более 1 раза, т. е. 0 или 1 раз. Это получится, если либо А либо В — не константа и MaxIters = 1. Цикл в этом случае транслируется в «n:=A; IF n <= B THEN тело цикла END»
С учетом вышесказанного флажком будет ~e & (L=1). Но чтобы отличить этот случай от последующих введем еще флажок obj=NIL (что значит «цикл может не выполнится ни разу»).

4)Цикл заведомо выполнится 1 раз. Это происходит при условии А=MIN(T) или B=MAX(T). Флажок пусть будет obj#NIL. Из общей схемы цикла в этом случае удаляется проверка IF A<=B THEN...

5)Во всех остальных случаях, задаваемых флажками (L#1)&(obj=NIL), применяется общая схема.


Другое направление оптимизации — отбрасывание вспомогательной переменной в случае, если вместо нее можно использовать саму переменную цикла. Очевидно, что эта оптимизация имеет смысл только в случаях 4 и 5. В случаях 1-3 этой вспомогательной переменной уже нет. Но об этом в следующий раз.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 26 авг 2013, 12:35 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
Займемся теперь реализацией цикла FOR без вспомогательной переменной-счетчика. Вместо нее будем использовать саму переменную цикла. Очевидно, что эта оптимизация имеет смысл только в случаях 4 и 5. В случаях 1-3 этой вспомогательной переменной уже нет.

Флажком служит переменная t. Если t=id, то вспомогательной переменной нет, вместо нее применяется id (сам параметр цикла). Если t#id, то эта переменная t как раз и указывает на вспомогательную переменную-счетчик.
Однако, в каких случаях возможна эта оптимизация и в какие операторы должен транслироваться FOR?

Будем считать, что на любой платформе сравнение параметра цикла с нулем является эффективной операцией. Ну, в крайнем случае, настолько эффективной, чтобы оправдать отбрасывание вспомогательной переменной. Значит мы можем применить такую оптимизацию, если условие выхода из цикла удастся записать как «UNTIL n ? 0», где операция «?» - любая из операций сравнения (=, #, < ,> ,<= ,>= ). Изменение переменной цикла лучше делать после тела цикла, тогда условие «UNTIL n ? 0» означает «n вышло за пределы диапазона A..B», вернее даже «n впервые вышло за пределы этого диапазона».
Код: "OBERON"
  1. REPEAT
  2. тело цикла
  3. INC(n, Step);
  4. UNTIL n ? 0;
В крайнем случае можно делать инкремент и до тела цикла. В этом случае перед циклом понадобится дополнительный декремент, чтобы «впрыгнуть внутрь» - к телу цикла. Этот декремент можно спрятать в присваивание n:=A,если A – константа (правда тогда усложнится условие IF A <=B , что можно также подправить, если и В-константа). Это менее эффективно, но даст возможноть выполнить отбрасывание вспомогательной переменной для условия «n – это последнее значение в диапазоне, которое должно быть обработано», если такое условие можно записать как сравнение с нулем.
Код: "OBERON"
  1. DEC(n,Step);
  2. REPEAT
  3. INC(n, Step);
  4. тело цикла
  5. UNTIL n ? 0;
Что нам известно к моменту выполнения цикла REPEAT UNTIL? Мы знаем, что тело цикла выполнится по крайней мере 1 раз. Знаем, что цикл может выполнится 2 или более раз (а может только 1), потому что случаи, когда цикл выполняется заведомо 1 раз, разобраны в предыдущем посте.
Можно ли отбросить вспомогательную переменную, если обе величины А и В вычисляются динамически? Очевидно нет. По значению шага мы можем найти MaxIters, которое равно самое меньшее 2 (случай MaxIters=1 рассмотрен ранее). Мы можем заключить из этого, что А и А+Step должны иметь разные знаки. Но мы не знаем 1 или 2 раза должен быть выполнен цикл, а значит не можем записать условие для обеспечения этого количества выполнений. При меньшем значении шага информации еще меньше.
Если заранее известна величина А, но не известно В, мы знаем начало цикла, но не знаем, где он закончится. Возможно А=В и цикл выполнится 1 раз, а возможно А+Step тоже входит в диапазон, тогда цикл выполняется более 1 раза (по величине шага можно оценить количество выполнений сверху). Как и в предыдущем случае оптимизация неприменима.

Если А и В известны, то нам известно о цикле всё! В частности мы можем вычислить не только точное количество итераций NumIters, но и последнее значение, для которого должно быть исполнено тело цикла Nlast=B-(B-A) MOD Step ( Nlast=B+(A-B) MOD (-Step), для Step <0). Если мы производим инкремент переменной после тела цикла, то это число Nlast не должно удовлетворять искомому условию, в то время как Nlast+Step должно. Тут нужно быть осторожным, т. к. Nlast+Step может выйти за пределы не только В, но и MAX(T), что нужно учитывать в рассуждениях.
Из NumIters>=2 следует A < Nlast. Для положительно шага Step>0 имеем:
1.1 Если Nlast=0, то A<=Nlast-Step <0. Следующее за последним значение Nlast+Step =Step>0, если только не произойдет переполнение. Пока мы не ввели больший шаг, чем MAX(T), переполнения не произойдет. Если шаг будет в диапазоне 1..MAX(T)-MIN(T) необходимо дополнительно проверить условие Step<=MAX(T). Искомое условие UNTIL n>0.

1.2 Если Nlast>0, то смена знака может произойти только в результате переполнения, т.е Nlast+Step после переполнения должно быть <=0 ( Nlast>MAX(T)-Step, если 1<=Step<=MAX(T)). Но нужно не выскочить из цикла досрочно, ведь элементы до Nlast могут быть неположительны! Для n=A цикл заведомо выполнится, поэтому нужно проверить величину A+Step.
При Nlast+Step<0 должно выполняться
    либо A+Step>0 ( тогда искомое условие n<0 (а можно взять n<=0))
    либо A+Step=0 (тогда искомое условие n<0)
    иначе оптимизация неприменима
При Nlast+Step=0 (а это будет только при расширенном шаге Step>MAX(T)) может существовать только одно предшествующее Nlast значение, это А=Nlast-Step. Следовательно следующее значение A+Step = Nlast>0 и это можно не проверять . Искомое условие n=0 (а можно взять n<=0).

1.3 Если Nlast<0, то Nlast+Step должно быть >=0. За искомое условие можно взять либо n=0 (если Nlast+Step=0), либо n>0 (если Nlast+Step>0), либо n>=0 в любом из этих случаев. При Nlast+Step<0 оптимизация неприменима.


Для шага Step<0 аналогично. Необходимо только учесть, что отрицательных чисел на одно больше, чем положительных.
2.1 Если Nlast=0, то A>=Nlast-Step >0. Следующее за последним значение Nlast+Step =Step<0, если только не произойдет переполнение. Пока мы не ввели расширенный шаг, переполнения не произойдет. Если ABS(Step) будет в диапазоне 1..MAX(T)-MIN(T) необходимо дополнительно проверить условие Step>=MIN(T). Искомое условие UNTIL n<0.

2.2 Если Nlast<0, то смена знака может произойти только в результате переполнения, т.е Nlast+Step после переполнения должно быть >=0 (Nlast<MIN(T)-Step, если -1>=Step>=MIN(T)). Но нужно не выскочить из цикла досрочно, ведь элементы до Nlast могут быть неотрицательны ! Для n=A цикл заведомо выполнится, поэтому нужно проверить величину A+Step.
При Nlast+Step>0 должно выполняться
    либо A+Step<0 ( тогда искомое условие n>0 (а можно взять n>=0))
    либо A+Step=0 (тогда искомое условие n>0)
    иначе оптимизация неприменима
При Nlast+Step=0 (а это будет не только при расширенном шаге, но и если Step=MIN(T)) может существовать только одно предшествующее Nlast значение, это А=Nlast-Step. Следовательно следующее значение A+Step = Nlast<0 и это можно не проверять . Искомое условие n=0 (а можно взять n>=0).

2.3 Если Nlast>0, то Nlast+Step должно быть <=0. За искомое условие можно взять либо n=0 (если Nlast+Step=0), либо n<0 (если Nlast+Step<0), либо n<=0 в любом из этих случаев. При Nlast+Step>0 оптимизация неприменима.

В следующий раз займемся поиском условий для цикла REPEAT INC(n, Step);тело цикла UNTIL n ? 0;

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 26 авг 2013, 13:39 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
Если делать инкремент счетчика до тела цикла,
Код: "OBERON"
  1. DEC(n,Step);
  2. REPEAT
  3. INC(n, Step);
  4. тело цикла
  5. UNTIL n ? 0;
то искомое условие "n ? 0" должно выполняться для последнего обработанного значения Nlast и должно быть ложным для предыдущего значения Nlast-Step. Данный вид цикла проще, потому что из условия NumIters>=2 следует, что и Nlast и Nlast-Step находятся в диапазоне А..В , а значит их выход за пределы А..В и всего целого типа можно не проверять.Достаточно убедиться, что Nlast и Nlast-Step имеют разные знаки.

Для Step>0 имеем:
3.1 Nlast=0. Тогда заведомо Nlast-Step<0, а значит условие можно взять либо n=0 либо n>=0.
3.2 Nlast>0.
    При Nlast-Step <0 условие можно взять n>0, а можно n>=0
    При Nlast-Step =0 условие будет n>0
    иначе оптимизация неприменима
3.3 Nlast<0. В этом случае Nlast-Step также было отрицательно, а значит в этом случае мы не сможем сделать рассматриваемую оптимизацию.

Аналогично для Step<0 имеем:
4.1 Nlast=0. Тогда заведомо Nlast-Step>0, а значит условие можно взять либо n=0 либо n<=0.
4.2 Nlast<0.
    При Nlast-Step >0 условие можно взять n<0, а можно n<=0
    При Nlast-Step =0 условие будет n<0
    иначе оптимизация неприменима
4.3 Nlast>0. В этом случае Nlast-Step также было положительно, а значит в этом случае мы не сможем сделать рассматриваемую оптимизацию.

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

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 26 авг 2013, 20:52 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
Ранее было показано, что для В=0,1,-1 и ABS(Step)=1 можно построить эффективный цикл без использования вспомогательной переменной. Но, оказывается, набор возможных значений параметров несколько шире.
В цикле DEC(n,Step); REPEAT INC(n,Step); тело цикла; UNTIL n ? 0;
условие выхода должно выполняться для последнего значения Nlast и не должно для предыдущего Nlast-Step. Поэтому последнее и предыдущее должны иметь разные знаки. Для Step=1 или -1 последнее Nlast=B, а предыдущее равно Nlast+\-1. Условия для цикла видим в таблице:
Код: "OBERON"
  1. проверить условие: B=Step+1 B=Step-1 B=Step B=0
  2. 5.1 Step>0 n>=0 n>0
  3. 5.2 Step<0 n<=0 n<0
  4. 5.3 Step=1 n=0
  5. 5.4 Step=-1 n=0
Если же в REPEAT UNTIL инкремент происходит после “тела цикла”
REPEAT тело цикла; INC(n,Step) UNTIL n ? 0;
то можно провести следующие рассуждения.

Для В=0 получим следующее.
Пусть Step>0. Тогда Nlast<=B, а Nlast+Step>B, что для В=0 даёт Nlast<=0, Nlast+Step>0. Поэтому если не произойдет переполнения (а для Step<=MAX(T) не произойдет), получим цикл
REPEAT тело цикла; INC(n,Step) UNTIL n > 0;.

Для MIN(T)<=Step<0, В=0 аналогично получаем Nlast>=0, Nlast+Step<0 и цикл
REPEAT тело цикла; INC(n,Step) UNTIL n < 0;

Для В=-1 имеем соотношения
При Step>0: Nlast<0, Nlast+Step>=0, что позволит построить цикл
REPEAT тело цикла; INC(n,Step) UNTIL n >=0;

А для В=1 имеем соотношения
При Step<0: Nlast>0, Nlast+Step<=0, что позволит построить цикл
REPEAT тело цикла; INC(n,Step) UNTIL n<=0;

Соберем полученные данные в таблицу
Код: "OBERON"
  1. проверить условие: B=-1 B=0 B=1
  2. 6.1 Step>0 n>=0 n>0
  3. 6.2 Step<0 n<0 n<=0
  4. 6.3 Step=1 n=0
  5. 6.4 Step=-1 n=0

Можем ли мы воспользоваться сменой знака при переполнении? Увы нет, ведь мы не знаем А. Вполне может оказаться, что А+Step имеет такой же знак, что и Nlast+Step. Единственное исключение — случай Step=MIN(T). В этом случае цикл выполняется не более 2х раз, причем на каждой итерации переменная принимает числа разных знаков. Так что A+Step, если до нее вообще дойдет дело, заведомо отрицательна. Поэтому при Step=MIN(T), B<0 цикл
REPEAT тело цикла; INC(n,Step) UNTIL n >=0; выполнится 1 или 2 раза, как и должен.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 26 авг 2013, 23:10 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
И вот после всех этих выкладок наконец понимаешь, что всё можно было проделать гораздо проще!
Отбрасывание переменной возможно, когда меняется знак при переходе от предпоследней итерации к последней или от последней к следующей. А для знака в математике есть специальная функция signum.
Она не является стандартной в Обероне, но наверняка имеется в какой-нибудь библиотеке для работы с целыми числами. Я нашел только Integers.Sign (x: Integer) для целых произвольной разрядности и Math.Sign (x: REAL) для определения знака у вещественных. Поэтому пока для экспериментов задам функцию Sign прямо в OfrontOPP
Код: "OBERON"
  1.  
  2. PROCEDURE Sign(n: INTEGER):INTEGER;
  3. BEGIN
  4. IF n=0 THEN RETURN 0
  5. ELSIF n>0 THEN RETURN 1
  6. ELSE RETURN -1
  7. END
  8. END Sign;
А потом, когда у нас появятся 64-разрядные типы, можно найти более эффективную реализацию функции Sign через машинные коды процессора, как это сделано в модулях Math или Multi.

Пусть А,В - константы, количество итераций NumIters>=2, Nlast -значение переменной цикла на последней итерации. Тогда для построения цикла
REPEAT тело цикла; INC(n,Step) UNTIL n ? 0;
необходимо проверить выполнение условий: Sign(Nlast) # Sign( Nlast+Step) и Sign(Nlast+Step) # Sign( A+Step). Второе условие необходимо проверять только если Nlast+Step вызвало переполнение. Впрочем можно проверять всегда, без переполнения оно будет заведомо выполняться. Заметим, что
    при Step>0, Sign( A+Step)<=Sign(Nlast)
    при Step<0, Sign( A+Step)>=Sign(Nlast)

При Step>0 получим таблицу возможных значений Sign
Код: "OBERON"
  1. № Sign(A+Step) Sign(Nlast) Sign(Nlast+Step) возможные условия
  2. 1 -1 -1 0 n=0 или n>=0
  3. 2 -1 -1 1 n>0 или n>=0
  4. 3 -1 0 1 n>0
  5. -1 1 0* невозможно при Step<=MAX(T)
  6. 4 0 0 1 n>0 или n#0
  7. 5 0 1 -1* n<0
  8. 6 1 1 -1* n<0 или n<=0
  9. * переполнение

При Step<0 получим аналогичную таблицу возможных значений Sign
Код: "OBERON"
  1. № Sign(A+Step) Sign(Nlast) Sign(Nlast+Step) возможные условия
  2. 1 1 1 0 n=0 или n<=0
  3. 2 1 1 -1 n<0 или n<=0
  4. 3 1 0 -1 n<0
  5. 1 -1 0 * невозможно при Step>=MIN(T)
  6. 4 0 0 -1 n<0 или n#0
  7. 5 0 -1 1* n>0
  8. 6 -1 -1 1* n>0 или n>=0
  9. 7 -1 -1 0* ! n=0 или n>=0
  10. * переполнение
  11. ! случай 7 имеет место только при Nlast=Step=MIN(T)= A+Step, A=0

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 27 авг 2013, 08:03 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
А если не удалось подобрать условие в предыдущей таблице, стоит попытаться построить цикл
DEC(n,Step); REPEAT INC(n,Step); тело цикла; UNTIL n ? 0;
где нужно будет сравнить знаки переменной на последней и предпоследней итерации. Переполнения при этом не возникает, и последняя и предпоследняя итерации существуют, т. к. NumIters>=2.
Для оптимизации должно выполняться Sign(Nlast-Step)#Sign(Nlast). А вообще эти величины связаны условием
    при Step>0, Sign( Nlast-Step)<=Sign(Nlast)
    при Step<0, Sign( Nlast-Step)>=Sign(Nlast)
Поэтому отбрасывание переменной возможно при
    (Step>0) & (Sign( Nlast-Step)<Sign(Nlast))
    или (Step<0) & (Sign( Nlast-Step)>Sign(Nlast))

Для Step>0 получим таблицу
Код: "OBERON"
  1. № Sign( Nlast-Step) Sign(Nlast) возможные условия
  2. 1 -1 -1 условия нет
  3. 2 -1 0 n=0 или n>=0
  4. 3 -1 1 n>0 или n>=0
  5. 0 0 невозможно
  6. 4 0 1 n>0
  7. 5 1 1 условия нет


Для Step<0 получим таблицу
Код: "OBERON"
  1. № Sign( Nlast-Step) Sign(Nlast) возможные условия
  2. 1 1 1 условия нет
  3. 2 1 0 n=0 или n<=0
  4. 3 1 -1 n<0 или n<=0
  5. 0 0 невозможно
  6. 4 0 -1 n<0
  7. 5 -1 -1 условия нет


Сравним с полученным нами ранее. Как видим, результаты совпали.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 27 авг 2013, 20:39 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
Объединим таблицы из двух предыдущих сообщений в одну. Предполагаем по-прежнему, что А и В - константы, количество итераций не менее 2.
Первая таблица для шага Step>0.
Код: "OBERON"
  1. № Sign(A+Step) Sign(Nlast-Step) Sign(Nlast) Sign(Nlast+Step) возможные условия
  2. 1 -1 -1 0 n=0 или n>=0
  3. 2 -1 -1 1 n>0 или n>=0
  4. 3 -1 -1 0 1 n>0 [n=0 или n>=0]
  5. 4 0 -1 0 1 n>0 или n#0[n=0или n>=0]
  6. 5 0 0 1 -1* n<0 [n>0]
  7. 6 1 -1 1 -1* n<0 или n<=0[n>0 или n>=0]


А эта таблица для Step<0
Код: "OBERON"
  1. № Sign(A+Step) Sign( Nlast-Step) Sign(Nlast) Sign(Nlast+Step) возможные условия
  2. 1 1 1 0 n=0 или n<=0
  3. 2 1 1 -1 n<0 или n<=0
  4. 3 1 1 0 -1 n<0 [n=0 или n<=0]
  5. 4 0 1 0 -1 n<0 или n#0[n=0 или n<=0]
  6. 5 0 0 -1 1* n>0 [n<0]
  7. 6 -1 1 -1 1* n>0 или n>=0 [n<0 или n<=0]
  8. 7 -1 0 -1 0* ! n=0 или n>=0 [n<0]
В столбце "возможные условия" в квадратные скобки заключены условия UNTIL для цикла DEC(n,Step); REPEAT INC(n,Step); тело цикла; UNTIL n ? 0;, а если условие не стоит в [], то оно предназначено для цикла REPEAT тело цикла; INC(n,Step) UNTIL n ? 0;Во многих случаях мы имеем выбор — построить цикл с изменением шага в начале или в конце REPEAT UNTIL, выбрать строгое или нестрогое условие. И мы должны сделать выбор, но из каких соображений? Конечно, у каждой платформы свои особенности, но какие-то общие соображения все-таки возможны.

Видимо каждый процессор имеет флажки Zero и Sign, чтобы фиксировать возникновение нулевых и отрицательных величин. Поэтому условия n=0, n<0, как и противоположные им (n#0, n>=0) выполняются на любой платформе достаточно быстро. Значит условия n<0, n>=0, n=0, n#0 лучше чем n<=0 и n>0.
Но выбор между n=0 и n<0 не так однозначен. С одной стороны для многобайтовых переменных n<0 (n>=0) даже проще проверить, чем равенство нулю — ведь достаточно проверить всего 1 старший байт со знаковым битом. С другой стороны, например у Z80 есть специальные «короткие» команды JRZ\JRNZ для условий n=0\n#0, а для n<0\n>=0 условные переходы только длинные. Возможно и у других процессоров сравнения на равенство нулю более распространены. Может быть использовать n=0 только если можно выполнить сравнение одной командой процессора, предпочитая n<0 для многобайтных переменных? Но как это определить такие особенности процессоров Ofront? У кого-то есть мысли на этот счет?

Цикл REPEAT тело цикла; INC(n,Step) UNTIL n ? 0; предпочтительней цикла
DEC(n,Step); REPEAT INC(n,Step); тело цикла; UNTIL n ? 0;
потому что
1) не нужен лишний декремент перед циклом (хотя если А и В — константы, то декремент можно объединить с n:=A)
2) компилятор может объединить инкремент и проверку условия, если они расположены рядом

Поэтому сначала по Sign(A+Step),Sign(Nlast-Step), Sign(Nlast),Sign(Nlast+Step) выбираем наиболее оптимальное условие, фиксируем свой выбор в наборе флажков. Потом генерируем цикл в соответствии с установленными флажками.
Для выбора оптимального условия, нужно выкинуть из таблицы все "неоптимальные". В каждой строчке должно остаться максимум 2 условия - в [] и без, потому что бывает, что при данном сочетании Sign возможен только 1 из видов цикла, а бывает, что оба.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 72 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8  След.

Часовой пояс: UTC + 2 часа


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

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


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

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
© VEDAsoft Oberon Club