多倍長演算を用いた平方数

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
kaikai

多倍長演算を用いた平方数

#1

投稿記事 by kaikai » 11年前

初めてこちらを利用させて頂きます。至らない点などはご指摘頂ければと思います。

件名通り、多倍長演算を用いた平方数を表示させたいのですが、プログラムの流れとしてはfor文で1~任意の数までを二乗して、表示するといった形にしたいのですが、どのように書けばよいのかわからずご相談させて頂きました。

AKIЯA
記事: 58
登録日時: 11年前

Re: 多倍長演算を用いた平方数

#2

投稿記事 by AKIЯA » 11年前

文章をそのまま受け取ります。
任意の文字を10にしてあります。
► スポイラーを表示
最後に編集したユーザー AKIЯA on 2012年11月02日(金) 18:37 [ 編集 1 回目 ]

アバター
h2so5
副管理人
記事: 2212
登録日時: 13年前
住所: 東京
連絡を取る:

Re: 多倍長演算を用いた平方数

#3

投稿記事 by h2so5 » 11年前

>> kaikaiさん
まずはフォーラムルールをお読みください。

>> AKIЯAさん
それを多倍長演算とは言いません。

Suikaba
記事: 194
登録日時: 13年前

Re: 多倍長演算を用いた平方数

#4

投稿記事 by Suikaba » 11年前

あと、void mainではなくint main()またはint main( int argc, char* argv[] )でお願いします。
細かいですがw

AKIЯA
記事: 58
登録日時: 11年前

Re: 多倍長演算を用いた平方数

#5

投稿記事 by AKIЯA » 11年前

こんなの1から作るのは面倒だ

http://katahiromz.web.fc2.com/c/bigfact2.html

box
記事: 2002
登録日時: 13年前

Re: 多倍長演算を用いた平方数

#6

投稿記事 by box » 11年前

AKIЯA さんが書きました:文章をそのまま受け取ります。
その結果がそのコードっていうのはちょっとなぁ…。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

AKIЯA
記事: 58
登録日時: 11年前

Re: 多倍長演算を用いた平方数

#7

投稿記事 by AKIЯA » 11年前

プログラムの流れとしてはfor文で1~任意の数までを二乗して、表示する
ここしか見てなかったwww

AKIЯA
記事: 58
登録日時: 11年前

Re: 多倍長演算を用いた平方数

#8

投稿記事 by AKIЯA » 11年前

なのでURLを投げました。

ホヅミ
記事: 110
登録日時: 13年前

Re: 多倍長演算を用いた平方数

#9

投稿記事 by ホヅミ » 11年前

それっぽいサンプルコードなら見つけましたよ。
http://www5.airnet.ne.jp/tomy/cpro/csource.htm

kaikai

Re: 多倍長演算を用いた平方数

#10

投稿記事 by kaikai » 11年前

フォーラムルールも読まず失礼しました。
プログラム暦は大学で学ぶ基礎的なものを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[])  
{


}
}

 
まず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には桁上がりを入れる。
という文を書きたいのですが。

kaikai

Re: 多倍長演算を用いた平方数

#11

投稿記事 by kaikai » 11年前

AKIЯAさん
ホヅミさん
リンクありがとうございます。

コード:

#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;がおかしいと思うのですが、どのようにすれば良いかお知恵を拝借させてください。

AKIЯA
記事: 58
登録日時: 11年前

Re: 多倍長演算を用いた平方数

#12

投稿記事 by AKIЯA » 11年前

19行目と39行目と10行目の引数の数があっていませんのでエラー原因はそこかと思います。

たいちう
記事: 418
登録日時: 13年前

Re: 多倍長演算を用いた平方数

#13

投稿記事 by たいちう » 11年前

AKIЯAさん

> プログラムの流れとしてはfor文で1~任意の数までを二乗して、表示する
> ここしか見てなかったwww

任意の数まで処理してないです。


kaikaiさん

