Nabble has removed Mailing-list integration.
Posts created here DO NOT GET SENT TO THE MAILING LIST.
Mailing-list emails DO NOT GET POSTED TO THE FORUM.
So basically the Forum is now out of date, we are looking into migrating the history.

# Recursive Binary Chop Classic List Threaded 21 messages 12
Open this post in threaded view
|

## Recursive Binary Chop

 I had a complicated function to calculate an area according to its one argument. The function was monotonic. There was then a need to find the argument value which gave a specific area - an inverse function was created. Its arguments are the input value to be looked up                      lowest start value and its function                     highest start value and its function                     required accuracy               InvFF performs a binary chop until the upper and lower values are within the required accuracy //---------------------------------------------------------------------------------------- // test out with a simple inverse sin // sin(T) goes between 0 and 1 for angles 0 : 90 // if we give the recursive function a number 0 : 1, we want the angle 0 : 90 //------------------------------------------------------------------------------- function FF(A) = sin(A); //------------------------------------------------------------------------------- function InvFF(Value,LowArg,LowValue,HighArg,HighValue,Accuracy) =   let(MidArg = (HighArg + LowArg)/2)     abs(HighValue - LowValue)/(HighValue + LowValue) < 2*Accuracy     ?   MidArg                                    // Stop here with best answer     :   FF(MidArg) > Value               ? InvFF(Value,LowArg,LowValue,MidArg,FF(MidArg),Accuracy)     // too high       : InvFF(Value,MidArg,FF(MidArg),HighArg,HighValue,Accuracy);   // too low //------------------------------------------------------------------------------ LowestValue     =   0;      // for this test HighestValue    =   90;     // for this test // lookup the angle which gives a sine of 0.5 - ie 30 degrees echo(InvFF(0.5, LowestValue, FF(LowestValue), HighestValue, FF(HighestValue), 0.00001)); returns ECHO: 29.9999 Sent from the OpenSCAD mailing list archive at Nabble.com._______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email]
Open this post in threaded view
|

## Re: Recursive Binary Chop

 Nice!On Sat, May 15, 2021 at 12:10 PM GregL <[hidden email]> wrote:I had a complicated function to calculate an area according to its one argument. The function was monotonic. There was then a need to find the argument value which gave a specific area - an inverse function was created. Its arguments are the input value to be looked up                      lowest start value and its function                     highest start value and its function                     required accuracy               InvFF performs a binary chop until the upper and lower values are within the required accuracy //---------------------------------------------------------------------------------------- // test out with a simple inverse sin // sin(T) goes between 0 and 1 for angles 0 : 90 // if we give the recursive function a number 0 : 1, we want the angle 0 : 90 //------------------------------------------------------------------------------- function FF(A) = sin(A); //------------------------------------------------------------------------------- function InvFF(Value,LowArg,LowValue,HighArg,HighValue,Accuracy) =   let(MidArg = (HighArg + LowArg)/2)     abs(HighValue - LowValue)/(HighValue + LowValue) < 2*Accuracy     ?   MidArg                                    // Stop here with best answer     :   FF(MidArg) > Value               ? InvFF(Value,LowArg,LowValue,MidArg,FF(MidArg),Accuracy)     // too high       : InvFF(Value,MidArg,FF(MidArg),HighArg,HighValue,Accuracy);   // too low //------------------------------------------------------------------------------ LowestValue     =   0;      // for this test HighestValue    =   90;     // for this test // lookup the angle which gives a sine of 0.5 - ie 30 degrees echo(InvFF(0.5, LowestValue, FF(LowestValue), HighestValue, FF(HighestValue), 0.00001)); returns ECHO: 29.9999 Sent from the OpenSCAD mailing list archive at Nabble.com._______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email]
Open this post in threaded view
|

