Можем ли мы вычислить

Я ищу эффективный алгоритм для решения проблемы:

Входные данные : положительное целое число $3^n$ (сохраняется в виде битов) для некоторого целого числа $n \geq 0$ .

Вывод : число $n$ .

Вопрос : Можем ли мы вычислить $n$ из битов $3^n$ за $O(n)$ времени?

Это теоретический вопрос, мотивированный моим ответом на вопрос по математике. Как найти формулу для этой биекции? , В этом вопросе автор хотел найти биекцию из

{2^{n} 3^{m} : n \geq 0 and m \geq 0}

$\{2^n 3^m: n \geq 0 \text{ and } m \geq 0\}$ и натуральных чисел

N = {1, 2, \dots}

$\mathbb{N}=\{1,2,\ldots\}$ . Я предложил

2^{m} 3^{n} \mapsto 2^{m} (2 n + 1)

$2^m 3^n \mapsto 2^m(2n+1)$ как решение. Другой ответ там утверждал, что «нет простой формулы», что заставляет меня задаться вопросом, насколько (вычислительно) просто мое предлагаемое решение.

С моим предложенным решением, если мы знаем $n$ и $m$ , мы можем легко вычислить $2^m(2n+1)$ (запишите двоичные цифры $n$ за которыми следует $1$ последующими $m$ нулями). Это занимает $O(n+m)$ времени.

Нахождение из битов равносильно нахождению младшего значащего бита (который можно вычислить путем подсчета сдвигов правильных битов, оставив в памяти ). Это занимает времени. $m$ $2^m 3^n$ $3^n$ $O(m)$

Однако нам также нужно найти , что может быть сложнее. Можно было бы найти путем повторного деления на , но это кажется расточительным. Требуется операций деления, каждая из которых займет времени, так что это всего времени. [На самом деле, после каждой итерации количество цифр будет линейно уменьшаться, но это все равно приводит к времени .] $n$ $n$ $3$ $n$ $O(n)$ $O(n^2)$ $O(n^2)$

Кажется, что мы должны быть в состоянии использовать, зная, что вход является степенью . $3$

ds.algorithms time-complexity Ребекка Дж. Стоунс
источник

Какая у вас точная модель вычислений? Какие операции разрешены за

раз? (Если бы мы могли делать арифметику с такими числами, как

это было бы весьма полезно ...)

O (1)

$O(1)$

\log_{2} 3

$\log_2 3$

Юваль Фильмус

Может ли downvoter объяснить downvote? Это не кажется тривиальным вопросом вообще. Какое время работы лучше при разумной модели вычислений?

Юваль Фильмус

Я представляю ленты с 0, 1 и пустыми ячейками (с бесконечным количеством лент). Я хочу, чтобы операции однобитового переключения и переключения влево / вправо выполнялись за

раз. (Если у нас есть маркер 0-го бита на бесконечной ленте, то сдвиг влево / вправо достигается путем смещения маркера). В отличие от машины Тьюринга, я не хочу, чтобы перемещение указателя занимало какое-то время. Таким образом, «переключение 0-го бита» занимает то же время, что и «переключение 124126-го бита».

O (1)

$O(1)$

Ребекка Дж. Стоунс

Это может быть как-то связано с этим вопросом

Ж.-Е.

Является ли нижняя граница

очевидной?

Ω (n)

$\Omega(n)$

Борис Бух,

Ответы:

Очевидный подход:

(1) Вычислить приближение к . Вы можете приблизить его с точностью до аддитивной ошибки, равной 1, подсчитав количество битов в данном двоичном представлении, и с точностью до аддитивной ошибки, , дополнительно взглянув на верхнюю часть $\log_2(3^n)$ $\epsilon$ биты входных данных. Это должно быть достаточночтобы выбрать постоянное значение, так что (после объединения с ошибкой на стадии (2)) конечных результатов концов вверхпределах аддитивной погрешностиот правильной. $O(\log\frac{1}{\epsilon})$ $\epsilon$ $1/2$

(2) Вычислить приближение к . Я не знаком с алгоритмами для этого, но я ожидаю, что они занимают полиномиальное время в количестве битов точности, которые вам нужны, и вам нужно только битов точности. $\log_2(3)$ $O(\log n)$

(3) Разделите ответ на (1) на ответ на (2) и округлите до ближайшего целого числа.

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

Дэвид Эппштейн
источник

\log_{2} (3)

$\log_2(3)$

t

$t$

O (M (t) \log t)

$O(M(t) \log t)$

M (t) \leq O (t \log t 2^{\log^{*} t})

$M(t) \leq O(t \log t 2^{\log^* t})$

t

$t$

Спасибо за ссылку и извиняюсь за то, что слишком ленив, чтобы самому ее найти.

Дэвид Эппштейн

$n>0$ $3^n$ $L = \lceil \log_2(3^n)+1\rceil$

\frac{L - 2}{\log_{2} 3} \leq n \leq \frac{L - 1}{\log_{2} 3} .

$\frac{L-2}{\log_2 3} \le n \le \frac{L-1}{\log_2 3}.$

L \geq 1

$L\ge 1$

3

$3$

L

$L$

n = ⌊ \frac{L - 1}{\log_{2} 3} ⌋ .

$n = \left\lfloor\frac{L-1}{\log_2 3}\right\rfloor.$

Jeffε
источник

$k$ $3^n$ $3^n \bmod 10^k$ $3^n \bmod 5^k$ $3$ $5^k$ $3$ $\varphi(5^k)=5^{k-1} \times 4$

Поэтому, используя дискретный логарифм и поднятие по Хензелю, я думаю, вы должны быть в состоянии вычислить из младших цифр очень эффективно. Другими словами, вы начинаете с вычисления с цифры , беря дискретный лог в основание по модулю ; это показывает и может быть сделано за время. Затем вы найдете дискретный логарифм к базе по модулю ; это показывает , и может быть сделано в $n \bmod \varphi(5^k)$ $k$ $3^n$ $n \bmod 4$ $3^n$ $3^n \bmod 5$ $3$ $5$ $n \bmod 4$ $O(1)$ $3^n \bmod 25$ $e$ $25$ $n \bmod 20$ $O(1)$ время (используя знания , вам нужно попробовать всего возможностей). Итерация. На каждом этапе вы используете знания чтобы помочь вам эффективно вычислить дискретный журнал , используя тот факт, что есть только возможных значений для . $n \bmod 4$ $5$ $n \bmod \varphi(5^{k-1})$ $3^n \bmod 5^k$ $5$ $n \bmod \varphi(5^k)$

Теперь просто позвольте быть достаточно большим, и это показывает . $k$ $n$

Вам нужно выяснить, является ли время выполнения , но мне кажется, что это может быть. Я подозреваю, что достаточно, чтобы позволить , и я подозреваю, что вы можете выполнять каждую итерацию за время, всего . $O(n)$ $k=O(n)$ $O(1)$ $O(n)$

DW
источник