《n的阶乘高精度算法解析（N factorial high-precision algorithm analysis）.doc》由会员分享，可在线阅读，更多相关《n的阶乘高精度算法解析（N factorial high-precision algorithm analysis）.doc（13页珍藏版）》请在三一文库上搜索。
1、n的阶乘高精度算法解析（N factorial high-precision algorithm analysis）In a n factorial, n is greater than 16 n factorial results always overflow long plastic preservation, for just learning C students always feel very difficult, so Baidu in the search box type factorial two characters in search results, Baidu e
2、ncyclopedia interpretation, open the page, and turn down, saw a high precision factorial n of the C code:#include #define N 5000 it to hold larger number / / modifyInt main (void)Int, N, I, J, s, up, fN = 0;Scanf (%d, &n);For (I = 2, f0 = 1; I n; i+)For (J = up = 0; J = 0; i-) printf (%d, fi);Printf
3、 (n);Return 0;If you dont feel good enough to understand, you can change to the following code, and youll probably get a little better:#include #define N 5000 it to hold larger number / / modifyInt main (void)Int, N, I, J, s, up, fN = 0;Scanf (%d, &n);F0 = 1;For (I = 2; I n; / / i+) outer loop contr
4、ol factorial numberUp=0;For (j=0; J = 0; i-) printf (%d, fi);Printf (n);Return 0;When we first contact this code, will you feel very helpless? Dont you see why you do that?Heres my understanding of the code:First of all, in order to understand how this string of code works, the best way is to find a
5、 number to take in, find a good white paper, write well, draw a picture, from 0 to 5. In essence, just take 5 with you, because.0! *1=1! ;1! *2=2!;2! *3=3!;3! *4=4!;4! *5=5!;But 3! =610; 4; =24 is just over 10; taking 5 is more universal.Lets talk about what happened when we were in n=5.Since the ou
6、ter loop starts with i=2, we start with i=2.The inner loop is for (j=0, up=0; js=f0*2+0=1*2+0=2;Fj=s%10; -f0=2%10=2;Up=s/10; -up=2/10=0;TwoJ=1: s=fj*i+up; -s=f1*2+0=0*2+0=0;Fj=s%10; -f1=0%10=0;Up=s/10; -up=0/10=0;When the j is greater than or equal to 2, the case is the same as 2., and the result is
7、: f0=2; f1=0; f2=0.Two: i=31.j=0: s=fj*i+up; -s=f0*3+0=2*3+0=6;Fj=s%10; -f0=6%10=6;Up=s/10; -up=6/10=0;2.j=1: s=fj*i+up; -s=f1*3+0=0*3+0=0;Fj=s%10; -f1=0%10=0;Up=s/10; -up=0/10=0;When J is greater than or equal to 2, the case is the same as 2., and the result is: f0=6; f1=0; f2=0;.Three: i=4OneJ=0:
8、s=fj*i+up; -s=f0*4+0=6*4+0=24;Fj=s%10; -f0=24%10=4;Up=s/10; -up=24/10=2;TwoJ=1: s=fj*i+up; -s=f1*4+2=0*4+2=2;Fj=s%10; -f1=2%10=2;Up=s/10; -up=2/10=0;ThreeJ=2: s=fj*i+up; -s=f2*4+0=0*4+0=0;Fj=s%10; -f2=0%10=0;Up=s/10; -up=0/10=0;When the j is greater than or equal to 2, the case is the same as 3., an
9、d the results are: f0=4; f1=2; f2=0; f3=0;.Four: i=5OneJ=0: s=fj*i+up; -s=f0*5+0=20;Fj=s%10; -f0=s%10=20%10=0;Up=s/10; -up=20/10=2;TwoJ=1: s=fj*i+up; -s=f1*5+2=2*5+2=12;Fj=s%10; -f1=12%10=2;Up=s/10; -up=12/10=1;ThreeJ=2: s=fj*i+up; -s=f2*5+1=0*5+1=1;Fj=s%10; -f2=1%10=1;Up=s/10; -up=1/10=0;FourJ=3: s
10、=fj*i+up; -s=f3*5+up=0*5+0=0;Fj=s%10; -f3=0%10=0;Up=s/10; -up=0/10=0;When the j is greater than or equal to 4, the case is the same as 3., and the results are: f0=0; f1=2; f2=1; f3=0; f4=0;.By this time, we have brought the situation of n=5 into the program and completely written it out. What can we
11、 find out through this expansion? Before this problem is solved, lets take a look at the following multiplication:24*5=120, if we were in elementary school, that would be the case:Operation 1:24* 5- - -120We first use 4 by 5 to get 20 and write down 0 in 2; and let 2 multiplied by 5 by 10, 10 and 2
12、are 12, we should write down 2 in 1; because the 24 is a pre 0, we can think of is 0 multiplied by 5 and 1 by 1, then write down 1, the end of 24*5 multiplication.Do you have any inspiration for being here? Look at the next example of multiplication, and perhaps youll have some ideas:Operation 2:122
13、* 45- - - - - - - - - - - -610488- - - - - - - - - - - -5490This is the multiplication we used in elementary school, but we can also deform the multiplication process above and get another similar multiplication:Operation 3:122* (45) in the operation / / the 45 as a whole_First with 122 of the highe
14、st 2 multiplied by 45 to get 90, write down 0 in 9; in 122 to the second high in 2 by 45 to get 90, plus carry 9, 99, write down the most high 9, the lowest in 9; and let the low of 122 in 1 times 45 get 45, 45 and 9 carry, 54, write down 4, 5; because the 122 can be considered to be 0122,So we get
15、0 by 0, 45 by 0, and 5 by carry 5, write down 5, we can still get 5490 this answer, in fact, operation 3 can be equivalent to the following 4:Operation 4:45* 122- - - - - - - - - -909045- - - - - - - - - -5490We found that the operation of 3 and 4 is an arithmetic operation, operation process becaus
16、e they are all the same, but because the product we usually use the computation operation method 2 number two, even 4 people operation methods are rarely used, not to mention the 3 operations. Although the method of computing 3 is rarely used, it is actually the method used in programming, especiall
17、y in the high precision operations of factorial operations.In the process of operation in 3 122*45 is equivalent to the internal circulation in the whole cycle, equivalent to 122 of the top 44 (outer circulating i-1) product number (assuming is actually not, this product is equivalent to I-1, the eq
18、uivalent of 45 factorial) outer loop in i;In arithmetic, the program operates 45 as a whole. Lets see how the program uses arrays to hold large integers. Still use 122*45 as an example.In fact, each element in the array holds the elements of fi=0&fi=9. In the multiplication of 122*45, there are122|
19、| |F2 f1 f0So thereOperation 3:122* (45)- - - - - - - - - -Equivalent toOperation 5:F3 f1 f0* I_We have 3 arithmetic operation process into 5 operations can be found in this process, and we will n=5 the program into the analysis of the process is the same, here, we have fully proved that the program
20、 code in the inner loop is I-1 factorial results multiplied by I process, and this method is used in the process of our in 3 with the method of operation.Here, we have been able to fully understand the Baidu encyclopedia in the program code provided by the operation process, the outer loop control o
21、rder multiplier, just as:0! *1=1! ;1! *2=2!;2! *3=3!;3! *4=4!;4! *5=5!;Internal loop control i-1! The process of product quadrature with I, such as 4! *5 process, of which 4! In the previous inner loop, the loop has been found and stored in an array.The analysis process is over, dear friends. Do you already understand?