Geek Answers Handbook

Find the largest number x for given y and n such that x ^ y <= n

I need to find the largest number x for given y and n such that x ^ y <= n

Here n can be a very large number - 1 <= n <= 10 ^ 10 and 1 <= y <= 10 x 5 </p>

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

I wrote a small program, but I want a more efficient technique, because n and y can be very large.

def get(y, n):

    x = 1
    while x ** y <= n:
        x += 1
    return x - 1
-1
source share
2 answers

Using an arithmetic library with multiple points, for example gmpy2 iroot.

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

This is just the integer nth root algorithm. It should be fast and correct even for huge numbers (what floats cannot guarantee in the general case).

- , , .

>>> print(*gmpy2.iroot(1024, 5))
4 True
>>> print(*gmpy2.iroot(480, 5))
3 False
+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 . , , . :

[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 , ++:

#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.

0

More articles:


All Articles