I've got a pretzel in my brain! Over the decades the standards requirement for division has shifted around quite a bit. I'm trying to figure out which ones to implement and looking for suggestions here.

I'm leaning toward PETTIL having these, with "floored division" throughout. That way I can legitimately include the word FORTH-83 in my dictionary. Also I'd like to have code for division/modulo and multiplication exactly once, in accordance with Ruby's DRY principle.

/ * */ */MOD /MOD MOD UM* UM/MOD M* M*/

Having grabbed Garth's code for division from http://6502.org/source/integers/ummodfix/ummodfix.htm and the multiplication from http://6502.org/source/integers/32muldiv.htm , the unsigned part of this is working. I'll implement the signed stuff by subroutine calls to the unsigned math, XORing the sign bits and a bit of branching.

Dilemma 1: Garth's code returns $FFFFFFFF in the event of an error (quotient overflow or division by zero attempt). This could be confused with the results of " -8. 7 sm/rem " which in gforth returns " -1 -1 ". I was thinking about having the rule "remainders are always positive" and then I could test the sign of the remainder to determine if it was an error or not, but something about violating all three standards documents bothers me.

On a semi-related note, I am thinking about implementing a complete suite of floating point, based on the simple expedient of calling the PET ROM math routines and passing things around as 24-bit values on the stack.

What say you, geniuses? Any thoughts?

Everything below this point was extracted verbatim from the various standards documents:

Forth-79 required words
/ * */ */MOD /MOD MOD U* U/

Forth-83 required words
/ * */ */MOD /MOD MOD UM* UM/MOD

DPANS adds these to Forth-83
FM/MOD M* M*/ SM/REM


Integer division

Division produces a quotient q and a remainder r by dividing operand a by operand b. Division operations return q, r, or both. The identity b*q + r = a shall hold for all a and b. When unsigned integers are divided and the remainder is not zero, q is the largest integer less than the true quotient.

The Forth-79 Standard specifies that the signed division operators (/, /MOD, MOD, */MOD, and */) round non-integer quotients towards zero (symmetric division). Forth-83 changed the semantics of these operators to round towards negative infinity (floored division). Some in the Forth community have declined to convert systems and applications from the Forth-79 to the Forth-83 divide. To resolve this issue, an ANS Forth system is permitted to supply either floored or symmetric operators. In addition, ANS Forth systems must provide a floored division primitive (FM/MOD), a symmetric division primitive (SM/REM), and a mixed precision multiplication operator (M*).

When signed integers are divided, the remainder is not zero, and a and b have the same sign, q is the largest integer less than the true quotient. If only one operand is negative, whether q is rounded toward negative infinity (floored division) or rounded towards zero (symmetric division) is implementation defined.

In cases where the operands differ in sign and the rounding direction matters, a program shall either include code generating the desired form of division, not relying on the implementation-defined default result, or have an environmental dependency on the desired rounding direction.

Floored division is integer division in which the remainder carries the sign of the divisor or is zero, and the quotient is rounded to its arithmetic floor.



Symmetric division is integer division in which the remainder carries the sign of the dividend or is zero and the quotient is the mathematical quotient rounded towards zero or truncated.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

The PET ROM functions are based on excess-128 notation, which in this case limits you to seven significant digits. Also, there are ASCII to binary conversion errors that will get you. Better to follow Garth's suggestion and use scaled integer math. You will not get the range that excess-128 produces, but you will get a lot more significant digits, which is usually more important than absolute range.

Be that as it may, using a 64 bit signed format (bit 63 is the sign bit) will express a range of ±9,223,372,036,854,775,808. That's more than enough to store the national debt or Bill Gates' net worth, even after shifting to account for the fractional component.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

Note that for t / b, 0 <= abs(r) < abs(b) -- i.e. less than instead of less than or equal to abs(b) -- so in the unsigned case if you get a $FFFFFFFF it must be an error, since the largest b is $FFFFFFFF. In the signed case, you could return $80000000 for an error, since r cannot possibly have that value unless there was an error, because the largest (absolute value of) b is 2^31. Then you just test r in the for whichever of those two values applies depending on whether its signed or unsigned division.



The "always positive remainder" is called Euclidian division. See:

http://en.wikipedia.org/wiki/Modulo_operation

(What the Forth spec(s) calls Symmetric division, Wikipedia calls Truncated division.)

I like Euclidian division, but it depends whether you need compatibility with ANS Forth or Forth-83. If so, there are implementations of FM/MOD in high-level Forth out there (eForth has one, I think) in terms of UM/MOD. To me, unsigned division/modulo is far more useful than signed anyway. I've tended to define U/ and UMOD as unsigned versions of / and MOD and then used the former instead of the latter.

This was very helpful. Let's see what happens when we start with Leo Brodie's "quarters" word from Starting Forth and throw some negative numbers into the story.
How about changing that to, "If I owe you 22 quarters and you want it in dollar bills..." (-22 quarters)

Blazin' Forth -22 quarters -6 ones and 2 quarters
gforth -22 quarters -6 ones and 2 quarters
PETTIL -22 quarters -6 ones and 2 quarters
Euclidian: -6 ones and 2 quarters
Floored/Forth-83: -6 ones and 2 quarters
Symmetric/Truncated/Forth'79: -5 ones and -2 quarters

