トップページ⇒tech
237コメント73KB

C++の機能だけで多倍長計算を考えるスレ

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさんNGNG
C++の機能だけで多倍長計算を考え。
0153146NGNG
>>151
RSA暗号に利用する予定なので、x, y, nは正整数限定なんです・・・

>>152
二進展開を厳密に知らないのでなんともいえないのですが、
x, y, nは、unsigned short（16bit）の配列にして扱ってます。
（つまり、65536進数です）これを二進展開というのでしょうか？
0154デフォルトの名無しさんNGNG
>>146
二進展開っていうのはこういうやつ。関係ないのかな？
typedef unsigned long int uint32;

uint32 modplus(uint32 a, uint32 b, uint32 m){
return (a > m - b)? a - (m - b): a + b;
}

uint32 modby(uint32 a, uint32 b, uint32 m){
uint32 sum;
for(sum = 0; b > 0; a = modplus(a, a, m), b >>= 1)
if(b & 1) sum = modplus(sum, a, m);
return sum;
}

uint32 modpow(uint32 a, uint32 k, uint32 m){
uint32 b;
for(b = 1; k > 0; a = modby(a, a, m), k >>= 1)
if(k & 1) b = modby(b, a, m);
return b;
}
0155146NGNG
>>154
二進展開では、数値を全て法mで還元された状態で表現するようですね、
確か似たようなやり方にRNS表現があったと思いますけど、それとは違うのですか？
0156デフォルトの名無しさんNGNG
なるほど。違うみたいね。
http://www.google.co.jp/search?q=cache:DcfJc-wJCOEC:www.toshiba.co.jp/tech/review/2001/07/56_07pdf/a04.pdf+rns%E8%A1%A8%E7%8F%BE&hl=ja&ie=UTF-8
0157デフォルトの名無しさんNGNG
>>153
　ああ、て事は せいぜい100桁程度？　で x,y,nは同じくらいの桁数なんでしょ？

なら FFT使えば多少速くなるかな でも　モンゴメリ法とやらはとは関係ないか
0158146NGNG
>>153
桁数は大体そのぐらいですね、もう少し多くなりますけど。
モンゴメリが無理そうなら、FFTを試してみます。
（諦める気はありませんが）

皆さん有難うございました、もう少し自分で考えてみます。
0159146NGNG
ミスった↑
>>153は>>157の間違いです・・・
0160デフォルトの名無しさんNGNG
この前VC+のテスト代わりに作ってみたけど、わかったこと。
「2進より10進パックの方が絶対楽」
0161デフォルトの名無しさんNGNG
10進パックって COBOL の？ 16進数ダンプすれば数に見える方法？

それならまだ100進数の方が楽だと思うけど
0162山崎渉NGNG
（＾＾）
0163山崎渉NGNG
　　 ∧＿∧
　　（　　＾＾ ）＜ ぬるぽ（＾＾）
0164 ◆y3A2MadQ16 NGNG
>160-161
速度・記憶効率のこと考えないならその方がいい。
ま、数式処理とかのコアに使うんでなく、
従来からBCDが使われているように国家予算スケールの加減乗除くらいなら
速さ・記憶領域的にもそれほどは気にならないかも。
0165デフォルトの名無しさんNGNG
保守。
0166デフォルトの名無しさんNGNG
>>165
終了ぽ？
0167デフォルトの名無しさんNGNG
多倍長の四則演算が基本型の変数と同じように自然にできて、
VC++からも簡易に使えるライブラリは一つくらいあるだろう、と思っていたら
適当なものが無い。

http://www.nitoyon.com/vc/tips/multi_precision.htm
みたいにシンプルな機能が良いけれど、これは実現法が似非で桁精度が出ない。

あとは演算子をオーバーロードせず関数で演算させる古めかしい方法や、やたら
規模が大きくて組込むのに躊躇してしまうものばかり。

