I need to find a greatest number, x for given y and n such that x ^ y <= n
Here n can be very large number - 1 <= n <= 10^10
and 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
i have written a small program, But i want 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
Using a multiple-precision arithmetic library, such as gmpy2's iroot.
>>> import gmpy2
>>> root, exact = gmpy2.iroot(n, y)
This is simply an integer n-th root algorithm. It should be fast and correct even for huge numbers (something that floats cannot guarantee in the general case).
The second value returned is a boolean which indicates if the root is exact or not.
>>> print(*gmpy2.iroot(1024, 5))
4 True
>>> print(*gmpy2.iroot(480, 5))
3 False
you can use binary search on integer to move from your O(x) to O(log(x)) if you apply floating math then:
x^y = n // ^(1/y)
x = n^1/y
x = floor(pow(n,1/y))
your example n=400 and y=5 is like this:
x = floor(pow(400,1/5))
x = floor(pow(400,0.2))
x = floor(3.3144540173399868004685801443126)
x = 3
of coarse for big n will this not work with basic floating types. In such case either use bin search on big integers or implement your own bigint pow if you do not have it already at your disposal. Anyway both approaches are described here:
- Power by squaring for negative exponents do not get fouled by the title it is all integer math ...
[edit1]
after absorbing your comments:
n = < 1 , 10^10 >
y = < 1 , 10^5 >
no FPU just integer math
I would use binary search. You need to use at least ceil(log2(10^10))=34 bit variables for this so unsigned 64 bit QWORD it is. if you do not have such variables you need to implement it from lower bit width variables first.
The binary search mask will be:
m = 2^33 = 1<<33 = 0x0000000200000000
so you first need to implement pow and then root adapting code from linked answer here is C++ result:
#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;
}
for those of you that have just 32 bit arithmetics and have lover limit n<2^32 change the defines to:
#define T_bits 32
#define T_MSB 0x80000000
#define T DWORD
or use any other variable type you got at your disposal. The T is your data-type T_MSB is MSB bit set and T_bits is used bit count.
If you use:
root(400,5);
it will return 3. You can use your ** instead of pow I can not as my compiler does not recognize ** operator. Now to explanation of binary search
let assume your example. You start with x=1 then test x=2 then x=3 and so on until you cross x^y>=n so in reality you had checked pow(n,1/y) values. if we use n=10000, y=2 that will lead to 100 tests.
The binary search does not increment but set individual bits instead. 10000 has 14 bits so ceil(14/y)=7 so the process will be:
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
leading to only 7 tests instead of your naive 100.
