2020年12月23日 (水) 18:41にWikiによる

2020-12-23T18:41:03Z

← 古い版		2020年12月24日 (木) 03:41時点における版
457行目:		457行目:
	}		}
	</syntaxhighlight>		</syntaxhighlight>
			<br><br>

			__FORCETOC__
			[[カテゴリ:C]]

2020年12月23日 (水) 18:38にWikiによる

2020-12-23T18:38:38Z

← 古い版		2020年12月24日 (木) 03:38時点における版
4行目:		4行目:

	== 値の表現方法 ==		== 値の表現方法 ==
	大きな桁数の計算を行うために、値を配列で持たせるとする。		大きな桁数の計算を行うために、値を配列で持たせるとする。<br>
	1つの要素に2桁ずつ値を格納して、それを配列として持つことにより大きな桁数を扱うことができる。		1つの要素に2桁ずつ値を格納して、それを配列として持つことにより大きな桁数を扱うことができる。<br>
			<br>
	* 500を表現する場合		* 500を表現する場合
	*: ar[4]=00 ar[3]=00 ar[2]=00 ar[1]=05 ar[0]=00		*: ar[4]=00 ar[3]=00 ar[2]=00 ar[1]=05 ar[0]=00
20行目:		20行目:

	== 加算 ==		== 加算 ==
	加算の桁の繰り上がりにおいて、下図のパターンが考えられる。		加算の桁の繰り上がりにおいて、下図のパターンが考えられる。<br>
	# 99より大きな値を見つけたら現在の要素から100を減算して、上の要素に1を繰り上げる。		# 99より大きな値を見つけたら現在の要素から100を減算して、上の要素に1を繰り上げる。
	# -99より小さな値を見つけたら現在の要素から-100を減算して、上の要素に-1を繰り上げる。		# -99より小さな値を見つけたら現在の要素から-100を減算して、上の要素に-1を繰り上げる。
26行目:		26行目:
	# 全体が-であり、現在の要素が+である場合、上の要素から-1を減算して、現在の要素に-100を加算する。		# 全体が-であり、現在の要素が+である場合、上の要素から-1を減算して、現在の要素に-100を加算する。
	<br>		<br>
	2つの配列の要素を加算して、1〜4の処理を添え字の小さい値から順に繰り返すことで、加算が出来る。		2つの配列の要素を加算して、1〜4の処理を添え字の小さい値から順に繰り返すことで、加算が出来る。<br>
	<br>		<br>
			[[ファイル:C Multiple Length Calc 1.jpg\|フレームなし\|中央]]
	<br><br>		<br><br>

	== 減算 ==		== 減算 ==
	減算は、減算する値の符号を反転させることで、加算で代用できる。		減算は、減算する値の符号を反転させることで、加算で代用できる。<br>
	100 - 10 → 100 + (-10)		100 - 10 → 100 + (-10)
	~~<br>~~

	<br><br>		<br><br>

	== 乗算 ==		== 乗算 ==
	乗算は、加算を繰り返すことでできるが、時間が掛かりすぎる。		乗算は、加算を繰り返すことでできるが、時間が掛かりすぎる。<br>
	そこで、筆算で計算する手順と同じ手順で計算する。		そこで、筆算で計算する手順と同じ手順で計算する。<br>
	<br>		<br>
	下図において、1020×523の場合を示す。<br>		下図において、1020×523の場合を示す。<br>
			[[ファイル:C Multiple Length Calc 2.jpg\|フレームなし\|中央]]
	<br><br>		<br><br>

	== 除算 ==		== 除算 ==
	除算は、被除数から法を繰り返して減算すれば計算できるが、時間が掛かりすぎる。		除算は、被除数から法を繰り返して減算すれば計算できるが、時間が掛かりすぎる。<br>
	そこで、シフトを使用して計算する。		そこで、シフトを使用して計算する。<br>
			<br>
			[[ファイル:C Multiple Length Calc 3.jpg\|フレームなし\|中央]]
	<br><br>		<br><br>

