Talk:ITP method

This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Articles for creation This article was reviewed by member(s) of WikiProject Articles for creation. The project works to allow users to contribute quality articles and media files to the encyclopedia and track their progress as they are developed. To participate, please visit the project page for more information.Articles for creationWikipedia:WikiProject Articles for creationTemplate:WikiProject Articles for creationAfC This article was accepted from this draft on 4 January 2021 by reviewer Eumat114 (talk · contribs). Mathematics Low‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Low This article has been rated as Low-priority on the project's priority scale.

One of the weak spots in this article is how to tune the κ {\displaystyle \kappa } parameters, particularly κ 1 {\displaystyle \kappa _{1}} . The original paper discusses the question a bit, but doesn't itself give any clear guidance. After a bit of experimentation (mostly on inverse arc length problems), I'm pretty confident that κ 2 = 2 {\displaystyle \kappa _{2}=2} is a reasonable default choice, suitable in most cases unless experiment or analysis strongly suggests a different value. But κ 1 {\displaystyle \kappa _{1}} is a bit of a different question. The current example in this article uses a value of 0.1 {\displaystyle 0.1} , which is the same numerical value as the examples in the paper, but I think that fact is a bit misleading. The examples in the paper have b − a = 2 {\displaystyle b-a=2} , while the example here has b − a = 1 {\displaystyle b-a=1} , and there is scaling involved. If κ 2 = 2 {\displaystyle \kappa _{2}=2} , then I think the heuristic that captures the intent of the paper is κ 1 = 0.2 / ( b − a ) {\displaystyle \kappa _{1}=0.2/(b-a)} , and this is what I have documented in the kurbo implementation. Also note, if the example were to adopt this recommendation, then n 0 = 0 {\displaystyle n_{0}=0} would work with fast convergence; I think you can say that you need more "slack" as provided by n 0 {\displaystyle n_{0}} when κ 1 {\displaystyle \kappa _{1}} is lowballed.

On that last point, I feel like I might be skating a little close to the edge of WP:NOR here. I personally consider an open source project such as kurbo a reasonably reliable source, but can see how others may feel differently. Ideally there would be some survey paper or textbook chapter that we could cite, but, partly due to the technique being so new, there's precious little out there. I'm going to shamelessly self-promote in the interest of providing useful resources to readers, but open to hearing better ways to handle this. Raph Levien (talk) 16:19, 5 April 2021 (UTC)[reply]