## Re: Recursive Binary Chop

 Yes, nice, I have written one or two binary chops to do things like space two pulleys for a closed belt, which surprisingly has no algebraic formula, like the circumference of an ellipse. But it was before function literals, so not generic.On Sat, 15 May 2021 at 20:36, Leonard Martin Struttmann <[hidden email]> wrote:Nice!On Sat, May 15, 2021 at 12:10 PM GregL <[hidden email]> wrote:I had a complicated function to calculate an area according to its one argument. The function was monotonic. There was then a need to find the argument value which gave a specific area - an inverse function was created. Its arguments are the input value to be looked up                      lowest start value and its function                     highest start value and its function                     required accuracy               InvFF performs a binary chop until the upper and lower values are within the required accuracy //---------------------------------------------------------------------------------------- // test out with a simple inverse sin // sin(T) goes between 0 and 1 for angles 0 : 90 // if we give the recursive function a number 0 : 1, we want the angle 0 : 90 //------------------------------------------------------------------------------- function FF(A) = sin(A); //------------------------------------------------------------------------------- function InvFF(Value,LowArg,LowValue,HighArg,HighValue,Accuracy) =   let(MidArg = (HighArg + LowArg)/2)     abs(HighValue - LowValue)/(HighValue + LowValue) < 2*Accuracy     ?   MidArg                                    // Stop here with best answer     :   FF(MidArg) > Value               ? InvFF(Value,LowArg,LowValue,MidArg,FF(MidArg),Accuracy)     // too high       : InvFF(Value,MidArg,FF(MidArg),HighArg,HighValue,Accuracy);   // too low //------------------------------------------------------------------------------ LowestValue     =   0;      // for this test HighestValue    =   90;     // for this test // lookup the angle which gives a sine of 0.5 - ie 30 degrees echo(InvFF(0.5, LowestValue, FF(LowestValue), HighestValue, FF(HighestValue), 0.00001)); returns ECHO: 29.9999 Sent from the OpenSCAD mailing list archive at Nabble.com._______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email]
Open this post in threaded view
|

## Re: Recursive Binary Chop

 CONTENTS DELETED The author has deleted this message.
Open this post in threaded view
|

## Re: Recursive Binary Chop

Open this post in threaded view
|

## Re: Recursive Binary Chop

 CONTENTS DELETED The author has deleted this message.
Open this post in threaded view
|

## Re: Recursive Binary Chop

 I think the standard name for this algorithm in the context of root finding is Bisection.  I've never heard "binary chop" before and "binary search" to me refers to searching a sorted list, not root finding.   https://en.wikipedia.org/wiki/Bisection_methodThe spacing for two pulleys seems like a problem that does have a closed form solution.  I worked out math to make models like the one below with varying radii at each end and separation and it was all simple trig. CraigLindley wrote OK I've always called this a binary search. The term binary chop is new to me. Thanks for enlightening me. On Sat, May 15, 2021 at 3:58 PM nop head <[hidden email]> wrote: > You start with two extreme values that you assume to be either side of the > solution. Then you pick the midpoint and decide if the solution is between > the first point and the mid or the mid and the second, so you get a smaller > range for the solution and then recurse until the ends points are close > enough for your desired accuracy. > > On Sat, 15 May 2021 at 21:51, craig and heather <[hidden email]> wrote: > >> Could someone define what a binary chop is? >> >> On Sat, May 15, 2021 at 2:04 PM nop head <[hidden email]> wrote: >> >>> Yes, nice, I have written one or two binary chops to do things like >>> space two pulleys for a closed belt, which surprisingly has no >>> algebraic formula, like the circumference of an ellipse. But it was before >>> function literals, so not generic. >>> >>> On Sat, 15 May 2021 at 20:36, Leonard Martin Struttmann < >>> [hidden email]> wrote: >>> >>>> Nice! >>>> >>>> On Sat, May 15, 2021 at 12:10 PM GregL <[hidden email]> >>>> wrote: >>>> >>>>> I had a complicated function to calculate an area according to its one >>>>> argument. The function was monotonic. >>>>> There was then a need to find the argument value which gave a specific >>>>> area - an inverse function was created. >>>>> Its arguments are the input value to be looked up >>>>>                      lowest start value and its function >>>>>                     highest start value and its function >>>>>                     required accuracy >>>>> >>>>> InvFF performs a binary chop until the upper and lower values are >>>>> within the required accuracy >>>>> >>>>> >>>>> //---------------------------------------------------------------------------------------- >>>>> >>>>> // test out with a simple inverse sin >>>>> // sin(T) goes between 0 and 1 for angles 0 : 90 >>>>> // if we give the recursive function a number 0 : 1, we want the angle >>>>> 0 : 90 >>>>> //------------------------------------------------------------------------------- >>>>> >>>>> function FF(A) = sin(A); >>>>> //------------------------------------------------------------------------------- >>>>> >>>>> function InvFF(Value,LowArg,LowValue,HighArg,HighValue,Accuracy) >>>>> =   let(MidArg = (HighArg + LowArg)/2) >>>>>     abs(HighValue - LowValue)/(HighValue + LowValue) < 2*Accuracy >>>>>     ?   MidArg                                    // Stop here with >>>>> best answer >>>>>     :   FF(MidArg) > Value >>>>>       ? InvFF(Value,LowArg,LowValue,MidArg,FF(MidArg),Accuracy)     // >>>>> too high >>>>>       : InvFF(Value,MidArg,FF(MidArg),HighArg,HighValue,Accuracy); >>>>> // too low >>>>> //------------------------------------------------------------------------------ >>>>> >>>>> LowestValue     =   0;      // for this test >>>>> HighestValue    =   90;     // for this test >>>>> // lookup the angle which gives a sine of 0.5 - ie 30 degrees >>>>> echo(InvFF(0.5, LowestValue, FF(LowestValue), HighestValue, >>>>> FF(HighestValue), 0.00001)); >>>>> >>>>> returns >>>>> ECHO: 29.9999 >>>>> >>>>> >>>>> ------------------------------ >>>>> Sent from the OpenSCAD mailing list archive >>>>>  at Nabble.com. >>>>> _______________________________________________ >>>>> OpenSCAD mailing list >>>>> To unsubscribe send an email to [hidden email]>>>>> >>>> _______________________________________________ >>>> OpenSCAD mailing list >>>> To unsubscribe send an email to [hidden email]>>>> >>> _______________________________________________ >>> OpenSCAD mailing list >>> To unsubscribe send an email to [hidden email]>>> >> >> >> -- >> Craig Lindley / Heather Hubbard >> >> New Recordings are here >> >> Personal Website is here >> >> Please call the Rockrimmon house. Our cell phones don't work at home. >> Rockrimmon House: (719) 426-9873 >> Craig's Cell: (719) 502-7925 >> Heather's Cell: (719) 571-0944 >> >> If you’re one in a million, there are now more than seven thousand people >> exactly like you. >> _______________________________________________ >> OpenSCAD mailing list >> To unsubscribe send an email to [hidden email]>> > _______________________________________________ > OpenSCAD mailing list > To unsubscribe send an email to [hidden email]> -- Craig Lindley / Heather Hubbard New Recordings are here Personal Website is here Please call the Rockrimmon house. Our cell phones don't work at home. Rockrimmon House: (719) 426-9873 Craig's Cell: (719) 502-7925 Heather's Cell: (719) 571-0944 If you’re one in a million, there are now more than seven thousand people exactly like you. _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] Sent from the OpenSCAD mailing list archive at Nabble.com._______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email]