> エラー E2193 a.c 19: 呼び出し時のパラメータが足りない:muls(関数 main )

mulsは引数が2つ必要という事です。

x[0]=i;
muls(x, ans);

kaikai

Re: 多倍長演算を用いた平方数

#14

投稿記事 by kaikai » 11年前

AKIЯAさん
たいちうさん
お早いお返事ありがとうございます。無事プログラムは動きました。

目標自体にはまだ届いていないので、質問すると思いますが、またお時間がありましたらお願い致します。

たいちう
記事: 418
登録日時: 13年前

Re: 多倍長演算を用いた平方数

#15

投稿記事 by たいちう » 11年前

> 目標自体にはまだ届いていないので、質問すると思いますが、またお時間がありましたらお願い致します。

そうですね。コンパイルエラーが取れただけです。
99までの自乗ならば多倍長は必要ないので正しい答えになっていますが、
関数muls()は、2重のforループになるはずですよ。(1重で書けないこともないけど)

アバター
GRAM
記事: 164
登録日時: 13年前
住所: 大阪

Re: 多倍長演算を用いた平方数

#16

投稿記事 by GRAM » 11年前

ぶっちゃけ誰かが絶対言うだろうと思ってたのですが、
そもそも質問に対する突込みって違いますよね。

「多倍長が必要になるところまで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;
}
BigInteger.hの中身(閲覧注意;非常に読む気のうせるコードが記載されております。)
BigInteger.txt
(20.34 KiB) ダウンロード数: 201 回
(コードとして書くと記事が表示されなくなるバグがあるようでしたので添付ファイルにしました)

また後からboostを使用していることに気が付いたため、導入されていないかもと思い実行ファイルも添付しておきますが、
単純に入力値の2乗を表示するだけのプログラムにしてあります。
添付ファイル
ctest.zip
(17.35 KiB) ダウンロード数: 125 回

kaikai

Re: 多倍長演算を用いた平方数

#17

投稿記事 by kaikai » 11年前

たいちうさん
ありがとうございました。for2回というのは、自分の方向性があってると再確認できました。

GRAMさん
最終的に表示するのは条件付けを幾つかするので減るのですが、まだ今の段階ですら出来てないので少しずつ進めようと思っております。

ご指摘、ありがとうございます 。

かずま

Re: 多倍長演算を用いた平方数

#18

投稿記事 by かずま » 11年前

任意の数ってどこまで? とりあえず 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: 多倍長演算を用いた平方数

#19

投稿記事 by かずま » 11年前

かずま さんが書きました:任意の数ってどこまで? とりあえず 100桁までなら。
s が固定長で、x と y を動的に確保してもあまり意味がありませんね。
ということで、全部固定にしてみました。今度は 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;
}

kaikai

Re: 多倍長演算を用いた平方数

#20

投稿記事 by kaikai » 11年前

かずまさん
わざわざ2度も書き込みをいただきありがとうございます。

任意桁はまだプログラミングすら未完成なので、出来る所まで調べてみたいと曖昧な目標です。
乗せて頂いたプログラミングは是非参考にさせてもらいます。

kaikai

Re: 多倍長演算を用いた平方数

#21

投稿記事 by kaikai » 11年前

多倍長についてある程度出来ましたので、回文である、偶数桁である。
この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で割り切れれば偶数桁。

自分が考えたのは以上です。他にも考え方があれば是非御教え頂きたい。

たいちう
記事: 418
登録日時: 13年前

Re: 多倍長演算を用いた平方数

#22

投稿記事 by たいちう » 11年前

回文も偶数桁も、案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" と表示される

kaikai

Re: 多倍長演算を用いた平方数

#23

投稿記事 by kaikai » 11年前

コード:

/*多倍長*/
#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は、他の処理方法は無いか。です

宜しければご意見下さい。また文章でおかしい点・伝わらない点などございましたらご指摘頂けると幸いです。

