Наиболее значительный бит диаграмм умножения целых чисел и двоичных решений

15

Пусть и два двоичных числа с битами и двоичное число (длина ) произведения и . Мы хотим вычислить наиболее значимый бит произведения .уxyz = x y 2 n x y z 2 n - 1 z = z 2 n - 1z 0nz=xy 2nxyz2n1z=z2n1z0

Чтобы проанализировать сложность этой функции в модели бинарных диаграмм решений (в частности, разветвляющихся программ с однократным чтением), я пытаюсь найти некоторые эквивалентные выражения для случая . Первая очевидная вещь - это (здесь и - соответствующие целые числа двоичным числам). Я хочу понять, что произойдет, если я установлю постоянные входные биты. Например, если я установлю самый значимый входной бит от и до 0, я получу функцию константы 0. Но биты с меньшей значимостью не влияют на результат.z 2 n - 1 = 1 x y 2 2 n - 1 x y x yz2n1=1z2n1=1xy22n1xyxy

Существуют ли другие эквивалентные выражения для случая которые помогут больше увидеть, что произойдет, если я исправлю некоторые входные биты? Существуют ли усовершенствованные методы для вычисления произведения двух двоичных чисел, которые могут помочь? Или у вас есть другой подход к этой проблеме?z2n1=1

Марк Бери
источник
Я нахожу три вопроса в последнем абзаце довольно расплывчатыми. Пожалуйста, подумайте над более конкретным вопросом.
Slimton
Вопросы намеренно расплывчаты. Возможно, у кого-то есть новый подход или новые идеи для этой проблемы.
Марк Бери
Вы ищете ширину BDD для проблемы?
Сильвен Пейроннет
Меня интересует нижняя граница размера BDD.
Марк Бери
1
Вы имеете в виду нижнюю границу многочлена? Умножение находится в L, следовательно, оно имеет однородные BDD полиномиального размера (четная ширина 5, поскольку оно находится в равномерном ). NC1
Эмиль Йержабек поддерживает Монику

Ответы:

5

Интересным источником является Д.Е. Кнут: Искусство компьютерного программирования, том 4, глава 1, Побитовые приемы и приемы; Двоичные диаграммы принятия решений , Эддисон-Уэсли, Pearson Education 2009

На странице 96 есть BDD для всех битов z = x⋅y, где x и y имеют 3 бита. Это показывает, что в случае 3 битов BDD, представляющий наиболее значимый бит, имеет 7 нетерминальных узлов. Смотрите изображение ниже, я перерисовал его, используя ваши индексы x = (x2, x1, x0) и y = (y2, y1, y0).

На странице 140 в книге Кнута есть вопрос (№ 183) о том, что BDD представляет наиболее значимый бит для умножения двух чисел на бесконечно много битов (это называется «функцией ограничения ведущего бита») - это похоже на то, что вы ищем! Ответ на странице 223 дает первые уровни результирующего BDD и обсуждает количество узлов на всех уровнях, но, к сожалению, он не дает алгоритм для создания такого BDD.

Самый старший бит для умножения двух 3-битных чисел

Рис. 1: старший значащий бит для умножения (x2, x1, x0) * (y2, y1, y0)

meolic
источник
1
Спасибо за эту ссылку. Я не знал, что бинарные диаграммы решений являются частью этой «энциклопедии программирования».
Марк Бери