C Language Big Number Processing
Higher category : 【C Language】 C Language Table of Contents
a. GitHub
#include <stdio.h>
#include <stdlib.h>
#define Max 100
/* This program can help you calculate huge numbers (∈ ℕ) */
// Using the function 'strlen()' is not that efficient
int max(char *array_I, int array_I_size, char *array_II, int array_II_size){
// array_I ≥ array_II → 1
// array_I < array_II → 2
if(array_I_size > array_II_size) return 1;
else if(array_II_size > array_I_size) return 2;
else{
int i = 0;
while(1){
if(i == array_I_size) return 1;
if(array_I[i] > array_II[i]) return 1;
else if(array_I[i] < array_II[i]) return 2;
i ++;
}
}
}
int array_addition(char *array, char *array_I, int array_I_size, char *array_II, int array_II_size){
/* array can be same with array_I */
int i, j;
char converted_array[Max] = {0, };
i = 0;
if(array_I_size > array_II_size){
while(1){
if(i < array_I_size){
converted_array[i] += array_I[array_I_size - 1 - i];
if(i < array_II_size) converted_array[i] += array_II[array_II_size - 1 - i];
converted_array[i + 1] += converted_array[i] / 10;
converted_array[i] %= 10;
}
else break;
i ++;
}
}
else{
while(1){
if(i < array_II_size){
converted_array[i] += array_II[array_II_size - 1 - i];
if(i < array_I_size) converted_array[i] += array_I[array_I_size - 1 - i];
converted_array[i + 1] += converted_array[i] / 10;
converted_array[i] %= 10;
}
else break;
i ++;
}
}
if(converted_array[i] != 0) i ++;
for(j = 0; j < i; j ++) array[j] = converted_array[i - 1 - j];
return i;
}
int converted_array_addition(char *array, char *array_I, int array_I_size, char *array_II, int array_II_size){
/* this function is used when multiplying */
int i, j;
for(i = 0; i < Max; i ++) array[i] = 0;
i = 0;
if(array_I_size > array_II_size){
while(1){
if(i < array_I_size){
array[i] += array_I[i];
if(i < array_II_size) array[i] += array_II[i];
array[i + 1] += array[i] / 10;
array[i] %= 10;
}
else break;
i ++;
}
}
else{
while(1){
if(i < array_II_size){
array[i] += array_II[i];
if(i
< array_I_size) array[i] += array_I[i];
array[i + 1] += array[i] / 10;
array[i] %= 10;
}
else break;
i ++;
}
}
if(array[i] != 0) i ++;
return i;
}
int array_subtraction(char *array, char *array_I, int array_I_size, char *array_II, int array_II_size){
/* array can be same with array_I */
int i, j;
char converted_array[Max] = {0, };
for(i = 0; i < Max; i ++) array[i] = 0;
i = 0;
while(1){
if(i < array_I_size){
converted_array[i] += array_I[array_I_size - 1 - i];
if(i < array_II_size) converted_array[i] -= array_II[array_II_size - 1 - i];
if(converted_array[i] < 0){
converted_array[i] += 10;
converted_array[i + 1] --;
}
}
else break;
i ++;
}
while(1){ // Ex. 112 - 93 = 019 →19
if(converted_array[i - 1] != 0) break;
if(i == 0) return 1; // only if array_I = array_II
i --;
}
for(j = 0; j < i; j ++) array[j] = converted_array[i - 1 - j];
return i;
}
int array_multiplication(char *array, char *array_I, int array_I_size, char *array_II, int array_II_size){
/* array can be same with array_I */
if((array_I_size == 1 && array_I[0] == 0) || (array_II_size == 1 && array_II[0] == 0)){
array[0] = 0; // if this source doesn't exist, "array = 0" can't be realized(①)
return 1;
}
int i, j, k, temp;
int size = 0; // 'size' means the size of converted_array at each situation
char converted_array[Max];
char notepad_I[Max];
char notepad_II[Max];
for(i = 0; i < Max; i ++) converted_array[i] = 0;
for(i = 0; i < array_II_size; i ++){ // array_II[i] is such 7(i = 0) or 6(i = 1)
for(j = 0; j < Max; j ++){ // Ex. 132 × 76
notepad_I[j] = 0; // notepad_I can be 792, 9240
}
for(j = 0; j < array_I_size; j ++){ // array_I[j] is such 1(j = 0), 3(j = 1), or 2(j = 2)
temp = array_I[array_I_size - 1 - j] * array_II[array_II_size - 1 - i];
notepad_I[j + i] += temp % 10;
notepad_I[j + i + 1] += temp / 10;
}
if(notepad_I[j + i] != 0) j ++;
for(k = 0; k < size; k ++) notepad_II[k] = converted_array[k];
/* notepad_II totally
equals to converted_array */
size = converted_array_addition(converted_array, notepad_II, size, notepad_I, j + i);
}
for(i = 0; i < size - 1; i ++){
if(converted_array[i] < 0){
converted_array[i] += 10;
converted_array[i + 1] --;
}
}
j = size - 1;
while(1){
if(converted_array[j] != 0) break; // this is related with ①
j --;
}
for(i = 0; i < j + 1; i ++) array[i] = converted_array[j - i];
return j + 1;
}
int array_division(char *array, char *array_I, int array_I_size, char *array_II, int array_II_size){
/* array should not be same with array_I (∵ Information Loss) */
int i, j, k, l, x;
char notepad_I[Max];
char notepad_II[Max];
char notepad_III[Max];
char notepad_IV[Max];
char number[1];
for(i = 0; i < Max; i ++) array[i] = 0;
if(array_I_size < array_II_size) return 1;
i = 0;
while(1){ // Example: 1237 ÷ 117
if(i == array_I_size) return 1; // cf. it means array_I < array_II
for(j = 0; j <= i; j ++) notepad_I[j] = array_I[j]; // notepad_I can be 1, 12, 123, but 1237
if(max(notepad_I, i + 1, array_II, array_II_size) == 1) break;
i ++;
}
for(j = 0; j < array_I_size; j ++) notepad_II[j] = array_I[j];
for(j = i; j < array_I_size; j ++){
k = 0;
while(1){
if(notepad_II[k] != 0) break; // notepad_II will be 1237, 0067
k ++;
}
for(l = k; l <= j; l ++) notepad_I[l - k] = notepad_II[l]; // notepad_I will be 123, 67
for(l = 0; l <= 10; l ++){
number[0] = l;
x = array_multiplication(notepad_III, number, 1, array_II, array_II_size);
if(max(notepad_I, j - k + 1, notepad_III, x) == 2) break;
/* cf. notepad_III can be (array_II ×0) ~ (array_II ×9) */
}
if(l == 0) array[j - i] = 0;
else array[j - i] = l - 1; // array_II ×(l - 1) ≤ notepad_I < array_II ×l
number[0] = l - 1;
x = array_multiplication(notepad_III, number, 1, array_II, array_II_size); // notepad_III = array_II ×(k - 1)
x = array_subtraction(notepad_IV, notepad_I, j - k + 1, notepad_III, x);
for(l = 0; l
< j - x + 1; l ++) notepad_II[l] = 0;
for(l = j - x + 1; l <= j; l ++) notepad_II[l] = notepad_IV[l - (j - x + 1)];
}
return j - i;
}
int array_remainder(char *array, char *array_I, int array_I_size, char *array_II, int array_II_size){
int i, j, k, l, x;
char notepad_I[Max];
char notepad_II[Max];
char notepad_III[Max];
char notepad_IV[Max];
char number[1];
for(i = 0; i < Max; i ++) array[i] = 0;
if(array_I_size < array_II_size){
for(i = 0; i < array_I_size; i ++)
array[i] = array_I[i];
return array_I_size;
}
i = 0;
while(1){
if(i == array_I_size){
for(i = 0; i < array_I_size; i ++)
array[i] = array_I[i];
return 1;
}
for(j = 0; j <= i; j ++) notepad_I[j] = array_I[j];
if(max(notepad_I, i + 1, array_II, array_II_size) == 1) break;
i ++;
}
for(j = 0; j < array_I_size; j ++) notepad_II[j] = array_I[j];
for(j = i; j < array_I_size; j ++){
k = 0;
while(1){
if(notepad_II[k] != 0) break;
k ++;
}
for(l = k; l <= j; l ++) notepad_I[l - k] = notepad_II[l];
for(l = 0; l <= 10; l ++){
number[0] = l;
x = array_multiplication(notepad_III, number, 1, array_II, array_II_size);
if(max(notepad_I, j - k + 1, notepad_III, x) == 2) break;
}
number[0] = l - 1;
x = array_multiplication(notepad_III, number, 1, array_II, array_II_size);
x = array_subtraction(notepad_IV, notepad_I, j - k + 1, notepad_III, x);
for(l = 0; l < j - x + 1; l ++) notepad_II[l] = 0;
for(l = j - x + 1; l <= j; l ++) notepad_II[l] = notepad_IV[l - (j - x + 1)];
}
k = 0;
while(1){
if(notepad_II[k] != 0) break;
if(k == array_I_size){
array[0] = 0;
return 1;
}
k ++;
}
for(l = k; l < array_I_size; l ++) array[l - k] = notepad_II[l];
return array_I_size - k;
}
int main(int argc, char *argv[]) {
char array[Max];
char array_I[Max];
int array_I_size;
char array_II[Max];
int array_II_size;
char ch; int i, j;
printf("Enter two natural numbers, a and b.\n");
i = 0;
while(1){
ch
= getchar();
if(ch < 33) break; // ch = 32 ↔ ch = ' '
array_I[i] = ch - '0';
i ++;
}
array_I_size = i;
i = 0;
while(1){
ch = getchar();
if(ch < 33) break;
array_II[i] = ch - '0';
i ++;
}
array_II_size = i;
printf("a + b = ");
i = array_addition(array, array_I, array_I_size, array_II, array_II_size);
for(j = 0; j < i; j ++) printf("%d", array[j]);
printf("\n");
printf("a - b = ");
if(max(array_I, array_I_size, array_II, array_II_size) == 1){
i = array_subtraction(array, array_I, array_I_size, array_II, array_II_size);
for(j = 0; j < i; j ++) printf("%d", array[j]);
}
else{
printf("-");
i = array_subtraction(array, array_II, array_II_size, array_I, array_I_size);
for(j = 0; j < i; j ++) printf("%d", array[j]);
}
printf("\n");
printf("a * b = ");
i = array_multiplication(array, array_I, array_I_size, array_II, array_II_size);
for(j = 0; j < i; j ++) printf("%d", array[j]);
printf("\n");
printf("a / b = ");
i = array_division(array, array_I, array_I_size, array_II, array_II_size);
for(j = 0; j < i; j ++) printf("%d", array[j]);
printf("\n");
printf("a %% b = ");
i = array_remainder(array, array_I, array_I_size, array_II, array_II_size);
for(j = 0; j < i; j ++) printf("%d", array[j]);
return 0;
}
Input: 2016.02.18 21:16