Geekly Articles each Day

.NETの数匏解析、埮分、単玔化、分数、コンパむル

孊生時代から、分析的導関数を導き出し、衚珟を単玔化するアルゎリズムに興味がありたした。 このタスクは、倧孊の埌半で関連しおいたした。 その埌、それを実装したしたが、すべおが意図した方法ではありたせんでしたILコヌドの代わりに、テキスト圢匏でCコヌドを生成しただけで、アセンブリはアンロヌドされず、さらに分析圢匏で掟生物を導出する方法はありたせんでした しかし、関心が残ったため、そのようなラむブラリを実装するこずにしたした。 むンタヌネット䞊にそのようなラむブラリが倚数あるこずは泚目に倀したすが、ILコヌドに匏をコンパむルする段階、぀たり 実際、コンパむルずは異なり、それほど効果的ではない解釈がどこでも実行されたす。 それに、特に、自分の仕事の結果がどこかで必芁になるこずを特に望んでいないのに、新しい技術を研究するために、私自身のためにそれを開発したした。 せっかちな人 ゜ヌスコヌド 、 プログラム 。

䜿甚枈みのプログラムずラむブラリ


  1. GOLD Parsing System-文法を蚘述し、さたざたな蚀語C、C、Java、JavaScript、Objective-C、Perl、Python、Rubyなどのレクサヌずパヌサヌのコヌドを生成するIDE。 LALR解析に基づいおいたす。
  2. Visual Studio 2010
  3. GOLD.Engine-生成されたテヌブルず察話するために接続された.NETのアセンブリ。
  4. NUnit-.NET甚のオヌプン゜ヌスの単䜓テスト環境。
  5. ILSpy-.NET甚のオヌプン゜ヌス逆アセンブラヌ 。

プロセス党䜓を壊した段階
  1. 匏ツリヌの構築
  2. 分析導関数の蚈算
  3. 匏の簡略化
  4. 合理的な分数凊理
  5. 匏のコンパむル


匏ツリヌの構築


GANTパヌサヌゞェネレヌタヌを遞択したした。ANTLRの経隓があり、新しいものが欲しかったからです。 たあ、その利点は、他ず比范しお、この衚で芋るこずができたす 。 ご芧のずおり、ANTLRず比范するず、GOLDはLLではなくLALRアルゎリズムに基づいおいたす。 これは、理論的には、生成されたパヌサヌはより高速で匷力ですが、䞀方でデバッグできないこずを意味したすGOLDでは、ファむルはバむナリ圢匏でダりンロヌドされたす。可胜であれば、完党に䞍明瞭で䞍䟿です。 もう1぀の倧きな違いは、文法圢匏 EBNFではなくBNFです。 これは、この圢匏で曞かれた文法は、山括匧、定矩の蚘号、条件付きの出珟ず繰り返しの欠劂のためにわずかに倧きいサむズを持぀こずを意味したす  wikiにありたす 。たた、䟋えば、EBNFのようなルヌル

ExpressionList = Expression { ',' Expression }

次の圢匏で曞き換えられたす。

 <ExpressionList> ::= <ExpressionList> ',' <Expression> | <Expression>

したがっお、数匏の最終的な文法は次の圢匏になりたす。

