ZXSimulator

[bwinkel67]

Starting my first crack at introducing floating point into ZXSimulator. Main concern is speed and of course always conscious of space as well. Digital 'C' SE uses a library with function calls to implement floating point, and its data structures takes up 48 bits per number (an array of 3 ints). So that will be both slow and take lots of memory.

My idea is to do the old bookkeeping method of assuming the last two digits are the decimal place, i.e. 1.00 is represented as 1 00 or 100, etc. That only gives 2 digits after the decimal point, but at least it allows for some precision floating point. Using 32 bits (a long) this will make the number range approximately 24 bits (high number of 21 million instead of 16 million for 24 bits). Initial bonus is that it won't slow down adding and subtracting and so things like FOR loops or simple GOTO loops will continue to run just as fast.

Multiplication and division will be harder. I think initially I will implement them like this:

Multiplication:

a * b / 100

Division:

a * 100 / b


This has some major limitations in that the size of numbers to multiply or divide becomes rather small. Plus, simple math like this, breaks, i.e. 250,000 / 1 overflows because its representation would be 25000000 (i.e. for 250000.00), and when multiplied by 100 it becomes 2.5 billion which is past the half mark of 4 billion a 32 bit integer can store. Multiplication is even worse, as numbers as small as 500 can't be multiplied together, i.e. 500 x 500 overflows because its representation is 50000 x 50000 which again equals 2.5 billion.

I could fix multiplication...for variable a and b to be multiplied, I could do this:

a1 = a / 100;
a2 = a % 100;

b1 = b / 100;
b2 = b % 100;

(a1*b1*100) + ((a2*b2)/100) + (a2*b1) + (a1*b2);

But that is a lot of computation for a simple operation (and I don't know how to fix division similarly). In the end, I will implement multiplication and division with Digital 'C' SE's floating point library calls and then copy its result back into a 32-bit long value. This will guarantee I only overflow when I'e hit the absolute max.

So with the initial change to 32 bit and the simple implementation of multiply and divide above, there are really only two places I need to change code to get this to work: 1) in the PRINT routine, to make sure I normalize (divide by 100) when printing out (and decide when to print decimal and when to ignore it), and 2) any place I either parse or input a number, where I need to make sure to multiply by 100 and ensure it's an integer.

Those are my next steps.


Edit: I guess I could speed up the convoluted multiplication by doing this, though that is still a lot of processing:

a2 = a % 100;

b1 = b / 100;
b2 = b % 100;

a*b1 + ((a2*b2)/100) + (a2*b1);

[bwinkel67]

there are really only two places I need to change code

...oh, I forgot about GOTOs and GOSUBs, since you can do GOTO 100.50, which takes you to line 101 and GOTO 100.49 takes you to line 100...so ZX81 jump statements do rounding here. To fix that, I would basically do this formula, with "a" containing the value to jump to.

a + 50 / 100

So if a is 100.50 (i.e. 10050) you'd get 10100 which comes to 101. Same with 100.99 (i.e. 10099) which would get you to 10149 which also comes to 101. But if it's 100.49 (i.e. 10049) you'd get 10099 which comes to 100 and for 100.00 (i.e. 10000) you'd get 10050 which also comes to 100. So that all works.

[bwinkel67]

