|
|
/*========================================================*/ ＜＜＜あゆしゃのＣ言語プログラミング＞＞＞ /*========================================================*/ 第４３２回 掛け算割り算アルゴリズム 発行 ２００４年３月８日（月曜日） 発行数 約３１００ {magclick} /*========================================================*/ はじめに （ 決り文句 ） /*========================================================*/ ・このメールマガジンはまぐまぐさんから発行しています。 ・ジャンルは、マルチメディアのプログラム、Ｃ言語です。 ・このメールマガジンは、横６０文字で作成しています。 また、インデントはすべて半角スペース４つで構成しています。 ・ここで扱うプログラムは、C言語と半光年以内のものです。 ・登録解除は、まぐまぐさんのホームページでお願いします。 ・まぐまぐさんのバックナンバー（下欄参照）を活用して下さい。 ・ここは私の復習の場です。内容は約１ヶ月内外に私が勉強した 内容になっています。最新の技術があれば、へたれもあります。 ・わかりやすさを優先させる為、たまに嘘があるかもしれません。 /*========================================================*/ ご挨拶 /*========================================================*/ こんにちは。あゆしゃです。 先日、私としては極めて珍しいことに、車を拭きました。 雨にぬれた車体をタオルで拭いただけですが。 ところがそれがいけなかったのか、その後、こんな季節なのに、 ★真昼の３時、豊田に雪が降りました。 ・・・私のせい？ {magclick} /*========================================================*/ 今回のお題 ＜＜ 掛け算割り算アルゴリズム ＞＞ /*========================================================*/ の前に、前回の内容に２点間違いがありました。 １つは、４０クロックなどと紹介したところ、単位がクロック ではなくてマイクロ秒でした。 もう１点は、割り算を使った処理も速度は同じ、と紹介した ところ、同じではなく、４倍の差がありました。 もちろん、割り算なんざを使ったほうが、４倍遅いのです。 ちなみに、計測した割り算を使ったほうの処理は、こんな感じ です。 UINT s = 1, x = a; if( a == 0 ) return 0; while( s < x ) { s <<= 1, x >>= 1; } // xの桁数半減 do { x = s; s = ( a / s + s ) / 2; } while( s < x ); // 誤差がある間ループ return x; 桁数半減、というところは、前回お話したポイント通りで、 桁数を半分にすることで、平方根の近似値を求めているのです。 その後のループでそれを正解に近づけている、というわけです。 正解になるとsとxの値が一致します。WHILEはそれを待ちます。 これが大体２８０マイクロ秒でした。 ちなみにCPUは２メガヘルツ、１クロックあたり 0.000488マイクロ秒 になります。1/2048です。 ちなみに１ヘルツだと、１クロック１秒です。 /*========================================================*/ さて本題、掛け算と割り算のアルゴリズムについて。 これがあると、３２ビットをサポートしていない旧式CPUで ３２ビット掛け算割り算をサポートできます。 また、巨大な桁数をサポートすることもできるでしょう。 当たり前すぎることなので、アルゴリズムを調べても、 この手のものは見付けられませんでした。 （あったら教えてください。。。） よって、比較するものがありません。 ここに紹介するのは、まぁ平方根もそうなのですが、あゆしゃ流 のアルゴリズムのみです。 ミスがあったら、ごめんなさいね？ /*========================================================*/ さて、掛け算。 掛け算は、単純に足し算の連続です。 しかし、馬鹿正直に１つずつ足して行っては、日が暮れます。 よって、ビットのスケールにあわして、足していきます。 つまり、*257ならば、+*1+*256、を計算します。 *256だったら、シフトで求めることができますよね。 UINT mulul( UINT a, UINT b ); UINT ret = 0; int i = 32; while( --i >= 0 ) { if( b & 1 ) ret += a; b >>= 1, a <<= 1; } return ret; まぁ、こんな感じですか。 retは最初は０で、かける数（b）のビットが足っていたら、 元の数（a）をretに足し込みます。 そして１回ごとに、aとbのスケールを変更します。 bについては&1でビット判定をするためにシフトします。 アセンブラをつかってシフトしてキャリーに値を拾うほうがよい のですが、まぁ、いいでしょう。 /*========================================================*/ 続いて、割り算。 割り算は、単純に引き算の連続です。 しかし、馬鹿正直に１つずつ引いて行っては、日が暮れます。 よって、ビットのスケールにあわして、引いていきます。 つまり、/257ならば、-*256-*1、を計算します。 *256だったら、シフトで求めることができますよね。 ただし、大きいほうから引いていくのがポイントです。 UINT divul( UINT a, UINT b ); UINT ret = 0; UINT mask = 1; int i = 32 - 1; while( --i >= 0 && a > b ) b <<= 1, mask <<= 1; while( mask ) { if( a > b ) ret += mask, a -= b; b >>= 1, mask >>= 1; } return ret; まぁ、こんな感じですか。 最初のループで、初めてaを上回るbを求めています。 ついでにそのときのビット位置をmaskに求めています。 次のループで、引けるのであれば引く、ということを繰り返し ます。 引くときに、その位置に相当するmaskをretに足すことで、 割り算の商を求めています。 足すのではなく、論理ORでもOKです。そっちのほうが早いかな。 意外に、簡単です。 /*========================================================*/ ちなみに、掛け算や割り算のアルゴリズムの中で、スケールの 小さい掛け算や割り算を使うのは、反則です。 ・・・シフトはいいのです、シフトだから。。。 {magclick} /*========================================================*/ さいごに /*========================================================*/ あんまし動作確認していません。時間がなくて、というのは いいわけですが。 平方根についてはループをまわして１億パターンぐらい やりましたが、今回は手入力で２，３パターン・・・？ 駄目ですか？ {magclick} /*========================================================*/ 次回予告 /*========================================================*/ 次回は３月１５日（月曜日）に、第４３３回を送ります。 お題は「。。。」 あれが降臨中ですので、周一ペーストさせていただきます。 お題は・・・、えー、えー、困ったな。頭があれでいっぱいで。 何か話題を考えておきますゆえ。 お楽しみに！ /*========================================================*/ 最後の決り文句 /*========================================================*/ このメールマガジンは、まぐまぐさんから発行しています。 このメールマガジンを解除したい場合は、まぐまぐさんをご利用 ください。このメルマガのまぐまぐアイディーは最後にあります。 このメールマガジンには広告が挿入されていますか？ このメールマガジンの内容に文面の引用はありませんか？ めーらっくすの場合はめーらっくすの利用方に従ってください。 このメールマガジンの内容の、転用、流用、宣伝、リンク、 レッスンしませんか？ なんて大歓迎です。 {magclick} /*========================================================*/ /*========================================================*/ 発行者 あゆしゃ まぐまぐアイディー 0000020674 まぐまぐバックナンバー http://jazz.tegami.com/backnumber/frame.cgi?id=0000020674 あゆしゃの世界 http://ayusya.hp.infoseek.co.jp/ 登録と解除 http://www.mag2.com/m/0000020674.htm ご意見・ご感想・ご質問メール mailto:ayusya@flamenco.plala.or.jp めーらっくす ＜＜過去ログがタイトル別になっています＞＞ http://www.mailux.com/mm_dsp.php?mm_id=MM3E1AEE285AB4F |