?

Log in

No account? Create an account

Машинно-арифметическое - Общество дровосеков Бердичева по изучению Мишны

Dec. 3rd, 2014

08:50 pm - Машинно-арифметическое

Previous Entry Share Next Entry


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

int imax=0, next=1;
while (next > imax) {
    imax = next;
    next = next*2+1;
}
не будет работать.

Это система, у которой нет отдельного целочисленного арифметического устройства, а целые числа суть точно представленные числа с плавающей точкой, имеющие целое значение.

Comments:

[User Picture]
From:fatoff
Date:December 4th, 2014 05:23 am (UTC)
(Link)
int имеет фиксированное количество бит. Хм... Почему вопрос? Прерывание по переполнению, это сигнал от процессора?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:December 4th, 2014 06:27 am (UTC)
(Link)
Ну имеет, но целое переполнение - это UB, помимо прочих деталей. Прерывание в данном случае - это любое нарушение линейного выполнения программы, будь то сигнал от процессора, брошенное исключение, начало ядерной войны или убийство котенка. В рамках вопроса гарантируется, что UB лимитировано значением результата.
(Reply) (Parent) (Thread)
[User Picture]
From:avva
Date:December 4th, 2014 08:06 am (UTC)
(Link)
Просто считать 1000...0 положительным, а не отрицательным, и все. Да, проверять знак становится чуть более сложным, но не значительно.
(Reply) (Thread)
[User Picture]
From:archaicos
Date:December 4th, 2014 08:16 am (UTC)
(Link)
А как это число получится из, скажем, 0x7fffffff 2 * 1 +?
(Reply) (Parent) (Thread)
[User Picture]
From:avva
Date:December 4th, 2014 08:22 am (UTC)
(Link)
Не получится, в том-то и суть.
(Reply) (Parent) (Thread)
[User Picture]
From:archaicos
Date:December 4th, 2014 09:41 am (UTC)
(Link)
А, да.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:December 4th, 2014 08:24 am (UTC)
(Link)
Допустим. Тогда это значение при imax == 0111...1 должно оказаться результатом imax*2+1, т.е. 0111...1*2 == 0111...1, из чего вытекает saturation к значению, не являющемуся максимальным. Не бывает.
(Reply) (Parent) (Thread)
[User Picture]
From:avva
Date:December 4th, 2014 08:41 am (UTC)
(Link)
huh? в условии спрашивается, как устроить, чтобы *2+1 НЕ приводило к максимальному значению ("не будет работать"), ну так оно и не приводит.

