Re: 11476 - Factorizing Large Integers
Posted: Mon Feb 23, 2009 4:45 pm
I have an idea. What if you try recursivity? Just like in math, when we use recurrent functions, we can apply the formulas also here:
We' ll use n!=(n-1)!*n, for any natural number n >=1.
#include <iostream.h>
int factorial(n)
{
if(n==1)
return 1;
else return factorial(n-1) * n;
}
main()
{
cout<<"n=";cin>>n;
factorial(n);
}
Let' s make a debug. (I won' t run for big natural numbers the program now
, but you' ll see the idea)
Let the natural number n be 5. The computer reads it, then the factorial(5) function is called. The variable answer takes the value of what this function return. And this will be:
return factorial(5-1)*5 = factorial(4)*5, which brings us to calling again the factorial function. Only this time, n=4. We check again if n=1, we see n=4 then we return factorial(4-1)*4 = . We can' t return a number so far, because we' re in the middle of a recurrent process: factorial(3)*4*5. What we can do is calling the factorial(3). This brings us to return factorial(2)*3. And multiplied with the previous result we get (factorial(2)*3*4*5 -factorial(2) equals factorial(1)*2. So until now, based on the previous calculus, we have factorial(1)*2*3*4*5 Now n==1 => we stop the recurrent calculus and we return the value of factorial(1), which is 1, plus the other factors: 2*3*4*5*6. Now, we have the entire result.
The complexity in time (O(n)) of this method is improved.
We' ll use n!=(n-1)!*n, for any natural number n >=1.
#include <iostream.h>
int factorial(n)
{
if(n==1)
return 1;
else return factorial(n-1) * n;
}
main()
{
cout<<"n=";cin>>n;
factorial(n);
}
Let' s make a debug. (I won' t run for big natural numbers the program now
, but you' ll see the idea)Let the natural number n be 5. The computer reads it, then the factorial(5) function is called. The variable answer takes the value of what this function return. And this will be:
return factorial(5-1)*5 = factorial(4)*5, which brings us to calling again the factorial function. Only this time, n=4. We check again if n=1, we see n=4 then we return factorial(4-1)*4 = . We can' t return a number so far, because we' re in the middle of a recurrent process: factorial(3)*4*5. What we can do is calling the factorial(3). This brings us to return factorial(2)*3. And multiplied with the previous result we get (factorial(2)*3*4*5 -factorial(2) equals factorial(1)*2. So until now, based on the previous calculus, we have factorial(1)*2*3*4*5 Now n==1 => we stop the recurrent calculus and we return the value of factorial(1), which is 1, plus the other factors: 2*3*4*5*6. Now, we have the entire result.
The complexity in time (O(n)) of this method is improved.