もちろん、ほとんどの言語にはこのためのライブラリ関数がありますが、自分でやりたいとします。
float が C または Java プログラム ('f' または 'd' 接尾辞を除く) のように与えられるとします。たとえば、" 4.2e1"、" .42e2"、または単に " 42" です。一般に、小数点の前に「整数部」、小数点の後に「小数部」、「指数部」があります。3 つすべてが整数です。
個々の数字を見つけて処理するのは簡単ですが、どのようにしてそれらを型の値に、floatまたはdouble精度を失わずに構成するのでしょうか?
整数部分に 10^ nを掛けることを考えています。nは小数部分の桁数です。次に、小数部分を整数部分に加算し、指数からnを減算します。これは、たとえば4.2e1に効果的に変わります。42e0次に、pow関数を使用して 10^指数を計算し、その結果に新しい整数部分を掛けることができます。問題は、この方法が全体を通して最大の精度を保証するかどうかです。
これについて何か考えはありますか？
他のすべての回答は、これを適切に行うことがいかに難しいかを見逃しています。これである程度正確な最初のカットアプローチを実行できますが、IEEE 丸めモード (その他) を考慮するまで、正しい答えは得られません。以前、かなり大量のエラーを伴う単純な実装を作成しました。
数学が苦手でない場合は、David Goldberg による次の記事、What Every Computer Scientist Should Know About Floating-Point Arithmeticを読むことを強くお勧めします。内部で何が起こっているのか、なぜビットがそのように配置されているのかをよりよく理解できるようになります。
私の最善のアドバイスは、機能する atoi 実装から始めて、そこから移動することです。不足していることがすぐにわかりますが、strtodのソースを少し見てみると、正しい道 (長くて長い道のり) にたどり着きます。最終的には、標準ライブラリがあることをここに挿入してください。
/* use this to start your atof implementation */
/* atoi - christopher.watford@gmail.com */
/* PUBLIC DOMAIN */
long atoi(const char *value) {
unsigned long ival = 0, c, n = 1, i = 0, oval;
for( ; c = value[i]; ++i) /* chomp leading spaces */
if(!isspace(c)) break;
if(c == '-' || c == '+') { /* chomp sign */
n = (c != '-' ? n : -1);
i++;
}
while(c = value[i++]) { /* parse number */
if(!isdigit(c)) return 0;
ival = (ival * 10) + (c - '0'); /* mult/accum */
if((n > 0 && ival > LONG_MAX)
|| (n < 0 && ival > (LONG_MAX + 1UL))) {
/* report overflow/underflow */
errno = ERANGE;
return (n > 0 ? LONG_MAX : LONG_MIN);
}
}
return (n>0 ? (long)ival : -(long)ival);
}
10 進数を最適な浮動小数点近似値に変換するための「標準」アルゴリズムは、William Clinger のHow to read float numbers accuracyで、ここからダウンロードできます。これを正しく行うには、まれなケースを処理するために、少なくとも一定の割合の時間で多倍精度の整数が必要になることに注意してください。
逆に、浮動小数点数から最適な 10 進数を出力するためのアルゴリズムは、Burger と Dybvig のPrinting Floating-Point Numbers Quickly and Accuratelyにあり、ここからダウンロードできます。これには、多倍精度の整数演算も必要です
両方向のアルゴリズムについては、David M Gay のCorrectly Rounded Binary-Decimal and Decimal-Binary Conversionsも参照してください。
バイナリ表現を使用して、浮動小数点数を直接組み立てます。
数字を次々と読み取り、最初にすべての数字を見つけます。整数演算でそれを行います。また、小数点と指数を追跡します。これは後で重要になります。
これで、浮動小数点数を組み立てることができます。最初に行うことは、最初のセットの 1 ビット (最高から最低) の数字の整数表現をスキャンすることです。
最初の 1 ビットの直後のビットが仮数です。
指数を取得することも難しくありません。最初の 1 ビット位置、小数点の位置、および指数表記からのオプションの指数がわかります。それらを組み合わせて、浮動小数点指数バイアスを追加します（127だと思いますが、参考にしてください）。
この指数は、0 から 255 の範囲のどこかにある必要があります。それより大きいか小さい場合は、正または負の無限数になります (特殊なケース)。
指数をそのまま float のビット 24 から 30 に格納します。
最上位ビットは単に符号です。1 はマイナス、0 はプラスを意味します。
説明するのは実際よりも難しく、浮動小数点数を分解して指数と仮数を調べてみると、それがいかに簡単であるかがわかります。
ところで - 浮動小数点自体で算術演算を行うことは、常に仮数を 23 有効ビットに切り捨てることを強制するため、悪い考えです。そのように正確な表現を得ることはできません。
はい、これらの演算がEXACTである限り、構造を浮動小数点演算に分解でき、最終的な不正確な演算を 1 つ実行できます。
残念ながら、浮動小数点演算はすぐに不正確になります。仮数の精度を超えると、結果が丸められます。丸めの「エラー」が導入されると、それはその後の操作で累積されます...
したがって、一般的にいいえ、そのような単純なアルゴリズムを使用して任意の小数を変換することはできません。他の人がすでにあなたに言ったように、正しいもののulp。
しかし、どこまで行けるか見てみましょう:
次のようにフロートを慎重に再構築すると:
if(biasedExponent >= 0)
return integerMantissa * (10^biasedExponent);
else
return integerMantissa / (10^(-biasedExponent));
桁数が多い場合に integerMantissa を累積するときと、10 を biasedExponent で累乗するときの両方で、精度を超えるリスクがあります...
幸いなことに、最初の 2 つの演算が正確であれば、最後の不正確な演算 * または / を許容できます。IEEE プロパティのおかげで、結果は正しく丸められます。
これを、精度が 24 ビットの単精度浮動小数点数に適用してみましょう。
10^8 > 2^24 > 10^7
2 の倍数は指数を増やすだけで、仮数は変更しないことに注意してください。
5^11 > 2^24 > 5^10
ただし、integerMantissa で 7 桁の精度と、-10 から 10 の間の biasedExponent を使用できます。
倍精度で53ビット、
10^16 > 2^53 > 10^15
5^23 > 2^53 > 5^22
したがって、15 桁の 10 進数と、-22 から 22 の間の偏った指数を使用できます。
数字が常に正しい範囲に収まるかどうかは、あなた次第です...（本当に難しい場合は、末尾のゼロを挿入/削除することで、仮数と指数のバランスをとることができます）。
それ以外の場合は、拡張精度を使用する必要があります。あなたの言語が任意精度の整数を提供する場合、それを正しく理解するのは少し難しいですが、それほど
難しくはありません。-optimizing.htmlおよびhttp://smallissimo.blogspot.fr/2011/09/reviewing-fraction-asfloat.html
これらは単純で単純な実装であることに注意してください。幸いなことに、libc はより最適化されています。
解析時に小数点を無視できます（その場所を除く）。入力が156.7834e10であったとしましょう...これは簡単に整数1567834に解析され、その後にe10が続きます。小数点はfloatの「数値」部分の末尾から4桁であるため、これをe6に変更します。 .
精度が問題です。使用している言語の IEEE 仕様を確認する必要があります。仮数 (または分数) のビット数が整数型のビット数よりも大きい場合、誰かが次のような数値を入力すると、精度が失われる可能性があります。
5123.123123e0 - 私たちのメソッドでは 5123123123 に変換されます。これは Integer には適合しませんが、5.123123123 のビットは float 仕様の仮数に適合する場合があります。
もちろん、小数の前の各桁を取得し、現在の合計 (浮動小数) を 10 倍してから、新しい桁を追加するメソッドを使用することもできます。小数点以下の桁数については、現在の合計に加算する前に、その桁に 10 のべき乗を掛けます。ただし、この方法では、すぐに利用できる解析ライブラリを使用せずに浮動小数点プリミティブを使用する必要があるため、なぜこれを行うのかという疑問が生じるようです。
とにかく、頑張ってください！
int64私の最初の考えは、仮数の最初の18桁のみを使用して、文字列を仮数とint10進指数に解析することです。たとえば、1.2345e-5は12345と-9に解析されます。次に、仮数に10を掛け、仮数が18桁の長さ（> 56ビットの精度）になるまで指数を減らし続けます。次に、テーブルで10進数の指数を調べて、数値を10進数のn * 10^mから2進数のp*2^q形式に変換するために使用できる係数と2進数の指数を見つけます。係数は別のものになるint64ので、仮数にそれを掛けて、結果の128ビット数の上位64ビットを取得します。このint64仮数は、必要な精度のみを失う浮動小数点にキャストでき、2 ^ q指数は、精度を失うことなく乗算を使用して適用できます。
これは非常に正確で非常に高速であると思いますが、特殊な数値NaN、-infinity、-0.0、およびinfinityを処理することもできます。非正規化数や丸めモードについては考えていません。
数値を表す任意の文字列を、精度を失うことなくdoubleまたはfloatに変換することはできません。2進数のfloatまたはdoubleでのみ近似できる、10進数（「0.1」など）で正確に表すことができる多くの小数があります。これは、分数1/3を正確に小数で表すことができない方法に似ています。0.333333としか記述できません...
ライブラリ関数を直接使用したくない場合は、それらのライブラリ関数のソースコードを見てみませんか？あなたはJavaについて言及しました。ほとんどのJDKには、クラスライブラリのソースコードが付属しているため、java.lang.Double.parseDouble（String）メソッドがどのように機能するかを調べることができます。もちろん、BigDecimalのようなものは、精度と丸めモードを制御するのに適していますが、floatまたはdoubleである必要があるとおっしゃいました。
そのためには、適切なバイナリ表現のために標準 IEEE 754 を理解する必要があります。その後、Float.intBitsToFloatまたはDouble.longBitsToDoubleを使用できます。
可能な限り正確な結果が必要な場合は、より高い内部作業精度を使用してから、結果を目的の精度にダウンコンバートする必要があります。いくつかの ULP のエラーを気にしない場合は、必要に応じて、目的の精度で 10 を繰り返し掛けることができます。大きな指数に対して不正確な結果が生成されるため、pow() 関数は避けます。
ターミナルに同意します。パーサーを壊すことができる多くの愚かな方法があるので、ステートマシンはこのタスクを達成するための最良の方法です。私は現在1つに取り組んでいます、それは完了していると思います、そしてそれは私が13の州を持っていると思います。
問題は些細なことではありません。
私は浮動小数点ハードウェアの設計に興味のあるハードウェアエンジニアです。私は2回目の実装を行っています。
私は今日これを見つけましたhttp://speleotrove.com/decimal/decarith.pdf
18ページにいくつかの興味深いテストケースがあります。
はい、私はClingerの記事を読みましたが、単純なハードウェアエンジニアであるため、提示されたコードについて頭を悩ませることはできません。Knuthのテキストに示されているSteeleのアルゴリズムへの参照は、私にとって役に立ちました。入力と出力の両方に問題があります。
前述のさまざまな記事への参照はすべて優れています。
私はまだここでサインアップしていませんが、サインアップすると、ログインが行われなかったと仮定すると、それは失敗に終わります。（ブロードット）。
クライド
ステート マシンの使用。これはかなり簡単に実行でき、データ ストリームが中断された場合でも機能します (状態と部分的な結果を保持するだけで済みます)。パーサー ジェネレーターを使用することもできます (もっと複雑なことをしている場合)。