Open this post in threaded view
|

## Re: Recursive Binary Chop

 In reply to this post by GregL Binary chop can work for this but Newton Raphson should do it in less iterations  https://en.wikipedia.org/wiki/Newton%27s_methodOn Sun, May 16, 2021 at 1:09 AM GregL <[hidden email]> wrote:I had a complicated function to calculate an area according to its one argument. The function was monotonic. There was then a need to find the argument value which gave a specific area - an inverse function was created. Its arguments are the input value to be looked up                      lowest start value and its function                     highest start value and its function                     required accuracy               InvFF performs a binary chop until the upper and lower values are within the required accuracy //---------------------------------------------------------------------------------------- // test out with a simple inverse sin // sin(T) goes between 0 and 1 for angles 0 : 90 // if we give the recursive function a number 0 : 1, we want the angle 0 : 90 //------------------------------------------------------------------------------- function FF(A) = sin(A); //------------------------------------------------------------------------------- function InvFF(Value,LowArg,LowValue,HighArg,HighValue,Accuracy) =   let(MidArg = (HighArg + LowArg)/2)     abs(HighValue - LowValue)/(HighValue + LowValue) < 2*Accuracy     ?   MidArg                                    // Stop here with best answer     :   FF(MidArg) > Value               ? InvFF(Value,LowArg,LowValue,MidArg,FF(MidArg),Accuracy)     // too high       : InvFF(Value,MidArg,FF(MidArg),HighArg,HighValue,Accuracy);   // too low //------------------------------------------------------------------------------ LowestValue     =   0;      // for this test HighestValue    =   90;     // for this test // lookup the angle which gives a sine of 0.5 - ie 30 degrees echo(InvFF(0.5, LowestValue, FF(LowestValue), HighestValue, FF(HighestValue), 0.00001)); returns ECHO: 29.9999 Sent from the OpenSCAD mailing list archive at Nabble.com._______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email]
Open this post in threaded view
|

