実数型(double)を使用せずに浮動小数点の計算を行う

Question

はじめに

いつもお世話になっています。

表題について質問があります。
組込みC(C99)でdouble型を使わずに小数点の計算を行いたいのですが可能でしょうか？
取りあえずVisual Studioで以下の様なソースコードを作ってみましたがやはり端数処理が上手くいきません。

#include <stdio.h>

#define MILLION_TIMES (1000000)

int main(char argc, char *argv[]) {

	int dividend;	// 被除数
	int divisor;	// 除数(0は絶対に使わない)

	dividend =  87;
	divisor = 31;

	// 確認用です(実数型は使わない)
	double dDiv = (double)dividend / divisor;


	int integer = dividend / divisor;
	int idec = ((dividend * MILLION_TIMES) / divisor)-(integer * MILLION_TIMES) ;


	// 商に除数をかければ被除数になる
	printf("[double]\n");
	printf("%d / %d =%lf\n", dividend, divisor, dDiv);
	printf("%f * %d =%lf\n", dDiv, divisor, dDiv*divisor);
	printf("\n");
	printf("[int]\n");
	printf("%d / %d =%d.%06d\n", dividend, divisor, integer, idec);
	printf("%d.%d * %d =%d\n", integer, idec, divisor, divisor*integer+(divisor*idec)/ MILLION_TIMES);

	return 0;
}

[double]
87 / 31 =2.806452
2.806452 * 31 =87.000000

[int]
87 / 31 =2.806451
2.806451 * 31 =86

これ以外にも負数の場合の動作も考える必要があって悩んでいます。
これ以上は無理なのでしょうか？

Comments

[Zuishin]

除算アルゴリズムは色々ありますが、double を使わないのは何のためですか？

[kuma_dansyaku]

組み込みなので使えないのです。正確には使えないわけでは無いですが、使うとめちゃめちゃ処理が遅くなるので使えません。あと使うとレビューで怒られます

[Zuishin]

つまり、組み込みの double より高速で同程度の精度を持った除算関数を作らなければならないということですか？

[kuma_dansyaku]

そうですね。検討用なのでそれ程重要度は高くないですが自分で調べていて限界だったのでヒントでも頂ければとこの質問をしました

Answer 1

さて、どのような理由で、doubleを使わずにどんな計算を行いたいのでしょうか。やりたいことによって、適切なモデルは変わってきます。

• ネイティブで浮動小数点演算のできない環境向けにコードを書く
• 精度は犠牲にしていいから、できるだけ高速に計算したい
• 誤差なく有理数として計算を行いたい
• 通貨計算なので、浮動小数点演算で生じる小数の誤差が問題になる

その事情がわからないと、不適切な計算モデルを提案されることになります。

Comments

[kuma_dansyaku]

画像縮小です。
1byte/1pixの画像(色の格納方法は話がややこしくなるので考え無いでください)
縮小サイズからベース画像の位置を割り出しそこから上下左右の色情報を取って中間色を得ると言う事をしたいのです。

実際やるなら潤沢なAPI(メソッド)を持った言語でやるか、専用のライブラリを用意する必要があるのですが、何も無いこの状況で実装してくれと言われたので右往左往しています。

> ネイティブで浮動小数点演算のできない環境向けにコードを書く
→マイコンに焼くのでその通りです
> 精度は犠牲にしていいから、できるだけ高速に計算したい
→精度の方が重要です

取りあえず小数の計算が出来れば良いと思っていたのと、仕事の話に密になるので多く書けなかったので、情報が少なすぎると思われましたらすみませんでした。

Answer 2

こんにちは。

組込みの場合は、浮動小数点計算負荷が許容できないケースが多いですね。
そのような時は、固定小数点を良く使います。掲示されてるソースは正に固定小数点処理です。

端数がうまくあわないのは丸め処理の問題です。0.999999999でも切り捨てると0です。本来丸めて1にしたいところです。浮動小数点処理はこのような丸め処理をしています。

divisorinteger+(divisoridec)/ MILLION_TIMES

は、下記処理でお手軽な四捨五入になります。

(divisorinteger+(divisoridec) + MILLION_TIMES/2)/ MILLION_TIMES

負の数では妥当ではない気もしますので、良く検討下さい。
（負の数の四捨五入を考え出すと、丸め処理は様々な考え方があるので頭痛いです。）

---

【追記】
書こうと思いつつ忘れてました。
小数点位置を10進数で決めると計算が重くなるし、オーバーフローするしないの桁数が曖昧になるので、2進数で決めると良いです。固定小数点処理をシフト演算で済ませられるので高速なのです。なれない2進数で検討するのは少したいへんですが、10進数変換誤差がない分 楽ですよ。

