math functions in the jump table near $AF12-$AF57

[dr.v]

My question goes to the obvious functions for which this applies (JMP [TRIG/INV. TRIG/LOG]).  Does the c128 use a type of Taylor series expansion to evaluate these functions?  Has anyone seen literature/documentation on writing optimized mathematics code with an 8502?

Thanks.

[Hydrophilic]

Yes, Commodore BASIC (all versions AFAIK), uses Taylor Series Polynomials for transcendental functions like atn, log, sin, etc.

SIN(), COS(), and TAN() all use the 5th-order polynomial whose coefficients begin at $9495 on the C128 (BANK 14 or 15):

-14.3813907
+42.0077971
-76.7041703
+81.6052237
-41.3417021
+6.28318531 (2*pi)


Note COS() works by adding pi/2 to argument before calling SIN(), and TAN() works by calculating SIN/COS.

ATN() uses the 11th-order polynomial whose coefficients begin at $94E4 on the C128 (BANK 14 or 15):

-6.84793912e-04
+4.85094216e-03
-0.0161117018
+0.034209638
-0.0542791328
+0.0724571965
-0.0898023954
+0.110932413
-0.142839808
+0.19999912
-0.333333316
+1.00000000

EXP() uses the 7th-order polynomial whose coefficients begin at $900B on the C128 (BANK 14 or 15):

+2.14987637e-05
+1.4352314e-04
+1.34226348e-03
+9.61401701e-03
+0.0555051269
+0.240226385
+0.693147186 (natural log 2)
+1.00000000


LOG() uses the 3rd-order polynomial whose coefficients begin at $89A2 on the C128 (BANK 14 or 15):

+0.434255942
+0.576584541
+0.961800759
+2.88539007

Note, that power operator, like 2 ^ 3 = 8, uses both EXP() and LOG().

Note SQR() operates like x ^ (1/2).

Did I miss anything?

BONUS:

I wrote a BASIC 7.0 program that will print a polynomial table in BASIC ROM.  Just specify the start of the table in hexadecimal.  Note the tables really begin with the polynomial order = coeffecient count - 1 at the address 1 byte before the start of the coeffecient data.

For example, the six coeffecients of SIN() (5th-order polynomial) begin at $9495 on the C128.  The order = number of coeffecients - 1 (5 = 6 - 1) is stored at $9495-1.  So when the program asks for ADRS? enter $9494.

Code Select Expand


10 do:input"adrs";x$:a=dec(x$):n=peek(a):a=a+1:fori=0ton
20 e=peek(a+i*5)-160:m=0:for d=1to4:m=m*256+peek(a+d+i*5):ifd=1thenm=mor128
30 next:ifpeek(a+1+i*5)>127thenm=-m
40 printm*2^e:next:loop


[dr.v]

I couldn't have asked for a more clear and concise answer.  Thank you.  I plan on writing a piece of code on my c128 to find certain types of localized solutions to nonlinear PDE's.  Not sure if I can pull it off within the 1Mhz/2Mhz constraint, but I'm gonna try.  Gonna start with an ODE solver, though.  Most PDE's I work with I can reduce to a stationary state ODE.  What I have in mind is an adaptive Runga-Kutta method with elements of a linear shooting technique.  I figured it was best to fully understand the stock mathematics capability of the machine before getting started.

       

[Mark Smith]

EErrrk!!!!  You guys aren't talking english!!!!  :-)

Polywhatsits ?!? .. you can see I'm real good at math! hehe

Mark

[airship]

At ACT, we use the Taylor Series for all kinds of statistical analyses.

I just read about the C128's use of Taylor series in its advanced math calculations in one of my C128 books last week. I was surprised to learn that it was right there in my C128's ROMs all this time.

[dr.v]

Mark - It is a very common way to calculate values of "tougher" functions (referred to appropriately in this thread as "transcendental functions").  Ever wonder how a computer can calulate the value of sin(x) given that it's native capabilities amount to add, subtract, multiply, and divide?  Well the answer is known as "Taylor Series" in mathematics.  It allows for a representation of a function in terms of a polynomial.  Note that the evaluation of polynomials involve only those 4 basic arithmetic operations mentioned above.  Of course, the exact representation of one of these transcendental functions requires an infinite number of terms to converge to the exact value.  As I am sure you are aware, an infinite number of terms can be hard to squeeze into 128k  But if you take only a finite number of terms (say half a dozen or so), you can still achieve remarkable accuracy.  Hope that helps!

airship - what book are you referring to?

Tom

[airship]

airship - what book are you referring to?

I KNEW someone was going to ask me that!

I can't remember and I'm at work right now. I'll have to sort through some books at home to find it.

[BigDumbDinosaur]

Ever wonder how a computer can calulate the value of sin(x) given that it's native capabilities amount to add, subtract, multiply, and divide?

Any 65xx powered system's native capabilities will be limited to addition and subtraction.  Other operations must be synthesized in software.  Hence the relatively slow floating point performance of an eight bit CBM box.

[airship]

Well, it only took me four months to keep my promise!

