?

Log in

No account? Create an account

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

Mar. 21st, 2016

07:44 pm - Работа над ошибками

Previous Entry Share Next Entry

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

Даны N K-битных слагаемых. Каждый бит каждого слагаемого представлен булевской переменной (возможно, неуникальной, как, например, в случае размножения знака) или константой 0/1. Предложите алгоритм вычисления минимальной разрядности операции сложения для получения правильного результата разрядности K.

Пример: пусть требуется сложить два 8-битных слагаемых вида "aaaaaaab" и "cccccccd". Понятно, что реально складывать нужно всего несколько младших бит слагаемых, а старшие биты окончательного результата будут всегда равны старшему биту полученной суммы. Задача заключается в нахождении алгоритма вычисления оптимума для общего случая.
До исправления ошибки мой алгоритм давал правильный оптимальный ответ в подавляющем большинстве случаев, но иногда его результат был на 1 меньше, чем надо.

Tags: ,

Comments:

[User Picture]
From:mi_ze
Date:March 22nd, 2016 05:14 am (UTC)
(Link)
Ничего не понимаю, но поздравляю! :)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:March 22nd, 2016 05:58 am (UTC)
(Link)
Спасибо! Машинная арифметика - это страшная алхимия, поэтому ошибки со всеми бывают. Я сам в ней многого не понимаю.
(Reply) (Parent) (Thread)
[User Picture]
From:arno1251
Date:March 22nd, 2016 05:18 am (UTC)
(Link)
Снимаю шляпу.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:March 22nd, 2016 06:03 am (UTC)
(Link)
Спасибо! Задачка, впрочем, не сложнее матшкольно-олимпиадного уровня, высшей математики там нет, просто цель "нечеловеческая". Но ведь во многих головоломках требуется получить алгоритм - с разными взвешиваниями, мудрецами в шляпах и т.п., и ничего, даже дети как-то справляются.
(Reply) (Parent) (Thread)
[User Picture]
From:fatoff
Date:March 22nd, 2016 06:31 am (UTC)
(Link)
Пример: пусть требуется сложить два 8-битных слагаемых вида "aaaaaaab" и "cccccccd".

Почему биты такие fancy, и даже у них наблюдается полиморфизм?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:March 22nd, 2016 06:42 am (UTC)
(Link)
Почему fancy? Где полиморфизм?
(Reply) (Parent) (Thread)
[User Picture]
From:fatoff
Date:March 22nd, 2016 02:49 pm (UTC)
(Link)
Ok, то переменные в строку.

Вид сущности изменяется, в то время, когда она несёт ту же функцию. a == 0, c == 0; b == 1, d == 1, или там вовсе другое понимание бита?

Edited at 2016-03-22 02:50 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:janatem
Date:March 22nd, 2016 09:13 am (UTC)
(Link)
Забавно, буквально на днях решал похожую задачу (только у меня вместо битов цифры-матрицы, а случай настолько частный, что решение тривиально).

Только условие требует уточнения. Можно считать, что мы берем универсальный случай (когда слагаемые пробегают все возможное значения) и вычисляем длину результата (она, очевидно, равна K+log N). Потом думаем, сколько старших разрядов результата можно отбросить в данном конкретном случае. Вопрос (уточнение формулировки): мы отбрасываем только нули или вообще константы?
(Reply) (Thread)
[User Picture]
From:janatem
Date:March 22nd, 2016 09:19 am (UTC)
(Link)
Если бит представляется именно переменной (а не функцией от одной или нескольких переменных), то я вижу очень простое решение (пригодное для обеих формулировок). В силу монотонности достаточно рассмотреть только экстремальные значения — когда все переменные равны 1 (во второй формулировке — два случая: все равны 0 и все равны 1). И смотреть, сколько старших битов равны нулю (смотреть, какие старшие биты не варьируются).
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:March 22nd, 2016 03:06 pm (UTC)
(Link)
В приложении к приведенному примеру (aaaaaaab+cccccccd), сколько бит этот алгоритм скажет складывать?
(Reply) (Parent) (Thread)
[User Picture]
From:janatem
Date:March 22nd, 2016 03:58 pm (UTC)
(Link)
Да, я делал не то — искал количество битов, которых достаточно для представления результата.

