« 今日の脳年齢2006年2月20日 | メイン | 今日の脳年齢2006年2月21日 »
2006年 2月 21日（火） 赤口 今日は何の日？
50桁同士の足し算
世の中、いろいろな要望がある物で。金融系のシステムで、50桁同士の足し算を行いたい。と言う仕様がありました。今回、 僕はプログラミングにも設計にも参加していないのだけど、暇だったので組んでみました。
#!/usr/bin/perl
use strict;
my(@a);
$a[0]="12345678901234567890";
$a[1]="23456789012345678901";$a[2] = &bigadd($a[0], $a[1]);
print $a[0]. " + ". $a[1]. " = ". $a[2]. "\n";exit 0;
sub bigadd($$$) {
my(@a) = @_;my($cy, $r, $i, @al, @a1);
$cy = 0;
$r = "";for ($i = 0; $i <= 1; $i++) {
$al[$i] = length($a[$i]);
}
$al[2] = ($al[0] > $al[1]) ? $al[0] : $al[1];
for ($i = 0; $i <= 1; $i++) {
if ($al[$i] < $al[2]) {
$a[$i] = ('0'x ($al[2] - $al[$i])). $a[$i];
}
}for ($i = 0; $i < $al[2]; $i++) {
$a1[0] = &get1(\$a[0]);
$a1[1] = &get1(\$a[1]);
($a1[2], $cy) = &add1($a1[0], $a1[1], $cy);
$r = "$a1[2]$r";
}if ($cy == 1) {
$r = "1$r";
}($r);
}
sub get1($) {
my($a) = @_;
my($r);$r = substr($$a, -1, 1);
$$a = substr($$a, 0, length($$a)-1);
($r);
}
sub add1($$$) {
my($a, $b, $cy) = @_;
my($r);$r = $a + $b + $cy;
$cy = int($r / 10);
$r %= 10;($r, $cy);
}
ブログの幅もあるので、桁数は少なくしてみましたが、数字文字列同士の足し算なので、
文字列として認識できる桁数まで計算させる事ができます。
Perlの場合、メモリ容量に依存ですから、数万桁同士の足し算でもこなせます。 時間は係ると思いますが
ソースをご覧頂くと直ぐに分かるかとは思いますが、右から1文字ずつ切り出して、1桁の足し算を繰り返す。
と言うシンプルな物です。
ポイントは、足す値, 足される値とも同じ桁数にしてから処理を始める。と言う事です。少し冗長な処理が入っていますが、
実はこの部分がこのタイプの計算を行う時に重要になってくるところです。
計算処理でポイントになるのは、桁上がりの処理でしょうか。桁上がりを管理するために、「キャリーフラグ」
を持たせて処理しています。1桁目は桁上がりが無いので、キャリーフラグを0にしてから処理を開始します。この辺り、
アセンブラ経験者の方の方がピンと来るアルゴリズムかも知れませんね。
get1で、スカラー変数のリファレンスを利用しているのは、数字文字列の右端1文字を取り出し時、その文字を切り取る必要があり、
それをget1の中でやらせてしまいたかったので、この様な形式にしています。リファレンスにせず、
戻り値として取得しても全く問題はありません。
滅多に使う様な処理では無いけれど、天文学的数字同士の足し算, 引き算程度なら、 この様な方法を利用する事ができますよ。と言う見本でした。
Posted by kibiwaka : 2006年02月21日 22:27
トラックバック
- トラックバックを頂く記事の内容については、記事に関係する内容、記事への同調、記事への反論など、 記事の内容に関するもののみとします。
- トラックバック先の記事に、当サイト、または該当記事へのリンクが無い場合には、トラックバックを削除させていただく場合があります。
- Movable Typeの迷惑トラックバック感知機能により、トラックバックが受け付けられない場合があります。
- 法律に触れる可能性があると判断できるもの、当サイトへの掲載が不適当と思われる内容については、 事前の連絡をなしに削除する場合があります。
- 当サイト、黍若個人への連絡事項などがあれば、連絡用記事へトラックバックを付けてください。 個別の記事に付けないで下さい。
または、ウェブメールでご連絡下さい。 - 詳しくし、黍若日記 コメント・トラックバック・リンク基本方針をご覧下さい。
このエントリーのトラックバックURL:
このエントリーのリンク用URL:
コメント
- コメントを頂く記事の内容については、記事に関係する内容、記事への同調、記事への反論など、 記事の内容に関するもののみとします。
- Movable Typeの迷惑コメント感知機能により、コメントが受け付けられない場合があります。
- 法律に触れる可能性があると判断できるもの、当サイトへの掲載が不適当と思われる内容については、 事前の連絡をなしに削除する場合があります。
- 当サイト、黍若個人への連絡事項などがあれば、連絡用記事へコメントを付けてください。 個別の記事に付けないで下さい。
または、ウェブメールでご連絡下さい。 - 詳しくし、黍若日記 コメント・トラックバック・リンク基本方針をご覧下さい。
![[Valid RSS]](http://www.kibiwaka.com/blog/archives/valid-rss.png "Validate my RSS feed"){kind=small}
![[Valid Atom]](http://www.kibiwaka.com/blog/valid-atom.png "Validate my Atom feed"){kind=small}
