Почему работает алгоритм двойного барабана?

Question

Я пытаюсь понять, почему работает алгоритм с двойной ошибкой, но я не получаю его.

Есть много хороших описания шагов и цель алгоритма, как http://www.classiccmp.org/cpmarchives/cpm/mirrors/cbfalconer.home.att.net/download/dubldabl.txt или http://en.wikipedia.org/wiki/Double_dabble

Есть также некоторые попытки объяснения. Самый лучший, который я нашел, это один: http://www.minecraftforum.net/forums/minecraft-discussion/redstone-discussion-and/340153-why-does-the-double-dabble-algorithm-work#c6

Но я все еще чувствую, что мне не хватает соединительных деталей. Вот что я получаю:

• Я получаю, что вы можете преобразовать двоичные числа в десятичные числа, читая их слева направо, начиная с десятичным значением 0, итерация цифр двоичного числа, добавляя 1 до десятичного числа для каждого 1, которое вы достигнете в двоичном числе, и умножения на 2, когда вы переходите к следующей цифре (как объясняется в последнем сообщении).
  • Но почему это приводит к двойному алгоритму? Мы не хотим конвертировать в десятичной форме, мы хотим конвертировать в BCD. Почему мы сохраняем умножение (смещение), но мы бросаем добавление 1? Где соединение?
• Я получаю, почему мы должны добавить 3, когда число в поле BCD превышает 4 перед переходом. Потому что, если вы хотите, чтобы число BCD умножалось на 2, если вы меняете его, вам нужно сделать некоторые исправления. Если вы переместите номер BCD 0000 1000 (8), и вы хотите получить двойной 0001 0011 (16), перед переносом вам нужно добавить 3 (половина из 6), потому что, просто переместив вас, вы получите 0001 0000 (10) (вы 'отсутствует 6).
  • Но почему мы хотим этого и где добавление 1 происходит?

Я предполагаю, что я просто не хватает небольшую часть.

Answer 1

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

Мы используем метод для преобразования двоичного числа в десятичное число, объясняемое в вопросе, но мы немного его изменим.

Мы не начинаем с десятичного числа 0, а с номера BCD 0000 0000 (0).

BCD binary

0000 0000 1111 1111

Сначала мы должны добавить 1 к BCD-числа. Это может быть сделано путем простого сдвига

0000 0001 1111 1110

Теперь мы переходим дальше и хотим умножить BCD-число на 2. В следующем шаге мы хотим, чтобы добавить текущую двоичную цифру в BCD-числа. Оба могут быть выполнены за один шаг (снова) сдвигом.

0000 0011 1111 1100

Это работает снова и снова. Единственная ситуация, в которой это не работает, - это когда блок BCD-номера превышает 4. В этом случае вам нужно сделать исправление, объясненное в вопросе.

После перебора двоичного числа, вы получаете BCD-представление числа на левой стороне \ о/

Answer 2

Вся идея заключается в том, чтобы использовать перенесение объяснило в вашей ссылке, но затем преобразовать число в слева в BCD. На каждом этапе вы приближаетесь к фактическому двоичному числу слева, но удостоверяетесь, что число остается в BCD, а не в двоичном.

Когда вы меняете «1», вы по существу добавляете его.

Посмотрите на ссылку ниже, чтобы получить суть аргумента «добавить 3»:

https://olduino.files.wordpress.com/2015/03/why-does-double-dabble-work.pdf

Answer 3

Преобразование N в его десятичное представление включает в себя несколько раз определения R (отдых) после деления на 10. Вместо деления на 10 вы также можете разделить на 2 (это всего лишь сдвиг), за которым следует деление на 5. Следовательно, 5. Длительное разделение означает попытку вычесть 5, и если это удастся фактически выполнить вычитание при отслеживании этого успех, установив бит в Q. Добавление 3 совпадает с вычитанием 5 при установке бит, который впоследствии будет смещен в Q. Следовательно, 3.