Целочисленное деление с использованием только сложения, умножения, вычитания и максимума - PullRequest
Новая
       10

Целочисленное деление с использованием только сложения, умножения, вычитания и максимума

0 голосов
/ 30 апреля 2018

Предположим, у нас есть язык программирования & # x2124; который имеет следующий синтаксис: 

ℤ := 0 | 1 | (+ ℤ ℤ) | (* ℤ ℤ) | (- ℤ ℤ) | (max ℤ ℤ)

Для удобства мы можем определить новые формы связывания на нашем языке следующим образом:

  1. (not x) = (- 1 x)
  2. (abs x) = (- (max 0 (+ x x)) x)
  3. (min x y) = (- 0 (max (- 0 x) (- 0 y)))
  4. (nil x) = (not (min 1 (abs x)))

Этот язык достаточно мощный для выражения операторов ветвления и сравнения:

  1. (if x y z) = (+ (* x y) (* (not x) z))
  2. (eq x y) = (nil (- x y))
  3. (ne x y) = (not (eq x y))
  4. (le x y) = (nil (max 0 (- x y)))
  5. (gt x y) = (not (le x y))
  6. (ge x y) = (le y x)
  7. (lt x y) = (not (ge x y))

Теперь вопрос в том, можем ли мы определить целочисленное деление, это язык:

  1. (div x y) = ?
  2. (rem x y) = (- x (* y (div x y)))

Не думаю, что можно определить (div x y), потому что & # x2124; не имеет петель. Однако я не знаю, как это доказать. Обратите внимание, что если это возможно, то результат (div x 0) не имеет значения. Следовательно, либо определите (div x y), либо докажите, что это невозможно.

Ответы [ 2 ]

0 голосов
/ 01 мая 2018

Это невозможно.

Вызов функции f : Z -> Z в конечном итоге полином , если существует полином p с целочисленными коэффициентами и порогом t, таким образом, что для каждого x > t мы имеем f(x) = p(x). Пусть d(x) = [x/2] будет делением пола на два. d не является в конечном итоге полиномом, потому что разностная последовательность d имеет бесконечно много нулей (f(2y) = y = f(2y+1) для всех y), тогда как разностная последовательность каждого непостоянного полинома имеет конечное число. Достаточно показать, что все реализуемые функции в конечном итоге являются полиномами.

Доказательство проводится структурной индукцией. 0 и 1 являются полиномами. Нетрудно показать, что суммы, произведения и различия в конечном итоге полиномиальных функций в конечном итоге являются полиномами: используйте максимум двух порогов и тот факт, что множество полиномов замкнуто при этих операциях. Все, что остается, это закрытие под max.

Пусть f будет в конечном итоге многочленом через многочлен p, а g будет в конечном итоге многочленом через многочлен q. Если p = q, то ясно, что x |-> max(f(x), g(x)) в конечном итоге является полиномом через тот же полином. В противном случае обратите внимание, что p - q имеет конечное число реальных корней. Устанавливая порог на верхнюю границу для корней, мы наблюдаем, что функция max в конечном итоге становится полиномиальной через p или q, поскольку другой случай max здесь никогда не срабатывает.

0 голосов
/ 30 апреля 2018

Комбинация рекурсии и ветвления даст вам петли. 

(div x y) = (iff gte(x y) (+ 1 (div((- x y) y))) 0)

В более функциональных терминах мы делаем повторное вычитание. Если x> = y, добавьте единицу к частному, вычтите y из x и повторите. В противном случае верните 0. 

if x >=y
    return 1 + div(x-y y)
else
    return 0
...