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

Пусть и два двоичных числа с битами и двоичное число (длина ) произведения и . Мы хотим вычислить наиболее значимый бит произведения . $x$ $y$ $n$ $z = x \cdot y\$ $2n$ $x$ $y$ $z_{2n-1}$ $z = z_{2n-1} \ldots z_0$

Чтобы проанализировать сложность этой функции в модели бинарных диаграмм решений (в частности, разветвляющихся программ с однократным чтением), я пытаюсь найти некоторые эквивалентные выражения для случая . Первая очевидная вещь - это (здесь и - соответствующие целые числа двоичным числам). Я хочу понять, что произойдет, если я установлю постоянные входные биты. Например, если я установлю самый значимый входной бит от и до 0, я получу функцию константы 0. Но биты с меньшей значимостью не влияют на результат. $z_{2n-1} = 1$ $z_{2n-1} = 1 \Leftrightarrow x \cdot y \geq 2^{2n-1}$ $x$ $y$ $x$ $y$

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

cc.complexity-theory binary-decision-diagrams Марк Бери
источник

Я нахожу три вопроса в последнем абзаце довольно расплывчатыми. Пожалуйста, подумайте над более конкретным вопросом.

Slimton

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

Марк Бери

Вы ищете ширину BDD для проблемы?

Сильвен Пейроннет

Меня интересует нижняя граница размера BDD.

Марк Бери

Вы имеете в виду нижнюю границу многочлена? Умножение находится в L, следовательно, оно имеет однородные BDD полиномиального размера (четная ширина 5, поскольку оно находится в равномерном ).

{N C}^{1}

$\mathrm{NC}^1$

Эмиль Йержабек поддерживает Монику

Ответы:

Интересным источником является Д.Е. Кнут: Искусство компьютерного программирования, том 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
источник

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

Марк Бери