So it boils down to I'd rather you owe me 50 cents than I owe you 50 cents. I'm having a hard time coming up with a real world division example that involves a negative divisor, which is where Euclidean division distinguishes itself from the other two flavors.

This raises the issue of how does one best do error handling? I could just ABORT" division overflow" from a "/" secondary, but UM/MOD is a primitive so calling ABORT" would be problematic.

1. Have a USER variable (called what?) that displays errors (true) or ignores them (false) or aborts on specific bitmask AND operations (positive)
2. implement something like Java's catch/throw exception processing. This seems like overkill.
3. define and return error values on the stack and let the application programmer deal with it. "0 remainder -32768" or $80000000 for signed results and "32727 remainder 32767" or $FFFFFFFF for unsigned results

The way I wound up handling this was to have two words (UM/MOD) and UM/MOD, the first was a primitive that did no range checking (i.e. garbage in, garbage out) and the second was a high-level word that did an ABORT (or later on, a THROW, after I had implemented an exception mechanism (which I found helpful when dealing with files)) when (for t/b) upper-cell-of-t >= b. You can do a similar thing for signed division as well.

Those of you who are on a first name basis with irony may have already guessed what happened. I never really used the high-level word, since the primitive was faster and in almost all instances the parameters were already valid in by the time UM/MOD was executed; I can't recall ever adding any additional range checking for UM/MOD.

This discussion is, in essence, the age-old "error code" versus "exception" religio...er...debate.

Towards that end, my take is that you need to ask yourself, "What is a function's range?" In the case of addition and multiplication of two integers, the result is always an integer. Division, though, requires a wider range.

If you want to think abstractly, you can think of division as being quite well defined for the case when the denominator is zero -- the result is a symbolic concept known as "undefined." In other words, the range of the integer division operator is the set of all integers and undefined.

If your program expects division to always yield a numeric result, it will be in error unless you can assert, prior to the division, that its denominator parameter will never equal zero. You can do this by an explicit IF statement, or through careful data/control-flow analysis in your program, or through formal techniques, such as the application of Hoare logic.

If you cannot guarantee, at all times, validity of input parameters, then you must now decide who is responsible for dealing with this problem. Errors tend to be best handled near their point of occurrence, so returning a sentinel value to indicate "undefined" seems a reasonable choice. Alternatively, you can document those conditions where a division-by-zero would result and place the burden on the programmer to avoid those preconditions. This way, a programmer at least has the knowledge to detect when bad things happen, as proximately as possible to invoking your word.

Exceptions, ideally, ought to be reserved for truly exceptional (e.g., completely unanticipated) problems. Out of stack space, parity errors, and the like.

This is just my minority opinion on this topic, influenced by my experience with the Haskell programming language.

Here it is in all it's "I just now got it working" glory, my 32-bit unsigned division code. My first thought is, it's gigantic. I wish I could make it smaller. The idea is I'll use this divmod subroutine everywhere else where division is used and then fiddle with the stack before and after to make the other flavors.

There's a neat trick called non-restoring division: you do the subtraction, take action according to the sign of the answer, and proceed. You don't have to add back, or save/restore the unsubtracted value. Instead your next 'subtraction' becomes an addition if you overflowed. The wikipedia writeup does not look useful - it implies a need to post-process, which is wrong - perhaps see the bottom of this page instead.

I can't quite figure out whether Garth's division page is non-restoring or not.

Speaking of which here's Rodnay Zaks code for 16/8 non-restoring
division which I said I'd post and then forgot about
(couldn't lay my hands on the book at the time)



(I still haven't tryed it)

That looks like a dodgy to me. What is the value in the accumulator on entry supposed to be? 'd' is subtracted from it but its not loaded or stored.

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

The accumulator appears to be the upper 8-bits of the 16-bit numerator. d appears to be the divisor.

It is. I dug out my copy of Zaks to see what he was up to. Looks weird but is probably right and I'm just too tired to read it correctly (started new job this morning, London tubes went on strike to celebrate, drove in to London at 6am got home at 8pm)

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

That non-restoring code looks like it has the UM/MOD bug (or what amounts to the equivalent of it). Compare $9000/$C0 to $4800/$60 (which should, of course, give the same remainder and quotient), or compare $00F0/$C0 to $00F0/$60 (same remainder, quotient of the former should be half the quotient of the latter -- also, note that this means that unlike restoring division, there's still an issue when the upper byte of the numerator is 0).

The red flag to look for is a bit being shifted out that is subsequently ignored/overwritten. In this case it's the "asl b rol a" sequence. (The rol q doesn't matter, since that's an output, not an input. In fact, you could return the quotient in b and eliminate two instructions from the loop below.)

Here's what I came up with. I haven't tested it for all (valid) cases, though.

the only "improvement" that I was contemplating is getting the remainder/
dividend aligned with the divisor.
Zak's code always does an add or subtract whether he needs to or not.
That's not so bad in his case because he's got a single byte divisor it'd
be a bit more costly with a 32/16 divide.

I put "improvement" in quotes because I did a 16/16 non-restoring
division routine that did try and keep the alignment. It was years
and years ago and I don't remeber the details (I've got it here
somewhere but I haven't been able to find it yet). From what I
recall it involved a moderately complicated bit of xoring of carries
and signs to determine whether to add, subtract or just shift, and
it was about ten-twenty times as much code and was painfully slow
(in my memory at least)

I'm sure I can do better now.