Работа над ошибками
Mar. 21st, 2016 07:44 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
spamsinkСегодня я исправил ошибку в собственном коде, которой практически ровно 10 лет. Интересно, что за всё это время она ни разу не проявлялась ни на примерах из реальной жизни, ни на стандартном пакете тестов, а была обнаружена при очередном раунде улучшения тестирования.
Даны N K-битных слагаемых. Каждый бит каждого слагаемого представлен булевской переменной (возможно, неуникальной, как, например, в случае размножения знака) или константой 0/1. Предложите алгоритм вычисления минимальной разрядности операции сложения для получения правильного результата разрядности K.
Пример: пусть требуется сложить два 8-битных слагаемых вида "aaaaaaab" и "cccccccd". Понятно, что реально складывать нужно всего несколько младших бит слагаемых, а старшие биты окончательного результата будут всегда равны старшему биту полученной суммы. Задача заключается в нахождении алгоритма вычисления оптимума для общего случая.
До исправления ошибки мой алгоритм давал правильный оптимальный ответ в подавляющем большинстве случаев, но иногда его результат был на 1 меньше, чем надо.
Даны N K-битных слагаемых. Каждый бит каждого слагаемого представлен булевской переменной (возможно, неуникальной, как, например, в случае размножения знака) или константой 0/1. Предложите алгоритм вычисления минимальной разрядности операции сложения для получения правильного результата разрядности K.
Пример: пусть требуется сложить два 8-битных слагаемых вида "aaaaaaab" и "cccccccd". Понятно, что реально складывать нужно всего несколько младших бит слагаемых, а старшие биты окончательного результата будут всегда равны старшему биту полученной суммы. Задача заключается в нахождении алгоритма вычисления оптимума для общего случая.
До исправления ошибки мой алгоритм давал правильный оптимальный ответ в подавляющем большинстве случаев, но иногда его результат был на 1 меньше, чем надо.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2016-03-22 05:14 am (UTC)no subject
Date: 2016-03-22 05:58 am (UTC)no subject
Date: 2016-03-22 05:18 am (UTC)no subject
Date: 2016-03-22 06:03 am (UTC)no subject
Date: 2016-03-22 06:31 am (UTC)Почему биты такие fancy, и даже у них наблюдается полиморфизм?
no subject
Date: 2016-03-22 06:42 am (UTC)no subject
Date: 2016-03-22 02:49 pm (UTC)Вид сущности изменяется, в то время, когда она несёт ту же функцию. a == 0, c == 0; b == 1, d == 1, или там вовсе другое понимание бита?no subject
Date: 2016-03-22 09:13 am (UTC)Только условие требует уточнения. Можно считать, что мы берем универсальный случай (когда слагаемые пробегают все возможное значения) и вычисляем длину результата (она, очевидно, равна K+log N). Потом думаем, сколько старших разрядов результата можно отбросить в данном конкретном случае. Вопрос (уточнение формулировки): мы отбрасываем только нули или вообще константы?
no subject
Date: 2016-03-22 09:19 am (UTC)no subject
Date: 2016-03-22 03:06 pm (UTC)no subject
Date: 2016-03-22 03:58 pm (UTC)В данном примере вроде достаточно трехбитового сумматора (с четырехбитовым результатом): tzyx := aab+ccd, тогда результат записывается как tzzzzzzyx. В общем случае пока не понял, как решать.
no subject
Date: 2016-03-22 04:04 pm (UTC)no subject
Date: 2016-03-22 04:48 pm (UTC)Для двух слагаемых в качестве вычислительного базиса можно использовать ровно один сумматор и любое количество операций, которые в схемотехнике считаются условно бесплатными: копирование переменных и размещение их где угодно. В этих условиях требуется минимизировать разрядность сумматора. В случае нескольких слагаемых, видимо, дается (N-1) сумматоров, и нужно минимизировать разрядность максимального из них (ну или, более точно, найти минимум в каком-то лексикографическом порядке).
Потому что если же не фиксировать количество сумматоров, то можно взять тучу элементарных одноразрядных сумматоров с переносом, поскольку они образуют логический базис.
А если нужно найти более прагматичное решение — минимизировать глубину схемы, используя произвольное количество сумматоров, то я могу предложить универсальное тролльское решение, которое будет побеждать при очень больших N и K.
Upd: я исправил "log N сумматоров" на "(N-1) сумматоров".
no subject
Date: 2016-03-22 06:21 pm (UTC)В случае более чем нескольких слагаемых сначала параллельно выполняются приведения "3-в-2" (т.н. Wallace tree: сумма трех бит в одной позиции представима двумя в соседних позициях), пока во всех позициях останется не более двух слагаемых, так что окончательный сумматор с переносами нужен только один.
no subject
Date: 2016-03-22 09:22 am (UTC)no subject
Date: 2016-03-22 06:12 pm (UTC)* сортируем все слагаемые по числу значащих бит
* берем два самых коротких, заменяем на одно, в котором бит будет как в более длинном из двух плюс один (поскольку сложение может вызвать перенос), вставляем это число на правильное место в сортированный список
* повторяем предыдущий пункт пока слагаемых в списке больше одного
* берем результат из последнего оставшегося элемента в списке
На всякий случай: слагаемые в приведенном примере будут "ab" и "cd", 2-битные (включая бит знака).
no subject
Date: 2016-03-22 06:24 pm (UTC)Если a=c=0, b=d=1, то двухбитная сумма будет 10, но знак результата - не 1, а 0, так что слагаемые должны быть 3-хбитные.
Для 7 слагаемых вида 0000a, 0000b, 0000c, ... алгоритм должен возвращать 3.
no subject
Date: 2016-03-22 08:06 pm (UTC)Если слагаемые со знаком, то должен возвращать 4, иначе бит знака испортится.
Но да, мой алгоритм субоптимально суммирует короткие значения.
no subject
Date: 2016-03-22 08:13 pm (UTC)no subject
Date: 2016-03-24 07:53 am (UTC)no subject
Date: 2016-03-24 07:26 pm (UTC)Или ответ более умный?
no subject
Date: 2016-03-24 08:25 pm (UTC)no subject
Date: 2016-03-27 03:50 am (UTC)no subject
Date: 2016-03-27 04:08 am (UTC)