Modulo recursive problem for exponents with decimals

[darkob93]

EDIT: cleaned out some of the stuff from int main() to make it more readable.

Hi, I have an exercise problem where I'm supposed to calculate N!modM where N! is a really big number without overflow issues. I managed to do it using ln function to output smaller numbers. However I had to also recursively implement modM of this number. So I read up on modular arithmetic, read some articles on how it's done for exponentiation however I keep getting the wrong number. I think I've wrongly applied the multiplication formula.The problem appears to arise when I use a decimal value where a^e/nmodM = (a^emodM * a^1/n) where the result is wrongly computed.
using namespace std;

double logfactorial(int N)
{
if (N < 0)
{
cerr << "Cannot calculate factorial of a negative number." << endl;
return 0.0;
}
if (N == 0) return 0.0;
double t = log(N);
t += logfactorial(N-1);
return t;
}

double modulo (double b, int exp, int M) // (b^exp)modM
{
if (exp == 0) return 1.0;
double v = modulo(b, exp/2, M); // v = (a%modM * b%modM)modM, modular property
if(exp % 2 == 0) return fmod(v*v, M);
else if (M < b) v = fmod(fmod(fmod(b, M) * v, M) * v, M);
else v = fmod(fmod(b * v, M) * v, M);
return v;
}

int main()
{

int N;
int M;
cout << "Enter N and M in given order to calculate N!modM." <<endl;
cout << "N cannot be a negative number." <<endl;

while (cin >> N >> M)
{
if (N > 0) break;
cout << "N cannot be a negative integer." << endl;
}
double fact = logfactorial(N);
int t = fact;
fact -= t;

cout << "e^fact = " << exp(fact) << endl;
cout << "(e^fact)modM = " << fmod(exp(fact), M) << endl;
cout << N << "! =~ e^" << setprecision(10) << logfactorial(N) << endl;
cout << N << "!mod(" << M << ") =~ "<< setprecision(10) << fmod(modulo(double(exp(1.0)), logfactorial(N), M)*fmod(exp(fact), M), M) << endl;
return 0;
[/code]

Here is the output:
Enter N and M in given order to calculate N!modM.
N cannot be a negative number.
4 5 // N = 4, M = 5
e^fact = 1.19489
(e^fact)modM = 1.19489
4! =~ e^3.17805383
4!mod(5) =~ 1.785317807

I've tried debugging it and calculating it by hand for a small number 4 and 5 as you can see. However 4!Mod5 = 24Mod5 = 4.
The multiplication rule says: A*BmodM = (AmodM * BmodM)modM however when I tried to do e^3modM = (e^2modM * emodM)modM), however I am getting 2 different values which I believe is the cause of the problem. I believe the problem arises from using fractions. I am working on a new solution right now, not sure if it will work. In the mean time, I hope someone here give me a clue or a hint on how to solve this.

[jonnin]

do you understand the difference between mod and fmod? I didnt read the code in great depth, but that stood out as a possible issue. Fmod is NOT exactly mod, its 'similar'.

[darkob93]

Yes, fmod is used for float types, while mod is used for integers, since both types have different binary representation 2 operators are needed. I found a second solution to the problem to evaluate big N! and then apply N!modM. But it's not exactly a great solution and the solution author of the book I'm reading had in mind. I think I discovered an interesting pattern that arises in N! numbers though. But, the problem with current solution I'm having is the math. Try to evaluate e^3.5mod5 and (e^3mod5 * e^0.5mod5)mod and see if you get the the same number of both equations.. This is where my algorithm collapses, at math level. I just don't know if there's a formula or property I can use to fix this in the way this solution is written as of now. I think I am supposed to find the solution using exponents because according to the previous exercise, I was supposed to find a recursive function for log(N!). So it would make sense if I were to use it to calculate N!modM.

[jonnin]

I get extremely close results with the below. Which is not exactly what you said, I corrected your logic for ep2. Pardon my C.

double zz;
double e = 2.7182818284590452353602874713527;
double ep1 = fmod(pow(e,3.5),5);
double ep2 = fmod((e*e*e) * sqrt(e),5);
printf("%1.20f\n%1.20f\n%1.20f\n", ep1,ep2,ep1-ep2);

-------------------------------------------------------
C:\c>a
3.11545195869230440167
3.11545195869231150709
-0.00000000000000710543

I get 0.14~stuff for doing fmod((e*e*e),5) * fmod(sqrt(e),5) -- it isnt right.

I have come to trust the modern windows' calculator program.
it gives
3.1154519586923137506532493503886


as to your problem, there is a highly reliable factorial approximation equation for larger factorials... I am wondering if you could factor that and insert a modulo or something into it.. it would be an approximation but presumably log(N!) is also an approximation, I don't know if the errors would be within your needs... or attack it with the log properties...

[darkob93]

jonnin, very nice and simple code however the exercise I was given was not that simple. I was tasked in Exercise1 of recursive functions to find log(N!) without overflow issues. Which I did, you can see my solution, a faster and even better solution would have been to use Stirling's approximation however that was not the solution for the exercise. Then I was asked to find (N!)modM without overflow for the modulus. I assumed I was supposed to use my recursive logN! function. However the result will never be correct due to a simple example of e^3.5mod5 != (e^3modM *e^0.5)modM which comes out of modular arithmetic. I am wondering on whether there is a way to use exponents with decimals for modular exponentiation.

Here is the exercise: Create a program to calculate N!modM such that overflow is no longer issue. Try running your program for M = 997 and N = 10^3, 10^4, 10^5 and 10^6, to get an indication of how your programming system handles deeply nested recursive calls. Now I've modified double logfactorial(int N) function to also call a new modulus function that uses addition properties of modular arithmetic. The function now looks something like this: int logfactiorialmod(N, M). I found another method to calculate N! using primes and multiples and apply modular arithmetic to that form of N! as well. Thanks for your answer! If you want to see the new code let me know in case you 're wondering. However for particularly large N, there is an overflow stack issue due to depth of recursion.

[lastchance]

You are making it ridiculously complicated. Calculate the factorial as a succession of multiplies, taking the modulus AFTER EACH. Then you won't overflow.

But why do you want to calculate N! mod M if N is 1000 and M=997? The answer is 0. Obviously. Same for any other N! mod M when N is greater than M ... N! contains a factor of M.

#include <iostream>
using namespace std;

using INT = unsigned long long;

INT factorial( INT N, INT M ) { return N <= 1 ? 1 : N * factorial( N - 1, M ) % M; }

int main()
{
   INT N, M;
   cout << "Input N M: ";   cin >> N >> M;
   cout << N << "! = " << factorial( N, M ) << " mod " << M << '\n';
}

Input N M: 5 11
5! = 10 mod 11

Input N M: 1000 997
1000! = 0 mod 997

[darkob93]

Yes, you are right I was overcomplicating, should have thought up of the easiest way to solve it instead of overcomplicating it. My new function is simpler but your answer is much simpler. Thank you so much for help! I won't overcomplicate it unless there is no simpler solution.