В данном примере вроде достаточно трехбитового сумматора (с четырехбитовым результатом): tzyx := aab+ccd, тогда результат записывается как tzzzzzzyx. В общем случае пока не понял, как решать.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:March 22nd, 2016 04:04 pm (UTC)
(Link)
Да. Моя задача даже чуть проще: результат требуется той же длины, что и слагаемые, т.е. ожидаемый результат zzzzzzyx.
(Reply) (Parent) (Thread)
[User Picture]
From:janatem
Date:March 22nd, 2016 04:48 pm (UTC)
(Link)
Теперь, когда я, наконец, усвоил условие задачи, могу его переформулировать с целью уточнения.

Для двух слагаемых в качестве вычислительного базиса можно использовать ровно один сумматор и любое количество операций, которые в схемотехнике считаются условно бесплатными: копирование переменных и размещение их где угодно. В этих условиях требуется минимизировать разрядность сумматора. В случае нескольких слагаемых, видимо, дается (N-1) сумматоров, и нужно минимизировать разрядность максимального из них (ну или, более точно, найти минимум в каком-то лексикографическом порядке).

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

А если нужно найти более прагматичное решение — минимизировать глубину схемы, используя произвольное количество сумматоров, то я могу предложить универсальное тролльское решение, которое будет побеждать при очень больших N и K.

Upd: я исправил "log N сумматоров" на "(N-1) сумматоров".

Edited at 2016-03-22 04:56 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:March 22nd, 2016 06:21 pm (UTC)
(Link)
Понятно, что если логических элементов не жалеть, то любой бит результата можно выразить как функцию от всех бит аргументов не старше данного, представленную в нормальной форме, но это не считается.

В случае более чем нескольких слагаемых сначала параллельно выполняются приведения "3-в-2" (т.н. Wallace tree: сумма трех бит в одной позиции представима двумя в соседних позициях), пока во всех позициях останется не более двух слагаемых, так что окончательный сумматор с переносами нужен только один.
(Reply) (Parent) (Thread)
[User Picture]
From:janatem
Date:March 22nd, 2016 09:22 am (UTC)
(Link)
Ой, я не ту задачу решал. ;)
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:March 22nd, 2016 06:12 pm (UTC)
(Link)
Совсем оптимальный - наверное такой:

* сортируем все слагаемые по числу значащих бит
* берем два самых коротких, заменяем на одно, в котором бит будет как в более длинном из двух плюс один (поскольку сложение может вызвать перенос), вставляем это число на правильное место в сортированный список
* повторяем предыдущий пункт пока слагаемых в списке больше одного
* берем результат из последнего оставшегося элемента в списке

На всякий случай: слагаемые в приведенном примере будут "ab" и "cd", 2-битные (включая бит знака).

Edited at 2016-03-22 06:15 pm (UTC)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:March 22nd, 2016 06:24 pm (UTC)
(Link)
Как определено "число значащих бит" в случае размножения знака?

Если a=c=0, b=d=1, то двухбитная сумма будет 10, но знак результата - не 1, а 0, так что слагаемые должны быть 3-хбитные.

Для 7 слагаемых вида 0000a, 0000b, 0000c, ... алгоритм должен возвращать 3.

Edited at 2016-03-22 06:27 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:March 22nd, 2016 08:06 pm (UTC)
(Link)
Для этого там "плюс один".

Если слагаемые со знаком, то должен возвращать 4, иначе бит знака испортится.

Но да, мой алгоритм субоптимально суммирует короткие значения.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:March 22nd, 2016 08:13 pm (UTC)
(Link)
Бит знака не испортится, поскольку благодаря константным нулям известно, что он будет равен нулю.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:March 24th, 2016 07:53 am (UTC)
(Link)
Ответ сказать?
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:March 24th, 2016 07:26 pm (UTC)
(Link)
Ну как бы из подсказок очевидно, что для пущей оптимальности суммировать надо не биты как таковые, а максимальные значения (плюс отдельно наличие бита знака).

Или ответ более умный?
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:March 24th, 2016 08:25 pm (UTC)
(Link)
Идея верная, а более умно ответ формулируется как value range analysis. :)
(Reply) (Parent) (Thread)
[User Picture]
From:kcmamu
Date:March 27th, 2016 03:50 am (UTC)
(Link)
А что должно быть ответом для N-значного abbb...bbbc + deee...eeef? Константа или нечто зависящее от N?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:March 27th, 2016 04:08 am (UTC)
(Link)
В рамках задачи это будет N, потому что сумматор, если он один, должен быть N-значный. Разрывание сумматора на части имеется, особо полезное в более частых, но простых случаях типа abc0def + ghi0jkl, но к пуанту задачи это отношения не имело, поэтому я решил не загромождать.
(Reply) (Parent) (Thread)