OberonCore
https://forum.oberoncore.ru/

Целочисленное деление
https://forum.oberoncore.ru/viewtopic.php?f=27&t=6259
Страница 3 из 4

Автор:  albobin [ Пятница, 29 Июнь, 2018 10:55 ]
Заголовок сообщения:  Re: Целочисленное деление

Придирка к :
"Еще один пример. У нас есть 10 тонн мусора. Сколько требуется вывезти трехтонных грузовиков, чтобы всё отправить на свалку?
10 DIV (-3) = -4"
собственно такая:
(-10) DIV (-3) = 4
один грузовик обеспечивает убыль в (-3), а нужно (-10)

Автор:  Comdiv [ Пятница, 29 Июнь, 2018 11:38 ]
Заголовок сообщения:  Re: Целочисленное деление

Иван Денисов писал(а):
Ну а деление на отрицательный делитель, ИМХО, всё таки имеет смысл в случае указания направления. Будь то направление движения денег, как в первом примере или направления поворота или движения чего-либо, как во втором.
Согласен, может.
И я думал над Вашими примерами, но в них присутствует произвольность в выборе знака. В том же примере с мусором Вы приписываете его количеству положительный знак, но если он вывозится, то есть вычитается, то должен быть отрицательным.

Я смог найти целостность условий задачи с результатами при отрицательном делителе только в случае оперирования отрицательными объектами. Если не прибегать к помощи антивселенной, то отрицательный объект можно интерпретировать как свободное место, которое тоже имеет физический смысл и может заканчиваться по тем же законам, что и объекты. Это может быть что угодно: и количество столиков(+) со свободными(-) от посетителей местами, и атомы(+) со свободными(-) от электронов орбиталями.

Автор:  Иван Денисов [ Пятница, 29 Июнь, 2018 13:17 ]
Заголовок сообщения:  Re: Целочисленное деление

Про произвольность выбора знаков согласен, не всё чисто, подгонка получается.

Из-за отрицательных знаков точно есть вред, то что затрудняется понимание программы.

В книге:
Nikitin E.W. Into the Realm of Oberon. New York, NY: Springer New York, 1997.
нашел вот тоже упоминание этой проблемы
Вложение:
div.png
div.png [ 88.53 КБ | Просмотров: 8542 ]

Автор:  Comdiv [ Пятница, 29 Июнь, 2018 13:53 ]
Заголовок сообщения:  Re: Целочисленное деление

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

Автор:  Пётр Кушнир [ Пятница, 29 Июнь, 2018 16:05 ]
Заголовок сообщения:  Re: Целочисленное деление

В задаче с грузовиками знаки вообще не нужны. Точно такой же смысл получится, если ждать, пока грузовик привезёт 10 тонн, везде плюсы будут. А для оператора DIV задача будет звучать "сколько полных грузовиков..." и для MOD будет задача "сколько тонн останется", а то что вы там огругляете в рамках деления в разные стороны - ничем реальным материальным не обосновано.

Автор:  Иван Денисов [ Пятница, 29 Июнь, 2018 17:50 ]
Заголовок сообщения:  Re: Целочисленное деление

Пётр Кушнир писал(а):
В задаче с грузовиками знаки вообще не нужны. Точно такой же смысл получится, если ждать, пока грузовик привезёт 10 тонн, везде плюсы будут. А для оператора DIV задача будет звучать "сколько полных грузовиков..." и для MOD будет задача "сколько тонн останется", а то что вы там огругляете в рамках деления в разные стороны - ничем реальным материальным не обосновано.

Да, Пётр, логично рассудил. Без минусов будет понятнее и более предсказуемо. Так что еще и после книжки этой, склоняюсь к мнению, что смысл придумать для минусов возможно, но больше от этого проблем, чем достоинств.

Автор:  Artyemov [ Пятница, 29 Июнь, 2018 20:37 ]
Заголовок сообщения:  Re: Целочисленное деление

Иван Денисов писал(а):
Пётр Кушнир писал(а):
В задаче с грузовиками знаки вообще не нужны. Точно такой же смысл получится, если ждать, пока грузовик привезёт 10 тонн, везде плюсы будут. А для оператора DIV задача будет звучать "сколько полных грузовиков..." и для MOD будет задача "сколько тонн останется", а то что вы там огругляете в рамках деления в разные стороны - ничем реальным материальным не обосновано.

Да, Пётр, логично рассудил. Без минусов будет понятнее и более предсказуемо. Так что еще и после книжки этой, склоняюсь к мнению, что смысл придумать для минусов возможно, но больше от этого проблем, чем достоинств.

Но тогда уж поправьте: 10 DIV 3 всё ж таки 3, а то арифметикой за 4-й класс повеяло ;)

Автор:  Пётр Кушнир [ Пятница, 29 Июнь, 2018 21:20 ]
Заголовок сообщения:  Re: Целочисленное деление

Artyemov писал(а):
а то арифметикой за 4-й класс повеяло ;)

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

По честному будет ввести арифметический и экономический операторы, тогда все будут довольны. Я бы ещё упомянул то, что в обероне сдвиги арифметические, а логические только в модуле SYSTEM, тоже спорный момент

