32bitについて…

質問

32bitについて…

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

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

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

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

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

回答No.8

Tacosan

unsigned long long は 64ビット以上であることが確定してます＞#7.
ただし unsigned long long (や long long) は C99 じゃないと使えないことに注意.

回答No.7

mi65536

１つは、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_

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

回答No.5

hashioogi

以下にvcで作成した、c++の演算子の多重定義を利用した符号なしの128ビット整数（リトルエンディアン）の加算(+)のプログラムを示します。
これを参考に関数を増やしたりコードを改良すれば符号付きの128ビットの加算もできるだろうし、乗算、除算、++、--、+=、/=等のc言語で定義されている多くの演算子も利用できるようになるし、ビット数だってあなたが希望するだけのビット数（100ビットだろうが10000ビットだろうが）にできます。

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

#include "stdafx.h"

class uint128 {
public :
unsigned char v [16] ;

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

const friend uint128 operator + (const uint128 &x, const uint128 &y)
{
uint128 w ;
int i ;
short kuriage = 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[])
{
uint128 a ;
uint128 b ;
uint128 c ;
int i ;

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

暗号な人だと「10進 100桁」は小さいと思うかもしれない＞#3. SHA シリーズでも 512bit とかあるし, RSA なら 1024bit とか 2048bit とかある.
本題に入ると, まあ「int がたとえば 4096bit」とかいう処理系を使えばいいんだけど, そんな処理系があるとは思えないので「多倍長演算」を駆使するんでしょうねぇ.

回答No.3

Tasuke22

既存のアルゴリズムを利用するか、自分で発明するかでしょうね。
私なら自分で発明したい。結果が既存のものと同じになっても、です。

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

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

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

回答No.2

kmee

Visual C++等、多くの処理系ではlongは32bitです。
64bitは long long int とか int64_t とかになっていることがあります。これも処理系依存の話です。

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

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

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

回答No.1

koi1234

そもそも100桁のデータを一つの型で扱うことなど出来ませんから
一定の桁ごと（各データ型で扱える桁）に自分で分割
分割したデータ間の処理も含めてプログラム作るしかありません