たいちう
記事: 418
登録日時: 13年前

Re: 多倍長演算を用いた平方数

#24

投稿記事 by たいちう » 11年前

コード:

zを初期化;
for (i = 0; i < N; i++) {
	for (j = 0; j < N; j++) {
		z[i + j] += x[i] * y[j];
		zの繰り上がり処理;
	}
}
大体こんなイメージですが、伝わるでしょうか。
繰り上がりは連鎖的に起きる可能性もあるので、注意してください。
例)9999 9999 + 0000 0001 -> 1 0000 0000

かずま

Re: 多倍長演算を用いた平方数

#25

投稿記事 by かずま » 11年前

質問内容がよく理解できません。
気がついたことを書いてみます。

コード:

#define N 8        //配列数

int x[N+1]={0000,0000,0000,0000,0000,0000,0000,0000,0001};
とありますから、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: 多倍長演算を用いた平方数

#26

投稿記事 by かずま » 11年前

かずま さんが書きました:なお、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");
修正は簡単なんですが、それだけでは面白くないので、w[N * 2] と
いう余計な領域を使わないように 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
}

kaikai

Re: 多倍長演算を用いた平方数

#27

投稿記事 by kaikai » 11年前

遅ればせながら、あけましておめでとうございます
たいちうさん、かずまさん御返信ありがとうございます。

かずまさん、分かりにくくて申し訳ありません。
add()に関しては間違いに気づかずそのまま乗せてしまいました。修正し正常に結果が出るので問題無いと思います。

以前の質問の内容はご指摘のあった、muls()のz0[N+1]~z8[N+1]の宣言と処理を簡潔にできないかというものでしたので、乗せて頂いたプログラムがとても参考になります。

また平方数の表示も私のように大量に0を出す必要がなく、とてもわかりやすいプログラムでしたので、参考になります。本当にありがとうございます。

kaikai

Re: 多倍長演算を用いた平方数

#28

投稿記事 by kaikai » 11年前

以前かずまさんよりプログラムを頂き、多倍長整数の平方数の偶数桁までは検索できるようになりました。
今回は回文を求める処理について意見を頂きたく。

今回お聞きしたいのは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);
            }
         }
このままではr[]の中身は r [1] [0]
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;
}

たいちう
記事: 418
登録日時: 13年前

Re: 多倍長演算を用いた平方数

#29

投稿記事 by たいちう » 11年前

> 今回お聞きしたいのは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;
  ...
}

kaikai

Re: 多倍長演算を用いた平方数

#30

投稿記事 by kaikai » 11年前

たいちうさん、返信ありがとうございます。
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: 多倍長演算を用いた平方数

#31

投稿記事 by かずま » 11年前

配列の要素数は、#define N 9 で、一要素に 10進 4桁を
収納するので、全部で 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;
}

kaikai

Re: 多倍長演算を用いた平方数

#32

投稿記事 by kaikai » 11年前

かずまさん、返信ありがとうございます。
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;
}

kaikai

Re: 多倍長演算を用いた平方数

#33

投稿記事 by kaikai » 11年前

遅くなってしまいましたが、完成しましたので解決とさせて頂きたいと思います。

皆様のおかげでなんとか完成しました、本当にありがとうございました。

h2so5さん、Suikabaさん、AKIЯAさん、boxさん、ホヅミさん、たいちうさん、GRAMさん、かずまさん
重ねて御礼申し上げます。

かずま

Re: 多倍長演算を用いた平方数

#34

投稿記事 by かずま » 11年前

本当に解決ですか?

「多倍長演算で平方数」ではなく、
「偶数桁の回文平方数」を求めるのが目的ですよね。

小さいほうから 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;
}

かずま

Re: 多倍長演算を用いた平方数

#35

投稿記事 by かずま » 11年前

4番目は、
831 6311 5486 ^2 = 69 1610 3777 3377 7301 6196

閉鎖

“C言語何でも質問掲示板” へ戻る