過去ログ
No．１３４６ 多倍長演算
[戻る] [ホームページ]No.18266 |
もんきっきのプログラムソース１ 投稿者---もんきっき(2004/11/20 00:50:07) |
||
返信遅くなりましたm(__)m２つに分けて 貼りますので一つのプログラムとして 見てください。f(^^; #include<stdio.h>
#include<string.h>
int change_int(char A)
{
switch(A){
case '0':
return 0;
case '1':
return 1;
case '2':
return 2;
case '3':
return 3;
case '4':
return 4;
case '5':
return 5;
case '6':
return 6;
case '7':
return 7;
case '8':
return 8;
case '9':
return 9;
}
return 0;
}
int addition(int a[],int b[])
{
int i,j=0,c=0,add[41];
for(i=0;i<=40;i++)
add[i]=0;
for(i=40;i>=0;i--){
add[i] = a[i] + b[i] + c;
if(add[i]>=10){
c = add[i]/10;
add[i] = add[i] % 10;
}
else
c = 0;
}
for(i=0;i<=40;i++){
if(add[i]==0)
j++;
else
break;
}
printf("x+y=");
for(i=j;i<=40;i++)
printf("%d",add[i]);
printf("\n");
return j+40;
}
int subtraction(int a[],int b[])
{
int i,j,c=0,d=0,e=0,p,sub[41];
for(i=0;i<=40;i++)
sub[i]=0;
for(i=0;i<=40;i++){
if(a[i]==0)
c++;
else
break;
}
for(i=0;i<=40;i++){
if(b[i]==0)
d++;
else
break;
}
if(c>d)
p=0;
else if(c==d){
for(i=0;i<=40;i++){
if(a[i]==b[i]){
e++;
continue;
}
else{
if(a[i]<b[i])
p=0;
else
p=1;
}
break;
}
}
else
p=1;
if(p==0){
for(i=40;i>=0;i--){
if(b[i]<a[i]){
sub[i] = b[i] + 10 - a[i];
b[i-1] = b[i-1] - 1;
}
else
sub[i] = b[i] - a[i];
}
}
else{
for(i=40;i>=0;i--){
if(a[i]<b[i]){
sub[i] = a[i] + 10 - b[i];
a[i-1] = a[i-1] - 1;
}
else
sub[i] = a[i] - b[i];
}
}
j = 0;
for(i=0;i<=40;i++){
if(sub[i]==0)
j++;
else
break;
}
if(e==41)
printf("x-y=0");
else if(p==0){
printf("x-y=-");
for(i=j;i<=40;i++)
printf("%d",sub[i]);
}
else{
printf("x-y=");
for(i=j;i<=40;i++)
printf("%d",sub[i]);
}
printf("\n");
if(e==41)
return 80;
else
return j+40;
}
|
|||
| No.18267 |
Re:もんきっきのプログラムソース２ 投稿者---もんきっき(2004/11/20 00:51:05) |
||
int multiplication(int a[],int b[])
{
int i,j,k,m,n,c,d,mul[82];
for(i=0;i<=81;i++)
mul[i]=0;
k=0;
for(i=40;i>=0;i--){
c=0;
for(j=40;j>=0;j--){
mul[j+41-k]=a[j]*b[i]+mul[j+41-k]+c;
if(mul[j+41-k]>=10){
c=mul[j+41-k]/10;
mul[j+41-k]=mul[j+41-k]%10;
}
else
c=0;
}
k++;
}
j=0;
for(i=0;i<=81;i++){
if(mul[i]==0)
j++;
else
break;
}
printf("x*y=");
for(i=j;i<=81;i++)
printf("%d",mul[i]);
printf("\n");
return j-1;
}
int keta(int a)
{
return 81-a;
}
void main()
{
char x[41], y[41];
int a[41], b[41];
int i, m, n ,c,d,e;
for(i=0;i<=40;i++){
a[i]=0;
b[i]=0;
}
printf("x=");
scanf("%s", &x);
printf("y=");
scanf("%s", &y);
m = strlen(x);
for(i=0;i<m;i++)
a[i] = change_int(x[i]);
for(i=m-1;i>=0;i--)
a[41-m+i] = a[i];
for(i=0;i<=40-m;i++)
a[i]=0;
n = strlen(y);
for(i=0;i<n;i++)
b[i] = change_int(y[i]);
for(i=n-1;i>=0;i--)
b[41-n+i] = b[i];
for(i=0;i<=40-n;i++)
b[i]=0;
c = addition(a,b);
printf("桁数…%d桁\n",keta(c));
d = subtraction(a,b);
printf("桁数…%d桁\n",keta(d));
e = multiplication(a,b);
printf("桁数…%d桁\n",keta(e));
}
|
|||
| No.18269 |
Re:もんきっきのプログラムソース１ 投稿者---ぽこ(2004/11/20 01:45:30) |
||
取り合えず、change_int()から。 '0'が入力されたとき、0が返って来ますが、正常の値かエラー値か判断できません。 エラーの時、-1を返すようにしたのが以下の例です。
int
change_int(char c)
{
return isdigit(c) ? c - '0': -1;
}
|
|||
| No.18270 |
Re:もんきっきのプログラムソース１ 投稿者---もんきっき(2004/11/20 02:06:54) |
||
>ぽこさんへ 先ほどのアドバイスを 実行しても変わりませんでした。(泣) 例えばx=22,y=5を入力してもらって実行 してもらうと本当は110なのですが60と 出力されます。またx=1000,y=99と入力 すると-9-18-90などと出力されてしまい ます。 |
|||
| No.18271 |
Re:もんきっきのプログラムソース１ 投稿者---ぽこ(2004/11/20 02:13:15) |
||
>>ぽこさんへ >先ほどのアドバイスを >実行しても変わりませんでした。(泣) それはそうかと。 関数が長かったので、短くしただけです^^; |
|||
| No.18272 |
Re:もんきっきのプログラムソース１ 投稿者---ぽこ(2004/11/20 02:36:09) |
||
>例えばx=22,y=5を入力してもらって実行 >してもらうと本当は110なのですが60と >出力されます。またx=1000,y=99と入力 >すると-9-18-90などと出力されてしまい >ます。 subtraction()がおかしいですね。 繰り下がりの引き算を行ったときに、 a[i]=a[i]-1(b[i]=b[i]-1)とやってますね。 これのおかげで、次の掛け算の際にx[]とy[]の値が変わっています。 なぜ変わるかというのは、以下のURLを参考にしてください。 http://www9.plala.or.jp/sgwr-t/c/sec11-2.html (2)アドレス渡しの※の部分をよく読んで下さい。 |
|||
| No.18273 |
Re:もんきっきのプログラムソース１ 投稿者---もんきっき(2004/11/20 03:27:54) |
||
>ぽこさんへ おお〜！！直りました！ a[i]=a[i]-1(b[i]=b[i]-1)をやると 元のmain内の値が変わってしまうって ことですよね？まだアドレス渡しを習って ないので自分で先ほどのURLを見てそのように 解釈しましたが、あってるんでしょうか？f(^^; 今回のおれが作ったようなプログラムの場合は subtraction関数内で元の配列の値を引いている ので、その次に実行されるmultiplication関数では 元の値が入っていないってことですよね！？ |
|||
| No.18274 |
Re:もんきっきのプログラムソース１ 投稿者---ぽこ(2004/11/20 03:30:45) |
||
>解釈しましたが、あってるんでしょうか？f(^^; >今回のおれが作ったようなプログラムの場合は >subtraction関数内で元の配列の値を引いている >ので、その次に実行されるmultiplication関数では >元の値が入っていないってことですよね！？ ということです。 |
|||
| No.18275 |
Re:もんきっきのプログラムソース１ 投稿者---もんきっき(2004/11/20 03:40:31) |
||
ぽこさん本当にありがとうございました！！ とても感謝しています！返信してくださった 方々、これからもよろしくお願いします。 |
|||
| No.18276 |
Re:もんきっきのプログラムソース１ 投稿者---かずま(2004/11/20 13:31:30) |
||
演算と入出力は別関数にしたほうがよいのではないでしょうか。そんな プログラムを書いてみました。オーバーフローのチェックはやっていません。
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define N 40
int add(const char *a, const char *b, char *c)
{
int i, x, y = 0;
for (i = 0; i < N; i++)
x = a[i] + b[i] + y, c[i] = (y = x >= 10) ? x - 10 : x;
return y;
}
int sub(const char *a, const char *b, char *c)
{
int i, x, y = 0;
for (i = 0; i < N; i++)
x = a[i] - b[i] - y, c[i] = (y = x < 0) ? x + 10 : x;
return y;
}
int mul(const char *a, const char *b, char *c)
{
int i, j; char x[N+1] = { 0 };
for (i = 0; i < N; i++)
for (j = 0; i+j < N; j++)
x[i+j] += a[i] * b[j], x[i+j+1] += x[i+j] / 10, x[i+j] %= 10;
memcpy(c, x, N);
return x[N];
}
int input(const char *msg, char *x)
{
int n, i, c, minus = 0;
char y[N] = { 0 }, c10[N] = { 0, 1 };
memset(x, 0, N);
fputs(msg, stdout);
do c = getchar(); while (isspace(c));
if (c == EOF) return EOF;
if (c == '-') minus = 1, c = getchar();
else if (c == '+') c = getchar();
if (!isdigit(c)) { ungetc(c, stdin); return EOF; }
do {
mul(x, c10, x), y[0] = c - '0', add(x, y, x);
c = getchar();
} while (isdigit(c));
ungetc(c, stdin);
if (minus) y[0] = 0, sub(y, x, x);
return 0;
}
void print(const char *pre, const char *x, const char *post)
{
int i; char y[N];
fputs(pre, stdout);
if (x[N-1] < 5) memcpy(y, x, N);
else memset(y, 0, N), sub(y, x, y), putchar('-');
for (i = N; --i > 0 && y[i] == 0; ) ;
for (; i >= 0; i--) putchar(y[i] + '0');
fputs(post, stdout);
}
int main(void)
{
char x[N], y[N], z[N];
while (input("x = ", x) != EOF && input("y = ", y) != EOF) {
add(x, y, z); print(" x + y = ", z, "\n");
sub(x, y, z); print(" x - y = ", z, "\n");
mul(x, y, z); print(" x * y = ", z, "\n");
}
return 0;
}
|
|||
| No.18277 |
Re:もんきっきのプログラムソース１ 投稿者---かずま(2004/11/20 13:58:16) |
||
input() に無駄な処理が多すぎるので訂正。
int input(const char *msg, char *x)
{
int n, i, c, minus = 0; static char zero[N] = { 0 };
fputs(msg, stdout);
do c = getchar(); while (isspace(c));
if (c == EOF) return EOF;
if (c == '-') minus = 1, c = getchar();
else if (c == '+') c = getchar();
if (!isdigit(c)) { ungetc(c, stdin); return EOF; }
for (i = N; i > 0 && isdigit(c); )
x[--i] = c - '0', c = getchar();
memmove(x, x+i, N-i), memset(x+(N-i), 0, i);
if (minus) sub(zero, x, x);
return 0;
}
|
|||
| No.18285 |
またまた質問です。 投稿者---もんきっき(2004/11/21 00:12:54) |
||
今までの多倍長演算に割り算を加えたいと思い 作成したのですが、結果が出力されずにおわりません。 どこがおかしいでしょうか？(また長くてすいません) #include<stdio.h>
#include<string.h>
int change_int(char c)
{
switch(c){
case '0':
return 0;
case '1':
return 1;
case '2':
return 2;
case '3':
return 3;
case '4':
return 4;
case '5':
return 5;
case '6':
return 6;
case '7':
return 7;
case '8':
return 8;
case '9':
return 9;
}
return 0;
}
int division(int a[],int b[])
{
int i,c=0,d=0,f,j,n,g,h,r,t,s,u,z,v,k,tmp[82],div[41];
for(i=0;i<=40;i++)
div[i]=0;
for(i=0;i<=40;i++){
if(a[i]==0)
c++;
else
break;
}
for(i=0;i<=40;i++){
if(b[i]==0)
d++;
else
break;
}
if(c<=d){
for(i=40-(d-c);i<=40;i++){
for(n=9;n>=0;n--){
div[i]=n;
k=0;
for(j=0;j<=40;j++)
tmp[j]=0;
for(g=40;g>=0;g--){
f=0;
for(h=40;h>=i;j--){
tmp[h+41-k]=div[h]*b[g]+tmp[h+41-k]+f;
if(tmp[h+41-k]>=10){
f=tmp[j+41-k]/10;
tmp[h+41-k]=tmp[h+41-k]%10;
}
else
f=0;
}
k++;
}
j=0;
for(r=0;r<=40;r++){
if(tmp[r+41]==0)
j++;
else
break;
}
g=0;
for(g=0;g<=40;g++){
if(a[g]==0)
g++;
else
break;
}
if(g>j)
break;
else{
t=0;
for(s=0;s<=40;s++){
if(a[s]==tmp[s+41])
t++;
else
break;
}
}
if(a[t]>tmp[t+41])
break;
}
for(u=40;u>=0;i--){
if(a[u]<tmp[u+41]){
a[u] = a[u] + 10 - tmp[u+41];
a[u-1] = a[u-1] - 1;
}
else
a[u] = a[u] - tmp[u+41];
}
z=0;
for(v=0;v<=40;v++){
if(a[v]==b[v])
z++;
else
break;
}
if(a[z]>b[z])
break;
}
}
j=0;
for(i=0;i<=40;i++){
if(div[i]==0)
j++;
else
break;
}
if(c>d)
printf("x/y=0\n");
else{
printf("x/y=");
for(i=j;i<=40;i++)
printf("%d",div[i]);
printf("\n");
}
if(c>d)
return 80;
else
return j+40;
}
int keta(int a)
{
return 81-a;
}
void main()
{
char x[41], y[41];
int a[41], b[41],f;
int i,m,n;
printf("x=");
scanf("%s", &x);
printf("y=");
scanf("%s", &y);
for(i=0;i<=40;i++){
a[i]=0;
b[i]=0;
}
m = strlen(x);
for(i=0;i<m;i++)
a[i]=change_int(x[i]);
for(i=m-1;i>=0;i--)
a[41-m+i]=a[i];
for(i=0;i<=40-m;i++)
a[i]=0;
n=strlen(y);
for(i=0;i<n;i++)
b[i]=change_int(y[i]);
for(i=n-1;i>=0;i--)
b[41-n+i]=b[i];
for(i=0;i<=40-n;i++)
b[i]=0;
f=division(a,b);
printf("桁数…%d\n",keta(f));
}
|
|||
| No.18286 |
Re:またまた質問です。 投稿者---かずま(2004/11/21 00:46:12) |
||
> for(h=40;h>=i;j--){
> for(u=40;u>=0;i--){
この 2行を修正すると、無限ループはなくなりますが、結果が正しく
ならないようですね。ちょっとコードを追い切れません。
私のプログラムにも割り算をつけてみました。
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define N 40
int add(const char *a, const char *b, char *c)
{
int i, x, y = 0;
for (i = 0; i < N; i++)
x = a[i] + b[i] + y, c[i] = (y = x >= 10) ? x - 10 : x;
return y;
}
int sub(const char *a, const char *b, char *c)
{
int i, x, y = 0;
for (i = 0; i < N; i++)
x = a[i] - b[i] - y, c[i] = (y = x < 0) ? x + 10 : x;
return y;
}
int mul(const char *a, const char *b, char *c)
{
int i, j; char x[N+1] = { 0 };
for (i = 0; i < N; i++)
for (j = 0; i+j < N; j++)
x[i+j] += a[i]*b[j], x[i+j+1] += x[i+j]/10, x[i+j] %= 10;
memcpy(c, x, N);
return x[N];
}
static char zero[N] = { 0 };
static void udiv(const char *a, const char *b, char *c, int rem)
{
int i, j; char x[2*N] = { 0 };
memcpy(x, a, N);
for (i = N; --i >= 0; ) {
for (j = 0; sub(x+i, b, x+i) == 0; j++) ;
add(x+i, b, x+i), c[i] = j;
}
if (rem) memcpy(c, x, N);
}
void dvd(const char *a, const char *b, char *c)
{
int neg = 0; char x[N], y[N];
udiv((a[N-1] < 5) ? a : (sub(zero, a, x), neg = 1, x),
(b[N-1] < 5) ? b : (sub(zero, b, y), neg ^= 1, y), c, 0);
if (neg) sub(zero, c, c);
}
void rem(const char *a, const char *b, char *c)
{
int neg = 0; char x[N], y[N];
udiv((a[N-1] < 5) ? a : (sub(zero, a, x), neg = 1, x),
(b[N-1] < 5) ? b : (sub(zero, b, y), y), c, 1);
if (neg) sub(zero, c, c);
}
int input(const char *msg, char *x)
{
int i, c, minus = 0;
fputs(msg, stdout);
do c = getchar(); while (isspace(c));
if (c == '-') minus = 1, c = getchar();
else if (c == '+') c = getchar();
if (!isdigit(c)) { ungetc(c, stdin); return EOF; }
for (i = N; i > 0 && isdigit(c); c = getchar())
x[--i] = c - '0';
memmove(x, x+i, N-i), memset(x+(N-i), 0, i);
if (minus) sub(zero, x, x);
return 0;
}
void print(const char *pre, const char *x, const char *post)
{
int i; char y[N]; const char *p;
fputs(pre, stdout);
p = (x[N-1] < 5) ? x : (sub(zero, x, y), putchar('-'), y);
for (i = N; --i > 0 && p[i] == 0; ) ;
for (; i >= 0; i--) putchar(p[i] + '0');
fputs(post, stdout);
}
int main(void)
{
char x[N], y[N], z[N];
while (input("x = ", x) != EOF && input("y = ", y) != EOF) {
add(x, y, z); print(" x + y = ", z, "\n");
sub(x, y, z); print(" x - y = ", z, "\n");
mul(x, y, z); print(" x * y = ", z, "\n");
dvd(x, y, z); print(" x / y = ", z, "\n");
rem(x, y, z); print(" x % y = ", z, "\n");
}
return 0;
}
|
|||
| No.18287 |
Re:またまた質問です。 投稿者---かずま(2004/11/21 00:56:48) |
||
> udiv((a[N-1] < 5) ? a : (sub(zero, a, x), neg = 1, x), dvd() の中ですが、neg = 1 を neg ^= 1 に訂正します。 |
|||
| No.18288 |
Re:またまた質問です。 投稿者---もんきっき(2004/11/21 01:24:07) |
||
まだ文字処理関数を習っていないので かずまさんのプログラムが少し理解で きないんですが四則全て計算してこの 短さなんですね(驚 自分のは長すぎて見にくいですね(><) |
|||
| No.18300 |
Re:またまた質問です。 投稿者---かずま(2004/11/22 12:57:45) |
||
> まだ文字処理関数を習っていないので memcpy(c, x, N); は、for (i = 0; i < N; i++) c[i] = x[i]; と 置き換えることができます。 memmove(x, x+i, N-i), memset(x+(N-i), 0, i); は for (c = 0; c < N-i; c++) x[c] = x[c+i]; for (; c < N; c++) x[c] = 0; と置き換えてください。 isspace(c) は (c==' ' || c=='\t' || c=='\n')、 isdigit(c) は (c >= '0' && c <= '9') と置き換えることで、 文字処理関数はなくなりますが、これで理解できますか？ 40桁で表現できる数は、0〜999...999 (9が 40個) ですが、これでは 負の数が表せないので、0〜499...999 (9が 39個) はそのままとし、 500...000〜999...999 を負の数として扱っています。 -1 は 0 より 1少ないので、999...999 です。 どうしても、正の数を 40桁扱いたいというのであれば、 #define N 40 を #define N 41 に変えれば済みます。 実は、割り算にはちょっと問題があって、dvd(x, y, y) とすると、 y に正しい値が返ってきません。 |
|||
| No.18308 |
Re:またまた質問です。 投稿者---もんきっき(2004/11/22 22:05:00) |
||
かずまさんありがとうございます。 できる限り自分で解釈してみました。 まだ習ってないことを教わってために なりました。 |
|||