News:

Masm32 SDK description, downloads and other helpful links
Message to All Guests

Main Menu

Horner scheme

Started by jj2007, March 19, 2013, 11:58:22 AM

Previous topic - Next topic

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

Quote from: dedndave on March 19, 2013, 01:52:09 PM
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

Quote from: jj2007 on March 19, 2013, 11:11:03 PM
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
MREAL macros - when you need floating point arithmetic while assembling!

jj2007

#5
Quote from: qWord on March 22, 2013, 12:56:02 PMmethod 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.
Assembly language programming should be fun. That's why I do it.

jj2007

Quote from: NoCforMe on December 19, 2023, 10:10:02 AMPretty good video explanation of Horner's Method here.

Great :biggrin:

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

HSE

 :thumbsup:  Just take into acount that precision drop from 10-12 (or so) to 10-4 making interpolations.
Equations in Assembly: SmplMath

jj2007

Quote from: HSE on December 19, 2023, 10:59:31 AMprecision drop

Which precision drop?

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

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

 :biggrin:

Quote from: HSE on December 19, 2023, 10:59:31 AMprecision drop ... making interpolations.

Using the table values is just table precision  :thumbsup:
Equations in Assembly: SmplMath

HSE

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

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
Equations in Assembly: SmplMath

jj2007

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

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

Quote from: jj2007 on December 19, 2023, 10:30:49 PMSure, but why a table with only 10 entries? What stops you from creating a bigger table?

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

Equations in Assembly: SmplMath