4

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

現在、数値をいくつかチェックして 100 倍または 1,000,000 倍していますが、*sealed システムによって行われる処理は、大きな数値を処理する場合に非常にコストがかかる可能性があるため、目的のためにすべてを 100 万倍にすることはあまり意味がありません。素晴らしいオプションです。概算として、封印されたアルゴリズムは、10 倍するたびに 10 倍のコストがかかると言えます。

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

*封印されたシステムは、実際には封印されていません。私はそのソースコードを所有/維持していますが、その100,000行の独自の魔法であり、バグとパフォーマンスが徹底的にテストされており、フロートを処理するように変更することは多くの理由でオプションではありません. それは、X x Y セルのグリッドを作成し、X x Y の四角形をグリッドにドロップし、「独自の魔法」が発生して結果を吐き出すシステムです。十分な近似です。

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

私のパフォーマンス テストでは、ランダムに生成された 100 の数値の 1000 の異なるセットを処理します。各アルゴリズムは、同じ乱数セットを使用してテストされます。アルゴリズムは .Net 3.5 で記述されています (ただし、これまでのところ 2.0 と互換性があります)。テストをできるだけ公正にするために、かなりの努力をしました。

  • Greg – 大きな数を掛けてから GCD で割る – 63 ミリ秒
  • Andy – 文字列解析 – 199 ミリ秒
  • Eric – Decimal.GetBits – 160 ミリ秒
  • Eric – 二分探索 – 32 ミリ秒
  • Ima – 申し訳ありませんが、ソリューションを .Net で簡単に実装する方法がわかりませんでした (あまり時間をかけたくありませんでした)。
  • Bill – あなたの答えは Greg の答えにかなり近かったので、実装しませんでした。わずかに高速になると確信していますが、精度が低下する可能性があります。

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

私は本当に Decimal.GetBits ソリューションを最速にしたかったのですが、非常に遅かったです。BitConverter.GetBytes とここに含まれるいくつかの知識を使用して、ストレート Double の同様の使用可能なソリューションがあるはずです: http://blogs.msdn.com/bclteam/archive/2007/05/29/bcl-refresher-floating-point- types-the-good-the-bad-and-the-ugly-inbar-gazit-matthew-greig.aspx ですが、その記事を読むたびに目が眩み、最終的に実装を試みる時間がなくなりました。解決。

誰かがより良いものを考えることができれば、私は常に他の解決策を受け入れます.

4

7 に答える 7

6

十分に大きなもの (小数点以下 8 桁で 100,000,000) を掛けてから、結果の数値のGCDで割ります。他のアルゴリズムにフィードできる最小の整数の山になってしまいます。結果が得られたら、プロセスを逆にして元の範囲を回復します。

于 2008-09-12T08:21:43.077 に答える
1

N * xがフロートのセットの正確な整数でもあるように整数Nを見つけたい場合、与えられたセットのxはすべて整数であり、基本的に解決できない問題があります。x =タイプが表すことができる最小の正のフロート、たとえば10^-30であるとします。すべての数値に10^30を掛けてから、それらを2進数で表現しようとすると（そうでない場合は、なぜそれらをintにするのに苦労するのですか？）、基本的に他の数値のすべての情報が失われます。オーバーフローします。

したがって、ここに2つの提案があります。

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

ちなみに、フロートではなく分数を扱っている場合は、別のゲームです。分数a/b、c / d、e/fがたくさんある場合。そして、N *（各分数）=整数、次にN = a b c / gcd（a、b、c）;となる最小公倍数Nが必要です。およびgcd（a、b、c）= gcd（a、gcd（b、c））。ユークリッドのアルゴリズムを使用して、任意の2つの数値のgcdを見つけることができます。

于 2008-09-12T11:19:02.137 に答える
1
  1. 整数になるまで、すべての数値に 10 を掛けます。
  2. まだすべての整数があるうちに、2,3,5,7 で割ります。

すべてのケースを網羅していると思います。

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

それは、乗数が有理数になる可能性があると仮定しています。

于 2008-09-12T23:01:05.710 に答える
0

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

于 2008-09-12T10:47:54.117 に答える
0

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

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

C# の double の小数点以下の桁数を示します。それを各数値で実行し、最大の小数点以下の桁数 (x) を見つけてから、各数値に 10 を x 乗します。

編集: 好奇心から、整数のみを渡すことができるこの封印されたシステムは何ですか?

于 2008-09-12T08:36:29.360 に答える
0

Greg: すばらしい解決策ですが、100 以上の数値の配列で一般的な GCD を計算すると、少しコストがかかりませんか? そして、あなたはそれについてどうしますか？2 つの数値に対して GCD を実行するのは簡単ですが、100 の場合はより複雑になります (と思います)。

Evil Andy: 私は .Net でプログラミングしていますが、あなたが提示したソリューションは、私たちが現在行っていることとほぼ一致しています。元の質問にそれを含めたくありませんでした。なぜなら、箱の外（またはとにかく私の箱）の思考を望んでいたからであり、潜在的な解決策で人々の回答を汚したくありませんでした。確かなパフォーマンス統計はありませんが (比較する他の方法がなかったため)、文字列の解析は比較的コストがかかることを知っており、純粋に数学的なソリューションがより効率的である可能性があると考えました。公平を期すために、現在の文字列解析ソリューションは実稼働中であり、そのパフォーマンスについてはまだ不満はありません (VB6 形式の別のシステムで実稼働していても、そこにも苦情はありません)。気分が乗らないだけで、

そうは言っても、私は純粋に数学的であろうとなかろうと、他の解決策に対してまだオープンです。

于 2008-09-12T09:03:59.093 に答える
0

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

数値のバイナリ表現があれば、これはかなり簡単になります。プログラムの早い段階で、数値が有理数または科学的表記法から変換されていますか? もしそうなら、以前の変換をスキップして、はるかに簡単な時間を過ごすことができます. それ以外の場合は、浮動小数点表現を直接操作できる 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;
}

PS: 有価証券の価格をオプションの価格設定エンジンに渡すことはありませんか? まさにその味…。

于 2008-09-12T22:26:20.753 に答える