## Re: Recursive Binary Chop

 But you need the derivative of the function for Newton Raphson.On Mon, 17 May 2021 at 14:54, Colin Hercus <[hidden email]> wrote:Binary chop can work for this but Newton Raphson should do it in less iterations  https://en.wikipedia.org/wiki/Newton%27s_methodOn Sun, May 16, 2021 at 1:09 AM GregL <[hidden email]> wrote:I had a complicated function to calculate an area according to its one argument. The function was monotonic. There was then a need to find the argument value which gave a specific area - an inverse function was created. Its arguments are the input value to be looked up                      lowest start value and its function                     highest start value and its function                     required accuracy               InvFF performs a binary chop until the upper and lower values are within the required accuracy //---------------------------------------------------------------------------------------- // test out with a simple inverse sin // sin(T) goes between 0 and 1 for angles 0 : 90 // if we give the recursive function a number 0 : 1, we want the angle 0 : 90 //------------------------------------------------------------------------------- function FF(A) = sin(A); //------------------------------------------------------------------------------- function InvFF(Value,LowArg,LowValue,HighArg,HighValue,Accuracy) =   let(MidArg = (HighArg + LowArg)/2)     abs(HighValue - LowValue)/(HighValue + LowValue) < 2*Accuracy     ?   MidArg                                    // Stop here with best answer     :   FF(MidArg) > Value               ? InvFF(Value,LowArg,LowValue,MidArg,FF(MidArg),Accuracy)     // too high       : InvFF(Value,MidArg,FF(MidArg),HighArg,HighValue,Accuracy);   // too low //------------------------------------------------------------------------------ LowestValue     =   0;      // for this test HighestValue    =   90;     // for this test // lookup the angle which gives a sine of 0.5 - ie 30 degrees echo(InvFF(0.5, LowestValue, FF(LowestValue), HighestValue, FF(HighestValue), 0.00001)); returns ECHO: 29.9999 Sent from the OpenSCAD mailing list archive at Nabble.com._______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email]
Open this post in threaded view
|

## Re: Recursive Binary Chop

 You don't. You work out the slope from your two initial values. On Mon, May 17, 2021 at 10:27 PM nop head <[hidden email]> wrote:But you need the derivative of the function for Newton Raphson.On Mon, 17 May 2021 at 14:54, Colin Hercus <[hidden email]> wrote:Binary chop can work for this but Newton Raphson should do it in less iterations  https://en.wikipedia.org/wiki/Newton%27s_methodOn Sun, May 16, 2021 at 1:09 AM GregL <[hidden email]> wrote:I had a complicated function to calculate an area according to its one argument. The function was monotonic. There was then a need to find the argument value which gave a specific area - an inverse function was created. Its arguments are the input value to be looked up                      lowest start value and its function                     highest start value and its function                     required accuracy               InvFF performs a binary chop until the upper and lower values are within the required accuracy //---------------------------------------------------------------------------------------- // test out with a simple inverse sin // sin(T) goes between 0 and 1 for angles 0 : 90 // if we give the recursive function a number 0 : 1, we want the angle 0 : 90 //------------------------------------------------------------------------------- function FF(A) = sin(A); //------------------------------------------------------------------------------- function InvFF(Value,LowArg,LowValue,HighArg,HighValue,Accuracy) =   let(MidArg = (HighArg + LowArg)/2)     abs(HighValue - LowValue)/(HighValue + LowValue) < 2*Accuracy     ?   MidArg                                    // Stop here with best answer     :   FF(MidArg) > Value               ? InvFF(Value,LowArg,LowValue,MidArg,FF(MidArg),Accuracy)     // too high       : InvFF(Value,MidArg,FF(MidArg),HighArg,HighValue,Accuracy);   // too low //------------------------------------------------------------------------------ LowestValue     =   0;      // for this test HighestValue    =   90;     // for this test // lookup the angle which gives a sine of 0.5 - ie 30 degrees echo(InvFF(0.5, LowestValue, FF(LowestValue), HighestValue, FF(HighestValue), 0.00001)); returns ECHO: 29.9999 Sent from the OpenSCAD mailing list archive at Nabble.com._______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email]
Open this post in threaded view
|

