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) < 2Accuracy
? 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(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 colinhercus@gmail.com 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 nop.head@gmail.com wrote:
But you need the derivative of the function for Newton Raphson.
On Mon, 17 May 2021 at 14:54, Colin Hercus colinhercus@gmail.com wrote:
Binary chop can work for this but Newton Raphson should do it in less
iterations https://en.wikipedia.org/wiki/Newton%27s_method
On Sun, May 16, 2021 at 1:09 AM GregL greg@leonardresearch.co.uk
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
http://forum.openscad.org/ at Nabble.com.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
And after reworking recursion and termination
//----------------------------------------------------------------------------------------
// 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=LowArg +
(Value-LowValue)(HighArg-LowArg)/(HighValue-LowValue))
abs(HighValue - LowValue)/(HighValue + LowValue) < 2Accuracy
? MidArg // Stop here with best
answer
: InvFF(Value,HighArg,HighValue,MidArg,FF(MidArg),Accuracy);
//------------------------------------------------------------------------------
LowestValue = 0; // for this test
HighestValue = 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));
On Mon, May 17, 2021 at 11:00 PM Colin Hercus colinhercus@gmail.com wrote:
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) < 2Accuracy
? 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(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 colinhercus@gmail.com
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 nop.head@gmail.com wrote:
But you need the derivative of the function for Newton Raphson.
On Mon, 17 May 2021 at 14:54, Colin Hercus colinhercus@gmail.com
wrote:
Binary chop can work for this but Newton Raphson should do it in less
iterations https://en.wikipedia.org/wiki/Newton%27s_method
On Sun, May 16, 2021 at 1:09 AM GregL greg@leonardresearch.co.uk
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
http://forum.openscad.org/ at Nabble.com.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
Sorry, I can't help myself. Even simpler
//----------------------------------------------------------------------------------------
// 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,HighArg)
= let(MidArg=LowArg +
(Value-FF(LowArg))*(HighArg-LowArg)/(FF(HighArg)-FF(LowArg)))
MidArg==LowArg || MidArg==HighArg
? MidArg
: InvFF(Value,HighArg,MidArg,Accuracy);
//------------------------------------------------------------------------------
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, HighestValue));
On Mon, May 17, 2021 at 11:17 PM Colin Hercus colinhercus@gmail.com wrote:
And after reworking recursion and termination
//----------------------------------------------------------------------------------------
// 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=LowArg +
(Value-LowValue)(HighArg-LowArg)/(HighValue-LowValue))
abs(HighValue - LowValue)/(HighValue + LowValue) < 2Accuracy
? MidArg // Stop here with best
answer
: InvFF(Value,HighArg,HighValue,MidArg,FF(MidArg),Accuracy);
//------------------------------------------------------------------------------
LowestValue = 0; // for this test
HighestValue = 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));
On Mon, May 17, 2021 at 11:00 PM Colin Hercus colinhercus@gmail.com
wrote:
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) < 2Accuracy
? 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(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 colinhercus@gmail.com
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 nop.head@gmail.com wrote:
But you need the derivative of the function for Newton Raphson.
On Mon, 17 May 2021 at 14:54, Colin Hercus colinhercus@gmail.com
wrote:
Binary chop can work for this but Newton Raphson should do it in less
iterations https://en.wikipedia.org/wiki/Newton%27s_method
On Sun, May 16, 2021 at 1:09 AM GregL greg@leonardresearch.co.uk
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
http://forum.openscad.org/ at Nabble.com.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
Gentleman,
I've tried a couple of times online to stop OpenSCAD emails but that has not been successful. Will someone pass the word to the appropriate person that d58m@comcast.net mailto:d58m@comcast.net should be removed from the list.
Thank you,
David Mendalski
On 05/17/2021 10:24 AM Colin Hercus <colinhercus@gmail.com> wrote:
Sorry, I can't help myself. Even simpler
//----------------------------------------------------------------------------------------
// 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,HighArg)
= let(MidArg=LowArg + (Value-FF(LowArg))*(HighArg-LowArg)/(FF(HighArg)-FF(LowArg)))
MidArg==LowArg || MidArg==HighArg
? MidArg
: InvFF(Value,HighArg,MidArg,Accuracy);
//------------------------------------------------------------------------------
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, HighestValue));
On Mon, May 17, 2021 at 11:17 PM Colin Hercus < colinhercus@gmail.com mailto:colinhercus@gmail.com > wrote:
And after reworking recursion and termination
//----------------------------------------------------------------------------------------
// 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=LowArg + (Value-LowValue)*(HighArg-LowArg)/(HighValue-LowValue))
abs(HighValue - LowValue)/(HighValue + LowValue) < 2*Accuracy
? MidArg // Stop here with best answer
: InvFF(Value,HighArg,HighValue,MidArg,FF(MidArg),Accuracy);
//------------------------------------------------------------------------------
LowestValue = 0; // for this test
HighestValue = 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));
On Mon, May 17, 2021 at 11:00 PM Colin Hercus < colinhercus@gmail.com mailto:colinhercus@gmail.com > wrote:
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 test
HighestValue = 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 < colinhercus@gmail.com mailto:colinhercus@gmail.com > 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 < nop.head@gmail.com mailto:nop.head@gmail.com > wrote:
But you need the derivative of the function for Newton Raphson.
On Mon, 17 May 2021 at 14:54, Colin Hercus < colinhercus@gmail.com mailto:colinhercus@gmail.com > wrote:
Binary chop can work for this but Newton Raphson should do it in less iterations https://en.wikipedia.org/wiki/Newton%27s_method
On Sun, May 16, 2021 at 1:09 AM GregL < greg@leonardresearch.co.uk mailto:greg@leonardresearch.co.uk > 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 http://forum.openscad.org/ at Nabble.com.
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org mailto:discuss-leave@lists.openscad.org
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org mailto:discuss-leave@lists.openscad.org
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org mailto:discuss-leave@lists.openscad.org
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
Ummmm... "...even simpler.." is broke.
What happened to Accuracy parameter?
--
Sent from: http://forum.openscad.org/
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 LenStruttmann@gmail.com
wrote:
Ummmm... "...even simpler.." is broke.
What happened to Accuracy parameter?
Sent from the OpenSCAD mailing list archive http://forum.openscad.org/
at Nabble.com.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
Much better! Thanks!
--
Sent from: http://forum.openscad.org/
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 <
LenStruttmann@
>
wrote:
Ummmm... "...even simpler.." is broke.
What happened to Accuracy parameter?
Sent from the OpenSCAD mailing list archive
<http://forum.openscad.org/>
at Nabble.com.
OpenSCAD mailing list
To unsubscribe send an email to
discuss-leave@.openscad
OpenSCAD mailing list
To unsubscribe send an email to
discuss-leave@.openscad
--
Sent from: http://forum.openscad.org/
On Tue, May 18, 2021 at 10:09 AM adrianv avm4@cornell.edu 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]
http:///user/SendEmail.jtp?type=email&email=LenStruttmann%40>
wrote:
Ummmm... "...even simpler.." is broke.
What happened to Accuracy parameter?
Sent from the OpenSCAD mailing list archive http://forum.openscad.org/
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]
http:///user/SendEmail.jtp?type=email&email=discuss-leave%40.openscad
Sent from the OpenSCAD mailing list archive http://forum.openscad.org/
at Nabble.com.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
Hi,
In the original email it was stated that it was used for a monotonic
function. The same restriction applies to this.
The derivative is (HighArg-LowArg)/(FF(HighArg)-FF(LowArg)) or the inverse
of this. It's an approximation for the Hi/Lo range and it's not terrible.
It should work fine for any non constant monotonic function where the
values of FF at High & Low are not infinite.
The binary chop/search will not work if the function is not monotonic
and always
returns HighArg for a constant function.
For a constant function the results are undefined. It should fault with a
divide by zero. It would be easy to add a check for this. I can see there
is a possible issue if the function has a region of constant values
(derivative = 0) and we hit that with our Hi&Lo points.
In the original algorithm the user had to choose a High/Low range that was
meant to contain the solution.
I also think that it works better starting with a large range but my code
doesn't require that. With functions like Sine that are not monotonic over
their entire range it's important that the hi and low cover a monotonic
region and that the target value is inside the region. Much the same as the
original binary chop algorithm.
I can see there is a possible issue if the function has a region of
constant values (derivative = 0) Just adding a test for HiValue ==
LowValue and returning (HighArg+LowArg)/2 would solve this. But again the
assumption was monotonically increasing function.
On Tue, May 18, 2021 at 10:09 AM adrianv avm4@cornell.edu 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]
http:///user/SendEmail.jtp?type=email&email=LenStruttmann%40>
wrote:
Ummmm... "...even simpler.." is broke.
What happened to Accuracy parameter?
Sent from the OpenSCAD mailing list archive http://forum.openscad.org/
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]
http:///user/SendEmail.jtp?type=email&email=discuss-leave%40.openscad
Sent from the OpenSCAD mailing list archive http://forum.openscad.org/
at Nabble.com.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org