多倍長演算を用いた平方数
多倍長演算を用いた平方数
初めてこちらを利用させて頂きます。至らない点などはご指摘頂ければと思います。
件名通り、多倍長演算を用いた平方数を表示させたいのですが、プログラムの流れとしてはfor文で1~任意の数までを二乗して、表示するといった形にしたいのですが、どのように書けばよいのかわからずご相談させて頂きました。
件名通り、多倍長演算を用いた平方数を表示させたいのですが、プログラムの流れとしてはfor文で1~任意の数までを二乗して、表示するといった形にしたいのですが、どのように書けばよいのかわからずご相談させて頂きました。
Re: 多倍長演算を用いた平方数
文章をそのまま受け取ります。
任意の文字を10にしてあります。
任意の文字を10にしてあります。
► スポイラーを表示
最後に編集したユーザー AKIЯA on 2012年11月02日(金) 18:37 [ 編集 1 回目 ]
Re: 多倍長演算を用いた平方数
>> kaikaiさん
まずはフォーラムルールをお読みください。
>> AKIЯAさん
それを多倍長演算とは言いません。
まずはフォーラムルールをお読みください。
>> AKIЯAさん
それを多倍長演算とは言いません。
Re: 多倍長演算を用いた平方数
あと、void mainではなくint main()またはint main( int argc, char* argv[] )でお願いします。
細かいですがw
細かいですがw
Re: 多倍長演算を用いた平方数
その結果がそのコードっていうのはちょっとなぁ…。AKIЯA さんが書きました:文章をそのまま受け取ります。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
プログラムは思ったとおりには動かない。書いたとおりに動く。
Re: 多倍長演算を用いた平方数
それっぽいサンプルコードなら見つけましたよ。
http://www5.airnet.ne.jp/tomy/cpro/csource.htm
http://www5.airnet.ne.jp/tomy/cpro/csource.htm
Re: 多倍長演算を用いた平方数
フォーラムルールも読まず失礼しました。
プログラム暦は大学で学ぶ基礎的なものを2年ほどです。(変数の利用、if,while,forなどの分岐、1次、2次配列、関数とポインタ、構造体)
現在書籍を参考に作っているのですが、参考にし理解できた部分のみのプログラムが↓です。
まずmulsの中身を、配列i,ある数x,桁上がりup,退避shel,答えansとして,
int i,up=0,shel
for() {
x*x+up=shel
ans=shel%TM
up=shel/TM
for文でi回、x*x+桁上がりを計算し、答えにshelの余りを格納、upには桁上がりを入れる。
という文を書きたいのですが。
プログラム暦は大学で学ぶ基礎的なものを2年ほどです。(変数の利用、if,while,forなどの分岐、1次、2次配列、関数とポインタ、構造体)
現在書籍を参考に作っているのですが、参考にし理解できた部分のみのプログラムが↓です。
#include<stdio.h>
#include<math.h>
#define B 10 //格納する要素数
#define LIMIT 99 //任意の数 暫定で99
#define TM 10000000 //7桁の最大値9999999+1
//関数のプロトタイプ宣言
void printresult(int x[],int ans[])//結果出力
void muls()//計算処理
int main(int x[],int ans[])
{
int i; //回数
for(i=1;i<=LIMIT;i++) //繰り返し処理
printf("%dの二乗",i);
printresult(ans);
}
//結果出力
void printresult(int x[],int ans)
{
}
//計算処理
void muls(int x[],ans[])
{
}
}
int i,up=0,shel
for() {
x*x+up=shel
ans=shel%TM
up=shel/TM
for文でi回、x*x+桁上がりを計算し、答えにshelの余りを格納、upには桁上がりを入れる。
という文を書きたいのですが。
Re: 多倍長演算を用いた平方数
AKIЯAさん
ホヅミさん
リンクありがとうございます。
プログラムを暫定的に作ってみたのですが、
エラー E2193 a.c 19: 呼び出し時のパラメータが足りない:muls(関数 main )
となり実行できませんでした。
midans+=x*x;がおかしいと思うのですが、どのようにすれば良いかお知恵を拝借させてください。
ホヅミさん
リンクありがとうございます。
#include<stdio.h>
#include<math.h>
#define N 8 //格納する要素数
#define LIMIT 99 //任意の数 暫定で99
#define TM 10000000 //7桁の最大値9999999+1
//関数のプロトタイプ宣言
void printresult(unsigned long ans[]); //結果出力
void muls(unsigned long x[],unsigned long ans[]); //計算処理
int main()
{
unsigned long x[N]={0};
unsigned long ans[N]={0};
int i; //繰り返しカウンタ
x[0]=1;
for(i=1;i<=LIMIT;i++) {//繰り返し処理
muls(ans);
printf("%dの二乗",i);
printresult(ans);
}
return 0;
}
//結果出力
void printresult(unsigned long ans[])
{
int j; //繰り返しカウンタ
for(j=N-1;j>=0;j--) { //N-1=7
if(ans[j]==0) printf(" "); //配列の中身が0なら空白を8桁分出力する
else printf("%8lu",ans[j]); //配列の中身が0以外 つまり中身をそのまま表示
}
printf("\n");
}
//計算処理
void muls(unsigned long x[],unsigned long ans[])
{
int i; //繰り返しカウンタ
unsigned long midans[N]={0};
for(i=0;i<N;i++) {
midans[i]+=x[i]*x[i];
if(midans[i]>=TM) { //桁上がりなら足す
if(i!=N-1) { midans[i+1]+=midans[i]/TM; }
else {
fprintf(stderr,"桁あふれだぞ\n");
exit(1);
}
midans[i]=midans[i]%TM;
}
}
for(i=0;i<N;i++)
ans[i]=midans[i];
}
エラー E2193 a.c 19: 呼び出し時のパラメータが足りない:muls(関数 main )
となり実行できませんでした。
midans+=x*x;がおかしいと思うのですが、どのようにすれば良いかお知恵を拝借させてください。
Re: 多倍長演算を用いた平方数
AKIЯAさん
> プログラムの流れとしてはfor文で1~任意の数までを二乗して、表示する
> ここしか見てなかったwww
任意の数まで処理してないです。
kaikaiさん
> エラー E2193 a.c 19: 呼び出し時のパラメータが足りない:muls(関数 main )
mulsは引数が2つ必要という事です。
x[0]=i;
muls(x, ans);
> プログラムの流れとしてはfor文で1~任意の数までを二乗して、表示する
> ここしか見てなかったwww
任意の数まで処理してないです。
kaikaiさん
> エラー E2193 a.c 19: 呼び出し時のパラメータが足りない:muls(関数 main )
mulsは引数が2つ必要という事です。
x[0]=i;
muls(x, ans);
Re: 多倍長演算を用いた平方数
AKIЯAさん
たいちうさん
お早いお返事ありがとうございます。無事プログラムは動きました。
目標自体にはまだ届いていないので、質問すると思いますが、またお時間がありましたらお願い致します。
たいちうさん
お早いお返事ありがとうございます。無事プログラムは動きました。
目標自体にはまだ届いていないので、質問すると思いますが、またお時間がありましたらお願い致します。
Re: 多倍長演算を用いた平方数
> 目標自体にはまだ届いていないので、質問すると思いますが、またお時間がありましたらお願い致します。
そうですね。コンパイルエラーが取れただけです。
99までの自乗ならば多倍長は必要ないので正しい答えになっていますが、
関数muls()は、2重のforループになるはずですよ。(1重で書けないこともないけど)
そうですね。コンパイルエラーが取れただけです。
99までの自乗ならば多倍長は必要ないので正しい答えになっていますが、
関数muls()は、2重のforループになるはずですよ。(1重で書けないこともないけど)
Re: 多倍長演算を用いた平方数
ぶっちゃけ誰かが絶対言うだろうと思ってたのですが、
そもそも質問に対する突込みって違いますよね。
「多倍長が必要になるところまで1~nまでの二乗を表示する」
というということそのものが無理だと思います。
時間的に。
そもそもunsigned long longの最大値ですらとんでもない数ですからね。
1年ほど前に、暇つぶしに作った多倍長変数を扱うクラスを見つけたので(C++ですが)参考程度に乗せておきます。
ただし実装しているアルゴリズムはいわゆる筆算であり、出来のいいものではありません・・・。
一応加減乗除はでき、1000!くらいまでは頑張って計算できます。
しかし多倍長が必要になる領域まで表示するのにいったいどれくらいかかるのだろうか・・・?
以下のプログラムは任意の数(桁数に制限なし)まで2乗を表示し続けます
BigInteger.hの中身(閲覧注意;非常に読む気のうせるコードが記載されております。)
(コードとして書くと記事が表示されなくなるバグがあるようでしたので添付ファイルにしました)
また後からboostを使用していることに気が付いたため、導入されていないかもと思い実行ファイルも添付しておきますが、
単純に入力値の2乗を表示するだけのプログラムにしてあります。
そもそも質問に対する突込みって違いますよね。
「多倍長が必要になるところまで1~nまでの二乗を表示する」
というということそのものが無理だと思います。
時間的に。
そもそもunsigned long longの最大値ですらとんでもない数ですからね。
1年ほど前に、暇つぶしに作った多倍長変数を扱うクラスを見つけたので(C++ですが)参考程度に乗せておきます。
ただし実装しているアルゴリズムはいわゆる筆算であり、出来のいいものではありません・・・。
一応加減乗除はでき、1000!くらいまでは頑張って計算できます。
しかし多倍長が必要になる領域まで表示するのにいったいどれくらいかかるのだろうか・・・?
以下のプログラムは任意の数(桁数に制限なし)まで2乗を表示し続けます
#include <iostream>
#include "BigInteger.h"
using namespace std;
int main()
{
cout << "最大値を入力してください" <<endl;
Numeric::BigInteger max;
cin >> max;
for( Numeric::BigInteger i(0); i <= max; ++i )
{
cout << i*i << endl;
}
return 0;
}
また後からboostを使用していることに気が付いたため、導入されていないかもと思い実行ファイルも添付しておきますが、
単純に入力値の2乗を表示するだけのプログラムにしてあります。
- 添付ファイル
-
- ctest.zip
- (17.35 KiB) ダウンロード数: 155 回
Re: 多倍長演算を用いた平方数
たいちうさん
ありがとうございました。for2回というのは、自分の方向性があってると再確認できました。
GRAMさん
最終的に表示するのは条件付けを幾つかするので減るのですが、まだ今の段階ですら出来てないので少しずつ進めようと思っております。
ご指摘、ありがとうございます 。
ありがとうございました。for2回というのは、自分の方向性があってると再確認できました。
GRAMさん
最終的に表示するのは条件付けを幾つかするので減るのですが、まだ今の段階ですら出来てないので少しずつ進めようと思っております。
ご指摘、ありがとうございます 。
Re: 多倍長演算を用いた平方数
任意の数ってどこまで? とりあえず 100桁までなら。
#include <stdio.h> // printf, scanf, putchar
#include <stdlib.h> // malloc, calloc, free
#include <string.h> // strlen
int main(void)
{
int i, j, n, t;
char s[101], *x, *y;
while (printf("> "), scanf("%100s", s) == 1 && *s - '0' < 10u) {
n = strlen(s), x = malloc(n), y = calloc(2, n);
for (i = 0; i < n; i++) x[i] = s[n-i-1] - '0';
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
t = x[i] * x[j] + y[i+j], y[i+j] = t % 10, y[i+j+1] += t / 10;
for (i = n * 2; --i > 0 && y[i] == 0; ) ;
while (i >= 0) putchar(y[i--] + '0');
putchar('\n');
free(x), free(y);
}
return 0;
}
Re: 多倍長演算を用いた平方数
s が固定長で、x と y を動的に確保してもあまり意味がありませんね。かずま さんが書きました:任意の数ってどこまで? とりあえず 100桁までなら。
ということで、全部固定にしてみました。今度は 10000桁。
標準入力はファイルにしないと、キー入力の場合、行バッファの
制限により、そんなに多くの桁数の入力ができないかもしれません。
#include <stdio.h> // printf, scanf, putchar
#include <string.h> // strlen
#define N 10000
#define S(N) T(N)
#define T(N) #N
int main(void)
{
static char s[N + 1], x[N], y[2 * N];
int i, j, n, t;
while (printf("> "), scanf("%" S(N) "s", s) == 1 && *s - '0' < 10u) {
n = strlen(s);
for (i = 0; i < n; i++) x[i] = s[n-i-1] - '0';
memset(y, 0, 2 * n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
t = x[i] * x[j] + y[i+j], y[i+j] = t % 10, y[i+j+1] += t / 10;
for (i = n * 2; --i > 0 && y[i] == 0; ) ;
while (i >= 0) putchar(y[i--] + '0');
putchar('\n');
}
return 0;
}
Re: 多倍長演算を用いた平方数
かずまさん
わざわざ2度も書き込みをいただきありがとうございます。
任意桁はまだプログラミングすら未完成なので、出来る所まで調べてみたいと曖昧な目標です。
乗せて頂いたプログラミングは是非参考にさせてもらいます。
わざわざ2度も書き込みをいただきありがとうございます。
任意桁はまだプログラミングすら未完成なので、出来る所まで調べてみたいと曖昧な目標です。
乗せて頂いたプログラミングは是非参考にさせてもらいます。
Re: 多倍長演算を用いた平方数
多倍長についてある程度出来ましたので、回文である、偶数桁である。
この2つを条件付けたいのですが、考え方が決定しない・他に案があるならお聞きしたく書き込ませて頂きました。
回文判定
例として12345678という数値を使います。
案1
配列と配列の中身を入れ替える
12 34 56 78 桁数は少ないですが、多倍長を使うので2個ずつ配列に入れた状態で考えます。
78 56 34 12 配列の順序を真逆にする
87 65 43 21 その後配列の中身を入れ替える
案2
12345678%10=8,1234567%10=7の答えを0になるまで、別の多倍長配列に入れていく。
割り算も使うので案1よりも複雑になる。
案1,案2ともに最後は元の値=入れ替えた値になれば回文という処理を行う。
偶数桁の判定は
配列の中身の個数(長さ)を調べ、それら全てを足し、2で割り切れれば偶数桁。
自分が考えたのは以上です。他にも考え方があれば是非御教え頂きたい。
この2つを条件付けたいのですが、考え方が決定しない・他に案があるならお聞きしたく書き込ませて頂きました。
回文判定
例として12345678という数値を使います。
案1
配列と配列の中身を入れ替える
12 34 56 78 桁数は少ないですが、多倍長を使うので2個ずつ配列に入れた状態で考えます。
78 56 34 12 配列の順序を真逆にする
87 65 43 21 その後配列の中身を入れ替える
案2
12345678%10=8,1234567%10=7の答えを0になるまで、別の多倍長配列に入れていく。
割り算も使うので案1よりも複雑になる。
案1,案2ともに最後は元の値=入れ替えた値になれば回文という処理を行う。
偶数桁の判定は
配列の中身の個数(長さ)を調べ、それら全てを足し、2で割り切れれば偶数桁。
自分が考えたのは以上です。他にも考え方があれば是非御教え頂きたい。
Re: 多倍長演算を用いた平方数
回文も偶数桁も、案2の手法で文字列化すれば良いと思います。
以下は簡単な説明。
char buf[100] = { 0 };
int n = 12345678;
buf[0] = '0' + n % 10; // '8' が代入される
n /= 10;
buf[1] = '0' + n % 10; // '7' が代入される
n /= 10;
...
printf("%s\n", buf); // "87654321" と表示される
以下は簡単な説明。
char buf[100] = { 0 };
int n = 12345678;
buf[0] = '0' + n % 10; // '8' が代入される
n /= 10;
buf[1] = '0' + n % 10; // '7' が代入される
n /= 10;
...
printf("%s\n", buf); // "87654321" と表示される
Re: 多倍長演算を用いた平方数
/*多倍長*/
#include<stdio.h>
#define N 8 //配列数
#define KETA 10000 //桁数制限9999+1
void add(int x[],int y[],int z[]); //z=x+y
void mul(int x[],int y,int z[]); //z=x*y
void muls(int x[],int y[],int z[]);
void print_result(int z[]); //表示
void add(int x[],int y[],int z[]) {
int up,i,sum; //up:桁上がりした数,i:カウンタ,sum:4桁ごとの計算結果
up=0; //最初は桁上がりなし
for(i=0;i<=N;i++) {
sum=x[i]+y[i]+up; //xとyと桁上がりがある場合upが足される
if(sum>KETA-1) { //4桁の数が9999より大きいかで桁上がりを確認
z[i]=sum-KETA; //桁上がりの処理
up=1;
}
else { //桁上がり発生しない場合
z[i]=sum; up=0; //桁上がり発生しない場合の処理
}
}
}
void mul(int x[],int y,int z[]) {
int i,up=0,mir; //乗算
for(i=N;i>=0;i--) {
mir=x[i]*y+up;
z[i]=mir%KETA;
up=mir/KETA;
}
}
void muls(int x[],int y[],int z[]) {
int i,up=0,mir; //乗算
int z0[N+1]={0},z1[N+1]={0},z2[N+1]={0},z3[N+1]={0},z4[N+1]={0},z5[N+1]={0},z6[N+1]={0},z7[N+1]={0},z8[N+1]={0};
for(i=N;i>=0;i--) {
mir=x[i]*y[8]+up;
z8[i]=mir%KETA;
up=mir/KETA;
}
for(i=N;i>=0;i--) {
mir=x[i]*y[7]+up;
z7[i]=mir%KETA;
up=mir/KETA;
} mul(z7,KETA,z7);
for(i=N;i>=0;i--) {
mir=x[i]*y[6]+up;
z6[i]=mir%KETA;
up=mir/KETA;
} for(i=N;i>=0;i--) {
mir=x[i]*y[5]+up;
z5[i]=mir%KETA;
up=mir/KETA;
} for(i=N;i>=0;i--) {
mir=x[i]*y[4]+up;
z4[i]=mir%KETA;
up=mir/KETA;
} for(i=N;i>=0;i--) {
mir=x[i]*y[3]+up;
z3[i]=mir%KETA;
up=mir/KETA;
} for(i=N;i>=0;i--) {
mir=x[i]*y[2]+up;
z2[i]=mir%KETA;
up=mir/KETA;
} for(i=N;i>=0;i--) {
mir=x[i]*y[1]+up;
z1[i]=mir%KETA;
up=mir/KETA;
} for(i=N;i>=0;i--) {
mir=x[i]*y[0]+up;
z0[i]=mir%KETA;
up=mir/KETA;
}
add(z7,z8,z);
}
void print_result(int z[]) {
int i;
for(i=0;i<=N;i++) {
printf("%04u ",z[i]);
}
printf("\n");
}
/*平方数探索*/
#include"a.h"
void mul(int x[],int y,int z[]); //z=x*y
void muls(int x[],int y[],int z[]);
void print_result(int z[]); /*表示用関数*/
int main(void) {
int x[N+1]={0000,0000,0000,0000,0000,0000,0000,0000,0001};
int y[N+1];
int z[N+1]; /*結果はZへ*/
int i;
for(i=50008;i<=50009;i++) {
mul(x,i,y); printf("%dの2乗=",i); print_result(y);
muls(y,y,z); print_result(z);
}
return 0;
}
50008の2乗=0000 0000 0000 0000 0000 0000 0000 0005 0008
0000 0000 0000 0000 0000 0000 0025 0080 0064
50009の2乗=0000 0000 0000 0000 0000 0000 0000 0005 0009
0000 0000 0000 0000 0000 0000 0025 0090 0081
i,y
zの順で表示しています。i=yですが、多倍長としてきちんと入ってるか確認のため表示させてます。
また行き詰ってしまったので御知恵を拝借したく。
多倍長整数のxにiをかけyに結果を。y*y=zで平方数を得る形です。
4桁同士の掛け算まではいいのですが、5桁以上同士では同じ配列要素数の中でしか掛け算出来ていません。
5桁以上の処理としてはy[0000 1111 2222]*y[0000 1111 2222]の場合
0000 1111 2222 y 1111 2222 0000 y*10000
* 2222 y[3] * 1111 y[2]
=246 9135 7284 =123 4567 8642 0000
このような処理です。要素数Nとし、y[]*y[N],y[]*[N-1]、……y*y[0]と計算していき、yは計算の度に10000掛ける。
このような処理で作ろうとしているのですが、for文などで括るのがうまくいかなかったので、
例のz7[]=246 9135 7284、z6[]=123 4567 8642 0000をそれぞれ配列に入れて最後に全てを足し、z格納。
今回は 「yは計算の度に10000掛ける」 は必要箇所以外省いてます。
思いついた処理をそのまま書いてしまったため、かなり無駄が多いです。
お聞きしたいのは5桁以上同士の処理mulsは、他の処理方法は無いか。です
宜しければご意見下さい。また文章でおかしい点・伝わらない点などございましたらご指摘頂けると幸いです。
Re: 多倍長演算を用いた平方数
質問内容がよく理解できません。
気がついたことを書いてみます。
とありますから、N は「配列数」ではなく、「要素数 - 1」ですよね。
x[0] がs最上位桁、x[N] が最下位桁。
add() は、上位桁から処理しているので、繰り上がりの処理ができません。
main で i = 59999 にしてみると正しくない結果になることがわかります。
mul() の第2引数 の int y は、214769 より大きい値だと、
mir = x * y + up; でオーバーフローしますね。
x = 9999 の場合を考えてみてください。
muls() はインデントが変です。
z0[N+1], z1[N+1], ..., z8[N+1] なんて宣言するのなら、
z[N+1][N+1]; と 2次元配列にしたほうがよいのでは?
この行からあとは全部意味不明です。
なお、x[N-1] が最上位桁、x[0] が最下位桁 とすると、
次のようなプログラムが書けます。
気がついたことを書いてみます。
とありますから、N は「配列数」ではなく、「要素数 - 1」ですよね。
x[0] がs最上位桁、x[N] が最下位桁。
add() は、上位桁から処理しているので、繰り上がりの処理ができません。
main で i = 59999 にしてみると正しくない結果になることがわかります。
mul() の第2引数 の int y は、214769 より大きい値だと、
mir = x * y + up; でオーバーフローしますね。
x = 9999 の場合を考えてみてください。
muls() はインデントが変です。
z0[N+1], z1[N+1], ..., z8[N+1] なんて宣言するのなら、
z[N+1][N+1]; と 2次元配列にしたほうがよいのでは?
kaikai さんが書きました:4桁同士の掛け算まではいいのですが、5桁以上同士では同じ配列要素数の中でしか掛け算出来ていません。
この行からあとは全部意味不明です。
なお、x[N-1] が最上位桁、x[0] が最下位桁 とすると、
次のようなプログラムが書けます。
#include <stdio.h>
#include <string.h>
#define N 9
void clear(int x[]) { memset(x, 0, N * sizeof(int)); }
void print(int x[])
{
int i = N;
while (--i > 0 && x[i] == 0) ;
printf("%d", x[i]);
while (--i >= 0) printf(" %04d", x[i]);
}
int muls(int x[], int y[], int z[])
{
int i, j, w[N * 2] = { 0 };
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
int t = x[i] * y[j] + w[i+j];
w[i+j] = t % 10000;
w[i+j+1] += t / 10000;
if (i+j+1 > N && w[i+j+1] != 0) return 1; // overflow
}
z[i] = w[i];
}
return 0; // no error
}
int main(void)
{
int x[N], y[N];
clear(x), x[1] = 5, x[0] = 8; // x = 50008
muls(x, x, y);
print(x), printf(" の 2乗 = "), print(y), printf("\n");
clear(x), x[1] = 5, x[0] = 9999; // x = 59999
muls(x, x, y);
print(x), printf(" の 2乗 = "), print(y), printf("\n");
clear(x), x[1] = 1111, x[0] = 2222; // x = 11112222
muls(x, x, y);
print(x), printf(" の 2乗 = "), print(y), printf("\n");
return 0;
}
Re: 多倍長演算を用いた平方数
オーバーフローの判定方法が間違っていました。かずま さんが書きました:なお、x[N-1] が最上位桁、x[0] が最下位桁 とすると、
次のようなプログラムが書けます。
次のプログラムを実行してみると、わかります。
int x[N], y[N], z[N], of;
clear(x), x[N-1] = 5000; // x = 5000 0000 ... 0000
clear(y), y[0] = 2; // y = 2
of = muls(x, y, z);
printf("overflow = %d\n", of);
print(x), printf(" x "), print(y), printf(" = "), print(z), printf("\n");
いう余計な領域を使わないように muls を変更してみました。
int muls(int x[], int y[], int z[])
{
int i, j;
clear(z);
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (i+j < N) {
int t = x[i] * y[j] + z[i+j];
if (t < 10000)
z[i+j] = t;
else {
if (i+j+1 == N) return 1; // overflow
z[i+j+1] += t / 10000;
z[i+j] = t % 10000;
}
}
else if (x[i] && y[j]) return 1; // overflow
return 0; // no error
}
Re: 多倍長演算を用いた平方数
遅ればせながら、あけましておめでとうございます
たいちうさん、かずまさん御返信ありがとうございます。
かずまさん、分かりにくくて申し訳ありません。
add()に関しては間違いに気づかずそのまま乗せてしまいました。修正し正常に結果が出るので問題無いと思います。
以前の質問の内容はご指摘のあった、muls()のz0[N+1]~z8[N+1]の宣言と処理を簡潔にできないかというものでしたので、乗せて頂いたプログラムがとても参考になります。
また平方数の表示も私のように大量に0を出す必要がなく、とてもわかりやすいプログラムでしたので、参考になります。本当にありがとうございます。
たいちうさん、かずまさん御返信ありがとうございます。
かずまさん、分かりにくくて申し訳ありません。
add()に関しては間違いに気づかずそのまま乗せてしまいました。修正し正常に結果が出るので問題無いと思います。
以前の質問の内容はご指摘のあった、muls()のz0[N+1]~z8[N+1]の宣言と処理を簡潔にできないかというものでしたので、乗せて頂いたプログラムがとても参考になります。
また平方数の表示も私のように大量に0を出す必要がなく、とてもわかりやすいプログラムでしたので、参考になります。本当にありがとうございます。
Re: 多倍長演算を用いた平方数
以前かずまさんよりプログラムを頂き、多倍長整数の平方数の偶数桁までは検索できるようになりました。
今回は回文を求める処理について意見を頂きたく。
今回お聞きしたいのはfor文の同時進行です。
for( a = 10; a >= 0; a--) for( b = 0; b <= 10; b++)と言う場合に、
a=10のとき、b=1~10 a=9のとき、b=1~10ではなく
a=10のとき、b=0 a=9のとき、b=1と同時に進行させたいのです。
プログラムではこのような求め方にしようと↓
count=平方数の桁数、w[]=平方数
このままではr[]の中身は r [1] [0]
6988 9600
となってしまうので反転数rの1桁目が0以外の数になるまで、rを10で割ることで反転数を求めます。
あまりスマートな求め方では無いのではありませんが。
現在できているプログラムも一応載せておきます。
今回は回文を求める処理について意見を頂きたく。
今回お聞きしたいのはfor文の同時進行です。
for( a = 10; a >= 0; a--) for( b = 0; b <= 10; b++)と言う場合に、
a=10のとき、b=1~10 a=9のとき、b=1~10ではなく
a=10のとき、b=0 a=9のとき、b=1と同時に進行させたいのです。
プログラムではこのような求め方にしようと↓
count=平方数の桁数、w[]=平方数
if(count % 2 == 0) { //偶数かどうか
if(count % 4 ==0) { //要素数求め
count = count / 4;
}
else {
count = count / 4 + 1;
}
clear(r); //反転数r初期化
for(j = count; j >= 0; j--) for( k=0; k <= count; k++) //ここのforを同時進行させたい、jが1減ったら、kは1増える。jが2減ったら、kは2増える。
for(l = 0; l < 4; l ++) { //1要素内には数は4つなので4回実行
r[j] = w[k] % 10 + r[j] * 10;
div(w,10,w);
}
}
6988 9600
となってしまうので反転数rの1桁目が0以外の数になるまで、rを10で割ることで反転数を求めます。
あまりスマートな求め方では無いのではありませんが。
現在できているプログラムも一応載せておきます。
#include <stdio.h>
#include <string.h>
#define N 9
void clear(int x[]) { memset(x, 0, N * sizeof(int)); }
void add(int x[],int y[],int z[]) {
int up,i,sum;
up=0;
for(i=0;i<N;i++) {
sum=x[i]+y[i]+up;
if(sum>9999) {
z[i]=sum-10000;
up=1;
}
else {
z[i]=sum; up=0;
}
}
}
int muls(int x[], int y[], int z[]) {
int i, j;
clear(z);
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (i+j < N) {
int t = x[i] * y[j] + z[i+j];
if (t < 10000)
z[i+j] = t;
else {
if (i+j+1 == N) return 1; // overflow
z[i+j+1] += t / 10000;
z[i+j] = t % 10000;
}
}
else if (x[i] && y[j]) return 1; // overflow
return 0; // no error
}
void div(int x[],int n,int z[]) {
int amari,i,bunshi; /*除算*/
amari=0; /*上位桁の余りが下位桁に加算されないとする*/
for(i=N-1;i>=0;i--) {
bunshi=amari*10000+x[i];
z[i]=bunshi/n; /*上位桁の余りが下位桁に加算されないとする*/
amari=bunshi%n; /*上位桁の余りが下位桁に加算されないとする*/
}
}
void print(int x[]) {
int i = N;
while (--i > 0 && x[i] == 0) ;
printf("%d", x[i]);
while (--i >= 0) printf(" %04d", x[i]);
}
int main(void) {
int x[N], y[N], z[N], r[N], w[N]; //x:初期数、y:x*2、z:1、r:反転数、w:y=w桁数求めよう
int i,j,k,l,count; //i,j:カウンタ、count:桁数
clear(x), x[0] = 999;
clear(z), z[0] = 1;
for(i = 0; i < 2; i++) {
count = 0;
muls(x, x, y);
memcpy(w, y, N * sizeof(int));
while(!(w[8]==0 && w[7]==0 && w[6]==0 && w[5]==0 && w[4]==0 && w[3]==0 && w[2]==0 && w[1]==0 && w[0]==0)) { //桁数求め
div(w,10,w);
count++;
}
if(count % 2 == 0) { //偶数かどうか
print(x), printf(" の 2乗 = "),print(y), printf("\n");
}
add(x, z, x);
}
return 0;
}
Re: 多倍長演算を用いた平方数
> 今回お聞きしたいのはfor文の同時進行です。
> for( a = 10; a >= 0; a--) for( b = 0; b <= 10; b++)と言う場合に、
> a=10のとき、b=1~10 a=9のとき、b=1~10ではなく
> a=10のとき、b=0 a=9のとき、b=1と同時に進行させたいのです。
こういう事?
for (a = 10; a >= 0; a--) {
b = 10 - a;
...
}
> for( a = 10; a >= 0; a--) for( b = 0; b <= 10; b++)と言う場合に、
> a=10のとき、b=1~10 a=9のとき、b=1~10ではなく
> a=10のとき、b=0 a=9のとき、b=1と同時に進行させたいのです。
こういう事?
for (a = 10; a >= 0; a--) {
b = 10 - a;
...
}
Re: 多倍長演算を用いた平方数
たいちうさん、返信ありがとうございます。
for文に拘りすぎて簡単に表せることに驚き、阿呆なことを聞いたと恥じてしまいました。
一応完成したと思いますので乗せておきます。
まだ解決したかどうかわからないのでプログラム実行後に問題が無ければ解決にしたいと思います。
for文に拘りすぎて簡単に表せることに驚き、阿呆なことを聞いたと恥じてしまいました。
一応完成したと思いますので乗せておきます。
#include <stdio.h>
#include <string.h>
#define N 9
void clear(int x[]) { memset(x, 0, N * sizeof(int)); }
void add(int x[],int y[],int z[]) {
int up,i,sum;
up=0;
for(i=0;i<N;i++) {
sum=x[i]+y[i]+up;
if(sum>9999) {
z[i]=sum-10000;
up=1;
}
else {
z[i]=sum; up=0;
}
}
}
int muls(int x[], int y[], int z[]) {
int i, j;
clear(z);
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (i+j < N) {
int t = x[i] * y[j] + z[i+j];
if (t < 10000)
z[i+j] = t;
else {
if (i+j+1 == N) return 1; // overflow
z[i+j+1] += t / 10000;
z[i+j] = t % 10000;
}
}
else if (x[i] && y[j]) return 1; // overflow
return 0; // no error
}
void div(int x[],int n,int z[]) {
int amari,i,bunshi; /*除算*/
amari=0; /*上位桁の余りが下位桁に加算されないとする*/
for(i=N-1;i>=0;i--) {
bunshi=amari*10000+x[i];
z[i]=bunshi/n; /*上位桁の余りが下位桁に加算されないとする*/
amari=bunshi%n; /*上位桁の余りが下位桁に加算されないとする*/
}
}
void print(int x[]) {
int i = N;
while (--i > 0 && x[i] == 0) ;
printf("%d", x[i]);
while (--i >= 0) printf(" %04d", x[i]);
}
int main(void) {
int x[N], y[N], z[N], r[N], w[N]; //x:初期数、y:x*2、z:1、r:反転数、w:y=w桁数求めよう
int i,j,k,l,count; //i,j:カウンタ、count:桁数
clear(x), /*x[4] = 11, */x[3] = 1, x[2] = 0000, x[1] = 1000, x[0] = 0003;
clear(z), z[0] = 1;
for(i = 0; i < 2000000; i++) {
count = 0;
muls(x, x, y);
memcpy(w, y, N * sizeof(int));
while(!(w[8]==0 && w[7]==0 && w[6]==0 && w[5]==0 && w[4]==0 && w[3]==0 && w[2]==0 && w[1]==0 && w[0]==0)) { //桁数求め
div(w,10,w);
count++;
}
memcpy(w, y, N * sizeof(int));
//if(count % 2 == 0) { //偶数かどうか
if(count%4==0) {
count=count/4-1;
}
else {
count=count/4;
}
clear(r); //反転数r初期化
for(j=count;j>=0;j--) {
for(l=0;l<4;l++) {
r[j]=w[0]%10+r[j]*10;
div(w,10,w);
}
}
k=r[0]%10;
while(k==0) {
div(r,10,r);
k=r[0]%10;
}
if(y[8]==r[8] && y[7]==r[7] && y[6]==r[6] && y[5]==r[5] && y[4]==r[4] && y[3]==r[3] && y[2]==r[2] && y[1]==r[1] && y[0]==r[0]) {
print(x), printf(" の 2乗 = "), print(y), printf("\n");
print(r),printf("\n");
//}
}
add(x, z, x);
}
return 0;
}
Re: 多倍長演算を用いた平方数
配列の要素数は、#define N 9 で、一要素に 10進 4桁を
収納するので、全部で 36桁まで求めることができます。
N の値を変更することによって、40桁でも100桁でも計算できる
はずですが、kaikai さんのプログラムでは、w[8]==0 とか、
y[8]==r[8] などがハードコーディングされているので、
簡単には変更できません。
私なら次のように書きます。
収納するので、全部で 36桁まで求めることができます。
N の値を変更することによって、40桁でも100桁でも計算できる
はずですが、kaikai さんのプログラムでは、w[8]==0 とか、
y[8]==r[8] などがハードコーディングされているので、
簡単には変更できません。
私なら次のように書きます。
#include <stdio.h>
#define N 9
void clear(int x[]) { int i = N; while (--i >= 0) x[i] = 0; }
int muls(const int *x, const int *y, int *z)
{
int i, j;
clear(z);
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (i+j < N) {
int t = x[i] * y[j] + z[i+j];
if (t < 10000)
z[i+j] = t;
else {
if (i+j+1 == N) return 1; // overflow
z[i+j+1] += t / 10000;
z[i+j] = t % 10000;
}
}
else if (x[i] && y[j]) return 1; // overflow
return 0; // no overflow
}
int inc(int *x)
{
int i = 0;
while (i < N && ++x[i] >= 10000) {
x[i] = 0;
if (++i == N) return 1; // overflow
}
return 0; // no overflow
}
void print(const int *x)
{
int i = N;
while (--i > 0 && x[i] == 0) ;
printf("%d", x[i]);
while (--i >= 0) printf(" %04d", x[i]);
}
int val(const int *x, unsigned int i)
{
unsigned int j = i % 4;
i /= 4;
if (j == 0) return x[i] % 10;
if (j == 1) return x[i] / 10 % 10;
if (j == 2) return x[i] / 100 % 10;
return x[i] / 1000;
}
int palindrome(const int *x)
{
int i = N, j;
while (--i > 0 && x[i] == 0) ;
j = i * 4;
if (x[i] < 10) j++;
else if (x[i] < 100) j += 2;
else if (x[i] < 1000) j += 3;
else j += 4;
for (i = 0; i < --j; i++)
if (val(x, i) != val(x, j)) return 0;
return 1;
}
int main(void)
{
int x[N], y[N], i;
clear(x), x[3] = 1, x[1] = 1000, x[0] = 3; // x = 1 0000 1000 0003
for (i = 0; i < 2000000; i++) {
muls(x, x, y);
if (palindrome(y))
print(x), printf(" の 2乗 = "), print(y), printf("\n");
inc(x);
}
return 0;
}
Re: 多倍長演算を用いた平方数
かずまさん、返信ありがとうございます。
Nを変えた場合には、W[]やy[]==r[]の数を増やしたものを付け足せばいいと思ったのですが、ハードコーディングとご指摘頂いたので変更してみました。
w[8]==0とy[8]==r[8]の部分をmemcmpでまとめてみました。
しかし40桁や100桁の場合を考えていなかったのは浅はかでした。ご指摘ありがとうございます。
Nを変えた場合には、W[]やy[]==r[]の数を増やしたものを付け足せばいいと思ったのですが、ハードコーディングとご指摘頂いたので変更してみました。
w[8]==0とy[8]==r[8]の部分をmemcmpでまとめてみました。
しかし40桁や100桁の場合を考えていなかったのは浅はかでした。ご指摘ありがとうございます。
#include <stdio.h>
#include <string.h>
#define N 9
void clear(int x[]) { memset(x, 0, N * sizeof(int)); }
void add(int x[],int y[],int z[]) {
int up,i,sum;
up=0;
for(i=0;i<N;i++) {
sum=x[i]+y[i]+up;
if(sum>9999) {
z[i]=sum-10000;
up=1;
}
else {
z[i]=sum; up=0;
}
}
}
int muls(int x[], int y[], int z[]) {
int i, j;
clear(z);
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (i+j < N) {
int t = x[i] * y[j] + z[i+j];
if (t < 10000)
z[i+j] = t;
else {
if (i+j+1 == N) return 1; // overflow
z[i+j+1] += t / 10000;
z[i+j] = t % 10000;
}
}
else if (x[i] && y[j]) return 1; // overflow
return 0; // no error
}
void div(int x[],int n,int z[]) {
int amari,i,bunshi; /*除算*/
amari=0; /*上位桁の余りが下位桁に加算されないとする*/
for(i=N-1;i>=0;i--) {
bunshi=amari*10000+x[i];
z[i]=bunshi/n; /*上位桁の余りが下位桁に加算されないとする*/
amari=bunshi%n; /*上位桁の余りが下位桁に加算されないとする*/
}
}
void print(int x[]) {
int i = N;
while (--i > 0 && x[i] == 0) ;
printf("%d", x[i]);
while (--i >= 0) printf(" %04d", x[i]);
}
int main(void) {
int x[N], y[N], z[N], r[N], w[N],g[N]; //x:初期数、y:x*2、z:1、r:反転数、w:y=w桁数求めよう
int i,j,k,l,count; //i,j:カウンタ、count:桁数
clear(x), /*x[4] = 11, x[3] = 1, x[2] = 95, */x[1] = 79, x[0] = 8644;
clear(z), z[0] = 1;
clear(g);
for(i = 0; i <= 5; i++) {
count = 0;
muls(x, x, y);
memcpy(w, y, N * sizeof(int));
while(memcmp(w, g, N * sizeof(int))!=0) { //桁数求め
div(w,10,w);
count++;
}
memcpy(w, y, N * sizeof(int));
if(count % 2 == 0) { //偶数かどうか
if(count%4==0) {
count=count/4-1;
}
else {
count=count/4;
}
clear(r); //反転数r初期化
for(j=count;j>=0;j--) {
for(l=0;l<4;l++) {
r[j]=w[0]%10+r[j]*10;
div(w,10,w);
}
}
k=r[0]%10;
while(k==0) {
div(r,10,r);
k=r[0]%10;
}
if(memcmp(y, r, N * sizeof(int)) == 0 ) {
print(x), printf(" の 2乗 = "), print(y),printf(" は偶数桁の回文平方数"), printf("\n");
}
}
add(x, z, x);
}
return 0;
}
Re: 多倍長演算を用いた平方数
遅くなってしまいましたが、完成しましたので解決とさせて頂きたいと思います。
皆様のおかげでなんとか完成しました、本当にありがとうございました。
h2so5さん、Suikabaさん、AKIЯAさん、boxさん、ホヅミさん、たいちうさん、GRAMさん、かずまさん
重ねて御礼申し上げます。
皆様のおかげでなんとか完成しました、本当にありがとうございました。
h2so5さん、Suikabaさん、AKIЯAさん、boxさん、ホヅミさん、たいちうさん、GRAMさん、かずまさん
重ねて御礼申し上げます。
Re: 多倍長演算を用いた平方数
本当に解決ですか?
「多倍長演算で平方数」ではなく、
「偶数桁の回文平方数」を求めるのが目的ですよね。
小さいほうから 3番目までの「偶数桁の回文平方数」は、
すぐに求まりますが、4番目は短時間では求まりません。
836 ^2 = 69 8896
79 8644 ^2 = 6378 3223 8736
6403 0648 ^2 = 4099 9238 8329 9904
次のプログラムだと、CPU とコンパイラにもよりますが、
2時間程度で 4番目の「偶数桁の回文平方数」が求まるはずです。
「多倍長演算で平方数」ではなく、
「偶数桁の回文平方数」を求めるのが目的ですよね。
小さいほうから 3番目までの「偶数桁の回文平方数」は、
すぐに求まりますが、4番目は短時間では求まりません。
836 ^2 = 69 8896
79 8644 ^2 = 6378 3223 8736
6403 0648 ^2 = 4099 9238 8329 9904
次のプログラムだと、CPU とコンパイラにもよりますが、
2時間程度で 4番目の「偶数桁の回文平方数」が求まるはずです。
#include <stdio.h>
#define N 6
int inc(int *x)
{
int i = 0;
while (i< N) {
if (++x[i] < 10000) break;
x[i] -= 10000;
if (++i == N) return 1;
}
return 0;
}
int next(int *y, const int *x)
{
int i, carry = 1;
for (i = 0; i < N; i++) {
y[i] += x[i] * 2 + carry;
carry = y[i] / 10000;
y[i] %= 10000;
}
return carry;
}
int val(const int *x, unsigned int i)
{
unsigned int j = i % 4;
i /= 4;
if (j == 0) return x[i] % 10;
if (j == 1) return x[i] / 10 % 10;
if (j == 2) return x[i] / 100 % 10;
return x[i] / 1000;
}
int even_palindromic(const int *x)
{
int i = N, j;
while (--i > 0 && x[i] == 0) ;
j = i * 4;
if (x[i] < 10) return 0;
else if (x[i] < 100) j += 2;
else if (x[i] < 1000) return 0;
else j += 4;
for (i = 0; i < --j; i++)
if (val(x, i) != val(x, j)) return 0;
return 1;
}
void print(const int *x)
{
int i = N;
while (--i > 0 && x[i] == 0) ;
printf("%d", x[i]);
while (--i >= 0) printf(" %04d", x[i]);
}
int main(void)
{
const int K = 10000000;
int k = K;
int x[N] = {0}, y[N] = {0};
long long i;
for (i = 1; i <= 1000000000000LL; i++) {
if (--k == 0) k = K, printf("%lld\r", i), fflush(stdout);
next(y, x);
inc(x);
if (even_palindromic(y))
print(x), printf(" ^2 = "), print(y), printf("\n");
}
return 0;
}