## Re: Recursive Binary Chop

 function FF(A) = sin(A);//-------------------------------------------------------------------------------function InvFF(Value,LowArg,LowValue,HighArg,HighValue,Accuracy)= let(MidArg=LowArg + (Value-LowValue)*(HighArg-LowArg)/(HighValue-LowValue))   abs(HighValue - LowValue)/(HighValue + LowValue) < 2*Accuracy    ?   MidArg                                    // Stop here with best answer    :   FF(MidArg) > Value              ? InvFF(Value,LowArg,LowValue,MidArg,FF(MidArg),Accuracy)     // too high      : InvFF(Value,MidArg,FF(MidArg),HighArg,HighValue,Accuracy);   // too low      //------------------------------------------------------------------------------LowestValue     =   0;      // for this testHighestValue    =   90;     // for this test// lookup the angle which gives a sine of 0.5 - ie 30 degrees//echo(LowestValue, FF(LowestValue), HighestValue, FF(HighestValue));echo(InvFF(0.5, LowestValue, FF(LowestValue), HighestValue, FF(HighestValue), 0.00001)); ECHO: 30 Rendering Polygon Mesh using CGAL... UI-WARNING: No top level geometry to render On Mon, May 17, 2021 at 10:33 PM Colin Hercus <[hidden email]> wrote:You don't. You work out the slope from your two initial values. On Mon, May 17, 2021 at 10:27 PM nop head <[hidden email]> wrote:But you need the derivative of the function for Newton Raphson.On Mon, 17 May 2021 at 14:54, Colin Hercus <[hidden email]> wrote:Binary chop can work for this but Newton Raphson should do it in less iterations  https://en.wikipedia.org/wiki/Newton%27s_methodOn Sun, May 16, 2021 at 1:09 AM GregL <[hidden email]> wrote:I had a complicated function to calculate an area according to its one argument. The function was monotonic. There was then a need to find the argument value which gave a specific area - an inverse function was created. Its arguments are the input value to be looked up                      lowest start value and its function                     highest start value and its function                     required accuracy               InvFF performs a binary chop until the upper and lower values are within the required accuracy //---------------------------------------------------------------------------------------- // test out with a simple inverse sin // sin(T) goes between 0 and 1 for angles 0 : 90 // if we give the recursive function a number 0 : 1, we want the angle 0 : 90 //------------------------------------------------------------------------------- function FF(A) = sin(A); //------------------------------------------------------------------------------- function InvFF(Value,LowArg,LowValue,HighArg,HighValue,Accuracy) =   let(MidArg = (HighArg + LowArg)/2)     abs(HighValue - LowValue)/(HighValue + LowValue) < 2*Accuracy     ?   MidArg                                    // Stop here with best answer     :   FF(MidArg) > Value               ? InvFF(Value,LowArg,LowValue,MidArg,FF(MidArg),Accuracy)     // too high       : InvFF(Value,MidArg,FF(MidArg),HighArg,HighValue,Accuracy);   // too low //------------------------------------------------------------------------------ LowestValue     =   0;      // for this test HighestValue    =   90;     // for this test // lookup the angle which gives a sine of 0.5 - ie 30 degrees echo(InvFF(0.5, LowestValue, FF(LowestValue), HighestValue, FF(HighestValue), 0.00001)); returns ECHO: 29.9999 Sent from the OpenSCAD mailing list archive at Nabble.com._______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email]
Open this post in threaded view
|

## Re: Recursive Binary Chop

Open this post in threaded view
|

## Re: Recursive Binary Chop

Open this post in threaded view
|

## Re: Recursive Binary Chop

 Ummmm... "...even simpler.." is broke. What happened to Accuracy parameter? Sent from the OpenSCAD mailing list archive at Nabble.com._______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email]
Open this post in threaded view
|

## Re: Recursive Binary Chop

 Accuracy isn't req'd but I forgot to remove it from the recursive call of InvFF. It still worked and I missed the warning message. Sorry, it was very late here.There is now no accuracy setting and it still does less iterations than the Binary Chop.  Put and echo(MidArg) after the let() to watch it in action.function InvFF(Value,LowArg,HighArg)= let(MidArg=LowArg + (Value-FF(LowArg))*(HighArg-LowArg)/(FF(HighArg)-FF(LowArg)))MidArg==LowArg || MidArg==HighArg    ?   MidArg                                        :   InvFF(Value,HighArg,MidArg);On Tue, May 18, 2021 at 3:06 AM LenStruttmann <[hidden email]> wrote:Ummmm... "...even simpler.." is broke. What happened to Accuracy parameter? Sent from the OpenSCAD mailing list archive at Nabble.com._______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email]
Open this post in threaded view
|

## Re: Recursive Binary Chop

 Much better!  Thanks! Sent from the OpenSCAD mailing list archive at Nabble.com._______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email]
Open this post in threaded view
|

