2008年2月23日星期六

計算超長位數整數

今個星期開始了第二個學期的課(之前從聖誔開始就一直放假呀OTL)
Data的第一堂科就教了怎麼計算50位整數相加和乘法

花了兩天時間終於寫好了
現在給上代碼
………………………………
/* addtimes.c */
/* this program can do addition and multiplication for two very very long integers,
* the maximum range of digits is 1000, but it can change
* so the longest digits of addition is 1000 and
* the longest digits of multiplication is 500
* because multiply will have most double digits of the result
*
* the base principle of this program is save the long integer in an array
* digits by digits
* so when we need to do the addition
* just add two small integers which is one digits of the very very long integer
* and the multiplication also the same
*
* this program can add tow very very long integers,
* and it can mutiply very long integers
*
* Written by Jimmy DA728071
* @ 080223
* Ver 1.0
*/

#include <stdio.h>

/* define a mirco that is the maximum of the array */
#define MAX 10000

int Isdigit(char cha) {
/* this function can check a character is digital or not
* like the function "isdigit" in ctype.h
*/
int x = 0; /* the return value */

if (cha >= '0' && cha <= '9') {
x = 1; }

return x;
}
void carry(short int numbers[], int n)
{
/* this function can do the carry of an array
* after add or times calculation, can use this function to do carry */

int i; /* the index of an array */

for (i=0; i<n-1; i++) {
/* note that the heighest digit of result array also no need carry */
if (numbers[i] > 9) {
numbers[i+1] += numbers[i] / 10;
numbers[i] = numbers[i] % 10; } }

}

int add(const short int n1[], int nn1, /* the first long integer and the number of digits */
const short int n2[], int nn2, /* the second long integer and the number of digits */
short int result[]) /* the result */
{
/* this function do the add action */
int i, /* the index of two integer arraies */
nru; /* total number in calculate result */

if ( nn1 > nn2 ) {
/* if the integer n1 is longer than n2 */
/* the result should have same digits as the first integer */
nru = nn1;
/* start calculate the sum */
for (i=0; i<nn2; i++) {
/* just put the sum to the result array first */
result[i] = n1[i] + n2[i]; }
for (i=nn2; i<nn1; i++) {
/* get the leavings digit to result */
result[i] = n1[i]; } }

else if ( nn1 <= nn2 ) {
/* if the integer n1 is shorter than n2 */
/* the result should have same digits as the second integer */
nru = nn2;
/* start calculate the sum */
for (i=0; i<nn1; i++) {
/* just put the sum te the result array first */
result[i] = n1[i] + n2[i]; }
/* if two long integer is not as long as same,
* need to get the leavings digit to result */
if ( nn1 != nn2) {
for (i=nn1; i<nn2; i++) {
result[i] = n2[i]; } } }

/* then, check the carry */
carry(result, nru);

/* return the nru */
return nru;
}

int stimes(const short int n1[], int nn1, /* the first long integer */
int nn2, /* the multiplicator */
short int result[]) /* the calculation result */
{
/* this function do tha times action
* a simple multiplication action */
int nru, /* total number in calculate result */
i; /* the index of array */

/* count how many digit of the result integer */
nru = nn1;

/* start calculate, multiply one digit by one digit */
for (i=0; i<nn1; i++) {
/* just put the product to the result array */
/* here is a protype, so only multiply the first digit of n2 */
result[i] = n1[i] * nn2; }

/* then check the carry */
carry(result, nru);

/* return the nru */
return nru;
}

int ctimes(const short int n1[], int nn1,
const short int n2[], int nn2, short int result[])
{
/* this function do the complex multioplication action
* do this complex action, can separate to several simple multioplication
*/

int nru = 0, /* total number of digits in calculate result */
n = 0, /* mark which place of digit in the long integer */
mutor, /* the multiplicator */
nt1,
nt2, /* the number of digits inside temp integer */
i,
j; /* the index of array */
short int tn2[MAX],
tn1[MAX]; /* a temp integer */

/* the result must be had digits which is digits of n1 plus digits of n2 minus 1 */
nru = nn1 + nn2 - 1;

if (nn1 > nn2) {
/* if the first integer is longer than the second integer */

for (i=0; i<nn2; i++) {
/* clean the temp integer, just make it has none digit inside */
nt1 = 0;

/* put some zero after the integer, because after multiply the unidigit
* the multiplicator will have more 0,
* so put the 0 to multiplier make the calculation more easier */
for (j=0; j<n; j++) {
tn1[j] = 0;
nt1++; }
/* than copy the digits inside the first integer to temp integer */
for (j=0; j<nn1; j++) {
tn1[nt1] = n1[j];
nt1++; }
/* get the multiplicator from the second integer */
mutor = n2[i];
/* get the product of temp integer and multiplicator */
nt2 = stimes(tn1, nt1, mutor, tn2);
/* add the product to result */
nru = add(result, nru, tn2, nt2, result);
n++; } }

else if (nn1 <= nn2) {
/* if the first integer is shorter than the second integer
* or as same length as the second integer */

for (i=0; i<nn1; i++) {
/* clean the temp integer, just make it has none digit inside */
nt1 = 0;

/* put some zero after the integer, because after multiply the unidigit
* the multiplicator will have more 0,
* so put the 0 to multiplier make the calculation more easier */
for (j=0; j<n; j++) {
tn1[j] = 0;
nt1++; }
/* than copy the digits inside the second integer to temp integer */
for (j=0; j<nn2; j++) {
tn1[nt1] = n2[j];
nt1++; }
/* get the multiplicator from the first integer */
mutor = n1[i];
/* get the product of temp integer and multiplicator */
nt2 = stimes(tn1, nt1, mutor, tn2);
/* add the product to result */
nru = add(result, nru, tn2, nt2, result);
n++; } }

return nru;
}

