Идеальное обнаружение мощности за линейное время

Question

Я пытаюсь написать программу на C, которая, учитывая положительное целое число n (> 1), определяет, существуют ли числа x и r, так что n = x ^ r

Это то, что я делал до сих пор:

while (c>=d) {
    double y = pow(sum, 1.0/d);
    if (floor(y) == y) {
        out = y;
        break;
    }

    d++;
}

В вышеприведенной программе "c" - это максимальное значение для показателя степени (r), а "d" начнется с значения, равного 2. Y - значение, которое нужно проверить, и переменная«out» устанавливается для вывода этого значения позже.По сути, сценарий проверяет, существуют ли квадратные корни y: если нет, он пытается использовать квадратный куб и т. Д. Когда он его находит, он сохраняет значение y в «out», чтобы: y = out ^ d

Мой вопрос: есть ли более эффективный способ найти эти значения?Я нашел некоторую документацию в Интернете, но это намного сложнее, чем моя школьная алгебра.Как я могу реализовать это более эффективным способом?

Спасибо!

Answer 1

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

Это открытый исходный код, поэтому вы можете проверить исходный код и посмотреть, как они это делают, если вы не хотите вносить всю библиотеку.

Answer 2

Если n помещается в целочисленную переменную фиксированного размера (например, 32-разрядную), оптимальным решением, вероятно, будет просто жесткое кодирование списка таких чисел и его двоичный поиск. Имейте в виду, что в диапазоне int примерно 1003 *

• sqrt(INT_MAX) идеальные квадраты
• cbrt(INT_MAX) идеальные кубики
• и т.д.

В 32 битах это примерно 65536 + 2048 + 256 + 128 + 64 + ... <70000. </p>

Answer 3

После того как вы вычислили y в

double y = pow(sum, 1.0/d);

, вы можете получить ближайший к нему int и использовать свою собственную степенную функцию для проверки условия равенства с суммой.

int x = (int)(y+0.5);
int a = your_power_func(x,d);
if (a == sum)
     break;

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

Answer 4

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

Итак:

log_r(x) = log(x)/log(r)

Поэтому вам нужно вычислить:

x = log(n)/log(r)

(В моей шее из дерева это является математикой для старших классов. Это сразу объясняет, что мне нужно посмотреть, правильно ли я запомнил эту личность :))