Horner scheme

[jj2007]

I am playing with two new macros that use a variant of the Horner scheme:
                SetPoly3 My3Pts()                ; use three XY pairs to get a0...a2
                GetPoly3(AllPts())                ; fill an array using y=a0+a1*(x-x0)+a2*(x-x0)*(x-x1)

Work in progress. In the attached executable, the two outer points are fixed, the middle one moves with the mouse.

[dedndave]

very cool   :t
i remember, long ago, i needed something like this
now, i can't remember what it was for - lol
that was back in the DOS days

it seems to hang up under certain conditions - hard to describe
i am sure you are aware of it - as you say, work in progress

[jj2007]

it seems to hang up under certain conditions - hard to describe

Usually you can unblock it by moving around the lower right corner.

Here is a variant that uses the three red points to define the bounding rectangle. The only difference is that now the other points can go outside the rect.

if 1        ; optional: use the "biggest" array to define a common range
        ArrayPlot My3Pts(XY), 0, 0, MyMargins, SetRange        ; the three red points define the range
else
        ArrayPlot AllPts(XY), 0, 0, MyMargins, SetRange        ; the big array defines the range
endif

[dedndave]

Seeing your code would be nice indeed ;-)

it is an assembler forum, afterall   :P

[qWord]

I somehow like the idea and looked up for an robust algorithm for getting polynomials through arbitrary points and found the method of divided differences (similar: hermite interpolation ).
An C implementation can be found here (functions: data_to_dif  and dif_val).

In the attachment a example (sry, no source): with the left mouse button you can add and drag points, which are used for interpolation. With the right mouse button selected points are removed.

qWord

[jj2007]

method of divided differences (similar: hermite interpolation )

Nice link :t
Reference:
    Carl deBoor,
    A Practical Guide to Splines,
    Springer, 2001
The reference for my macros is Dubbel, Taschenbuch für den Maschinenbau, Springer 19xx (can't find the book right now, but it must be before 1981).
If I find time over the weekend, I'll post a new edition of MasmBasic with the sources.

EDIT: Sources are online, see here

[NoCforMe]

Pretty good video explanation of Horner's Method here.

[jj2007]

Pretty good video explanation of Horner's Method here.

Great

So the basics of FastMath were invented 1000 years ago by Jia Xian (1010...1070)

[HSE]

   Just take into acount that precision drop from 10^-12 (or so) to 10^-4 making interpolations.

[jj2007]

precision drop

Which precision drop?

Code Select Expand

include \masm32\MasmBasic\MasmBasic.inc
  SetGlobals fct:REAL10
  Init
  Cls 5
  FastMath FastLog10 ; define a math function
For_ fct=0.001 To 10.0 Step 0.01 ; max 10,000 iterations
fld fct ; X
fstp REAL10 ptr [edi]
void Log10(fct) ; Y (built-in MasmBasic function)
fstp REAL10 ptr [edi+REAL10]
add edi, 2*REAL10
Next
  FastMath
  For_ fct=0.001 To 7.5 Step 0.5
Print Str$("Log(%3f):\t", fct), Str$("%Gf = ", FastLog10(fct)v), Str$("%Gf\n", Log10(fct)v)
  Next
EndOfCode

Code Select Expand

Log(0.00100):   -3.000000000000000 = -3.000000000000000
Log(0.501):     -0.3001622741327543 = -0.3001622741327543
Log(1.00):      4.340774793186407e-04 = 4.340774793186407e-04
Log(1.50):      0.1763806922432704 = 0.1763806922432704
Log(2.00):      0.3012470886362114 = 0.3012470886362114
Log(2.50):      0.3981136917305025 = 0.3981136917305025
Log(3.00):      0.4772659954248526 = 0.4772659954248526
Log(3.50):      0.5441921107650326 = 0.5441921107650326
Log(4.00):      0.6021685513789972 = 0.6021685513789972
Log(4.50):      0.6533090129384789 = 0.6533090129384789
Log(5.00):      0.6990568545476678 = 0.6990568545476678
Log(5.50):      0.7404416449497660 = 0.7404416449497660
Log(6.00):      0.7782236267660965 = 0.7782236267660965
Log(6.50):      0.8129801660394804 = 0.8129801660394804
Log(7.00):      0.8451600776519458 = 0.8451600776519458

[HSE]

 

precision drop ... making interpolations.

Using the table values is just table precision 

[HSE]

Code Select Expand

include \masm32\MasmBasic\MasmBasic.inc
  SetGlobals fct:REAL10
  Init
  Cls 5
  FastMath FastLog10 ; define a math function
For_ fct=1.0 To 10.0 Step 1.0 ; max 10,000 iterations
fld fct ; X
fstp REAL10 ptr [edi]
void Log10(fct) ; Y (built-in MasmBasic function)
fstp REAL10 ptr [edi+REAL10]
add edi, 2*REAL10
Next
  FastMath
  For_ fct=1.5 To 7.5 Step 1.0
Print Str$("Log(%3f):\t", fct), Str$("%Gf = ", FastLog10(fct)v), Str$("%Gf\n", Log10(fct)v)
  Next
EndOfCode

Code Select Expand

Log(1.50):      0.1661323399080281 = 0.1760912590556812
Log(2.50):      0.3954696904977445 = 0.3979400086720376
Log(3.50):      0.5430942134738429 = 0.5440680443502756
Log(4.50):      0.6527310937020445 = 0.6532125137753437
Log(5.50):      0.7413197895734896 = 0.7403626894942438
Log(6.50):      0.8135372823265489 = 0.8129133566428556
Log(7.50):      0.8754905888107381 = 0.8750612633917000

[jj2007]

Sure, but why a table with only 10 entries? What stops you from creating a bigger table?

Code Select Expand

664 µs for creating a table with 6400 entries
Log(0.00100):  -3.000000000000000 = -3.000000000000000
Log(0.251):    -0.6003262785189619 = -0.6003262785189619
Log(0.501):    -0.3001622741327543 = -0.3001622741327543
Log(0.751):    -0.1243600629958316 = -0.1243600629958316
Log(1.00):      4.340774793186407e-04 = 4.340774793186407e-04
...
Less than one millisecond for the creation of the table, which is done only once at program start...

[HSE]

Sure, but why a table with only 10 entries? What stops you from creating a bigger table?

That is the point: No problem using table values, be careful using interpolation.