数匏の文法
 "Name" = 'Mathematics expressions' "Author" = 'Ivan Kochurkin' "Version" = '1.0' "About" = '' "Case Sensitive" = False "Start Symbol" = <Statements> Id = {Letter}{AlphaNumeric}* Number1 = {Digit}+('.'{Digit}*('('{Digit}*')')?)? Number2 = '.'{Digit}*('('{Digit}*')')? AddLiteral = '+' | '-' MultLiteral = '*' | '/' <Statements> ::= <Statements> <Devider> <Statement> | <Statements> <Devider> | <Statement> <Devider> ::= ';' | '.' <Statement> ::= <Expression> '=' <Expression> | <Expression> <Expression> ::= <FuncDef> | <Addition> <FuncDef> ::= Id '(' <ExpressionList> ')' | Id '' '(' <ExpressionList> ')' | Id '(' <ExpressionList> ')' '' <ExpressionList> ::= <ExpressionList> ',' <Expression> | <Expression> <Addition> ::= <Addition> AddLiteral <Multiplication> | <Addition> AddLiteral <FuncDef> | <FuncDef> AddLiteral <Multiplication> | <FuncDef> AddLiteral <FuncDef> | <Multiplication> <Multiplication> ::= <Multiplication> MultLiteral <Exponentiation> | <Multiplication> MultLiteral <FuncDef> | <FuncDef> MultLiteral <Exponentiation> | <FuncDef> MultLiteral <FuncDef> | <Exponentiation> <Exponentiation> ::= <Exponentiation> '^' <Negation> | <Exponentiation> '^' <FuncDef> | <FuncDef> '^' <Negation> | <FuncDef> '^' <FuncDef> | <Negation> <Negation> ::= AddLiteral <Value> | AddLiteral <FuncDef> | <Value> <Value> ::= Id | Number1 | Number2 | '(' <Expression> ')' | '|' <Expression> '|' | '(' <Expression> ')' '' | '|' <Expression> '|' '' | Id ''


トヌクンを陀いお、文法ではすべおが明らかなようです Number1 = {Digit} + '。' {Digit} * '' {Digit} * '' この蚭蚈により、次の圢匏の行を解析できたす。0.123456。これは、合理的な小数郚を意味する61111/495000 このような文字列を分数に倉換する方法に぀いおは、埌で説明したす。

したがっお、コンパむル枈みの文法テヌブルコンパむル枈み文法テヌブルファむルが生成され、パヌサヌクラスフレヌムワヌクが䜜成された埌、適切なASTツリヌを構築するために埌者を倉曎する必芁がありたす。 この堎合のパヌサヌクラスフレヌムワヌクは、すべおの文法ルヌルのルヌプ、トヌクンの䞍正なシヌケンスやその他の゚ラヌの堎合の䟋倖凊理を含む.csファむルですちなみに、GOLDにはこのようなフレヌムワヌクの異なるゞェネレヌタヌがあり、Cook .NETを遞択したした したがっお、この堎合、「適切な」ずは、次のタむプを持぀こずができるノヌドで構成されるツリヌを意味したす。


図には、すべおのタむプのノヌドが明確に瀺されおいたす。


文法から、結果のツリヌのノヌドには子倀や倉数などがないか、暙準関数cos、加算、べき乗などの堎合は1〜2個の子があるこずがわかりたす。 他のすべおの関数にはさらに匕数がありたすが、考慮されたせんでした。

したがっお、すべおのノヌドたたは機胜を持぀ノヌドには、0〜2個の子が含たれたす。 これは理論的な芳点から圓おはたりたす。 しかし、実際には、「+」および「*」関数の子の数を無制限にし、埌で怜蚎する単玔化のタスクを容易にする必芁がありたした。 ちなみに、「-」や「/」などのバむナリ挔算も同じ理由で砎棄する必芁がありたした右偎の吊定による加算ず右偎の反転による乗算に眮き換えられたした。

そのため、解析段階で、各ルヌルのすべおのノヌドが萜ちるか、 Nodesずいうバッファヌから取埗されたす。 したがっお、プロセス党䜓の最埌に、右偎ず巊偎の郚分を持぀1぀以䞊の関数がこのバッファヌに残りたす。 たた、構文解析の過皋で、加算関数ず乗算関数が倚囜語ですぐに䜜成されるように、関数の珟圚の匕数の数ず珟圚の関数の型をそれぞれ栌玍する远加のバッファヌArgsCountずArgsFuncTypesが䜿甚されたした。 したがっお、たずえば、乗算関数の堎合、次のコヌドが䜿甚されたす。

最初の乗数の凊理

 // <Multiplication> ::= <Exponentiation> if (MultiplicationMultiChilds) PushFunc(KnownMathFunctionType.Mult);

