32bitについて…

32bitについて…

以前、素因数分解のプログラムについて質問させていただきました。
http://oshiete.goo.ne.jp/qa/6132983.html

int型では32bitなので、
-2147483648　～　2147483647（2^31-1）
の値までしか扱えないことは理解しました。

もし、20桁の素因数分解をしたい場合どうすればよいのですか？
long型とかですか？具体的に教えていただきたいです！！

同様に100桁でしたらどうするのでしょうか？


よろしくお願いしますm(_ _)m

No.8 回答者： Tacosan 回答日時： 2010/08/29 23:54

unsigned long long は 64ビット以上であることが確定してます＞#7.

ただし unsigned long long (や long long) は C99 じゃないと使えないことに注意.

No.7 回答者： mi65536 回答日時： 2010/08/29 19:39

１つは、GNU MP（GMPともいう）を使えばいい。

後は多倍長整数を自作。


ただ...

b[bit]の非負整数で表現できる10進整数の最大桁数kは？

k=log10(2^b-1)+1≒b*log10(2)+1≒0.30103*b+1.

k=20 ならば、b≒63.11≦64.

これなら、unsigned long long が64bit なら、使える！！
以上。

#素数だから、負数なんていらないでしょ。

No.6 回答者： _--_1l1_1_ 回答日時： 2010/08/27 19:36

すでに書かれているとおり、数字を

struct num {
　　unsigned char sign;
　　unsigned char num[N];
}
などで表現して、この構造体に対して加減乗除を関数で作ります。
多倍長演算や任意精度演算などで検索して下さい。

No.5 回答者： hashioogi 回答日時： 2010/08/27 09:24

以下にvcで作成した、c++の演算子の多重定義を利用した符号なしの128ビット整数（リトルエンディアン）の加算(+)のプログラムを示します。

これを参考に関数を増やしたりコードを改良すれば符号付きの128ビットの加算もできるだろうし、乗算、除算、++、--、+=、/=等のc言語で定義されている多くの演算子も利用できるようになるし、ビット数だってあなたが希望するだけのビット数（100ビットだろうが10000ビットだろうが）にできます。

演算子の多重定義の良いところは、今まであなたが作成してきた32ビットの因数分解やら何やらのソースプログラムをあまり変更することなく、例えば今までint a ;としてきたところをuint128 a ;に書き換えるだけでc=a+b;の部分は変更させずに動作させることができる点です。

#include "stdafx.h"

class uint128 {
public :
unsigned charv [16] ;

uint128 ()
{
inti ;
for (i=0 ; i<16 ; i++)
{
v [i] = 0 ;
}
}

const friend uint128 operator + (const uint128 &x, const uint128 &y)
{
uint128w ;
inti ;
shortkuriage = 0 ;

for (i=15 ; i>=0 ; i--)
{
kuriage = x.v [i] + y.v [i] + kuriage ;

w.v [i] = kuriage ;

kuriage >>= 8 ;
}

return w ;
}
} ;

int _tmain(int argc, _TCHAR* argv[])
{
uint128a ;
uint128b ;
uint128c ;
inti ;

a.v [14] = 0x01 ;
a.v [15] = 0x02 ;

b.v [13] = 0x05 ;
b.v [14] = 0x06 ;
b.v [15] = 0x07 ;

c = a + b ;

for (i=0 ; i<16 ; i++)
{
printf ("%02x ", c.v [i]) ;
}

return 0 ;
}

No.4 回答者： Tacosan 回答日時： 2010/08/27 00:01

暗号な人だと「10進 100桁」は小さいと思うかもしれない＞#3. SHA シリーズでも 512bit とかあるし, RSA なら 1024bit とか 2048bit とかある.

本題に入ると, まあ「int がたとえば 4096bit」とかいう処理系を使えばいいんだけど, そんな処理系があるとは思えないので「多倍長演算」を駆使するんでしょうねぇ.

No.3 回答者： Tasuke22 回答日時： 2010/08/26 22:35

既存のアルゴリズムを利用するか、自分で発明するかでしょうね。

私なら自分で発明したい。結果が既存のものと同じになっても、です。

ただ、100桁というと10の100乗です。実際問題としてこの世にない
数字です。
大きな数字の代表として「天文学的数字」と言われますが、私が知っ
ている限りでは全宇宙の素粒子の数が10の74乗個である、というのが
聞いた中では最も大きな数字です。

手段だけに囚われないで、目的をはっきりさせる必用はありそうですね。
この世にない数字でも、どんな数字でも全て扱いたい、とかであれば、
それこそご自分でアルゴリズムを考えるべきでしょう。
それがプログラマの醍醐味と思います。

例えば、パイをどこまで計算できるか、というチャレンジをしている人が
いますが、スーパーコンピュータを使っても限られた予算で限られた
時間内で計算をしなければなりませんが、そのアルゴリズムは研究者の
発明です。

No.2 回答者： kmee 回答日時： 2010/08/26 21:37

Visual C++等、多くの処理系ではlongは32bitです。

64bitは long long int とか int64_t とかになっていることがあります。これも処理系依存の話です。

それ以上に大きなものの場合、それだけの大きさに対応した「入れ物」と「演算」を自分で用意するか、既存のライブラリを使用します。
http://ja.wikipedia.org/wiki/%E4%BB%BB%E6%84%8F% …

原理としては、適当な桁で区切って配列に入れて、手計算での筆算のようにして演算します。


C言語と実行時間にこだわりが無ければ、整数が無限桁になっている言語(Python,Ruby等)を使うのが楽です。

No.1 回答者： koi1234 回答日時： 2010/08/26 20:58

そもそも100桁のデータを一つの型で扱うことなど出来ませんから

一定の桁ごと（各データ型で扱える桁）に自分で分割
分割したデータ間の処理も含めてプログラム作るしかありません