Wiki: ページの作成:「== 概要 == ここでは、大きな桁数の計算を行うアルゴリズムを記載する。

== 値の表現方法 == 大きな桁数の計算を行う…」

2020-12-23T18:24:31Z

ページの作成:「== 概要 == ここでは、大きな桁数の計算を行うアルゴリズムを記載する。 == 値の表現方法 == 大きな桁数の計算を行う…」

新規ページ

== 概要 ==
ここでは、大きな桁数の計算を行うアルゴリズムを記載する。 
 

== 値の表現方法 ==
大きな桁数の計算を行うために、値を配列で持たせるとする。
1つの要素に2桁ずつ値を格納して、それを配列として持つことにより大きな桁数を扱うことができる。

* 500を表現する場合
*: ar[4]=00 ar[3]=00 ar[2]=00 ar[1]=05 ar[0]=00
*: 注意 : C言語において、値の前に0をつけると8進数になるので注意すること。
*: 
* 1234567890を表現する場合
*: ar[4]=12 ar[3]=34 ar[2]=56 ar[1]=78 ar[0]=90
*: 
* -1234567890を表現する場合
*: マイナス値の場合は配列の総ての要素がマイナスになると考える。
*: ar[4]=-12 ar[3]=-34 ar[2]=-56 ar[1]=-78 ar[0]=-90
 

== 加算 ==
加算の桁の繰り上がりにおいて、下図のパターンが考えられる。
# 99より大きな値を見つけたら現在の要素から100を減算して、上の要素に1を繰り上げる。
# -99より小さな値を見つけたら現在の要素から-100を減算して、上の要素に-1を繰り上げる。
# 全体が+であり、現在の要素が-である場合、上の要素から1を減算して、現在の要素に100を加算する。
# 全体が-であり、現在の要素が+である場合、上の要素から-1を減算して、現在の要素に-100を加算する。
 
2つの配列の要素を加算して、1〜4の処理を添え字の小さい値から順に繰り返すことで、加算が出来る。
 

 

== 減算 ==
減算は、減算する値の符号を反転させることで、加算で代用できる。
100 - 10 → 100 + (-10)
 

 

== 乗算 ==
乗算は、加算を繰り返すことでできるが、時間が掛かりすぎる。
そこで、筆算で計算する手順と同じ手順で計算する。
 
下図において、1020×523の場合を示す。 

 

== 除算 ==
除算は、被除数から法を繰り返して減算すれば計算できるが、時間が掛かりすぎる。
そこで、シフトを使用して計算する。

 

== サンプルコード ==
<syntaxhighlight lang="c">
#include <stdio.h>

// ar1 + ar2 = ar3
void add(const short*ar,const short*ar2,short*ar3,const int size);

// ar - ar2 = ar3
void sub(const short*ar,short*ar2,short*ar3,const int size);

// ar * ar2 = ar3
void mul(const short*ar,const short*ar2,short*ar3,int size);

// ar / ar2 = ar3...ar
void div(short*ar,short*ar2,short*ar3,const int size);

// printf(ar)
void ar_print(short*ar,const int size);

// 配列を固定小数点型として画面表示する
// ar[size-1].ar[size-2]~ar[low]
void dp_print(short*ar,const int size,const int low);

void turn(short*ar,const int size);
int cmp(const short*ar,const short*ar1,const int size);
int cmp0(const short*ar,const int size);
void r_shift(short*ar,const int size);
void l_shift(short*ar,const int size);

#define SIZE 10