i番目の乗数の凊理

 // <Multiplication> ::= <Multiplication> MultLiteral <Exponentiation> // <Multiplication> ::= <Multiplication> MultLiteral <FuncDef> if (KnownMathFunction.BinaryNamesFuncs[r[1].Data.ToString()] == KnownMathFunctionType.Div) Nodes.Push(new FuncNode(KnownMathFunctionType.Exp, new MathFuncNode[] { Nodes.Pop(), new ValueNode(-1) })); ArgsCount[ArgsCount.Count - 1]++;

最埌の乗数の凊理

 // <Addition> ::= <Multiplication> if (MultiplicationMultiChilds) PushOrRemoveFunc(KnownMathFunctionType.Mult); if (AdditionMultiChilds) PushFunc(KnownMathFunctionType.Add);


このコヌドは、たずえば、乗算がない堎合、 PushOrRemoveFuncを䜿甚しお芁玠がれロの最埌の乗算関数を削陀する必芁があるこずを瀺しおいたす。 远加するには、同様のアクションを実行する必芁がありたす。

単䞀の匕数の関数、バむナリ関数、定数、倉数、倀の凊理は簡単であり、 MathExprParser.csでこれらすべおを確認できたす。

分析導関数の蚈算


この段階で、関数をその導関数に倉換する必芁がありたす。

最初の段階からわかるように、䜜成された匏ツリヌには4぀のタむプのノヌドしかありたせん5番目のノヌドは埌で衚瀺されたす。 それらに぀いお、導関数を定矩したす。


説明しおみたしょう導関数に぀いおは、事前に準備された衚圢匏の倀を取埗する必芁があり、この倀には導関数があるため、特定の困難が生じたす。 プロセスは本質的に再垰的です。 このような実装された眮換の完党なリストは、以䞋のネタバレの䞋にありたす。

デリバティブのリスト
 (f(x) ^ g(x))' = f(x) ^ g(x) * (f(x)' * g(x) / f(x) + g(x)' * ln(f(x)));"); neg(f(x))' = neg(f(x)');"); sin(f(x))' = cos(f(x)) * f(x)'; cos(f(x))' = -sin(f(x)) * f(x)'; tan(f(x))' = f(x)' / cos(f(x)) ^ 2; cot(f(x))' = -f(x)' / sin(f(x)) ^ 2; arcsin(f(x))' = f(x)' / sqrt(1 - f(x) ^ 2); arccos(f(x))' = -f(x)' / sqrt(1 - f(x) ^ 2); arctan(f(x))' = f(x)' / (1 + f(x) ^ 2); arccot(f(x))' = -f(x)' / (1 + f(x) ^ 2); sinh(f(x))' = f(x)' * cosh(x); cosh(f(x))' = f(x)' * sinh(x); arcsinh(f(x))' = f(x)' / sqrt(f(x) ^ 2 + 1); arcosh(f(x))' = f(x)' / sqrt(f(x) ^ 2 - 1); ln(f(x))' = f(x)' / f(x); log(f(x), g(x))' = g'(x)/(g(x)*ln(f(x))) - (f'(x)*ln(g(x)))/(f(x)*ln(f(x))^2);

すべおの掟生物がコヌド内でハヌドに蚘述されおいるわけではなく、動的に入力および解析するこずもできたす。

䞊蚘のように、これらはいく぀かの匕数を持぀関数であるため、このリストには加算たたは乗算はありたせん。 そしお、そのようなルヌルを解析するには、倚くのコヌドを曞く必芁がありたす。 同じ理由で、機胜の構成はありたせん。 fgx '= fgx' * gx 'の代わりに、すべおの関数は関数の構成ずしお衚されたす。

たた、Derivativesの関数぀たり、未定矩の関数の眮換が芋぀からなかった堎合、それは単にストロヌクのある関数に眮き換えられたす。 fxはfx 'になりたす。

分析導関数が正垞に取埗された埌、結果の匏には、a + 0、a * 1、a * a ^ -1など、倚くの「ガベヌゞ」があるずいう問題が発生したす。たた、結果の匏はより最適な方法で蚈算できたす。 たずえば、単玔な匏であっおも、芋苊しい匏になりたす。

 (x^2 + 2)' = 0 + 2 * 1 * x ^ 1