## Re: Recursive Binary Chop

 In reply to this post by Colin49 Note that this isn't really Newton's method, which requires use of the actual derivative, or even a standard approximate Newton's method, where the derivative would be approximated numerically, e.g. by (f(x+h)-f(x-h))/2h.  Anybody planning to use it should be aware that the solution can be any real number and is by no means guaranteed to lie in the interval [LowArg,HighArg].  Is there a convergence proof for this algorithm?  Can you prove that the interval shrinks?  I have this feeling that it might be possible to construct some kind of infinite loop case where it fails to converge because the derivative approximation is so horrible.   It will blow up with an error if the value of the function is equal at both endpoints, and it seems likely to misbehave if the function values are almost equal at the endpoints.   Given these various issues, one might ask, why not just use a regular approximate Newton's method, which will be better behaved, and easier to understand, and wouldn't require the mysterious use of two parameters (the high and low values) to kick off the iteration.    If you invoke this with the "high" and "low" values different by only a small amount like 1e-5 then I think might get an actual approximate Newton method.  (I'm haven't tried to prove that the interval doesn't grow, which would be necessary to ensure that the derivative approximation stays good.) Colin49 wrote Accuracy isn't req'd but I forgot to remove it from the recursive call of InvFF. It still worked and I missed the warning message. Sorry, it was very late here. There is now no accuracy setting and it still does less iterations than the Binary Chop.  Put and echo(MidArg) after the let() to watch it in action. function InvFF(Value,LowArg,HighArg) = let(MidArg=LowArg + (Value-FF(LowArg))*(HighArg-LowArg)/(FF(HighArg)-FF(LowArg))) MidArg==LowArg || MidArg==HighArg     ?   MidArg     :   InvFF(Value,HighArg,MidArg); On Tue, May 18, 2021 at 3:06 AM LenStruttmann <[hidden email]> wrote: > Ummmm... "...even simpler.." is broke. > > What happened to Accuracy parameter? > ------------------------------ > Sent from the OpenSCAD mailing list archive > at Nabble.com. > _______________________________________________ > OpenSCAD mailing list > To unsubscribe send an email to [hidden email]> _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] Sent from the OpenSCAD mailing list archive at Nabble.com._______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email]
Open this post in threaded view
|

## Re: Recursive Binary Chop

 On Tue, May 18, 2021 at 10:09 AM adrianv <[hidden email]> wrote:Note that this isn't really Newton's method, which requires use of the actual derivative, or even a standard approximate Newton's method, where the derivative would be approximated numerically, e.g. by (f(x+h)-f(x-h))/2h.  Anybody planning to use it should be aware that the solution can be any real number and is by no means guaranteed to lie in the interval [LowArg,HighArg].  Is there a convergence proof for this algorithm?  Can you prove that the interval shrinks?  I have this feeling that it might be possible to construct some kind of infinite loop case where it fails to converge because the derivative approximation is so horrible.   It will blow up with an error if the value of the function is equal at both endpoints, and it seems likely to misbehave if the function values are almost equal at the endpoints.   Given these various issues, one might ask, why not just use a regular approximate Newton's method, which will be better behaved, and easier to understand, and wouldn't require the mysterious use of two parameters (the high and low values) to kick off the iteration.    If you invoke this with the "high" and "low" values different by only a small amount like 1e-5 then I think might get an actual approximate Newton method.  (I'm haven't tried to prove that the interval doesn't grow, which would be necessary to ensure that the derivative approximation stays good.) Colin49 wrote Accuracy isn't req'd but I forgot to remove it from the recursive call of InvFF. It still worked and I missed the warning message. Sorry, it was very late here. There is now no accuracy setting and it still does less iterations than the Binary Chop.  Put and echo(MidArg) after the let() to watch it in action. function InvFF(Value,LowArg,HighArg) = let(MidArg=LowArg + (Value-FF(LowArg))*(HighArg-LowArg)/(FF(HighArg)-FF(LowArg))) MidArg==LowArg || MidArg==HighArg     ?   MidArg     :   InvFF(Value,HighArg,MidArg); On Tue, May 18, 2021 at 3:06 AM LenStruttmann <[hidden email]> wrote: > Ummmm... "...even simpler.." is broke. > > What happened to Accuracy parameter? > ------------------------------ > Sent from the OpenSCAD mailing list archive > at Nabble.com. > _______________________________________________ > OpenSCAD mailing list > To unsubscribe send an email to [hidden email]> _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] Sent from the OpenSCAD mailing list archive at Nabble.com._______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email]
Open this post in threaded view
|