Comments

[kuma_dansyaku]

レスありがとうございます。
具体的な手法まで書いて頂き参考になります。

あの後聞いたところunsinged(符号なし) との事なので負数を使う必要は無いとの事なので検討範囲は狭まりました。

上記のコメントにも記載いたしましたが、ソフト処理で画像の縮小を行ってほしいと言われバイニリア、(出来れば)バイキュービックも試して欲しいと言われ「冗談でしょ？なんちゃってバイニリアしか出来ませんよ？」と思いながら色々試していました。

ご提示頂いた2進数で扱う方法(考え方)は初めて知りました。
この辺は皆様から頂いた用語を元に調べてみようとおもいます。

[sharow]

コメント欄で失礼。私も固定小数点が良いと思います。
初代プレステが固定小数点だったことを思いながら取り組むと捗るのではないでしょうか。

固定小数点では浮動小数点よりもサイズ、拡縮度合いが厳密に制限されるので注意してください。
仕様として例えば「1/64より小さい縮小はできない」とか、「2048px以上の画像は扱えない」といった制限をあらかじめ設ける必要があります。

Answer 3

wikipedia

Chironianさんの言うとおり２進数(小数部分を何ビットとるか)で考えるのがミソのようです。

英語の方だとQフォーマットにもう少し詳しく書かれていました。
https://en.wikipedia.org/wiki/Q_(number_format)

以下 チラシの裏。
昔FPUのないpowerpcでカーネルのFPUエミュレーションが激遅なのが問題になって、GCCの4.3(だったかな？)で固定小数点型(_Fract)というのを使ってみようとしたけどコンパイルできなくて結局soft-float使ったのを思い出しました。

Comments

[kuma_dansyaku]

レスありがとうございます。
リンク先参考にさせていただきます。

今時の組込みチップなのでFPUはあるはずなのですがそんな無理難題を言われました。
浮動小数点演算ライブラリと言うのがあるんですね。
こっちで使っているコンパイラはなんだったかな？ARMかなんかだったと思いますが、下っ端のペーペーには仕様を流してくれないので言われた情報だけでやっています。

検討用なので採用はしてもらえないですが自分の知識になればこれも良い経験かと思い頑張っていきます。
ありがとうございました。

Answer 4

全くdoubleやfloat型を使わないのは難しいでしょうね。

組み込みのCPUで浮動小数点演算がソフトウェアの処理の場合は、速度的に速く処理したい場合に限って、全てを整数で演算して処理することはあります。その場合は、何倍するのかは数値が取りうる範囲と有効桁数をよくよく吟味した上でその処理に特化した書き方をしています。オーバーフローやアンダーフローにも注意しながらの処理なので慎重に設計しなくてはいけません。（倍数は桁取りが楽になる様に10000倍とか100000倍とかの10のn乗を使います）

桁を大きく取りたい場合は、多倍長演算のライブラリを用いる手もあります。

PC上で動かすソフトの場合は、こういうことはまず考えませんね。

Comments

[kuma_dansyaku]

レスありがとうございます。

>PC上で動かすソフトの場合は、こういうことはまず考えませんね。
そうなんですよ。言われた時目が点になりました。
画像の縮小処理でバイリニア手法を使うに当たってこの難題にぶち当たりました。
ここまで行くとコンバートになるのでこう言うのはハードの方でやってくれれば良いのに・・・・。

そんな事を思いながらクイズ感覚で色々試しています。
ここまでやって検討用のお試し処理なので実採用はしてもらえないですが自分の知識になればこれも良い経験かと思い頑張っていきます。
ありがとうございました。

Answer 5

固定小数の概念を教えて頂きありがとうございます。
端数処理や扱える値の範囲を明確にしておけば綺麗に表現出来る事を理解しました。
見直してみるとx100000とか確かに煩雑過ぎますね。
これで画像処理を検討しようと思います

/*
  小数を使って2byte(16bit)の変数を整数(8bit)/小数(8bit)で計算する

  シフト演算を使うので処理が速い事や分かり易いのが特徴
  扱える値の範囲に限界があるので事前に決めておく必要がある
  端数処理を意識しないと結果が大きく変わる (1/3)*3 ≠ 1
*/
#define SFT  (8)         /* Q8-format */
#define K   (1<<(SFT-1)) /* K = 0.5 */

int d1 = 87; // 被除数
int d2 = 31; // 除数

// 固定小数の除算
unsigned int ui = (d1 << SFT) / d2;

// 商に除数をかければ被除数になる
ui = ((ui * d2) + K) >> SFT;