単玔化は、このような欠点に察凊するために䜿甚されたす。

匏の簡略化


この段階では、導関数を蚈算する段階ずは異なり、単玔な芏則を別の堎所に曞き留めたせんでした。加算ず乗算の関数はいく぀かの匕数の関数であるため、そのような芏則を䜜成するのはある皋床困難です反埩蚀語のコンテキスト。

トピックの冒頭で、加算ず乗算がn項関数ずしお衚される理由のトピックに觊れたした。 䞋の写真に瀺されおいる状況を想像しおください。 ここで、aず-aが省略されおいるこずがわかりたす。 しかし、バむナリ関数の堎合にこれを行う方法は これを行うには、ノヌドa 、 b、およびcを反埩凊理しお、 aおよび-aが同じノヌドの子であるこずを埌で発芋したす。これは、ノヌドずずもにノヌドを削枛できるこずを意味したす。 ただし、右の図に瀺すように、ツリヌを゜ヌトするこずは、単玔なタスクではありたせん。すべおの子を䞀床にすべおのアクションを䞀床に実行する方がはるかに簡単だからです。 ずころで、このような列挙型により、 結合性ず可換性の数孊的特性を䜜成できたす。


単玔化プロセス䞭に、2぀のノヌドを比范するずいう問題が発生したす。2぀のノヌドは、4぀のタむプのいずれかになりたす。 これは、たずえば、sinx + yや-sinx + yなどの匏を枛らすために必芁です。 ノヌドごずにノヌド自䜓ずそのすべおの子孫を比范できるこずは明らかです。 しかし、問題は、この方法では、たずえばsinx + yや-siny + xのように、甚語や因子が再配眮される状況に察凊できないこずです。 この問題を解決するために、可換性の特性が満たされる甚語たたは因子の予備的な゜ヌトが䜿甚されたす぀たり、加算ず枛算。 ノヌドは、次の図に瀺すように比范されたす。 倀は定数より小さい、定数は倉数より小さい、など。 関数の堎合、名前だけでなく匕数の数ず匕数自䜓も比范する必芁があるため、すべおが少し耇雑になりたす。


したがっお、䞊蚘のすべおの倉換ず列挙の埌、元の匏は非垞に単玔化されたす。

合理的な分数凊理


私が芋぀けた合理的な実装では、通垞の文字列型、たずえば0.666666は、特定の分子ず分母を持぀分数型に倉換されたせんでした。 䞀定の粟床で2/3で。 次に、倚くのオプションを䜿甚しお実装を䜜成するこずにしたした。 以䞋の関数は、たずえば、特定の数が玔粋に非合理的であるか、それが呚期たたは有限小数郚を持ち、合理的なもの、たずえば䞀定の粟床でsinpiから0に倉換できるかを決定できたす。 䞀般的に、 stackoverflow.comぞの私の回答のその他の詳现を参照しおください。 メ゜ッドの簡単なグラフィカルな説明を䞋の図に瀺し、コヌドを䞋のリストに瀺したす。 それにもかかわらず、暙準的な数孊関数ずdouble型の粟床は、有理数ず実数の通垞の認識には十分ではありたせんが、理論的にはすべおが機胜するこずに泚意しおください。


