無限大整数加算アルゴリズムのC言語ソースコード
16330 ワード
忙しくて暇を盗んで、ついに無限大整数加算アルゴリズムのC言語コードを完成して、無限大整数加算アルゴリズムのアルゴリズム分析はここにあります.
500ビット加算は1000回実行され、結果を印刷しない場合は0.036秒、結果を印刷する場合は16.285秒かかります.
次はソースです.
500ビット加算は1000回実行され、結果を印刷しない場合は0.036秒、結果を印刷する場合は16.285秒かかります.
次はソースです.
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include <time.h>
#define MAXNUM 1000000000000000000
/*
long int (Number) long int , ,
10 18 。 。
int (Length) 。
int , “ ”。
*/
struct BigInt{
long long* Number;
int Length;
};
void PrintBigInt(BigInt* bigNumber);
long long pow(int x, int y);
BigInt* MakeBigIntFromString(char* bigIntString);
void DeleteBigInt(BigInt* bigNumber);
BigInt* Add2BigInt(BigInt* n1, BigInt* n2);
void main(){
char* numberStr = "99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999\0";
char* numberStr2 = "99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999\0";
BigInt* bn = MakeBigIntFromString(numberStr);
BigInt* bn2 = MakeBigIntFromString(numberStr2);
double tstart, tend, tcost;
tstart = clock();
PrintBigInt(bn);
PrintBigInt(bn2);
for (int i = 0; i < 1000; i++){
BigInt* result = Add2BigInt(bn, bn2);
//PrintBigInt(result);
DeleteBigInt(result);
}
DeleteBigInt(bn);
DeleteBigInt(bn2);
tend = clock();
tcost = (double)(tend - tstart) / CLOCKS_PER_SEC;
printf("%lf
", tcost);
}
BigInt* Add2BigInt(BigInt* n1, BigInt* n2){
int maxLength = n1->Length;
if (maxLength < n2->Length){
maxLength = n2->Length;
}
/*
1 , , 。
*/
BigInt* nOut = (BigInt*)malloc(sizeof(BigInt));
nOut->Length = maxLength;
nOut->Number = (long long*)malloc(sizeof(long long)* nOut->Length);
for (int i = 0; i < nOut->Length; i++){
nOut->Number[i] = 0;
}
for (int i = 0; i < nOut->Length; i++){
if (n1->Length > i){
nOut->Number[i] += n1->Number[i];
}
if (n2->Length > i){
nOut->Number[i] += n2->Number[i];
}
/*
。 。
*/
if (i != (nOut->Length - 1)){
if (nOut->Number[i] >= MAXNUM){
nOut->Number[i] -= MAXNUM;
nOut->Number[i + 1] = 1;
}
}
}
return nOut;
}
/*
long long 18 。
*/
void PrintBigInt(BigInt* bigNumber){
if (bigNumber == NULL){
return;
}
if (bigNumber->Length < 1){
return;
}
int length = bigNumber->Length - 1;
for (int i = length; i >= 0; i--){
if (i != length){
if (bigNumber->Number[i] == 0){
printf("000000000000000000");
}
else{
printf("%018lld", bigNumber->Number[i]);
}
}
else{
if ((*bigNumber).Number[i] != 0){
printf("%lld", bigNumber->Number[i]);
}
}
}
printf("
");
}
/*
BigInt
\0 。
*/
BigInt* MakeBigIntFromString(char* bigIntString){
/* */
int cLength = strlen(bigIntString);
BigInt* outBigInt = (BigInt*)malloc(sizeof(BigInt));
if (cLength % 18 != 0){
outBigInt->Length = cLength / 18 + 1;
}
else{
outBigInt->Length = cLength / 18;
}
if (outBigInt->Length == 0){
outBigInt->Length == 1;
outBigInt->Number = (long long *)malloc(sizeof(long long));
outBigInt->Number[0] = 0;
return outBigInt;
}
outBigInt->Number = (long long *)malloc(sizeof(long long)* outBigInt->Length);
for (int i = 0; i < outBigInt->Length; i++){
outBigInt->Number[i] = 0;
}
int powNum = 0;
int numPos = 0;
for (int i = cLength - 1; i >= 0; i--){
powNum = (cLength - 1 - i) % 18;
numPos = (cLength - 1 - i) / 18;
outBigInt->Number[numPos] += (bigIntString[i] - 48) * pow(10, powNum);
}
return outBigInt;
}
/*
x y
*/
long long pow(int x, int y){
if (x == 0 || x < 0 || y < 0){
return 0;
}
if (x == 1 || y == 0){
return 1;
}
long long outNum = x;
for (int i = 1; i < y; i++){
outNum = outNum * x;
}
return outNum;
}
void DeleteBigInt(BigInt* bigNumber){
if (bigNumber != NULL){
if (bigNumber->Number != NULL){
free(bigNumber->Number);
}
free(bigNumber);
}
}