void reverse(short int numbers[], int n)
{
/* this function using for reverse an array */
int i, /* the index of the array */
t; /* a temp valuable */

/* exchange the elements */
for (i=0; i<n/2; i++) {
t = numbers[i];
/* because n is the number of the elements,
* the index of the last element is n-1 */
numbers[i] = numbers[n-1-i];
numbers[n-1-i] = t; }

}

int main(void)
{
/* main function */

int nn2 = 0, /* how many numbers that user input in n2 */
nn1 = 0, /* how many numbers that user input in n1 */
nru = 0, /* how many numbers that in claculate result */
i = 0; /* the index of two long integer array */
char op = ' ', /* the operation that user want, read from input */
cha = ' '; /* the charact read from user input */
short int n1[MAX], /* the first long integer, save in an array */
n2[MAX], /* the second long integer */
result[MAX], /* the result of calculate */
mark = 0, /* mark that save the number to n1 or n2 */
over = 0; /* mark that the long integer is over range or not */

/* print out something so that user can know program started running */
printf(": ");

/* initial the n1, n2, result
for (i=0; i<MAX; i++) {
n1[i] = 0;
n2[i] = 0;
result[i] = 0; } */

/* read the input from user, the format like number1 + number2 */
/* because upper has used i, so initial i */
i = 0;
do {
cha = getchar();
if ( Isdigit(cha) && !mark ) {
/* if the charact that read from user is digital,
* put it into the number1's array */
/* because user input is charact, so need to convert into integer */
/* the charact 0 ~ 9 is in order, so just minus charact 0 */
n1[i] = cha - '0';
i++;
nn1++; }
else if ( Isdigit(cha) && mark ) {
/* if mark is true, it means the integer is n2 */
n2[i] = cha - '0';
i++;
nn2++; }
else if ( cha == '+' || cha == '*' ) {
/* if cha is + operation, that is the operation user input */
op = cha;
mark = 1;
i = 0; }
/* check the integer, if it is over range, print out an error message and exit */

} while ( cha != '\n' );

if ( over == 0 ) {
/* reverse the arraies
* infect, it's possible that do not do the reverse
* save the heightest digit in the 0 index
* but i like save it in the heightest index, so reverse it */
reverse(n1, nn1);
reverse(n2, nn2);

/* print out the result */
/* note that the highest digit is at the end of the array,
* because the array have beed reverse
* and the lowest digit should be the total number of digits minus one */
for (i=nn1-1; i>=0; i--) {
printf("%d", n1[i]); }
printf(" %c ", op);
for (i=nn2-1; i>=0; i--) {
printf("%d", n2[i]); }
printf("\n= ");

if ( op == '+' ) {
/* do the addition action */
/* check the two very long integer, confirm that they will NOT over range */
nru = add(n1, nn1, n2, nn2, result); }
else if ( op == '*' ) {
/* do the multiplication action */
/* check the two very long integer, confirm that they will NOT over range */
nru = ctimes(n1, nn1, n2, nn2, result); }

/* note that the result's order as same as two long integers */
for (i=nru-1; i>=0; i--) {
/* print out the calculate result */
printf("%d", result[i]); }

printf("\nProgram Exit!!\n"); }
return 0;
}

回想起某一天
在IRC上,有人問起怎麼計算200位整數開平方根
當時有人給出大大堆Lib叫他用
其實呢,我覺得這樣濫用API是不好的
應該抱着學習心態地去研究怎麼實現,而不應該全都用現成的代碼

不過人各有志~
別人喜歡怎麼做我都沒辦法的
只是見到有些人,因為自己知道有一堆API就以為自己是超厲害的高手
四處『認叻』
真討厭
發佈留言

熱門文章