Найти наибольшее число x для заданного y и n, такого что x ^ y <= n

Question

Мне нужно найти наибольшее число x для заданного y и n такое, что x ^ y <= n

Здесь n может быть очень большим числом - 1 <= n <= 10^10 и 1 <= y <= 10^5

for example : 

for y = 5 and n = 1024
x ^ 5, then x = 4 (4 ^ 5 = 1024)

for y = 5 and n = 480
x ^ 5 , then x = 3 (3 ^ 5 = 243, 4 ^ 5 = 1024) - selecting lowest one, so x = 3

Я написал небольшую программу, но я хочу более эффективную технику, потому что n и y могут быть очень большими.

def get(y, n):

    x = 1
    while x ** y <= n:
        x += 1
    return x - 1

Answer 1

Использование арифметической библиотеки с множественной точностью, такой как gmpy2's iroot,

>>> import gmpy2
>>> root, exact = gmpy2.iroot(n, y)

Это просто целочисленный n-й корневой алгоритм. Это должно быть быстро и правильно даже для огромных чисел (что-то, что не может гарантировать в общем случае).

Второе возвращаемое значение является логическим значением, которое указывает, является ли корень точным или нет.

>>> print(*gmpy2.iroot(1024, 5))
4 True
>>> print(*gmpy2.iroot(480, 5))
3 False

Answer 2

Вы можете использовать двоичный поиск по целому числу, чтобы перейти от вашего O(x) в O(log(x)) если вы примените плавающую математику, то:

x^y = n  // ^(1/y)
x = n^1/y
x = floor(pow(n,1/y))

ваш пример n=400 а также y=5 это так:

x = floor(pow(400,1/5))
x = floor(pow(400,0.2))
x = floor(3.3144540173399868004685801443126)
x = 3

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

• Власть, возводя в квадрат отрицательные показатели, не зацикливается на названии, это целая математика...

[edit1]

после поглощения ваших комментариев:

n = < 1 , 10^10 >
y = < 1 , 10^5 >
no FPU just integer math

Я бы использовал бинарный поиск. Вам нужно использовать хотя бы ceil(log2(10^10))=34 bit переменные для этого так без знака 64 бит QWORD это. если у вас нет таких переменных, вам нужно сначала реализовать их из переменных с меньшей разрядной шириной.

Маска двоичного поиска будет:

m = 2^33 = 1<<33 = 0x0000000200000000

так что сначала нужно реализовать pow а потом root адаптация кода из связанного ответа - это результат C++:

#define T_bits 34
#define T_MSB  0x0000000200000000
#define T      QWORD

T pow(T x,T y)  // power by squaring returns z=x^y where x>=0, y>=0
    {
    T i,z=1;
    for (i=0;i<T_bits;i++)  // test all bits from MSB to LSB
        {
        z*=z;
        if (T(y&T_MSB)) z*=x;
        y<<=1;
        }
    return z;
    }
T bits(T x) // count how many bits is in x
    {
    T m=T_MSB,z=T_bits;
    for (;m;m>>=1,z--)
     if (x>=m) break;
    return z;
    }
T root(T x,T y) // bin search y-th root returns z=x^(1/y)
    {
    T m,z;
    m=((bits(x)+y-1)/y);        // ceil(bits(x)/y)
    if (m) m=1<<m; else m=1;    // MSB of the result for bin search 2^(ceil(bits(x)/y))
    for (z=0;m;m>>=1)           // test all bits of x from MSB to LSB
        {
        z|=m;                   // set actual bit
        if (pow(z,y)>x) z^=m;   // clear if result exceedes x
        }
    return z;
    }

для тех из вас, кто имеет только 32-битную арифметику и имеет ограничение любовника n<2^32 изменить определения на:

#define T_bits 32
#define T_MSB  0x80000000
#define T      DWORD

или используйте любой другой тип переменной, который есть в вашем распоряжении. T ваш тип данных T_MSB установлен бит MSB и T_bits используется счетчик битов.

Если вы используете:

root(400,5);

это вернется 3, Вы можете использовать свой ** вместо pow Не могу, так как мой компилятор не распознает ** оператор. Теперь к объяснению бинарного поиска

давай предположим твой пример. Вы начинаете с x=1 затем проверить x=2 затем x=3 и так до тех пор, пока вы не пересечете x^y>=n так на самом деле вы проверили pow(n,1/y) ценности. если мы используем n=10000, y=2 это приведет к 100 тесты.

Бинарный поиск не увеличивает, а устанавливает отдельные биты. 10000 имеет 14 битов так ceil(14/y)=7 поэтому процесс будет:

x with set bit|  x^y  | action
-------------------------------
0100 0000 bin |  4096 | none
0110 0000 bin |  9216 | none
0111 0000 bin | 12544 | clear
0110 1000 bin | 10816 | clear
0110 0100 bin | 10000 | none
0110 0010 bin | 10404 | clear
0110 0001 bin | 10201 | clear
-------------------------------
0110 0000 bin | 10000 | result

приводя только 7 тесты вместо вашей наивности 100,