- =A=L=X=
- Постоялец
Наткнулся тут на забавный алгоритм конверсии двоичных чисел в десятичные с сабжевым названием.
На русском что-то не гуглится как оно должно называться, но вот краткое описание того как он работает с английской вики: https://en.wikipedia.org/wiki/Double_dabble
Проведём алгоритм над байтом - для начала резервируется нужное число бит BCD. Каждой цифре по 4 бита, классика.
Запишем BCD-число пока еще заполненное нулями и конвертируемое число рядом вот так:
Цфр1 Цфр2 Цфр3 Число (дв.) 0000 0000 0000 11110011
А теперь мы делаем следующее: 8 раз вдвигаем двоичное число в BCD-число бит за битом на каждой итерации прибавляя 3 к каждой из цифр которые после сдвига стали больше 4.
Получается вот что:
0000 0000 0000 11110011 Инициализация 0000 0000 0001 11100110 Сдвиг 0000 0000 0011 11001100 Сдвиг 0000 0000 0111 10011000 Сдвиг 0000 0000 1010 10011000 Добавили 3 к единицам, т.к. в них накопилось 7 0000 0001 0101 00110000 Сдвиг 0000 0001 1000 00110000 Добавили 3 к единицам, т.к. в них стало 5 0000 0011 0000 01100000 Сдвиг 0000 0110 0000 11000000 Сдвиг 0000 1001 0000 11000000 Добавили 3 к десяткам, т.к. там накопилось 6 0001 0010 0001 10000000 Сдвиг 0010 0100 0011 00000000 Сдвиг 2 4 3
ВТФ? :) Действительно всё сошлось.
Поискал объяснения как это работает https://stackoverflow.com/questions/28670539/why-is-the-double-da… rithm-working , но лично мне ничего не зашло - например первое же объяснение говорит про деление на 2 и 10, но мы ведь в алгоритме напротив - умножаем. Хм... Забавно. Кто-нибудь в курсе что тут происходит?
=A=L=X=
> например первое же объяснение говорит про деление на 2 и 10, но мы ведь в
> алгоритме напротив - умножаем.
не умножаем, а сдвигаем.
Деление столбиком тоже сдвиг и вычитание, а вычитание и сложение в принципе одно и тоже.
Количество сдвигов соответствует одному делению в столбик, но некоторая магия остается)
Tonal
> не умножаем, а сдвигаем.
В пояснениях не раз повторяется, что умножаем на 2 и добавляем 1 если верхний бит в числе подъехал единичный, что действительно тупо сама операция сдвига - 3 в одном. Но объясняторы не раз делают упор на умножении на 2.
> Деление столбиком тоже сдвиг и вычитание, а вычитание и сложение в принципе
> одно и тоже.
Это всё понятно, но не получается понять что происходит конкретно в алгоритме. Он какой то шиворот-навыворот, а взятие остатка от деления которым универсальные конвертеры к примеру работают вообще не просматривается.
=A=L=X=
> Кто-нибудь в курсе что тут происходит?
Происходит коррекция результата, на 6 при переходе из тетрады битов в тетраду (т.к для двоичной системы цена перехода равна 16, а для двоично-десятичной равна 10)
0iStalker
> Происходит коррекция результата, на 6 при переходе из тетрады битов в тетраду
То что коррекция опять таки понятно. Это написано в самом описании алгоритма.
Непонятно как она работает.
Ведь даже навскидку если задуматься, то эта коррекция может много раз происходить с разрядами по мере их сдвига влево, т.к. даже на границах отдельных бит, т.е. понятие цифры/разряда тут вообще какое то плавающее и непонятное.
Понятно только, что за счёт этого 8 исходных бит и могут в итоге расползтись по 12 разрядам BCD - их всё время "взбивают" этой вот коррекцией, причём многократно и в раздробленных битово комбинациях. Бред, но ведь работает...
0iStalker
> (т.к для двоичной системы цена перехода равна 16, а для двоично-десятичной
> равна 10)
Ааа... Кажется важная деталь прояснилась - коррекцию и надо делать каждый раз при переходе неких порогов в разрядной сетке, поэтому они многократно и планово запускаются. Хм... Удивительно только почему их там не корёжит при такой простой формулировке "стало больше 5 - корректируем", ведь казалось бы коррекции надо делать только после четырёх прокруток подряд на границах как раз разрядов.
=A=L=X=
> Непонятно как она работает.
Вот именно так она и работает, тут нет никаких других действий (и смыслов), при переходе разряда из тетрады в следующую - число в двоичной системе должно увеличиться на 16, вот его и добили до 16, пока оно ещё не переполнило разрядную сетку BCD
(BIN ) 1100 = (DEC) 12
(BIN) 1100 + 110 = (BCD) 1 0010 = (DEC) 12
А блин, дошло! Вот по этой ссылке нормально разжёвано: https://olduino.files.wordpress.com/2015/03/why-does-double-dabble-work.pdf
Там вообще не надо думать ни про какие разряды. В этом был мой затык - я пытался разглядеть как какие то группы разрядов из бинарного представления перемещаются в BCD-представление.
А нифига, это как раз и завело меня в тупик.
Всё что тут происходит же на самом деле это полная реконструкция числа методом умножения на 2, но в BCD-кодировке. Фактически никакие разряды тут не перетекают никуда, а просто полностью реконструируются. Мы просто сразу воссоздаём число в BCD-кодировке, просто из-за гениальности алгоритма это выглядит как "перетекание" двоичного числа в BCD - и в каком то смысле конечно так и есть, но на деле мы просто полностью его реконструируем просто проводя умножение на 2 с возможным добавление единицы тупо потому что суть числа не меняется в какой форме оно выражено.
Т.е. еще раз: каждый шаг алгоритма это не более чем умножение на 2 в BCD-кодировке с возможным добавлением единицы чтобы восстановить число по его полиноминальному разложению по степеням двойки чем оно является в бинарном представлении. А умножение на 2 можно рассматривать как сложение само с собой откуда легко и понять как делаются совершенно типовые BCD-коррекции.
Мда, а показалось прямо лютой битовой магией!
Тема в архиве.