Computer representation of numbers
The key issue with large numbers like factorials, is how they are represented on the computer. For performing mathematical operations the computer hardware has fixed size numbers. For integer number types, this is related to the size of registers and number of wires connecting devices. Each bit of a number is held in a flip-flop. A flip-flop is an electronic device with two stable states, one representing a 0 and the other a 1.Two types of integers are signed and unsigned. Unsigned integers are represented in straight binary based numbers. While signed integers are represented in twos compliment. To change signs in twos compliment, invert (compliment) all bits then add one. The following table shows four bit binary numbers and their values for both signed and unsigned integers.
8 bit Sign bit | 4 bit | 2 bit | 1 bit | Unsigned | Signed |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 0 | 2 | 2 |
| 0 | 0 | 1 | 1 | 3 | 3 |
| 0 | 1 | 0 | 0 | 4 | 4 |
| 0 | 1 | 0 | 1 | 5 | 5 |
| 0 | 1 | 1 | 0 | 6 | 6 |
| 0 | 1 | 1 | 1 | 7 | 7 |
| 1 | 0 | 0 | 0 | 8 | -8 |
| 1 | 0 | 0 | 1 | 9 | -7 |
| 1 | 0 | 1 | 0 | 10 | -6 |
| 1 | 0 | 1 | 1 | 11 | -5 |
| 1 | 1 | 0 | 0 | 12 | -4 |
| 1 | 1 | 0 | 1 | 13 | -3 |
| 1 | 1 | 1 | 0 | 14 | -2 |
| 1 | 1 | 1 | 1 | 15 | -1 |
An interesting thing with these four bit signed numbers is that seven plus one is negative eight. Also, for the unsigned numbers 15 plus one is zero. The same thing happens with larger number formats but at different numbers. This is also an issue when comparing signed and unsigned integers because -1 (signed) equals 15 (unsigned) for the four bit numbers above. The table below shows various numbers and the result of adding one.
Precision | Value (Signed Value) | Unsigned +1 | Signed +1 |
|---|---|---|---|
1 Byte | 127 | 128 | -128 |
1 Byte | 255 (-1) | 0 | 0 |
2 Bytes | 32767 | 32768 | -32768 |
2 Bytes | 65535 (-1) | 0 | 0 |
4 Bytes | 2147483647 | 2147483648 | -2147483648 |
4 Bytes | 4294967295 (-1) | 0 | 0 |
8 Bytes | 9223372036854775807 | 9223372036854775808 | -9223372036854775808 |
8 Bytes | 18446744073709551615 (-1) | 0 | 0 |
This is how numbers are represented in hardware on a computer. Memory addresses are also represented by fixed length binary numbers and the same issues can arise. The memory addresses are usually unsigned so an index of -1 typically results in a segmentation fault because it is translated into a very large unsigned number.
The hardware is very fast at arithmetic but software can also be used to extend the number range or change the behavior. The Gnu Multiple Precision Arithmetic Library (GMP) uses several integers internally to represent single larger integers. This is very slow compared to hardware arithmetic. Some hardware arithmetic is still used internally by the library.
Factorial Results
The C program for factorial was revised to calculate and print using different precision numbers. Both signed and unsigned numbers were used. The signed results were printed first withchar, short int, int, long int, long long int variables. The corresponding unsigned values were printed below. Your results may vary because the C standard does not specify a precision for the variable types, except for char which is one byte. The results for several factorials are listed below.Bytes 1 2 4 8 8
Enter a number > 0, or 0 to quit :5
5! 120 120 120 120 120
120 120 120 120 120
Enter a number > 0, or 0 to quit :6
6! -48 720 720 720 720
208 720 720 720 720
Enter a number > 0, or 0 to quit :7
7! -80 5040 5040 5040 5040
176 5040 5040 5040 5040
Enter a number > 0, or 0 to quit :8
8! -128 -25216 40320 40320 40320
128 40320 40320 40320 40320
Enter a number > 0, or 0 to quit :9
9! -128 -30336 362880 362880 362880
128 35200 362880 362880 362880
Enter a number > 0, or 0 to quit :10
10! 0 24320 3628800 3628800 3628800
0 24320 3628800 3628800 3628800
Enter a number > 0, or 0 to quit :11
11! 0 5376 39916800 39916800 39916800
0 5376 39916800 39916800 39916800
Enter a number > 0, or 0 to quit :12
12! 0 -1024 479001600 479001600 479001600
0 64512 479001600 479001600 479001600
Enter a number > 0, or 0 to quit :13
13! 0 -13312 1932053504 6227020800 6227020800
0 52224 1932053504 6227020800 6227020800
Enter a number > 0, or 0 to quit :14
14! 0 10240 1278945280 87178291200 87178291200
0 10240 1278945280 87178291200 87178291200
Enter a number > 0, or 0 to quit :15
15! 0 22528 2004310016 1307674368000 1307674368000
0 22528 2004310016 1307674368000 1307674368000
Enter a number > 0, or 0 to quit :16
16! 0 -32768 2004189184 20922789888000 20922789888000
0 32768 2004189184 20922789888000 20922789888000
Enter a number > 0, or 0 to quit :17
17! 0 -32768 -288522240 355687428096000 355687428096000
0 32768 4006445056 355687428096000 355687428096000
Enter a number > 0, or 0 to quit :18
18! 0 0 -898433024 6402373705728000 6402373705728000
0 0 3396534272 6402373705728000 6402373705728000
Enter a number > 0, or 0 to quit :19
19! 0 0 109641728 121645100408832000 121645100408832000
0 0 109641728 121645100408832000 121645100408832000
Enter a number > 0, or 0 to quit :20
20! 0 0 -2102132736 2432902008176640000 2432902008176640000
0 0 2192834560 2432902008176640000 2432902008176640000
Enter a number > 0, or 0 to quit :21
21! 0 0 -1195114496 -4249290049419214848 -4249290049419214848
0 0 3099852800 14197454024290336768 14197454024290336768
Enter a number > 0, or 0 to quit :32
32! 0 0 -2147483648 -6045878379276664832 -6045878379276664832
0 0 2147483648 12400865694432886784 12400865694432886784
Enter a number > 0, or 0 to quit :33
33! 0 0 -2147483648 3400198294675128320 3400198294675128320
0 0 2147483648 3400198294675128320 3400198294675128320
Enter a number > 0, or 0 to quit :34
34! 0 0 0 4926277576697053184 4926277576697053184
0 0 0 4926277576697053184 4926277576697053184
Enter a number > 0, or 0 to quit :64
64! 0 0 0 -9223372036854775808 -9223372036854775808
0 0 0 9223372036854775808 9223372036854775808
Enter a number > 0, or 0 to quit :65
65! 0 0 0 -9223372036854775808 -9223372036854775808
0 0 0 9223372036854775808 9223372036854775808
Enter a number > 0, or 0 to quit :66
66! 0 0 0 0 0
0 0 0 0 0
Typically, the result gets smaller or negative as the factorial increases beyond when the precision gets insufficient to hold the full result. The
int type at 16! is an exception. From the results above it can be seen that a long int and a long long int are the same on this system. Every multiplication by a number divisible by two adds a zero to the right side of the binary number. Thus after sufficient zeros are added the number becomes zero. Note that one odd number multiplication of the number before becoming zero does not change the result.The modified C code with different precision factorial computations.
#include <stdio.h>
/* Program for computing the factorial of a number */
int main(int nvar, char** vars) {
int n,i;
char ck;
short sk;
int ik;
long int lk;
long long int llk;
unsigned char uck;
unsigned short usk;
unsigned int uik;
unsigned long int ulk;
unsigned long long int ullk;
printf("Bytes\t%d\t%d\t%d\t%d\t%d\n",sizeof(ck),sizeof(sk),sizeof(ik),sizeof(lk),sizeof(llk));
while( 1 ) {
printf("Enter a number > 0, or 0 to quit :");
scanf("%d",&n);
if( n < 1 ) break;
ck = sk = ik = lk = llk = uck = usk = uik = ulk = ullk = 1;
for(i=1;i<=n;i++) {
ck *= i;
sk *= i;
ik *= i;
lk *= i;
llk *= i;
uck *= i;
usk *= i;
uik *= i;
ulk *= i;
ullk *= i;
}
printf("%d!\t%hhi\t%hi\t%i\t%li\t%lli\n",n,ck,sk,ik,lk,llk);
printf("\t%hhu\t%hu\t%u\t%lu\t%llu\n",uck,usk,uik,ulk,ullk);
}
}
No comments:
Post a Comment