小数を小数に倉換
 /// <summary> /// Convert decimal to fraction /// </summary> /// <param name="value">decimal value to convert</param> /// <param name="result">result fraction if conversation is succsess</param> /// <param name="decimalPlaces">precision of considereation frac part of value</param> /// <param name="trimZeroes">trim zeroes on the right part of the value or not</param> /// <param name="minPeriodRepeat">minimum period repeating</param> /// <param name="digitsForReal">precision for determination value to real if period has not been founded</param> /// <returns></returns> public static bool FromDecimal(decimal value, out Rational<T> result, int decimalPlaces = 28, bool trimZeroes = false, decimal minPeriodRepeat = 2, int digitsForReal = 9) { var valueStr = value.ToString("0.0000000000000000000000000000", CultureInfo.InvariantCulture); var strs = valueStr.Split('.'); long intPart = long.Parse(strs[0]); string fracPartTrimEnd = strs[1].TrimEnd(new char[] { '0' }); string fracPart; if (trimZeroes) { fracPart = fracPartTrimEnd; decimalPlaces = Math.Min(decimalPlaces, fracPart.Length); } else fracPart = strs[1]; result = new Rational<T>(); try { string periodPart; bool periodFound = false; int i; for (i = 0; i < fracPart.Length; i++) { if (fracPart[i] == '0' && i != 0) continue; for (int j = i + 1; j < fracPart.Length; j++) { periodPart = fracPart.Substring(i, j - i); periodFound = true; decimal periodRepeat = 1; decimal periodStep = 1.0m / periodPart.Length; var upperBound = Math.Min(fracPart.Length, decimalPlaces); int k; for (k = i + periodPart.Length; k < upperBound; k += 1) { if (periodPart[(k - i) % periodPart.Length] != fracPart[k]) { periodFound = false; break; } periodRepeat += periodStep; } if (!periodFound && upperBound - k <= periodPart.Length && periodPart[(upperBound - i) % periodPart.Length] > '5') { var ind = (k - i) % periodPart.Length; var regroupedPeriod = (periodPart.Substring(ind) + periodPart.Remove(ind)).Substring(0, upperBound - k); ulong periodTailPlusOne = ulong.Parse(regroupedPeriod) + 1; ulong fracTail = ulong.Parse(fracPart.Substring(k, regroupedPeriod.Length)); if (periodTailPlusOne == fracTail) periodFound = true; } if (periodFound && periodRepeat >= minPeriodRepeat) { result = FromDecimal(strs[0], fracPart.Substring(0, i), periodPart); break; } else periodFound = false; } if (periodFound) break; } if (!periodFound) { if (fracPartTrimEnd.Length >= digitsForReal) return false; else { result = new Rational<T>(long.Parse(strs[0]), 1, false); if (fracPartTrimEnd.Length != 0) result = new Rational<T>(ulong.Parse(fracPartTrimEnd), TenInPower(fracPartTrimEnd.Length)); return true; } } return true; } catch { return false; } } public static Rational<T> FromDecimal(string intPart, string fracPart, string periodPart) { Rational<T> firstFracPart; if (fracPart != null && fracPart.Length != 0) { ulong denominator = TenInPower(fracPart.Length); firstFracPart = new Rational<T>(ulong.Parse(fracPart), denominator); } else firstFracPart = new Rational<T>(0, 1, false); Rational<T> secondFracPart; if (periodPart != null && periodPart.Length != 0) secondFracPart = new Rational<T>(ulong.Parse(periodPart), TenInPower(fracPart.Length)) * new Rational<T>(1, Nines((ulong)periodPart.Length), false); else secondFracPart = new Rational<T>(0, 1, false); var result = firstFracPart + secondFracPart; if (intPart != null && intPart.Length != 0) { long intPartLong = long.Parse(intPart); result = new Rational<T>(intPartLong, 1, false) + (intPartLong == 0 ? 1 : Math.Sign(intPartLong)) * result; } return result; } private static ulong TenInPower(int power) { ulong result = 1; for (int l = 0; l < power; l++) result *= 10; return result; } private static decimal TenInNegPower(int power) { decimal result = 1; for (int l = 0; l > power; l--) result /= 10.0m; return result; } private static ulong Nines(ulong power) { ulong result = 9; if (power >= 0) for (ulong l = 0; l < power - 1; l++) result = result * 10 + 9; return result; }


匏のコンパむル


単玔化段階の埌、結果のセマンティックツリヌをILコヌドに倉換するために、Mono.Cecilを䜿甚したした。

プロセスの開始時に、コマンドが蚘述されるアセンブリ、クラス、およびメ゜ッドが䜜成されたす。 次に、各FuncNodeに぀いお、プログラムに衚瀺される回数が蚈算されたす。 たずえば、関数sinx ^ 2* cosx ^ 2がある堎合、その䞭にxを2のべき乗する関数が2回発生し、関数sinずcosが䞀床に1぀ず぀発生したす。 将来、関数蚈算の繰り返しに関するこの情報は、次のように䜿甚されたす぀たり、この方法では、2番目の関数は同じ関数を2回蚈算したせん。

 if (!func.Calculated) { EmitFunc(funcNode); func.Calculated = true; } else IlInstructions.Add(new OpCodeArg(OpCodes.Ldloc, funcNode.Number));


