プログラマ専用SNS ミクプラ

いつもお世話になっています。

今日はboostの多倍長整数演算に絡んだ質問を使用と思います。

三角数と平方数が等しい時にその値を出力するようなプログラムを書いたのですが、動作がつかめなくて困っています。

具体的には、入力が10000までは正常に動くのですが、100000になると何も表示されなくなります。1000000はコアダンプになります。
sizeof(int)で確認したところ、32bitだったので入力は4294967296までは問題無いはずです。

また、main関数内でコメントアウトしているif処理のところに関して、bisearchではちゃんと1を返しているのにも関わらず、ちゃんと値をcoutしない(なぜか36だけ出力する)状態です。とりあえずbisearch内で出力するように変更したので、問題ないと思ったのですが、今度は冒頭の問題が発生しました。

mp::cpp_int型で比較演算が可能なことは検証してありますし、何が問題なのか自分では全く分かりません。
どうかご助力お願いします。

コード:

#include<iostream>
#include<boost/multiprecision/cpp_int.hpp>

namespace mp=boost::multiprecision;

int bisearch(mp::cpp_int *b,mp::cpp_int tar,int s,int e)
{
	int m=(s+e)/2;
/*
std::cout<<"--------------------"<<std::endl;
std::cout<<tar<<","<<b[m]<<std::endl;
std::cout<<"--------------------"<<std::endl;
*/

	if(tar==b[m])
	{
		std::cout<<"@"<<std::endl;
		std::cout<<tar<<std::endl;

		return 1;

	}
	else if(s<m)
	{
		if(b[m]<tar)
		{
			bisearch(b,tar,m+1,e);
		}
		else
		{
			bisearch(b,tar,s,m);
		}
	}
	else
	{
		return 0;
	}
}


int main()
{
	int i;
	int n;
	std::cin>>n;
	mp::cpp_int a[n+1],b[n+1];

	for(i=1;i<=n;i++)
	{
		a[i]=i*i;
		b[i]=i*(i+1)/2;
	}

	for(i=1;i<=n;i++)
	{
// 	std::cout<<a[i]<<std::endl;

		bisearch(b,a[i],i,n);
		/*
		if(bisearch(b,a[i],i,n)==1)
		{
			std::cout<<a[i]<<std::endl;
		}
		*/
	}	
	return 0;
}

chop.chop さんが書きました:具体的には、入力が10000までは正常に動くのですが、100000になると何も表示されなくなります。1000000はコアダンプになります。
sizeof(int)で確認したところ、32bitだったので入力は4294967296までは問題無いはずです。

100000*100000は4294967296より大きいので、50行目などでオーバーフローを起こし、未定義動作になるかもしれません。
未定義動作で変なこと(ランタイムエラー、爆発、ミサイル発射など)にならなくても、データが昇順にならず、bisearch関数の入力として適さなくなるかもしれません。
また、Wandboxで

コード:

#include<iostream>
#include <cstdio>

int main()
{
	int n;
	std::cin>>n;
	printf("%p\n",&n);
	int a[n+1];
	printf("%p\n",a);
	int* test = new int;
	printf("%p\n",test);
	delete test;
	return 0;
}

というコードを入力1で実行したところ、

コード:

0x7ffda624ea24
0x7ffda624ea10
0x2120570

という出力が得られました。
aのアドレスがnewで確保した領域のアドレスよりローカル自動変数nのアドレスに近いので、
aはスタック領域に確保されていると予想できます。
したがって、コアダンプの原因はスタックオーバーフローであると予想できます。
a, bを動的配列(?)ではなく、素直にnew[]で確保してみてください。

chop.chop さんが書きました:また、main関数内でコメントアウトしているif処理のところに関して、bisearchではちゃんと1を返しているのにも関わらず、ちゃんと値をcoutしない(なぜか36だけ出力する)状態です。

入力10000のとき、Wandboxでは36も含めて何も出力が出ませんでした。
警告にある通り、bisearch関数でtar!=b[m] && s<mのときreturn文が実行されないのがまずそうだと思います。
27行目と31行目の直前にreturnを追加するべきではないでしょうか？

>>みけCATさん

いつもありがとうございます。

みけCAT さんが書きました: aのアドレスがnewで確保した領域のアドレスよりローカル自動変数nのアドレスに近いので、
aはスタック領域に確保されていると予想できます。
したがって、コアダンプの原因はスタックオーバーフローであると予想できます。
a, bを動的配列(?)ではなく、素直にnew[]で確保してみてください。

このテクニックは眼から鱗です…(単に私の経験不足もありますが)。そういえばスタック領域というものがあってこれを使い潰す場合もある、というのを授業でやったことを思い出しました。すごく腑に落ちました。
これからはアドレス確認のテクニックは活用させてもらいます。

みけCAT さんが書きました: 警告にある通り、bisearch関数でtar!=b[m] && s<mのときreturn文が実行されないのがまずそうだと思います。
27行目と31行目の直前にreturnを追加するべきではないでしょうか？

ご指摘の通りでした。mainから呼ばれるbisearchが1を返すためには、bisearchの中でtar!=b[m]の場合に呼ばれるbisearchが1を返さないとブツぎりになってしまうわけですね。

非常に良い勉強になりました。ありがとうございました！

コード:

#include<iostream>
#include<boost/multiprecision/cpp_int.hpp>

namespace mp=boost::multiprecision;

int bisearch(mp::cpp_int *b,mp::cpp_int tar,unsigned long long int s,unsigned long long int e)
{
	unsigned long long int m=(s+e)/2;
/*
std::cout<<"--------------------"<<std::endl;
std::cout<<tar<<","<<b[m]<<std::endl;
std::cout<<"--------------------"<<std::endl;
*/

	if(tar== b[m])
	{
		//std::cout<<tar<<std::endl;
		return 1;

	}
	else if(s<m)
	{
		if(b[m]<tar)
		{
			return bisearch(b,tar,m+1,e);
			
		}
		else
		{
			return bisearch(b,tar,s,m);
		}
	}
	else
	{
		return 0;
	}
}


int main()
{
	unsigned long long int i;
	unsigned long long int n;
	std::cin>>n;
	mp::cpp_int *a=new mp::cpp_int[n+1];
	mp::cpp_int *b=new mp::cpp_int[n+1];

std::cout<<b<<","<<a<<","<<&n<<std::endl;

	for(i=1;i<=n;i++)
	{
		a[i]=i*i;
		b[i]=i*(i+1)/2;
	}

	for(i=1;i<=n;i++)
	{
// 	std::cout<<a[i]<<std::endl;

		bisearch(b,a[i],i,n);
		
		if(bisearch(b,a[i],i,n)==1)
		{
			std::cout<<a[i]<<std::endl;
		}
		
	}

	delete[] a;
	delete[] b;
	return 0;
}

追記:
始めはインデックスもmp::cpp_intで宣言しようとしましたが、これ配列のインデックスとしては使えないんですね……多倍長は初めて弄ったのでいろいろ経験出来ました

プログラマ専用SNS ミクプラ

<boost/multiprecision/cpp_int.hpp>

<boost/multiprecision/cpp_int.hpp>

Re: <boost/multiprecision/cpp_int.hpp>

Re: <boost/multiprecision/cpp_int.hpp>