Raph Levien, I have added a small note to link to your library (I *feel* that's compliant to NOR). Cheers 🦀🍺. --Artoria2e5 🌉 12:56, 4 July 2021 (UTC)[reply]

Oh, while we are at it, I feel the description has a gap in the description of n 0 {\displaystyle n_{0}} . The paper (and this Wikipedia article) only mentions it's ≥ 0, while your documentation seems to suggest a smaller useful range of [0,1] further constrained by the optimization to use usize? --Artoria2e5 🌉 13:13, 4 July 2021 (UTC)[reply]

As the WP:NOR policy does not apply to Talk pages, I think it's OK to share a some yet-unpublished recommendations here: I have conducted a quasi Monte Carlo parametric study of epsilon and n 0 {\displaystyle n_{0}} , using two alternative monotonic curves of the form y = x ( ( 1 / c ) − 1 ) {\displaystyle y=x^{((1/c)-1)}} and y = 1 − ( 1 − x ) ( c / ( 1 − c ) ) {\displaystyle y=1-(1-x)^{(c/(1-c))}} , where c {\displaystyle c} is a ranomized constant in the range c ∈ ( 0 , 1 ) {\displaystyle c\in (0,1)} , and x {\displaystyle x} is in the range x ∈ ( 0 , 1 ) {\displaystyle x\in (0,1)} . Simulations were conducted in Visual Basic (machine floating-point epsilon = 1E-15). κ 2 = 2 {\displaystyle \kappa _{2}=2} was kept constant for reasons given above. My findings are as follows:

• I tried values 1E-16 ≤ ϵ ≤ {\displaystyle \leq \epsilon \leq } 0.1, in steps of factor 10.
• As ϵ {\displaystyle \epsilon } is reduced, the number of iterations increases and precision improves. However this effect levels out for small values of ϵ ≤ {\displaystyle \epsilon \leq } 1E-10.
• For large values of ϵ {\displaystyle \epsilon } : 1E-9 to 0.1, there is little benefit of this algorithm compared to basic Bisection, both in terms of number of iterations, and precision of x I T P {\displaystyle x_{ITP}} .
• For small values of ϵ {\displaystyle \epsilon } : 1E-16 to 1E-10, there is negligible difference in performance, both in terms of number of iterations and precision of x I T P {\displaystyle x_{ITP}} . It levels out, with median 8 iterations.
• Therefore I recommend to set ϵ {\displaystyle \epsilon } equal to the machine epsilon (1E-15 in my case), as there are no drawbacks compared to using lower precision.

• I tried values 0 ≤ n 0 ≤ 20 {\displaystyle 0\leq n_{0}\leq 20} in steps of +1, and from 20 up to 50 in steps of +10. This was repeated for a range of κ 1 {\displaystyle \kappa _{1}} values; see below. Results here apply for a wide-range of κ 1 {\displaystyle \kappa _{1}} values.
• n 0 = 0 {\displaystyle n_{0}=0} is identical to Bisection.
• n 0 = 1 {\displaystyle n_{0}=1} halves the number of iterations compared to Bisection, and improved precision of x I T P {\displaystyle x_{ITP}} (median 100000 times more accurate, and 3rd quartile 30 times more accurate), assuming small ϵ ≤ {\displaystyle \epsilon \leq } 1E-10.
• Increasing n 0 {\displaystyle n_{0}} further (i.e. n 0 = 2 {\displaystyle n_{0}=2} and higher) leads to further improvements in precision (median and Q3 statistics) with the added benefit of reducing the Mean number of iterations (median and Q3 remain static). The effect levels out exponentially, with no further improvement over 17 ≤ n 0 {\displaystyle 17\leq n_{0}} .
• The maximum possible number of iterations increases with n 0 {\displaystyle n_{0}} : Max iterations = n b i s e c t i o n + n 0 {\displaystyle n_{bisection}+n_{0}} . However, the likelihood of this hapening sinks for higher n 0 {\displaystyle n_{0}} , so the Mean number of iterations actually sinks for higher n 0 {\displaystyle n_{0}} , but the effect levels out exponentially, with a minimum in the range n 0 {\displaystyle n_{0}} = 14 to 17, as mentioned above.
• Thus I recommend n 0 = 14 {\displaystyle n_{0}=14} as an all-round value. I see little benefit in developing adaptive algorithms that automatically tune n 0 {\displaystyle n_{0}} , as I found little difference in the range 11 ≤ n 0 ≤ 20 {\displaystyle 11\leq n_{0}\leq 20} .

• I tried scaling factors in the range 0.01 <= f <= 1.00 {\displaystyle 0.01<=f<=1.00} in increments of 0.01, in calculating κ 1 = f / ( x b − x a ) {\displaystyle \kappa _{1}=f/(x_{b}-x_{a})} .
• The arithmentic mean number iterations reduces exponentially as f {\displaystyle f} increases from zero towards approx 0.33, above which the number of iterations flattens out in the region 0.33 < f <= 0.58 {\displaystyle 0.33<f<=0.58} , so the optimal value of f {\displaystyle f} may be anywhere in this region. Above 0.58 ≤ f {\displaystyle 0.58\leq f} , the number of iterations increaces again gradually.
• The median number of iterations is minimum in the range 0.08 <= f <= 0.33 {\displaystyle 0.08<=f<=0.33} , and the third-quartile is minimum in the range 0.33 <= f <= 0.58 {\displaystyle 0.33<=f<=0.58} .
• Thus I recommend κ 1 = 0.33 / ( x b − x a ) {\displaystyle \kappa _{1}=0.33/(x_{b}-x_{a})} as an all-round value, together with n 0 = 14 {\displaystyle n_{0}=14} and ϵ = {\displaystyle \epsilon =} 1E-15, which worked well for the large range of monotonic function shapes that I tested. This gives a mean number of iterations (9.8) that is a third that of Bisection (30). This finding is obviously influenced by the distribution of monotonic function shapes that I tried.

Comment written by Peter.schild (talk) 15:28, 2 January 2023 (UTC)[reply]

In the computation of ρ k ≡ min { ϵ 2 n 1 / 2 + n 0 − j − b − a 2 , | x t − x 1 / 2 | } {\displaystyle \rho _{k}\equiv \min \left\{\epsilon 2^{n_{1/2}+n_{0}-j}-{\frac {b-a}{2}},|x_{t}-x_{1/2}|\right\}} , the term ϵ 2 n 1 / 2 + n 0 − j − b − a 2 {\displaystyle \epsilon 2^{n_{1/2}+n_{0}-j}-{\frac {b-a}{2}}} must be non-negative. Round-off errors could result in a negative value for this term, and this can cause the algorithm to be unstable. This is explained in the ITP paper, but it is not shown in the Algorithm in the ITP paper. So it should be ρ k ≡ min { max { 0 , ϵ 2 n 1 / 2 + n 0 − j − b − a 2 } , | x t − x 1 / 2 | } {\displaystyle \rho _{k}\equiv \min \left\{\max \left\{0,\epsilon 2^{n_{1/2}+n_{0}-j}-{\frac {b-a}{2}}\right\},|x_{t}-x_{1/2}|\right\}} . One should also add r=max(0,r) in the pseudo-code. One should also subtract the unit of least precision before computing max(0,r), so the full expression should be r=max(0,r-ulp(r)). This is also in the ITP paper. One last interesting fact is that if r is ever equal to 0, then the ITP algorithm is the same as the bisection algorithm, so one can check for this case and switch to the bisection algorithm. KennethBaclawski (talk) 16:34, 22 March 2023 (UTC)[reply]

P.S. Yes, this is explained in Appendix B in the original paper. For programming languages that don't have the ULP() function, one can use ρ = max { 0 , ρ k − ϵ | ρ k | } {\displaystyle \rho =\max\{0,\rho _{k}-\epsilon |\rho _{k}|\}} Peter.schild (talk) 06:42, 16 May 2023 (UTC)[reply]

A practitioner technique that attempts to address a similar issue is to perform the three steps in a diffeerent order: Interpolate, Project and then Truncate. When inverting the order of the last two steps then only the last one needs to make sure the truncation step still produces an estimate inside the desired region. Trojan.chess (talk) 22:48, 12 November 2024 (UTC)[reply]

I would like someone to verify, but I am almost positive that the algorithm listed is wrong. It says to check if 0}"> y I T P > 0 {\displaystyle y_{ITP}>0} , when in reality it should be a check to see if 0}"> y T I P ∗ y b > 0 {\displaystyle y_{TIP}*y_{b}>0} . After I changed, that I was able to get the algorithm working and it's backed up by this code I found online. https://github.com/paulnorthrop/itp/blob/c5277bad81024600e16ad9b135449700661ef67a/src/itp_c.cpp — Preceding unsigned comment added by Smith1234567 (talk • contribs) 00:19, 30 January 2026 (UTC)[reply]