Power of two to get an integer

Question

I need a (fairly) fast way to get the following for my code. Background: I have to work with powers of numbers and their product, so I decided to use logs. Now I need a way to convert the log back to an integer.

I can't just take 2^log_val (I'm working with log base 2) because the answer will be too large. In fact i need to give the answer mod M for given M.

I tried doing this. I wrote log_val as p+q, where q is a float, q < 1 and p is an integer. Now i can calculate 2^p very fast using log n exponentiation along with the modulo, but i can't do anything with the 2^q. What I thought of doing is finding the first integral power of 2, say x, such that 2^(x+q) is very close to an integer, and then calculate 2^p-x.

This is too long for me because in the worst case I'll take O(p) steps. Is there a better way?

Answer 1

If you need an answer mod N, you can often do each step of your whole calculation mod N. That way, you never exceed your system's integer size restrictions.

Answer 2

While working with large numbers as logs is usually a good approach, it won't work here. The issue is that working in log space throws away the least significant digits, thus you have lost information, and won't be able to go back. Working in mod space will also throw away information (otherwise your number gets to big, as you say), but it throws away the most significant ones instead.

For your particular problem POWERMUL, what I would do is to calculate the prime factorizations of the numbers from 1 to N. You have to be careful how you do it, since your N is fairly large.

Now, if your number is k with the prime factorization {2: 3, 5: 2} you get the factorization of k^m by {2: m*3, 5:m*2}. Division similarly turns into subtraction.

Once you have the prime factorization representation of f(N)/(f(r)*f(N-r)) you can recreate the integer with a combination of modular multiplication and exponentiation. The later is a cool technique to look up. (In fact languages like python has it built in with pow(3, 16, 7)=4.

Have fun :)