小数を整数に変換するための共通の乗数を見つけるアルゴリズム

StackOverflow https://stackoverflow.com/questions/58493

  •  09-06-2019
  •  | 
  •  

質問

小数点以下 8 桁までの可能性がある数値の配列があり、それらをすべて整数にするために乗算できる最小の共通数を見つける必要があります。元の数値をすべて同じスケールで乗算し、整数のみを処理する密閉システムで処理できるようにするためにこれが必要です。その後、結果を取得して共通の乗数で割って相対的な結果を得ることができます。 。

現在、数値をいくつかチェックして 100 または 1,000,000 を掛けていますが、*sealed システムによって実行される処理は、大きな数値を扱う場合に非常に高価になる可能性があるため、目的のためにすべてを 100 万倍するのは実際にはそうではありません。素晴らしいオプションです。近似として、シールド アルゴリズムのコストが 10 倍になるたびに 10 倍になるとします。

必要なことを達成するために最も効率的で、可能な限り最良の結果をもたらすアルゴリズムは何ですか? 必要なことを表す数学的な名前や公式はありますか?

※密閉システムは実際には密閉されておりません。私はそのソース コードを所有/管理していますが、100,000 行もの独自のマジックが含まれており、徹底的にバグとパフォーマンス テストが行​​われているため、float を処理するためにソース コードを変更することは、多くの理由から選択肢ではありません。これは、X x Y のセルのグリッドを作成し、X x Y の四角形がグリッドにドロップされ、「独自の魔法」が発生し、結果が吐き出されるシステムです。明らかに、これは現実の非常に単純化されたバージョンですが、十分に良い近​​似値です。

これまでのところ、良い答えはいくつかありますが、「正しい」答えをどうやって選択すればよいのか疑問に思いました。最初は、各ソリューションを作成してパフォーマンス テストを行うことが唯一の公平な方法だと考えていましたが、後になって、純粋な速度だけが関連する要素ではなく、より正確なソリューションも非常に重要であることに気づきました。とにかくパフォーマンス テストを作成しましたが、現在は「直感」の公式を使用して、速度と精度に基づいて正しい答えを選択しています。

私のパフォーマンス テストでは、ランダムに生成された 100 個の数値からなる 1000 個の異なるセットを処理します。各アルゴリズムは、同じ乱数のセットを使用してテストされます。アルゴリズムは.NET 3.5で記述されています（これまでのところ2.0互換性がありますが）私はテストを可能な限り公平にするためにかなり一生懸命努力しました。

  • グレッグ - 多数を掛けてからGCDで除算 - 63ミリ秒
  • アンディ - 文字列解析 - 199ミリ秒
  • Eric – Decimal.GetBits – 160 ミリ秒
  • エリック - バイナリ検索 - 32ミリ秒
  • IMA - 申し訳ありませんが、.NETでソリューションを簡単に実装する方法を理解できませんでした（あまり長く費やしたくありませんでした）
  • ビル - 私はあなたの答えがグレッグのものにかなり近かったので、それを実装しませんでした。私はそれがより速くスミッジであると確信していますが、潜在的に正確ではありません。

したがって、Greg の「大きい数を掛けてから GCD で割る」ソリューションは 2 番目に高速なアルゴリズムであり、最も正確な結果が得られたため、今のところはそれが正しいと言えます。

Decimal.GetBits ソリューションを最速にしたかったのですが、非常に遅かったです。これが Double から Decimal への変換によるものなのか、それともビットのマスキングとシフトによるものなのかはわかりません。bitConverter.getBytesとここに含まれるいくつかの知識を使用して、ストレートダブルに同様の使用可能なソリューションが必要です。 http://blogs.msdn.com/bclteam/archive/2007/05/29/bcl-refresher-floating-point-types-the-good-the-bad-and-the-ugly-inbar-gazit-matthew-グレイグ.aspx しかし、その記事を読むたびに私の目は曇り続け、最終的には解決策を実行する時間がなくなってしまいました。

もっと良い解決策を思いつく人がいれば、いつでも受け入れます。

役に立ちましたか？

解決

十分大きな値 (小数点以下 8 桁で 100,000,000) を掛けて、次の値で割ります。 GCD 結果の数値の。最終的には、他のアルゴリズムに供給できる最小の整数の山ができあがります。結果を取得したら、プロセスを逆に実行して、元の範囲を回復します。

他のヒント

  1. 整数があるまで、すべてのすべての数値を10で複数回転させます。
  2. まだすべての整数がある間、2,3,5,7で分割します。

それはすべてのケースをカバーしていると思います。

2.1 * 10/7 -> 3
0.008 * 10^3/2^3 -> 1

これは、乗数が有理数であることを前提としています。

特定のセット内の浮動小数点数 x がすべて整数である場合に、N*x も正確な整数となるような整数 N を見つけたい場合、基本的に解決できない問題が発生します。x = 型が表現できる最小の正の浮動小数点数、たとえば 10^-30 であるとします。すべての数値を 10^30 で乗算し、それを 2 進数で表現しようとすると (そうでない場合、なぜ数値を int にしようとするのでしょうか?)、基本的に、他の数値の情報はすべて失われます。溢れること。