Finished implementing my first crack at adding floating point (well, maybe fixed point, or a very limited floating point of 2 decimals) to ZXSimulator. I only added the mechanism previously specified (i.e. multiply everything by 100 so that the number 1 is stored internally as 100, the number 1.5 is stored as 150, etc. I think I got it working. Not sure if I'm doing array indexing properly -- i.e. A$(X) where X = 10, internally is done A$( (X+50)/100 ). There's lots of code handling the ZX81's complex array sub-ranging.

Presently I haven't changed types, so everything is 16 bits, which makes things very limited (leaves only 13 bits for positive whole numbers). So I can only multiply numbers smaller than 2 right now (i.e. 1.2 * 2.3 works, but 2 * 2 doesn't since internally that's 200 * 200 (i.e. 2.0 * 2.0) which yields 40,000 and is greater than half of the 65K limit of 16 bits. It also means I presently can't handle line numbers greater than 320 (i.e. GOTO 320 is internally represented as GOTO 320.00 or 32,000, so anything bigger than that and it becomes a negative number).

This was only a quick implementation for proof of concept. All the math is currently working and it prints out decimal values when needed -- i.e. PRINT 1 / 2 now gives 0.5, and PRINT 2 / 4 gives 0.25, etc... You can also now step through a for loop in fractions -- i.e. FOR I = 1 TO 10 STEP 0.5 works. Next I'll change it to 32 bits and see if all my old BASIC demo programs still work (BANNER.BAS, BATTLESHIP.BAS, ELITE.BAS, etc...) as well as do timings to see how slow things have become. That's followed by integrating Digital 'C' SE's floating point library for math operations other than + and - and all the ZX81 supported math functions. The final step will be to optimize things time and space wise again...that usually takes the most time.

Here is the 16-bit floating point beta version to try (includes executable plus the Digital 'C' SE source code). Again, keep the internal representation in mind so small numbers become big quickly when multiplying, and even with addition, anything over a few hundred hits the limit as well since we really only have 13 bits available for holding the actual positive numeric value.

zx_beta.zip

(29.71 KiB) Downloaded 11 times

[M68008]

This is known as "fixed point" arithmetic (rather than "floating").

[bwinkel67]

Yup...though it does stretch between one or two depending on trailing zeros...

[bwinkel67]

Ok, found the two cases where I messed up with both string and integer (DIM) arrays. Seems to be bug-for-bug compatible with my pre-fixed point decimal hack.

zx_beta.zip

(29.68 KiB) Downloaded 12 times

[NormanDunbar]

...but 2 * 2 doesn't since internally that's 200 * 200 (i.e. 2.0 * 2.0) which yields 40,000 and is greater than half of the 65K limit of 16 bits.

If you are using fixed point "floats" with 2 decimal digits, then the answer will have 2+2 decimal digits, so your result, 4.0000, is correct. But...

...Obviously if you are doing singed arithmetic, you have overflowed. Can you not do the arithmetic in unsigned mode and adjust the sign of the results afterwards?

Just a thought.

Cheers,
Norm.

[tofro]

For many, for example graphical, applications, it is enough to let over- or underflow not wrap, but rather saturate. You don't need to be precise in all cases, but at least

i.e. MAXINT + 1 != -1, but rather MAXINT + 1 = MAXINT, and MININT - 1 = MININT
and
positive overflow = MAXINT and
negative underflow = MININT

That is often enough to fulfill what is needed (for applications that want exact values, that obviously won't help).

[bwinkel67]

If you are using fixed point "floats" with 2 decimal digits, then the answer will have 2+2 decimal digits, so your result, 4.0000, is correct. But...

...Obviously if you are doing singed arithmetic, you have overflowed. Can you not do the arithmetic in unsigned mode and adjust the sign of the results afterwards?

The above example was multiplication, not addition. So 2 x 2 (i.e. 2 * 2) internally is represented as 200 * 200 (for 2.00 * 2.00). So 200 squared is 40,000 which is 400.00 but I also divide by 100 to get it back down to 400 (i.e. 4.00, the right answer). The reason I get overflow presently is because I'm only using signed 16-bit, so any intermediate result over 32,768 overflows.

[bwinkel67]

The overflow is temporary since I only changed the underlying mechanism. When I turn things from 16-bits into 32-bits, this will somewhat solve it, though multiplication will still be an issue because even squaring 500 will overflow (i.e. 50000 x 50000 will give you 25 million, and my max signed value for 32-bit will be 21 million (i.e. 2^31 / 100).

As pointed out earlier, I can break down multiplication into this formula, but that's a lot of work for multiplication:

For a * b, instead of:

(a * b) / 100

I do 9 operations:

a2 = a % 100;

b1 = b / 100;
b2 = b % 100;

a*b1 + ((a2*b2)/100) + (a2*b1);


But that won't fix division, which will overflow pretty quickly as well because I have to multiply the first argument by 100...

For a / b:

(a * 100) / b


Note that all this will be solved when I'll eventually add 48-bit floating point operations for multiplication and division. There, I will convert my 32-bit integer fixed-point representation to 48-bit, do the operation, and convert back to 32-bit. Hopefully that will be more efficient than the above 9 operation attempt for multiplication.