There are just these two paragraphs on p. 233 of Commodore 128 Programming Secrets by William Wiese, Jr.

"SIN, COS, and ATN functions require calculations involving polynomial (Taylor) series; these series-evaluation routines are contained within the C-128 BASIC ROM. They can save the user much programming effort and time when any custom function expressible with a Taylor series is being created, since the only major task necessary is the creation of a table of floating-point numbers that will be used as coefficients of the polynomial.

The routine POLYX, at $9086 in the BASIC ROM, evaluates polynomials that have terms containing odd terms of x (including a zero-power, or constant, term). The POLY routine at $909C, however, evaluates polynomials that have terms containing both odd and even powers of x. Before calling either routine, the .A and .Y registers are loaded with the low- and high-address bytes of a table of floating-point coefficients, The first byte of the coefficient table contains a number that is one less than the degree (highest power of x) of the desired polynomial, while the remaining bytes are standard five-byte floating-point constants. These constants are arranged in order of degree; the coefficient  of x^0 (the constant term) comes first, followed by the coefficients of x, x^2, x^3, and so on."

These paragraphs follow seven pages which discuss BASIC 7 floating-point routines, which consist mostly of a commented jump table into the BASIC ROM. There is, however, a nice listing of an assembly routine to calculate square roots using Newton's method. The author claims it's four times faster than the ROM routine.

[dr.v]

BDD - I didn't realize that 65xx native capability is limited to addition and subtraction.  That's good to know!

Airship - I appreciate the reference.  I'm going to check out the claim about Newton's method.  Using Newtons Method, we can recover a recursive formula for calculating square roots:

                                           x_(n+1)=(1/2)*(x_n+a/x_n)

Where a is the target value we are tring to find the square root of and x_(n+1) is determined by the previous iteration x_n.  This requires, of course, a reasonable estimate for a "seed" x_0.

Ironically enough, this formula was used by the ancient Babylonians well before Netwon came on the scene.

In general, "universal" claims with Newton's method (i.e., its "x" times faster than whatever method...) are dicey at best.  Depending on the curvature of the underlying function, Newton's method may take longer to converge for some functions vs. others.  But a square root is well-behaved, I would sorta buy the claim if I could compare it to the ROM routine.

Tom

[bacon]

BDD - I didn't realize that 65xx native capability is limited to addition and subtraction.  That's good to know!

It can  also divide and multiply by 2 (LSR and ASL anyone?)

[BigDumbDinosaur]

BDD - I didn't realize that 65xx native capability is limited to addition and subtraction.  That's good to know!

It can  also divide and multiply by 2 (LSR and ASL anyone?)

Those aren't general purpose math operations like ADC and SBC.  They fall into the category of logic ops.  ASL is unfortunately named: LSL would have made more sense, given that the companion to ROR is ROL.  Also, it's a bit shift, not an arithmetic shift, as you can't specify how many bits to shift.

However, ASL is what MOS Technology used and now we're all "stuck" with it. 

[bacon]

ASL is what MOS Technology used and now we're all "stuck" with it. 

Motorola used ASL in the 6800 so that's most likely the reason MOS used the same name. The main selling points of the 6502 was that it was similar to the 6800 but much less expensive. Using the same mnemonics for the opcodes made a lot of sense when trying to lure over 6800 programmers to the 6502.

[BigDumbDinosaur]

From my perspective, the mnemonics BSL (bit shift left), BSR (bit shoft right), BRL (bit rotate left) and BRR (bit rotate right) would have been more appropriate.  The W65C816S appropriated the BRL mnemonic to mean branch always long (16 bit offset).

Instruction naming has always been a strange thing.  I can't recall the processor anymore, but one of them had an SOB instruction.  Not sure if it meant sob as in weep or...  There was also the infamous Motorola HCF instruction, which fortunately didn't do exactly what the mnenonic might suggest.

[bacon]

Halt and Catch Fire, huh? I've heard about that one.

Then there was the (IBM?) mainframe where the designers managed to sneak in a SEX instruction, but IIRC the marketing people found out and had it removed (or renamed I guess).

[BigDumbDinosaur]

Actually, SEX existed in the DEC PDP-11 assembly language.  It stood for "sign extend."

[Hydrophilic]

SEX sounds like a really cool instruction... I remember using MONITOR on the C128 before I knew anything about 6502 Assembly and couldn't figure out why there would be a TAX instruction... was Commodore working for the governement?

@BDD, I agree ASL is wrongly named because it never sets overflow flag.  Should be LSL (or BSL).

@dr.v, I have tried Newtons method because I also have the book Commodore 128 Programming Secrets as mentioned by Airship.  It is much faster than the polynomial method, even if you use only a moderately good guess; for example dividing the exponent by 2.

In (further) regards to Square Root:

I found a very good explanation / implementation of Newton's method at codebase64.

For integers, there is also excellent code available from 6502.org.  It is so simple, I don't understand it!  It loops 8 times doing a simple ASL and, if Carry out, a simple ADC.  It seems more like multiplication / division than Square Root...  Just goes to show that Hydrophilic is still lacking in some fundamentals!  Please respond if you can explain it... thanks!