int main()
{
short ar1[SIZE] = {0},
ar2[SIZE] = {0},
ar3[SIZE] = {0};

// ar1 = 1000000000000000
short ar[9] = 0, ar[8] = 0, ar[7] = 10,
ar[6] = 0, ar[5] = 0, ar[4] = 0,
ar[3] = 0, ar[2] = 0, ar[1] = 0,
ar[0] = 0;

// ar2 = -1234
short ar2[9] = 0, ar2[8] = 0, ar2[7] = 0,
ar2[6] = 0, ar2[5] = 0, ar2[4] = 0,
ar2[3] = 0, ar2[2] = 0, ar2[1] = -12,
ar2[0] = -34;

// 減算
sub(ar1, ar2, ar3, SIZE);
ar_print(ar1, SIZE);
printf("-");
ar_print(ar2, SIZE);
printf("=");
ar_print(ar3, SIZE);
printf("\n");

// 加算
add(ar1, ar2, ar3, SIZE);
ar_print(ar1, SIZE);printf("+");ar_print(ar2,SIZE);printf("=");ar_print(ar3,SIZE);printf("\n");

mul(ar,ar2,ar3,SIZE);//かけ算
ar_print(ar,SIZE);printf("*");ar_print(ar2,SIZE);printf("=");ar_print(ar3,SIZE);printf("\n");

ar_print(ar,SIZE);printf("/");ar_print(ar2,SIZE);printf("=");
div(ar,ar2,ar3,SIZE);//割り算
ar_print(ar3,SIZE);printf("...");ar_print(ar,SIZE);printf("\n");

return 0;
}

// 加算 : ar1 + ar2 = ar3
void add(const short* ar1, const short* ar2, short* ar3, const int size)
{
int p_flag;

for(int i = 0; i < size; i++)
{
ar3[i] = ar1[i] + ar2[i];
}

for(int i = 0; i < size; i++)
{
if(ar3[i] > 99)
{
ar3[i] -= 100;
ar3[i + 1] += 1;
}
else if(ar3[i] < -99)
{
ar3[i] -= -100;
ar3[i + 1] += -1;
}
}

p_flag = cmp0(ar3, size);

if(p_flag == 0)
{
return;
}

for(int i = 0; i < size; i++)
{
if(p_flag > 0)
{
if(0 > ar3[i])
{
ar3[i + 1] -= 1;
ar3[i] += 100;
}
}
else
{
if(0 < ar3[i])
{
ar3[i + 1] -= -1;
ar3[i] += -100;
}
}
}
}

// 減算 : ar1 - ar2 = ar3
void sub(const short* ar1, short* ar2, short* ar3, const int size)
{
turn(ar2, size);
add(ar1, ar2, ar3, size);
turn(ar2, size);
}

// 乗算 : ar1 * ar2 = ar3
void mul(const short* ar1, const short* ar2, short* ar3, const int size)
{
for(int i =0 ; i < size; i++)
{
ar3[i] = 0;
}

for(int i = 0; i < size; i++)
{
if(ar2[i])
{
for(int j = 0; j < size; j++)
{
ar3[j + i] += ar1[j] * ar2[i];

// 3桁目を繰り上げる
if(ar3[j + i] > 99 || ar3[j + i] < -99)
{
int pos = ar3[j + i] / 100;
ar3[j + i] -= (pos * 100);
ar3[j + 1 + i] += pos;
}
}
}
}
}

// 除算 : ar1 / ar2 = ar3...ar1
// ar1は書き換えられて余りになる
void div(short* ar1, short* ar2, short* ar3, const int size)
{
for(int i = 0; i < size; i++)
{
ar3[i]=0;
}

int div_flag; // 被除数の符号フラグ
int met_flag; // 法の符号フラグ

div_flag = cmp0(ar1, size);
met_flag = cmp0(ar2, size);

if(!div_flag || !met_flag)
{ // 法または被除数が0であるため計算を中止する
return;
}

if(-1 == div_flag)
{ // 被除数が負であるため被除数を正の値にする
turn(ar1, size);
}

if(-1 == met_flag)
{ // 法が負であるため法を正の値にする
turn(ar2, size);
}

int pos = 0;
while(1)
{
if(cmp(ar1, ar2, size) ==1 && (ar2[size - 1] / 10) == 0)
{
pos++;
l_shift(ar2, size);
}
else
{
break;
}
}

while(pos >= 0)
{
if(cmp(ar1, ar2, size) >= 0)
{
sub(ar1, ar2, ar1, size);
if(pos % 2)
{
ar3[pos / 2] += 10;
}
else
{
ar3[pos / 2]++;
}
}
else
{
if(pos)
{
r_shift(ar2, size);
}
pos--;
}
}

if(-1 == div_flag)
{ // 被除数の符号を戻す
turn(ar1, size);
}

if(-1 == met_flag)
{ // 法の符号を戻す
turn(ar2, size);
}

if(div_flag != met_flag)
{ // 被除数と法の符号が違うため解を負の値にする
turn(ar3, size);
}
}

