When calculating factorials exceeding 20 or more, the result value of factorials tends to be very large. The factorial result of a very small number may exceed the range of integers in the current personal computer. If you need a large factorial, for example, above 1000 cannot be solved in a simple recursive way. On the Internet, I have seen many algorithms about large integer factorials written in C, C++ and C#, including many classic but also many rough articles. The array crosses the boundary and you can see at a glance that the program itself cannot run. When reprinting other people's articles, take a closer look at the code. Alas, rough. It's the Chinese New Year, I feel so tired at home. I carefully analyzed and used Java to implement a program to calculate the super-large integer factorial. The idea is taken from the Internet and is optimized and improved by me personally.
This method uses the "array carry" algorithm. When the value range of computer variables is exceeded, multi-digit multiplication is converted into single-digit multiplication. Such as 11! =39916800. If you need a factorial of 12, you need to multiply 39916800 and 12, and you can use the multiplication allocation rate. The multiplication vertical formula is shown in the figure below:
Use an array to save the result of each bit of factorial, and an array element to save the one-digit number. For example: 399 of factorial result of 11
16800 is saved to the 8 elements of the array. To calculate the factorial of 12, multiply the value in each array element by 12, and save the result to the original array element. Next, we will determine whether each array element needs to carry. Through carry operations, the number saved by each element in the array is only one-digit. The schematic diagram is as follows:
Theoretically, as long as the computer memory space allows, the factorial result can be saved, no longer limited by the range of variables, but only limited by the addressing capability of the operating system and the computer memory. Friendly tips: If the required factorial number is large, you can define the array as a long type to avoid overflow when calculating the product of the unit number.
The implementation code is as follows:
public class BigInteger {/** * Calculate carry* @param bit array* @param pos Used to determine whether it is the highest bit of the array*/private void carry(int[] bit, int pos){int i ,carray = 0;for (i = 0 ; i<= pos ;i++)// Check whether carry is required bit by bit from 0 to pos {bit[i] += carray;//Accumulate carry if(bit[i] <= 9) //No carry if less than 9 {carray = 0;} else if(bit[i] >9 && i<pos)//Greater than 9, but not the highest bit{carray = bit[i]/10;//Save carry value bit[i] = bit[i]%10;//Get the single digit of this bit} else if(bit[i] > 9 && i >= pos)//Greater than 9, and is the highest bit{while(bit[i] > 9)//Loop forward bit{carray = bit[i]/10;//Calculate carry value bit[i] = bit[i] % 10;//The current first digit i ++ ;bit[i] = carray;//Save carry value in the next bit}}}}}/** * Large integer factorial* @param bigInteger The large integer calculated by the calculation*/private void bigFactorial(int bigInteger){int pos =0;//int digit;//Data length int a , b ;int m = 0 ;//Statistics output digits int n = 0 ;//Statistics output rows double sum = 0;//Factory digits for (a = 1 ; a <= bigInteger ; a ++)//Calculate factorial digits {sum += Math.log10(a);}digit = (int)sum + 1;//Data length int[] fact = new int[digit];//Initialize an array fact[0] = 1;//Suppose the single digit is 1for (a = 2 ; a <= bigInteger ; a++ )//Multiply 2^bigInteger with the original product one by one {for (b = digit-1 ; b >= 0 ; b--)//Find the highest digit {} {if( fact[b] != 0 ){pos = b ;//Record the highest bit break;}}for (b = 0; b <= pos ; b++){fact[b] *= a ;//Each bit is multiplied by i }carry(fact,pos);}for (b = digit-1 ; b >= 0 ; b --){if(fact[b] != 0){pos = b ;//Record the highest bit break;}}System.out.println(bigInteger +"Factory result is: ");for (a = pos ; a >= 0 ; a --)//Output calculation result{System.out.print(fact[a]);m++;if(m % 5 == 0){System.out.print(" ");}if(40 == m ){System.out.println("");m = 0 ;n ++;if(10 == n ){System.out.print("/n");n = 0;}}}System.out.println("/n"+" factorials have: "+(pos+1)+" bits");}public void doBigFactorial(int bigInteger){int timeBegin=(int) System.currentTimeMillis(); this.bigFactorial(bigInteger);int timeFinishi=(int) System.currentTimeMillis();int time = timeFinishi-timeBegin;System.out.println("Calculation time: " + time +"msec" );}public static void main(String[] args){BigInteger bi = new BigInteger();bi.doBigFactorial(100000);}}Calculate the factorial of 10,000 and display the following:
As a result, the console obviously cannot save the content. There are 450,000 factorials of 100,000, which is equivalent to a novel with 450,000 words. The factorial results of 1000 are as follows:
The console can be displayed in full.
Summarize
The above is all the content of this article about the detailed explanation of the Java version of super large integer factorial algorithm code - level 10,000. I hope it will be helpful to everyone. Interested friends can continue to refer to this site:
" Analysis of operation code of power index value in java "
" Java Programming Implementation Code Example for Exclusive Or Operation of Hexadecimal Strings "
" Java Programming Implementing User-Based Collaborative Filtering Recommended Algorithm Code Example "
If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!