このすべおのコヌドを生成した埌、䞋の図に瀺すように、ILコヌドの他の最適化が可胜です。

この写真では
  1. Ldarg-特定の関数匕数をスタックにロヌドする操䜜。
  2. Ldc_R8-特定のdouble倀をスタックにロヌドしたす。
  3. Stloc.n-スタックから最埌の倀を取埗し、ロヌカル倉数nに保存したす。
  4. Ldloc.n-ロヌカル倉数n をスタックにプッシュしたす。

特定の条件が満たされた堎合、ベヌゞュ色のボックス内の指瀺を削陀できたす。 たずえば、巊䞊の画像の堎合は次のように説明されたす珟圚の呜什が関数から匕数を読み蟌んでいるか、定数を読み蟌んでおり、次の呜什がそれをロヌカル倉数nに保存しおいる堎合、ロヌカル倉数nの読み蟌み呜什を読み蟌みで眮き換えるこずにより、この呜什のブロックを削陀できたす関数の匕数たたは定数の読み蟌み。 ロヌカル倉数nの最初のsaveステヌトメントたで眮換プロセスを続けたす。 他の3぀のケヌスも同様に説明されおいたす。 たずえば、シヌケンスLdloc.n ; Stloc.nはすぐに削陀できたす。

これらの最適化は、コヌドに分岐がない堎合にも適甚できるこずに泚意する䟡倀がありたす。これは明らかです完党に明らかでない堎合は、考えおみるこずをお勧めしたす。 しかし、私の堎合、数孊関数ずその導関数のコヌドにはサむクルを含めるこずができないため、これはすべお機胜したす。

高速べき乗

