Editing Arbitrary-precision arithmetic (section)

==Example==
The calculation of [[factorial]]s can easily produce very large numbers. This is not a problem for their usage in many formulas (such as [[Taylor series]]) because they appear along with other terms, so that—given careful attention to the order of evaluation—intermediate calculation values are not troublesome. If approximate values of factorial numbers are desired, [[Stirling's approximation]] gives good results using floating-point arithmetic. The largest representable value for a fixed-size integer variable may be exceeded even for relatively small arguments as shown in the table below. Even floating-point numbers are soon outranged, so it may help to recast the calculations in terms of the [[logarithm]] of the number.

But if exact values for large factorials are desired, then special software is required, as in the [[pseudocode]] that follows, which implements the classic algorithm to calculate 1, 1×2, 1×2×3, 1×2×3×4, etc. the successive factorial numbers.

 constants:
   Limit = 1000                   ''% Sufficient digits.''
   Base = 10                      ''% The base of the simulated arithmetic.''
   FactorialLimit = 365           ''% Target number to solve, 365!''
   tdigit: Array[0:9] of character = ["0","1","2","3","4","5","6","7","8","9"]
 
 variables:
   digit: Array[1:Limit] of 0..9  ''% The big number.''
   carry, d: Integer              ''% Assistants during multiplication.''
   last: Integer                  ''% Index into the big number's digits.''
   text: Array[1:Limit] of character ''% Scratchpad for the output.''
 
 digit[*] := 0                    ''% Clear the whole array.''
 last := 1                        ''% The big number starts as a single-digit,''
 digit[1] := 1                    ''% its only digit is 1.''
 
 '''for''' n := 1 '''to''' FactorialLimit:    ''% Step through producing 1!, 2!, 3!, 4!, etc. ''
 
   carry := 0                     ''% Start a multiply by n.''
   '''for''' i := 1 '''to''' last:            ''% Step along every digit.''
     d := digit[i] * n + carry    ''% Multiply a single digit.''
     digit[i] := d '''mod''' Base       ''% Keep the low-order digit of the result.''
     carry := d '''div''' Base          ''% Carry over to the next digit.''
 
   '''while''' carry > 0:               ''% Store the remaining carry in the big number.''
     '''if''' last >= Limit: error("overflow")
     last := last + 1             ''% One more digit.''
     digit[last] := carry '''mod''' Base
     carry := carry '''div''' Base      ''% Strip the last digit off the carry.''
 
   text[*] := " "                 ''% Now prepare the output.''
   '''for''' i := 1 '''to''' last:            ''% Translate from binary to text.''
     text[Limit - i + 1] := tdigit[digit[i]]  ''% Reversing the order.''
   '''print''' text[Limit - last + 1:Limit], " = ", n, "!"

With the example in view, a number of details can be discussed. The most important is the choice of the representation of the big number. In this case, only integer values are required for digits, so an array of fixed-width integers is adequate. It is convenient to have successive elements of the array represent higher powers of the base.

The second most important decision is in the choice of the base of arithmetic, here ten. There are many considerations. The scratchpad variable {{mvar|d}} must be able to hold the result of a single-digit multiply ''plus the carry'' from the prior digit's multiply. In base ten, a sixteen-bit integer is certainly adequate as it allows up to 32767. However, this example cheats, in that the value of {{mvar|n}} is not itself limited to a single digit. This has the consequence that the method will fail for {{math|''n'' > 3200}} or so. In a more general implementation, {{mvar|n}} would also use a multi-digit representation. A second consequence of the shortcut is that after the multi-digit multiply has been completed, the last value of ''carry'' may need to be carried into multiple higher-order digits, not just one.

There is also the issue of printing the result in base ten, for human consideration. Because the base is already ten, the result could be shown simply by printing the successive digits of array ''digit'', but they would appear with the highest-order digit last (so that 123 would appear as "321"). The whole array could be printed in reverse order, but that would present the number with leading zeroes ("00000...000123") which may not be appreciated, so this implementation builds the representation in a space-padded text variable and then prints that. The first few results (with spacing every fifth digit and annotation added here) are:

{| class="wikitable" style="text-align: right; white-space: nowrap; line-height: 80%"
! colspan=2 style="text-align: center" | Factorial numbers
! colspan=2 style="text-align: center" | Reach of computer integers
|-
|                                                 1 = ||  1!
|-
|                                                 2 = ||  2!
|-
|                                                 6 = ||  3!
|-
|                                                24 = ||  4!
|-
|                                               120 = ||  5!
| 8-bit || style="text-align: left" | 255
|-
|                                               720 = ||  6!
|-
|                                              5040 = ||  7!
|-
|                                             40320 = ||  8!
| 16-bit || style="text-align: left" | 65535
|-
|                                           3 62880 = ||  9!  
|-
|                                          36 28800 = || 10!  
|-
|                                         399 16800 = || 11!
|-
|                                        4790 01600 = || 12!
| 32-bit || style="text-align: left" | 42949 67295
|-
|                                       62270 20800 = || 13!  
|-
|                                     8 71782 91200 = || 14!  
|-
|                                   130 76743 68000 = || 15!  
|-
|                                  2092 27898 88000 = || 16!  
|-
|                                 35568 74280 96000 = || 17!  
|-
|                               6 40237 37057 28000 = || 18!  
|-
|                             121 64510 04088 32000 = || 19!  
|-
|                            2432 90200 81766 40000 = || 20!
| 64-bit || style="text-align: left" | 18446 74407 37095 51615
|-
|                           51090 94217 17094 40000 = || 21!  
|-
|                        11 24000 72777 76076 80000 = || 22!  
|-
|                       258 52016 73888 49766 40000 = || 23!  
|-
|                      6204 48401 73323 94393 60000 = || 24!  
|-
|                   1 55112 10043 33098 59840 00000 = || 25!  
|-
|                  40 32914 61126 60563 55840 00000 = || 26!  
|-
|                1088 88694 50418 35216 07680 00000 = || 27!  
|-
|               30488 83446 11713 86050 15040 00000 = || 28!  
|-
|             8 84176 19937 39701 95454 36160 00000 = || 29!  
|-
|           265 25285 98121 91058 63630 84800 00000 = || 30!  
|-
|          8222 83865 41779 22817 72556 28800 00000 = || 31!
|-
|       2 63130 83693 36935 30167 21801 21600 00000 = || 32!
|-
|      86 83317 61881 18864 95518 19440 12800 00000 = || 33!
|-
|    2952 32799 03960 41408 47618 60964 35200 00000 = || 34!
| 128-bit || style="text-align: left" | 3402 82366 92093 84634 63374 60743 17682 11455
|-
| 1 03331 47966 38614 49296 66651 33752 32000 00000 = || 35!
|}

This implementation could make more effective use of the computer's built in arithmetic. A simple escalation would be to use base 100 (with corresponding changes to the translation process for output), or, with sufficiently wide computer variables (such as 32-bit integers) we could use larger bases, such as 10,000. Working in a power-of-2 base closer to the computer's built-in integer operations offers advantages, although conversion to a decimal base for output becomes more difficult. On typical modern computers, additions and multiplications take constant time independent of the values of the operands (so long as the operands fit in single machine words), so there are large gains in packing as much of a bignumber as possible into each element of the digit array. The computer may also offer facilities for splitting a product into a digit and carry without requiring the two operations of ''mod'' and ''div'' as in the example, and nearly all arithmetic units provide a ''[[carry flag]]'' which can be exploited in multiple-precision addition and subtraction. This sort of detail is the grist of machine-code programmers, and a suitable assembly-language bignumber routine can run faster than the result of the compilation of a high-level language, which does not provide direct access to such facilities but instead maps the high-level statements to its model of the target machine using an optimizing compiler.

For a single-digit multiply the working variables must be able to hold the value (base&minus;1){{sup|2}} + carry, where the maximum value of the carry is (base&minus;1). Similarly, the variables used to index the digit array are themselves limited in width. A simple way to extend the indices would be to deal with the bignumber's digits in blocks of some convenient size so that the addressing would be via (block ''i'', digit ''j'') where ''i'' and ''j'' would be small integers, or, one could escalate to employing bignumber techniques for the indexing variables. Ultimately, machine storage capacity and execution time impose limits on the problem size.