Автор:  Иван Денисов [ Пятница, 29 Июнь, 2018 22:26 ]
Заголовок сообщения:  Re: Целочисленное деление

Artyemov писал(а):
Иван Денисов писал(а):
Пётр Кушнир писал(а):
В задаче с грузовиками знаки вообще не нужны. Точно такой же смысл получится, если ждать, пока грузовик привезёт 10 тонн, везде плюсы будут. А для оператора DIV задача будет звучать "сколько полных грузовиков..." и для MOD будет задача "сколько тонн останется", а то что вы там огругляете в рамках деления в разные стороны - ничем реальным материальным не обосновано.

Да, Пётр, логично рассудил. Без минусов будет понятнее и более предсказуемо. Так что еще и после книжки этой, склоняюсь к мнению, что смысл придумать для минусов возможно, но больше от этого проблем, чем достоинств.

Но тогда уж поправьте: 10 DIV 3 всё ж таки 3, а то арифметикой за 4-й класс повеяло ;)

10 DIV (-3) = -4
Так в Обероне и в Компонентном Паскале, так что поправлять нечего. Компонентный Паскаль точно никто править не собирается ближайшее время :)

Автор:  Trurl [ Пятница, 29 Июнь, 2018 23:22 ]
Заголовок сообщения:  Re: Целочисленное деление

В Обероне не так, на предыдущей странице было же.

Автор:  Иван Денисов [ Суббота, 30 Июнь, 2018 07:17 ]
Заголовок сообщения:  Re: Целочисленное деление

Trurl писал(а):
В Обероне не так, на предыдущей странице было же.

Попытка проверить ваше утверждение в XDS привело к интересному наблюдению :)

Код:
<*+ MAIN *>
MODULE hello;

IMPORT InOut;
VAR res: INTEGER;
BEGIN
  res := 10 DIV (-3);
  InOut.WriteInt (res, 5);
  InOut.WriteLn;
END hello.


В XDS запрещен делитель меньше нуля при целочисленном делении.
shall not have a value less than 0

Код:
dia@lenovo:/usr/local/xds/samples/oberon$ xc hello.ob2
XDS Oberon-2 v2.40 [x86, v1.50] - build 03.02.2012
Compiling "hello.ob2"

* [hello.ob2 7.07 E029]
* incompatible types:
    "INT16"
    "whole constant (ZZ)"
  res $:= 10 DIV (-3);

* [hello.ob2 7.13 E107]
* shall not have a value less than 0
  res := 10 $DIV (-3);
errors  2, no warnings, lines   10, time  0.01


В Онлайн компиляторе действительно получается -3
https://models.molpit.org/model/134

Автор:  Иван Денисов [ Суббота, 30 Июнь, 2018 07:43 ]
Заголовок сообщения:  Re: Целочисленное деление

Проверил как во время исполнения обрабатывается ошибка.
Код:
<*+ MAIN *>
MODULE hello;

IMPORT InOut;
VAR a, b: INTEGER;
BEGIN
  a := -3;
  b := 10 DIV a;
  InOut.WriteInt (b, 5);  InOut.WriteLn;
END hello.


Он еще на этапе компиляции сказал, что ошибка во время исполнения будет, но разрешил собрать программу.
Код:
dia@lenovo:/usr/local/xds/samples/oberon$ xc =m hello.ob2
O2/M2 development system v2.60 TS  (c) 1991-2011 Excelsior, LLC. (build 03.02.2012)
XDS Oberon-2 v2.40 [x86, v1.50] - build 03.02.2012
Compiling "hello.ob2"

* [hello.ob2 8.11 W912]
* wholeDivException will be raised here
  b := 10 $DIV a;
no errors, warnings  1, lines   11, time  0.01
gcc  -o hello hello.o  /usr/local/xds/lib/x86/libts.a /usr/local/xds/lib/x86/libxds.a  -lm -lncurses -m32


Как компилятор предупреждал, сработала обработка исключения во время выполнения:
Код:
dia@lenovo:/usr/local/xds/samples/oberon$ ./hello

#RTS: unhandled exception #6: zero or negative divisor at line 8 of hello.ob2
#RTS: No history available.

Автор:  Comdiv [ Суббота, 30 Июнь, 2018 14:11 ]
Заголовок сообщения:  Re: Целочисленное деление

В OFront воплощение функции деления было сделано с ошибками. Они остаются в OFront+ и в voc
Код:
LONGINT SYSTEM_DIV(LONGINT x, LONGINT y) // INT64 SYSTEM_DIV(INT64 x, INT64 y)
{
  if (x == 0) return 0;
  if (x >= 0)
    if (y >= 0) {return x/y;}
    else        {return -((x-y-1)/(-y));}
  else
    if (y >= 0) {return -((y-x-1)/y);}
    else        {return (-x)/(-y);}
}