私は、ほずんど誰もが、力を玠早く力に䞊げるためのアルゎリズムに぀いお知っおいるず思いたす。 ただし、以䞋のアルゎリズムはコンパむルレベルで衚瀺されたす。
ILコヌドに実装された高速べき乗アルゎリズム
 if (power <= 3) { IlInstructions.Add(new OpCodeArg(OpCodes.Stloc, funcNode.Number)); IlInstructions.Add(new OpCodeArg(OpCodes.Ldloc, funcNode.Number)); for (int i = 1; i < power; i++) { IlInstructions.Add(new OpCodeArg(OpCodes.Ldloc, funcNode.Number)); IlInstructions.Add(new OpCodeArg(OpCodes.Mul)); } } else if (power == 4) { IlInstructions.Add(new OpCodeArg(OpCodes.Stloc, funcNode.Number)); IlInstructions.Add(new OpCodeArg(OpCodes.Ldloc, funcNode.Number)); IlInstructions.Add(new OpCodeArg(OpCodes.Ldloc, funcNode.Number)); IlInstructions.Add(new OpCodeArg(OpCodes.Mul)); IlInstructions.Add(new OpCodeArg(OpCodes.Stloc, funcNode.Number)); IlInstructions.Add(new OpCodeArg(OpCodes.Ldloc, funcNode.Number)); IlInstructions.Add(new OpCodeArg(OpCodes.Ldloc, funcNode.Number)); IlInstructions.Add(new OpCodeArg(OpCodes.Mul)); } else { // result: funcNode.Number // x: funcNode.Number + 1 //int result = x; IlInstructions.Add(new OpCodeArg(OpCodes.Stloc, funcNode.Number + 1)); IlInstructions.Add(new OpCodeArg(OpCodes.Ldloc, funcNode.Number + 1)); power--; do { if ((power & 1) == 1) { IlInstructions.Add(new OpCodeArg(OpCodes.Ldloc, funcNode.Number + 1)); IlInstructions.Add(new OpCodeArg(OpCodes.Mul)); } if (power <= 1) break; //x = x * x; IlInstructions.Add(new OpCodeArg(OpCodes.Ldloc, funcNode.Number + 1)); IlInstructions.Add(new OpCodeArg(OpCodes.Ldloc, funcNode.Number + 1)); IlInstructions.Add(new OpCodeArg(OpCodes.Mul)); IlInstructions.Add(new OpCodeArg(OpCodes.Stloc, funcNode.Number + 1)); power = power >> 1; } while (power != 0); }


高速环乗アルゎリズムは最適な环乗アルゎリズムではないこずに泚意しおください。 たずえば、次の2぀の方法で同じ倉数を5回乗算したす。 x ^ 4 + x ^ 3 + x ^ 2 + x = x *x *x *x + 1+ 1+ 1などの最適化も実装されおいたせん。



ずころで、通垞の固定数doubleの堎合、䞊蚘の乗算の異なる順序での乗算の結果は異なるこずに泚意しおください぀たりa ^ 2^ 2 * a ^ 2=A ^ 3^ 2  このため、䞀郚のコンパむラはこれらの匏の倚くを最適化したせん。 stackoverlofwにはこれに関する興味深いQAがありたす。 なぜGCCはa * a * a * a * a * aをa * a * a*a * a * aに最適化しないのですか そしお、 なぜMath.Powx、2はx * xコンパむラヌにもJITにも最適化されおいないのですか 。

ロヌカル倉数の最適化

前の手順からわかるように、ロヌカル倉数は、元の匏で耇数回発生するすべおの関数の結果を栌玍するために䜿甚されたす。 ロヌカル倉数を操䜜するには、2぀の単玔な呜什stlocずldlocのみが䜿甚されたす。これらは、このロヌカル倉数の数を担圓する1぀の匕数を䜿甚したす。 ただし、ロヌカル倉数の数が、蚈算結果が繰り返し衚瀺されるたびに䜜成するためにむンクリメントされる堎合、ロヌカル倉数が倚数存圚する可胜性がありたす。 この問題を軜枛するために、ロヌカル倉数のラむフサむクルを圧瞮するアルゎリズムが実装されたした。そのプロセスは䞋の図に明確に瀺されおいたす。 ご芧のずおり、匏では5぀のロヌカル倉数の代わりに3぀しか䜿甚できたせん。ただし、この「貪欲な」アルゎリズムは最適な順列ではありたせんが、実装するタスクには非垞に適しおいたす。

未定矩の関数ずその掟生物のコンパむル

開発したラむブラリでは、fxずいう圢匏の1぀の倉数の単玔な関数だけでなく、fx、a、bxなどの他の倉数も䜿甚できたす。ここで、aは未知の定数で、bxは未知の関数ですデリゲヌトずしお送信されたす。 ご存知のように、関数の導関数の定矩は次のずおりですbx '=bx + dx-bx/ dx。 , :
 ldarg.1 ldarg.0 callvirt TResult System.Func`2<System.Double,System.Double>::Invoke(T) ret

(dx = 0.000001)
 ldarg.1 ldarg.0 ldc.r8 1E-06 add callvirt TResult System.Func`2<System.Double,System.Double>::Invoke(T) ldarg.1 ldarg.0 callvirt TResult System.Func`2<System.Double,System.Double>::Invoke(T) sub ldc.r8 0.000001 div ret


, , .



テスト䞭


, MathFunction.Tests. WolframAlpha.NET .

WolframAlpha

WolframAlpha.NET — API wolframalpha . , , , , . :

 public static bool CheckDerivative(string expression, string derivative) { return CheckEquality("diff(" + expression + ")", derivative); } public static bool CheckEquality(string expression1, string expression2) { WolframAlpha wolfram = new WolframAlpha(ConfigurationManager.AppSettings["WolframAlphaAppId"]); string query = "(" + expression1.Replace(" ", "") + ")-(" + expression2.Replace(" ", "") + ")"; QueryResult result = wolfram.Query(query); result.RecalculateResults(); try { double d; return double.TryParse(result.GetPrimaryPod().SubPods[0].Plaintext, out d) && d == 0.0; } catch { return false; } }



, , (MethodInfo):

 Domain = AppDomain.CreateDomain("MathFuncDomain"); MathFuncObj = _domain.CreateInstanceFromAndUnwrap(FileName, NamespaceName + "." + ClassName); Type mathFuncObjType = _mathFuncObj.GetType(); Func = mathFuncObjType.GetMethod(FuncName); FuncDerivative = mathFuncObjType.GetMethod(FuncDerivativeName);


:
 return (double)Func.Invoke(_mathFuncObj, new object[] { x })


:
 if (_domain != null) AppDomain.Unload(Domain); File.Delete(FileName);


IL

IL , , C# csc.exe Release ,
 x ^ 3 + sin(3 * ln(x * 1)) + x ^ ln(2 * sin(3 * ln(x))) - 2 * x ^ 3

csc.exe .NET 4.5.1MathExpressions.NET
 IL_0000: ldarg.0 IL_0001: ldarg.0 IL_0002: mul IL_0003: ldarg.0 IL_0004: mul IL_0005: ldc.r8 3 IL_000e: ldarg.0 IL_000f: ldc.r8 1 IL_0018: mul IL_0019: call float64 [mscorlib]System.Math::Log(float64) IL_001e: mul IL_001f: call float64 [mscorlib]System.Math::Sin(float64) IL_0024: add IL_0025: ldarg.0 IL_0026: ldc.r8 2 IL_002f: ldc.r8 3 IL_0038: ldarg.0 IL_0039: call float64 [mscorlib]System.Math::Log(float64) IL_003e: mul IL_003f: call float64 [mscorlib]System.Math::Sin(float64) IL_0044: mul IL_0045: call float64 [mscorlib]System.Math::Log(float64) IL_004a: call float64 [mscorlib]System.Math::Pow(float64, float64) IL_004f: add IL_0050: ldc.r8 2 IL_0059: ldarg.0 IL_005a: mul IL_005b: ldarg.0 IL_005c: mul IL_005d: ldarg.0 IL_005e: mul IL_005f: sub IL_0060: ret 

 IL_0000: ldc.r8 3 IL_0009: ldarg.0 IL_000a: call float64 [mscorlib]System.Math::Log(float64) IL_000f: mul IL_0010: call float64 [mscorlib]System.Math::Sin(float64) IL_0015: stloc.0 IL_0016: ldloc.0 IL_0017: ldarg.0 IL_0018: ldarg.0 IL_0019: mul IL_001a: ldarg.0 IL_001b: mul IL_001c: sub IL_001d: ldarg.0 IL_001e: ldc.r8 2 IL_0027: ldloc.0 IL_0028: mul IL_0029: call float64 [mscorlib]System.Math::Log(float64) IL_002e: call float64 [mscorlib]System.Math::Pow(float64, float64) IL_0033: add IL_0034: ret


, C# ILSpy , , .. に
 (ln(2 * sin(3 * ln(x))) * x ^ -1 + 3 * ln(x) * cos(3 * ln(x)) * sin(3 * ln(x)) ^ -1 * x ^ -1) * x ^ ln(2 * sin(3 * ln(x))) + 3 * cos(3 * ln(x)) * x ^ -1 + -(3 * x ^ 2) 

 double arg_24_0 = 2.0; double arg_1A_0 = 3.0; double num = Math.Log(x); double num2 = arg_1A_0 * num; double num3 = Math.Sin(num2); double num4 = Math.Log(arg_24_0 * num3); double arg_3B_0 = num4; double num5 = 1.0 / x; double arg_54_0 = arg_3B_0 * num5; double arg_4F_0 = 3.0 * num; num = Math.Cos(num2); return (arg_54_0 + arg_4F_0 * num / num3 * num5) * Math.Pow(x, num4) + num * num5 * 3.0 - x * x * 3.0;

, . , , , double arg_24_0 = 2.0; , .

, , , , , .

おわりに


C#, , , - . , , OpenSource maxima lisp. , F# codeproject , , . , , , .

Github: source . : MathExpressions.NET . . - .

PS , . .

UPDATE: , , . , . .

Source: https://habr.com/ru/post/J150043/

More articles:


All Articles