Как построить оператор сравнения (компаратор) в арифметической схеме - PullRequest
Новая
       71

Как построить оператор сравнения (компаратор) в арифметической схеме

0 голосов
/ 25 июня 2019

Я пытаюсь преобразовать основную программу в арифметическую схему. Я застрял на шаге преобразования оператора больше чем в арифметическую схему. Если быть точным, я не знаю, как преобразовать следующее в арифметическую схему (где x, y - это ввод):

if x >= y: return 1 else: return 0

Чтобы было ясно, я должен быть в состоянии выразить это с помощью арифметической схемы. Это означает, что мне нужно иметь возможность вычислить это, используя только сложение и умножение чисел (в Z_p).

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

1 Ответ

0 голосов
/ 25 июня 2019

Вам не нужна какая-либо схема, если вы используете правильное кодирование для ваших данных. Лучшим и наиболее широко используемым для кодирования целых чисел со знаком является дополнение к двум .
Положительные числа кодируются их двоичным кодом и отрицательным числом A & lt0; считается положительным, учитывая, что 2 ^ n- | A | = 2 ^ n + A, где n - количество бит n кода.

Два дополнения имеют (как минимум) два основных преимущества.
Первый заключается в том, что он значительно упрощает арифметические операции. Например, поскольку отрицательное число A кодируется арифметически с помощью 2 ^ n + A, не нужно заботиться о знаке операндов, при условии, что бит больше 2 ^ n игнорируется, и добавление чисел со знаком идентично добавлению без знака.

Вторым преимуществом является то, что положительные числа находятся в диапазоне 0..2 ^ (n-1) -1, и их старший бит всегда не установлен. Отрицательные числа находятся в диапазоне -1 ..- 2 ^ (n-1). После добавления к 2 ^ n диапазон их кода равен 2 ^ (n-1) .. 2 ^ n-1 и соответствует числу с установленным старшим значащим битом. Таким образом, чтобы узнать, является ли число> = 0, нужно просто проверить его самый старший бит.

Так что для этого не существует реального "контура" или арифметического оператора. В программе это может быть сделано путем вычисления «и» с помощью MSB. 

int is_positive(int x) { return (x & (1<<31)) == 0 ); }

Невозможно выразить это только арифметическими операциями без сравнения и, и, или, или. И у вас должен быть способ определить, является ли число полностью равным 0, что требует логических элементов.

...