При условии ( (x < 0) # (y < 0) ) & ( ABS(x) > MAX(LONGINT) - ABS(y) ) будет переполнение несмотря на допустимые для деления входные параметры. Согласно стандарту Си переполнение целых чисел со знаком является неопределённым поведением, что не позволяет предсказать поведение программы для общего случая - возможна и аварийная остановка. При использовании флага компилятора -fwrapv в gcc и clang переполнение будет проводится в соответствии с машинными вычислениями в дополнительном коде. Но и тогда результат во многих случаях будет некорректным.
Также, из-за дополнительного кода будет выполняться некорректное равенство MIN(LONGINT) DIV (-1) = MIN(LONGINT) . clang для такого деления может сгенерировать аварийное завершение несмотря на флаг -fwrapv, что можно рассматривать как преимущество для диагностики.

В CPFront нет проблемы с переполнением
Код:
INTEGER SYSTEM_DIV(INTEGER x, INTEGER y)
{
   if (y > 0) {
      if (x < 0) return ~(~x / y);
      else return x / y;
   } else if (y < 0) {
      if (x > 0) return ~((x - 1) / -y);
      else return -x / -y;
   } else {
      __HALT(-5);
   }
}
Ещё одним преимуществом этого варианта в том, что в нём явная проверка деления на 0. В Си полагаться на то, что при делении на 0 произойдёт аварийная остановка в общем случае нельзя, потому что это тоже неопределённое поведение. Тем не менее, в решении для КП тоже есть проблема с делением минимального значения на -1, а трюки с побитовым отрицанием жёстко завязаны на дополнительный код.

Автор:  Oleg N. Cher [ Воскресенье, 01 Июль, 2018 22:28 ]
Заголовок сообщения:  Re: Целочисленное деление

Comdiv писал(а):
В OFront воплощение функции деления было сделано с ошибками. Они остаются в OFront+ и в voc
Comdiv писал(а):
в решении для КП тоже есть проблема с делением минимального значения на -1, а трюки с побитовым отрицанием жёстко завязаны на дополнительный код.
Предложите корректное решение, внесём правки.

Автор:  Comdiv [ Воскресенье, 01 Июль, 2018 23:12 ]
Заголовок сообщения:  Re: Целочисленное деление

1. Побитовое отрицание эквивалентно вычитанию из -1.
2. Нельзя просто так менять знак отрицательного числа
2.1. Либо проверять на возможность переполнения при MIN(INTEGER)
2.2. Либо переписать так, чтобы отпала необходимость в смене знака
3. При отрицательных делимом и делителе нужно проверять на совпадение значений MIN(INTEGER) и -1

Автор:  Trurl [ Понедельник, 02 Июль, 2018 08:25 ]
Заголовок сообщения:  Re: Целочисленное деление

Иван Денисов писал(а):
Попытка проверить ваше утверждение в XDS привело к интересному наблюдению :)

Такого рода утверждения правильно проверять, читая описание языка.
Цитата:
The operators DIV and MOD apply to integer operands only. They are related by the following formulas defined for any dividend x and positive divisors y:
x = (x DIV y) * y + (x MOD y)
0 <= (x MOD y) < y

Автор:  Иван Денисов [ Понедельник, 02 Июль, 2018 10:44 ]
Заголовок сообщения:  Re: Целочисленное деление

Trurl писал(а):
Иван Денисов писал(а):
Попытка проверить ваше утверждение в XDS привело к интересному наблюдению :)

Такого рода утверждения правильно проверять, читая описание языка.
Цитата:
The operators DIV and MOD apply to integer operands only. They are related by the following formulas defined for any dividend x and positive divisors y:
x = (x DIV y) * y + (x MOD y)
0 <= (x MOD y) < y

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

Автор:  kemiisto [ Пятница, 12 Июль, 2019 01:35 ]
Заголовок сообщения:  Re: Целочисленное деление

Пётр Кушнир писал(а):
По честному будет ввести арифметический и экономический операторы, тогда все будут довольны.

Как в Аде, да. Две операции: rem (remainder) и mod (modulus). Первая определена согласно правилу A = (A/B)*B + (A rem B), вторая - A = B*N + (A mod B) для некоторого N. Иначе говоря, rem сохраняет знак делимого, а mod - делителя. И обычно таки нужен rem, а не mod.

P.S. В C, кстати, по крайней мере в С99, поведение % в этом отношении вообще implementation specific. :D

Автор:  Comdiv [ Пятница, 12 Июль, 2019 02:00 ]
Заголовок сообщения:  Re: Целочисленное деление

kemiisto писал(а):
В C, кстати, по крайней мере в С99, поведение % в этом отношении вообще implementation specific. :D
В С89, но не в С99, где это определено конкретно.

Автор:  kemiisto [ Пятница, 12 Июль, 2019 02:11 ]
Заголовок сообщения:  Re: Целочисленное деление

Comdiv писал(а):
kemiisto писал(а):
В C, кстати, по крайней мере в С99, поведение % в этом отношении вообще implementation specific. :D
В С89, но не в С99, где это определено конкретно.

Ошибся, да. В С99 таки уже чётенько "truncation toward zero". Ну, не суть. :D А две разных операции есть ещё, как минимум, в Fortran и всякой "функцианальщине" типа там Scheme, Haskell. :)

Страница 3 из 4 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/