英語ソースを探そうと考えているが、多倍長演算を英語では一般に何と言うのだろう？
0168デフォルトの名無しさんNGNG
>>160
数百桁の除算やpowmodをやらせようとすると
10進パックで実用的速度を出させるのは大変なこと。
256進数や65536進数など2の羃乗数でやれば
一晩で起こした簡易スクラッチでも
ある程度実用的速度にできるからおすすめ。
0169デフォルトの名無しさんNGNG
>>167
multi precision arithmeticsとかかねぇ。
0170山崎渉NGNG
　　　 　∧＿∧
ﾋﾟｭ.ｰ　(　　＾＾ ） ＜これからも僕を応援して下さいね（＾＾）。
　　＝〔~∪￣￣〕
　　＝ ◎――◎ 　　　　　　　　　　　　　　　　　　　　　山崎渉
0171デフォルトの名無しさんNGNG
>>170
むしろこの過疎スレを応援してくれｗ。
0172デフォルトの名無しさんNGNG
ヒッソリと保守。
0173デフォルトの名無しさんNGNG
>>168
むしろ100進・万進が実用的だと思うよ。
デバックも楽だし、加算減算ですぐにオーバフローしないから桁上がり処理も楽で速い
0174デフォルトの名無しさんNGNG
↓なにこのページ…(*´д｀)ﾊｧﾊｧ
http://3.141592653589793238462643383279502884197169399375105820974944592.jp/

誰か全部受信して何桁あるか報告きぼん。
0175デフォルトの名無しさんNGNG
>>174
add(30781)
までそらでいえる。
0176デフォルトの名無しさんNGNG
>174
20MB落としてもダウソが終わらないので途中でやめた
0177デフォルトの名無しさんNGNG
そのページってhtmlなのかな？
要求受けてから計算してたｒ何処までも逝くかも。
0178デフォルトの名無しさんNGNG
>>176
ﾏﾁﾞかよ
0179デフォルトの名無しさんNGNG
>>174
よく見つけた―ね
0180デフォルトの名無しさんNGNG
HTTP/1.1 200 OK
Date: Mon, 9 Jun 2003 10:11:47 GMT
Server: Pi-Server/0.1 (Unix)
Connection: close
Content-Type: text/html

だってさ。
0181デフォルトの名無しさんNGNG
>>176
前聞いたとき200Mくらいあると聞いた。
0182デフォルトの名無しさんNGNG
>>174
Googleのキャッシュは101302桁でつた。
0183デフォルトの名無しさんNGNG
>>173
一桁当たりの桁上がり処理の早い、遅いは機械語レベルでどうなるかってくらいの話だからなぁ。
一桁が2のべき乗ならビット論理演算、
ワード幅一杯まで使うときはＣＰＵのフラグとか見るわけ（高級言語ではムリだが）で…。
これが10進だと引き算（比較演算）とかでやることになるだろう？
ビット演算なら引き算と大差ないし、フラグが見られれば追加の演算無しで直接分岐できる。

ちなみに、一桁にできるだけ大きな数をつめたほうが桁数が減って記憶領域とループの回数は減る。
デバッグは一度やれば終わりだし、整数の加減程度ならそんなに大変って程でもないよ。
（乗除は効率よく計算するのは基数がいくつでもどのみち大変だしｗ。）

ところで、そういや記憶階層を意識した最適化とかした例はあるのかな？
0184デフォルトの名無しさんNGNG
そうかい？ ワード一杯まで使うとアセンブラ使わないと厳しいわけで、C++の機能だけでって訳にゆかないでしょ？

もちろんcだけでも無理すりゃできるけど、効率が悪いコードになる。
0185デフォルトの名無しさんNGNG
２のべき乗進数でつくった多倍長整数を１０進数で表示するのが大変。
0186デフォルトの名無しさんNGNG
それはあるよね。　
コードは大変って事はないけど、処理が重くなる。
デバッカでメモリイメージ見た時に簡単にチェック出来ないし
0187デフォルトの名無しさんNGNG
あ、でも、多倍長加算をcで無理してやる方法は２つあるんだけど、結構頭の体操的で面白いよ。

もちろんそれより長いレジスタにキャストしてってのはナシで

一つは計算前と計算後とで比較判断を組み合わせる方法
もう一つは論理演算を組み合わせる方法
0188デフォルトの名無しさんNGNG
>>184
まぁ、確かに「Ｃ＋＋の機能だけ」という限定下ではそうなんだけどね。
でもその前提を守ることは速度と保守性のトレードオフですなぁ。
最適化が頑張って同等のコードを吐けるように助ける手立てとかは無いもんかね。

>>185-186
用途にも拠るが表示は実行回数が少ないから演算より多少遅くても割とＯＫなんでは？
デバッガでの表示に関しては多倍長数に限らないような。

>>187
加算はまだしも乗算がかなり悩ましくないですか?
0189デフォルトの名無しさんNGNG
RSA等の暗号を使いたいのですが、
__int64の64bit程度じゃ実用になりませんか？
0190デフォルトの名無しさんNGNG
>>189
君の実用的の定義をくれたまえ。
0191デフォルトの名無しさんNGNG
>>190
極秘の伝達（今夜飲みにいかない〜？）とかがバレないレベルです。
0192デフォルトの名無しさんNGNG
>>187
掛算はCPUの掛算命令使わないとやっぱり速度出ないんだけど、
C++だけでやるなら、やっぱり100進万進の方が楽だな
0193デフォルトの名無しさんNGNG
>>192
CPUの乗算命令を使わないとしても
ヒトケタに収容できる数を大きくすると、桁数が減るので
速度効率とメモリ効率の改善に対してリニアに効くんですがね。
桁あふれの判定と10進変換をカプセル化してあれば、
それ以外の計算アルゴリズム自身は何進だろうが大して変わらないし。

100万進で楽できることってデバッグくらいでしょ。
それで楽できる分は大したことはないと思うから私はやらないだろうと思うけど。
ま、どうしても未練があるなら100万進で書き上げて
デバッグがあらかた終わったらヒトケタのサイズを変更すると言う手もないことはない。
0194デフォルトの名無しさんNGNG
リニアに効くと言っても、
16bitで 10000進数でも同じだけど　8bit マシンで 100進法と
バイナリの比較を考えると　メモリ効率については log(100)/log(2) : 8 = で17%悪化する。
17%の差を大きいかどうかだけど、そんなに必死になる程のレベルじゃない。

掛算の場合、フルビットを使ってしまうと桁上がりをその都度やらなければいけなくなる
FF*FF=FE01 でFE01 でこれを中間レジスタに足すとまた上の桁にキャリーが上がってゆく可能性があり
ループが複雑になる。

99*99=9801 ならば 桁上がりがあっても、とりあえず加算したままにしておいて、１ループ終わってから処理出来る
もちろんここらへんアセンブラで書けばそれでもフルビットを使った方に軍配が上がるけど
普通にCで書くと、たぶん速度的には100進や万進の方が早くなったように思う。

まあ、中にはそれでもCレベルでもフルビット使った方が早く書ける奴もいるかもしれないが
0195デフォルトの名無しさんNGNG
>>194
なんで今時わざわざ8ビット話かわからんが…。
まぁ17%が許容できるかどうかは>>1の「C++/Cだけで」という前提が
どういう理由で出てきたかに拠るんだけどね。
それがハッキリすればマシン・コードをどの程度避けねばならないかもハッキリするわけで。
極端な話、学校の宿題レベルなら頑張ってチューニングするより
手っ取り早く動くものが出来上がるほうがいいわけだしね。
0196デフォルトの名無しさんNGNG
じゃあさ、100進と　フルビットでそれぞれ

a[n] × b[m ] -> w[n+m]

for(int mm = 0 ; mm < m ; mm++) {
　for(int nn = 0 ; nn < n; nn++){
//　　ここを埋めてみて
　}
//　　ここも必要なら
}
0197デフォルトの名無しさんNGNG
なお、 (long)a[nn] * (long)b[mm] は計算結果がちゃんと収まるものとして
0198デフォルトの名無しさんNGNG
ごめん long -> unsigned long
0199デフォルトの名無しさんNGNG
>>196-198
まず餅つけ。で、順番にナニがいいたいのか整理してみれ。
0200デフォルトの名無しさんNGNG
保守。
0201山崎 渉NGNG

　__∧＿∧_
　|（　　＾＾ ）|　＜寝るぽ（＾＾）
　|＼⌒⌒⌒＼
　＼ |⌒⌒⌒~|　　　　　　　　　山崎渉
　　 ~￣￣￣￣
0202山崎 渉NGNG

　__∧＿∧_
　|（　　＾＾ ）|　＜寝るぽ（＾＾）
　|＼⌒⌒⌒＼
　＼ |⌒⌒⌒~|　　　　　　　　　山崎渉
　　 ~￣￣￣￣
0203デフォルトの名無しさんNGNG
>>196-198

もちついた？
続きキボンにゅ。

山崎に保守されてるようなこの状況はなぁｗ。
0204デフォルトの名無しさんNGNG
ﾎｼｭ。
0205山崎 渉NGNG
（＾＾）
0206山崎 渉NGNG
　　　 (⌒V⌒)
　　　│ ＾ ＾ │＜これからも僕を応援して下さいね（＾＾）。
　　⊂|　　　　|つ
　　　（＿）（＿）　　　　　　　　　　　　　　　　　　　　　　山崎パン
0207デフォルトの名無しさんNGNG
実は今書いてる。
乗算をFFTでやって、テンプレート･メタ･プログラミングで記憶階層毎の最適化対応の奴。
一応、プロファイル・ベースで自動チューニングまで考えているんだが…。

…だが単なるFFTのプログラミングとデバッグで1週間も掛かった…このペースではダメぽ。
0208デフォルトの名無しさんNGNG
保守。
0209デフォルトの名無しさんNGNG
だれだsageで保守してるやつは
0210デフォルトの名無しさんNGNG
ほしゅ
0211デフォルトの名無しさんNGNG
募集
02121NGNG
保守
02131NGNG
ホシュ
0214デフォルトの名無しさんNGNG
実はboostのsandboxにbigintクラスがあるぞ
なんで正式版に入らないのかはわからないが
0215デフォルトの名無しさんNGNG
じぃえぇむぴぃ
0216お仕事探していまつ（207） ◆y3A2MadQ16 NGNG
>>207
実は前段階のFFTについて、
テンプレート･メタ･プログラミングで記憶階層毎の最適化対応の奴。
一応、プロファイル・ベースで自動チューニング…
…ってのがやっと一通り動いたので先日青森で開かれた研究集会まで行って発表してきた。

多倍長整数の乗算はまだ遠い…。
02171NGNG
保守
02181NGNG
age
0219デフォルトの名無しさんNGNG
ＨＳＰでＲＰＧ作りたいんですが、正直難しいと思います。
でもやりたいんです！！僕はＨＳＰでブロック崩し（アルカノイド）
ぐらいなら作ったことあります。
今のところ、オープニングまで作ったのですが、どなたか僕に
ＨＳＰの基礎からすべてを叩き込んでくれませんか？？
お願いします。
0220デフォルトの名無しさんNGNG
ＨＳＰでＲＰＧ作りたいんですが、正直難しいと思います。
でもやりたいんです！！僕はＨＳＰでブロック崩し（アルカノイド）
ぐらいなら作ったことあります。
今のところ、オープニングまで作ったのですが、どなたか僕に
ＨＳＰの基礎からすべてを叩き込んでくれませんか？？
お願いします。
02211NGNG
やばい！落ちる！
0222デフォルトの名無しさん05/02/05 10:23:00
age
0223デフォルトの名無しさん2005/05/12(木) 10:09:51
すいません
char mozi[]="unko";　この文字列は16進数値で「756E6B6F」
ですけどこの数値を2バイトごとの合計値として求める場合
「756E + 6B6F」が適切なのか、それともバイト反転した「6E75 + 6F6B」
が適切なのかわからないので教えてくださいお願いします
02242232005/05/12(木) 12:52:52
やっぱいいです
0225デフォルトの名無しさん2005/05/13(金) 09:28:43
NUXI problem
0226配列だけ2005/05/15(日) 13:10:58
>>53
できたよ
#include <stdio.h>
#include <string.h>
#define MAX 20
int main()
{
int i;
char result[MAX + 1];
char *a = "1000000000910";
char *b = "1000000000193";
for (i = 0; i < MAX + 1; i++) result[i] = 0;
for (i = 0; i < strlen(a); i++) result[MAX - strlen(a) + i] += a[i] - '0';
for (i = 0; i < strlen(b); i++) result[MAX - strlen(b) + i] += b[i] - '0';
for (i = MAX - 1; i >= 0; i--)
{
if (result[i] >= 10)
{
result[i - 1] += 1;
result[i] -= 10;
}
result[i] += '0';
}
printf("%s(a)+%s(b): %s\n", a, b, result);
return 0;
}
0227デフォルトの名無しさん2005/05/15(日) 13:11:52
hage
0228デフォルトの名無しさん2005/05/15(日) 13:17:32
訂正
#include <stdio.h>
#define MAX 20
int main()
{
int i;
char result[MAX + 1];
char a[] = "1000000000910";
char b[] = "41000000000193";
for (i = 0; i < MAX + 1; i++) result[i] = 0;
for (i = 0; i < (sizeof(a) - 1); i++) result[MAX - (sizeof(a) - 1) + i] += a[i] - '0';
for (i = 0; i < (sizeof(b) - 1); i++) result[MAX - (sizeof(b) - 1) + i] += b[i] - '0';
for (i = MAX - 1; i >= 0; i--)
{
if (result[i] >= 10)
{
result[i - 1] += 1;
result[i] -= 10;
}
result[i] += '0';
}
printf("%s(a) + %s(b): %s\n", a, b, result);
return 0;
}
0229デフォルトの名無しさん2005/05/15(日) 15:28:17
>>53 名前：936[age] 投稿日：02/11/07 22:18
　　　　　　　　　　　　　　　　　~~~~~~~~~~~~~~~~
>>226 名前：配列だけ[sage] 投稿日：2005/05/15(日) 13:10:58
　　　　　　　　　　　　　　　　　　　　　　~~~~~~~~~~~~~~~~~~~~~~~~

(　ﾟдﾟ)

(つд⊂)ｺﾞｼｺﾞｼ

(；ﾟдﾟ)

(つд⊂)ｺﾞｼｺﾞｼ
　　_, ._
（；ﾟ Дﾟ）

0230デフォルトの名無しさん2005/05/15(日) 20:10:45
当時1年でも今4年だな…(ちゃんと単位取れてれば
023112005/05/16(月) 02:16:33
あれからもう1年半も経つとは…長いなぁ
023212005/05/16(月) 02:17:01
間違った
「あれからもう2年半も経つとは…長いなぁ」
0233デフォルトの名無しさん2005/05/16(月) 13:35:28
あれから僕たちは何かを信じてこれたかなぁ
02342162005/10/28(金) 01:15:42
>>216なFFT話を発表してきたのがきっかけでお仕事にありつきますた。
仕事は多倍長からはかなり離れてしまったけれどね。
しかしこのスレまだあったんだねぇ。人少ないけど長寿だねぇ。

たまにはage保守しときまつか。
0235デフォルトの名無しさん2005/10/28(金) 10:48:25
このスレは216の人生を記すスレとなりました。
0236デフォルトの名無しさん2005/10/28(金) 11:46:15
>>400は3年後の>>216
023712005/10/28(金) 15:22:59
このスレまだ存在してたのか。確かに長いなぁ。
新着チェックで上がってこなかったら気付かなかった。
■ このスレッドは過去ログ倉庫に格納されています