CODEWITHSUNDEEP
algorithmmodulenumbers
Narendra Modi
Narendra Modi

Reputation: 861

Making a very large calculation

I am want to calculate the value

X =n!/2^r

where n<10^6 and r<10^6
and it's guarantee that value of X is between O to 10

How to calculate X since i can't simple divide the factorial and power term since they overflow the long integer.

My Approach
Do with the help of Modulus. Let take a prime number greater than 10 let say 101 

 X=  [(Factorial N%101)*inverse Modulo of(2^r)]%101;

Note that inverse modulo can easily be calculate and 2^r%101 can also be calculated.

Problem:
It's not guarantee that X is always be integer it can be float also. My method works fine when X is integer ? How to deal when X is a floating point number

Upvotes: 1

Views: 118

Answers (4)

user4668606
user4668606

Reputation:

An approach that would be tunable for precision/performance would be the following:

Store the factorial in an integer with a fixed number of bits. We can drop the last few digits if the number gets too large, since they won't affect the overall result altogether that much. By scaling this integer larger/smaller the algorithm gets tunable for either performance or precision.

Whenever the integer would overflow due to multiplication, shift it to the right by a few places and subtract that value from r. In the end there should be a small number left as r and an integer v with the most significant bits of the factorial. This v can now be interpreted as a fixed-point number with r fractional digits.

Depending upon the required precision this approach might even work with long, though I haven't had the time to test this approach yet apart from a bit experimenting with a calculator.

Upvotes: 0

dmuir
dmuir

Reputation: 4431

Except for a very few cases (with small n and r) X will not be an integer -- for if n >= 11 then 11 divides n! but doesn't divide any power of two, so if X were integral it would have to be at least 11.

One method would be: initialise X to one; then loop: if X > 10 divide by 2 till its not; if X < 10 multiply by the next factors till its not; until you run out of factors and powers of 2.

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65498

If approximate results are OK and you have access to a math library with base-2 exponential (exp2 in C), natural log gamma (lgamma in C), and natural log (log in C), then you can do

exp2(lgamma(n+1)/log(2) - r).

Upvotes: 1

IVlad
IVlad

Reputation: 43487

Find the power that 2 appears at in n!. This is:

P = n / 2 + n / 2^2 + n / 2^3 + ...

Using integer division until you reach a 0 result.

If P >= r, then you have an integer result. You can find this result by computing the factorial such that you ignore r powers of 2. Something like:

factorial = 1
for i = 2 to n:

    factor = i
    while factor % 2 == 0 and r != 0:
        factor /= 2
        r -= 1

    factorial *= factor

If P < r, set r = P, apply the same algorithm and divide the result by 2^(initial_r - P) in the end.

Upvotes: 0

Related Questions