そこで、次の 2 つの提案があります。

  1. 関連するすべてのコードを制御している場合は、別のアプローチを見つけてください。たとえば、intのみを使用する機能があるが、フロートがある場合、フロートを関数に詰めたい場合は、フロートを受け入れるためにこの関数を書き直すかオーバーロードしたい場合。
  2. INTを必要とするシステムの一部を制御できない場合は、気にする精度を選択して、時々情報を失う必要があることを受け入れます（ただし、ある意味では常に「小さい」ものになります。 ）、そして、すべてのフロートにその定数を掛け、最寄りの整数に丸くするだけです。

ちなみに、浮動小数点ではなく分数を扱う場合は、別のゲームになります。多数の分数 a/b、c/d、e/f があるとします。N*(各分数) = 整数、つまり N = a となるような最小公倍数 N が必要です。bc / gcd(a,b,c);そして gcd(a,b,c) = gcd(a, gcd(b, c))。使用できます ユークリッドのアルゴリズム 任意の 2 つの数値の gcd を求めます。

グレッグ:素晴らしい解決策ですが、100 以上の数値の配列で一般的な GCD の計算は少し高価になりませんか?それについてはどうしますか?2 つの数値に対して GCD を計算するのは簡単ですが、100 の場合はより複雑になります (私はそう思います)。

邪悪なアンディ:私は .Net でプログラミングしていますが、あなたが提示した解決策は、現在私たちが行っていることとほぼ一致しています。私はそれを元の質問に含めたくありませんでした。なぜなら、私は既成概念にとらわれない（または私の常識にとらわれない）考えを期待していたためであり、潜在的な解決策で人々の回答を汚したくなかったからです。確かなパフォーマンス統計はありませんが (他に比較する方法がなかったため)、文字列の解析に比較的コストがかかることはわかっており、純粋に数学的な解決策のほうが潜在的により効率的である可能性があると考えました。公平を期すために言うと、現在の文字列解析ソリューションは実稼働中であり、そのパフォーマンスについての不満はまだありません (VB6 形式の別のシステムで実稼働中であり、そこにも不満はありません)。それはただ、それが正しくないと感じ、私のプログラミング感覚を傷つけると思いますが、おそらくそれが最良の解決策である可能性があります。

とはいえ、純粋に数学的であろうとなかろうと、他の解決策にはまだオープンです。

どの言語でプログラミングしていますか?何かのようなもの

myNumber.ToString().Substring(myNumber.ToString().IndexOf(".")+1).Length

C# の double の小数点以下の桁数が得られます。各数値を計算して小数点以下の最大桁数 (x) を見つけ、各数値に 10 の x 乗を掛けます。

編集：好奇心が強いのですが、整数のみを渡すことができるこのシールドされたシステムは何ですか?

ループ内で、各数値の仮数と指数を整数として取得します。指数には frexp を使用できますが、仮数にはビットマスクが必要になると思います。最小の指数を見つけます。仮数の最上位桁を検索します (ビットをループして最後の「1」を探します) - または単純に事前定義された有効桁数を使用します。その場合、倍数は 2^(numberOfDigits-minMantissa) のようなものになります。バイアス/オフセット/範囲を覚えていないため、「のようなもの」ですが、アイデアは十分に明確だと思います。

したがって、基本的には、各数値の小数点以下の桁数を決定する必要があります。

数値のバイナリ表現があれば、これはかなり簡単になります。数値はプログラムの早い段階で有理数または科学的表記法から変換されていますか?その場合は、以前の変換をスキップして、はるかに簡単に行うことができます。それ以外の場合は、C で記述された外部 DLL 内の関数に各数値を渡し、浮動小数点表現を直接操作することができます。または、数値を 10 進数にキャストして何らかの処理を行うこともできます。 Decimal.GetBits.

適切な条件に従って私が考えることができる最速のアプローチは、前に提案したように、必要な最小の 10 のべき乗 (または 2 など) を見つけることです。ただし、ループで実行する代わりに、可能な累乗に対して二分探索を実行することで計算を節約します。最大 8 と仮定すると、次のようになります。

int NumDecimals( double d )
{
   // make d positive for clarity; it won't change the result
   if( d<0 ) d=-d;

   // now do binary search on the possible numbers of post-decimal digits to 
   // determine the actual number as quickly as possible:

   if( NeedsMore( d, 10e4 ) )
   {
      // more than 4 decimals
      if( NeedsMore( d, 10e6 ) )
      {
          // > 6 decimal places
          if( NeedsMore( d, 10e7 ) ) return 10e8;
          return 10e7;
      }
      else
      {
         // <= 6 decimal places
         if( NeedsMore( d, 10e5 ) ) return 10e6;
         return 10e5;
      }
   }
   else
   {
      // <= 4 decimal places
      // etc...
   }

}

bool NeedsMore( double d, double e )
{
   // check whether the representation of D has more decimal points than the 
   // power of 10 represented in e.
   return (d*e - Math.Floor( d*e )) > 0;
}

追伸：証券価格をオプション価格設定エンジンに渡すことはないでしょう?まさにその味わいですね…。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top