Максимальное значение 10000....0
Прыжки *2+1 приводят к 0111....1, следующий такой прыжок даст 1111...1 = -1, отрицательное число, поэтому алгоритм останавливается на 0111...1, но на самом деле максимальное целое значение на 1 больше.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:December 4th, 2014 08:46 am (UTC)
(Link)
При желаемом понимании слова "реалистичная", пожалуй, правильно. :)
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:December 4th, 2014 06:01 pm (UTC)
(Link)
Мне пришло в голову просто поменять местами представление положительных и отрицательных чисел в дополнительном коде. Что приводит к тому же эффекту.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:December 4th, 2014 06:11 pm (UTC)
(Link)
Строго говоря, это нельзя. Стандарт допускает 3 варианта: two's complement, one's complement, sign + magnitude.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:December 4th, 2014 06:56 pm (UTC)
(Link)
Про стандарт в вопросе речи не было.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:December 4th, 2014 07:11 pm (UTC)
(Link)
В вопросе было слово "реалистичная".
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:December 4th, 2014 07:14 pm (UTC)
(Link)
Ну так реалистичная. Если по какой-то причине очень-очень надо расширить диапазон представления положительных чисел на единичку, то самый дешевый способ это сделать - вот так.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:December 4th, 2014 06:12 pm (UTC)
(Link)
Это не будет соответствовать стандарту. Стандарт допускает 3 варианта представления целых чисел: two's complement, one's complement, sign + magnitude.
(Reply) (Parent) (Thread)
[User Picture]
From:avva
Date:December 4th, 2014 06:25 pm (UTC)
(Link)
И зря, кстати. И вообще, это в C, а в C++ стандарт разрешает, насколько я вижу. В записи не указан язык :)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:December 4th, 2014 06:52 pm (UTC)
(Link)
Спасибо, исправил. :)
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:December 4th, 2014 07:18 pm (UTC)
(Link)
Реализация на странном железе не обязана соответствовать стандарту. Тут уж какое есть - такое есть, придется писать нестандартные программы.
(Reply) (Parent) (Thread)
[User Picture]
From:archaicos
Date:December 4th, 2014 08:11 am (UTC)
(Link)
Один вариант могу дать из соображения того, что при наступлении переполнении условие next*2+1 > next может оставаться верным. Например, если среди битового представления чисел существует специальное значение типа плюс бесконечности, которое получается при переполнении. Тогда на выходе из цикла imax будет равно этой бесконечности, а не максимальному представимому целому.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:December 4th, 2014 08:28 am (UTC)
(Link)
Ну да, теперь остался один шаг до формулировки названия такого представления чисел.
(Reply) (Parent) (Thread)
[User Picture]
From:archaicos
Date:December 4th, 2014 09:38 am (UTC)
(Link)
Представление с сатурированными жирными кислотами! :)
(Reply) (Parent) (Thread)
[User Picture]
From:kouzdra
Date:December 4th, 2014 07:32 pm (UTC)
(Link)
Емним обычная арифметика PDP-11 - там при сравнении учитывается флаг переполненния. Потому при переполнении оно все равно останется "больше"
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:December 4th, 2014 07:55 pm (UTC)
(Link)
При сравнении учитывается флаг переполнения, чтобы отличать сравнения со знаком от сравнений без знака. А переполнение при умножении было "заиграно" при сохранении результата в память.
(Reply) (Parent) (Thread)
[User Picture]
From:gegmopo4
Date:December 4th, 2014 09:16 am (UTC)
(Link)
Хитрый оптимизатор может предположить, что переполнения никогда не случится (иначе UB) и next > imax всегда.

Насколько я понимаю логику оптимизаторов, ндёжнее использовать unsigned int (и приводить к int только при сравнении). А ещё лучше — взять INT_MAX. Но, боюсь, речь идёт не об int, а о каком-то специфическом типе, не имеющем беззнакового аналога (вроде uid_t)?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:December 4th, 2014 06:20 pm (UTC)
(Link)
Если двойку вынести в переменную, значение которой неизвестно оптимизатору, то не сможет предположить, потому что не будет знать, как изменяется значение next.

А ещё лучше — взять INT_MAX.

Речь идет о коде, тестирующем конформность реализаций (enquire.c)

о каком-то специфическом типе, не имеющем беззнакового аналога

Именно. У какого числового типа нет беззнакового аналога? :)
(Reply) (Parent) (Thread)
[User Picture]
From:gegmopo4
Date:December 4th, 2014 09:23 pm (UTC)
(Link)
> Если двойку вынести в переменную, значение которой неизвестно оптимизатору, то не сможет предположить, потому что не будет знать, как изменяется значение next.

Оптимизаторы становятся всё умнее. Прятать переменную придётся очень хорошо и без гарантии, что оптимизатор следующей версии не найдёт.

> У какого числового типа нет беззнакового аналога?

Пример я привёл. Платформо-зависимый псевдоним, для которого даже неизвестно, знаковый он или нет.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:December 4th, 2014 10:14 pm (UTC)
(Link)
Человек умнее оптимизатора; в крайнем случае всегда можно ввести значение извне.

Платформо-зависимый псевдоним, для которого даже неизвестно, знаковый он или нет.

Всё проще. :)
(Reply) (Parent) (Thread)
From:anonim_legion
Date:January 5th, 2015 01:21 pm (UTC)

Извиняюсь за некропост

(Link)
Подойдет любая реализация длинной арифметики. Завершится оно не из-за прерывания по переполнению, а по OutOfMemoryException.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 5th, 2015 03:46 pm (UTC)

Re: Извиняюсь за некропост

(Link)
Разумеется, потому я и спросил про машинную арифметику, а не про просто арифметику (хотя микропрограммные реализации длинной арифметики, как на машинах типа МИР, и размывают границу).
(Reply) (Parent) (Thread)