// 画面表示
void ar_print(short* ar1, const int size)
{
int start_flag = 0;
int p_flag = cmp0(ar1, size);

if(p_flag == 0)
{
printf("0");
return;
}

if(p_flag == -1)
{
printf("-");
turn(ar1, size);
}

for(int i = size - 1; i> = 0; i--)
{
if(ar1[i] || start_flag)
{
if(!start_flag)
{
printf("%d", ar1[i]);
}
else
{
printf("%02d", ar1[i]);
}
start_flag=1;
}
}

if(p_flag == -1)
{
turn(ar1, size);
}
}

// 配列を固定小数点型として画面表示する
// ar1[size-1].ar1[size-2]~ar1[low]
void dp_print(short* ar1, const int size, const int low)
{
int p_flag = cmp0(ar1, size);
if(p_flag == 0)
{
printf("0");
return;
}

if(p_flag == -1)
{
printf("-");
turn(ar1, size);
}

printf("%d.", ar1[size - 1]);

int j = 0,
k = 0;
for(int i = size - 2; i >= low; i--)
{
if(j++ % 5 == 0)
{
printf(" ");
}

if(k++ % 25 == 0)
{
printf("\n");
}

printf("%02d", ar[i]);
}

if(p_flag == -1)
{
turn(ar1, size);
}
}

// 符号の反転
void turn(short* ar1, const int size)
{
for(int i = 0; i < size; i++)
{
ar1[i] =- ar1[i];
}
}

// ar1 < ar2の場合は-1を返す
// ar1 > ar2の場合は+1を返す
// ar1 == ar2の場合は0を返す
int cmp(const short* ar1, const short* ar2, const int size)
{
for(int i = size - 1; i >= 0; i--)
{
if(ar1[i] < ar2[i])
{
return -1;
}

if(ar1[i] > ar2[i])
{
return 1;
}
}

return 0;
}

// ar1が正の場合は 1を返す
// ar1が負の場合は-1を返す
// ar1が0の場合は0を返す
int cmp0(const short* ar1, const int size)
{
for(int i = size - 1; i >= 0; i--)
{
if(ar[i] < 0)
{
return -1;
}

if(ar1[i] > 0)
{
return 1;
}
}

return 0;
}

// 右に1桁シフト
void r_shift(short* ar1, const int size)
{
ar1[0] = ar1[0] / 10;

for(int i = 1; i < size; i++)
{
int pos = ar1[i];
ar1[i] = ar1[i] / 10;
ar1[i - 1] += ((pos - (ar1[i] * 10)) * 10);
}
}

// 左に1桁シフト
void l_shift(short* ar1, const int size)
{
for(int i = size - 1; i >= 0; i--)
{
ar1[i] = ar1[i] * 10;
int pos = ar1[i] / 100;
ar1[i] -= (pos * 100);

if(pos)
{
ar1[i + 1] += pos;
}
}
}
</syntaxhighlight>

C言語の応用 - 多倍長計算 - 版の履歴

2020年12月23日 (水) 18:41にWikiによる

2020年12月23日 (水) 18:38にWikiによる

Wiki: ページの作成:「== 概要 == ここでは、大きな桁数の計算を行うアルゴリズムを記載する。 == 値の表現方法 == 大きな桁数の計算を行う…」

Wiki: ページの作成:「== 概要 == ここでは、大きな桁数の計算を行うアルゴリズムを記載する。

== 値の表現方法 == 大きな桁数の計算を行う…」