A Taylor expansion differentiates without simplifying, so sin(x)/x to 11 terms runs out of memory

未關閉
  • 哪裡不對？
#2,291 0 則留言 0 個 reaction 已指派 0 人 在 GitHub 檢視

維護者通常 1 天內回覆

已經有一個關聯 PR 被合併了。

  • #2302 來自 @Rafael-SOWNet —— 已合併

評估

難度
4/5
預估耗時
3-5 天
新手友好度
55/100
Issue 類型
缺陷
描述清晰度
基本清楚
活躍度
活躍
技術堆疊
csharp
領域
performance

研究方向

Start with Sources/AngouriMath/Functions/Series.cs, especially SingleTaylorExpansionTerms and MultivariableTaylorExpansionTerms. Reproduce the reported Taylor(sin(x) / x, 11, ("x", 1)) case and compare the derivative growth and runtime. Done means the requested expansion completes efficiently without computing and discarding an extra term; the expected behavior at x = 0 needs triage.

由索引模型根據 Issue 內容生成。

描述

MathS.Series.Taylor on master (87a0eff), with the heap capped at 4 GB:

Answered
Taylor(sin(x) / x, 7, ("x", 1)) 36 421 characters, 1.4 s
Taylor(sin(x) / x, 9, ("x", 1)) 2 039 500 characters, 87 s
Taylor(sin(x) / x, 11, ("x", 1)) OutOfMemoryException in SingleTaylorExpansion after 89 s
Taylor(sin(x) / x, 11, ("x", 0)) OutOfMemoryException after 42 s; without the cap, on an earlier build, the process passed 35 GB before it was killed
Taylor(sin(x) / x, 4, ("x", 0)) NaN + NaN + NaN / 2! + NaN / 3!

The cause is in SingleTaylorExpansionTerms: each derivative is taken from the previous one as it stands (currExpr = currExpr.Differentiate(exprVariable)), and only the term built from it is simplified. For a quotient the tree grows about eightfold per step:

k nodes of the k-th derivative, as differentiated simplified before the next step
1 11 11
3 122 33
5 2 647 47
7 110 799 69
9 7 797 110 87

Simplifying each derivative before taking the next gives the 11 terms at x = 1 in 0.85 s. Two smaller points in the same place:

  • SingleTaylorExpansion checks terms.Count >= termCount only after the iterator has produced the next term, so one derivative more than is kept (the largest) is taken, substituted and simplified, then dropped. MultivariableTaylorExpansion has the same order.
  • MultivariableTaylorExpansionTerms differentiates the partial derivatives unsimplified in the same way.

What it should have done: answer Taylor(sin(x) / x, 11, ("x", 1)) in about a second. At x = 0, sin(x) / x has no value, so every coefficient is NaN; the expansion should say that once (the step-simplified loop above answers NaN), or expand the continuous extension 1 - x^2/6 + x^4/120 - ..., which is a choice for triage, instead of differentiating ten times to print a sum of NaNs.

Found while building a Taylor-polynomial view for browser demos of the library.

主要語言
C#
星號
831
分支
79
平均合併
1 小時 11 分鐘
30 天內合併 PR
523

環境準備

  • 沒有 Dockerfile 或 Docker Compose 檔案
  • 沒有 Pull Request 範本
  • 閱讀貢獻指南

從這裡開始

  1. 先讀完整個 Issue，再讀專案的貢獻指南。
  2. 在 Issue 下留言說明你要接手 —— 這能避免兩個人做同樣的事。
  3. Fork 儲存庫，在一個分支上完成修改。
  4. 送出 Pull Request，並在描述裡引用這個 Issue 編號。

ASC-Community/AngouriMath 的其他 Issue

查看 ASC-Community/AngouriMath 的全部 Issue

相似的 Issue

更多 C# Issue

把新 issue 寄到你的電子郵件信箱

精選適合新手參與的 GitHub issue 摘要。