Examples of floating-point numbers that don’t round-trip losslessly through text conversion in Microsoft BASIC

Question

For a long time I thought it was kind of crazy that 8-bit Microsoft BASIC stores numeric constants in ASCII and has to parse them into its 32- or 40-bit floating point format at runtime. Why not parse the number once, when the user enters the line, and store the number in binary?

The other day I came up with a possible answer: It's really hard to write a pair of functions that can convert between ASCII and binary floating point formats without data loss (source). So the user might use the constant 1.234 in the program, and then, when they go to LIST it, see 1.23399999.

However, Microsoft BASIC at least doesn't use all the precision available when printing floating-point values. The 40-bit format has a 32-bit significand, but it only ever prints 9 decimal digits, so it's throwing away about 2 bits. I'm wondering if this could potentially paper over the accuracy gap when the program prints out numbers it originally read in decimal or parses its own output.

My question is, can anyone think of any decimal numbers that Microsoft BASIC cannot accurately parse and re-output?

The only one I could come up with was 9.99999999, which Applesoft at least prints back as 10.

Answer 1

Once you know the underlying implementation, it’s not too hard to come up with numbers that neither correctly parse, nor losslessly print back. All examples below use Commodore 64 BASIC V2, which is to say, Microsoft BASIC with 40-bit floats.

READY.
PRINT 999999999.25
 1E+09

READY.
PRINT 999999999.25-999999999
 .5

This is not a matter of lack of sufficient precision in the underlying format. The number 999 999 999 ¼ is actually perfectly representable, though it cannot be exactly printed either:

READY.
PRINT 999999999+.25
 999999999

READY.
PRINT 999999999+.25-999999999
 .25

The actual value that comes out of parsing can even depend on the nominally insignificant trailing zeroes after the decimal point:

READY.
PRINT 99999999.9
 99999999.9

READY.
PRINT 99999999.90
 100000000

The first value parses to 99 999 999.90625, and the other to 99 999 999.9375. Neither is printed exactly, though that alone can be probably forgiven.

Answer 2

I'd like to address this bit:

Why not parse the number once, when the user enters the line, and store the number in binary?

As you noted, such conversions can result in "oddities" (there's a name for this, hazing?). One way to address those is to use BCD for storage. BCD is less dense and slower in the math libraries, but it is easier to convert back and forth to ASCII and does eliminate the problem you raise.

And this is what Atari BASIC did, it used BCD and converted all constants to that format at parse time so it didn't have to do it again over and over at runtime. Later BASICs like MSX and others did the same. But there are some other things to consider:

Memory

MS wrote BASIC for the Altair with 4k RAM. To make this work they had to shave every byte they could. Even leaving out string variables and functions and other useful bits, the machine still ended up with only a whopping 780 bytes of free memory for source code.

~30% of the constants in a typical BASIC program are 0 or 1. When converted to MS binary format, these are represented by a 40-bit value (typically). This means that all those 1's and 0's take up 5 bytes of RAM instead of 1. And if we use BCD, we might want another byte to make up for lost precision. So converting these values at parse time would require more RAM to hold the source, and this would quickly eat up all the memory.

This could be addressed by using a special format for small numbers. For instance, it makes a lot of sense to have special tokens for 0 and 1, so these would take up only one byte. Or you could have a separate integer format, which is not uncommon on later BASICs. This would reduce or eliminate the memory hit; for instance, "1000" can be stored in a 16-bit value, which is 2 bytes shorter than the ASCII.

But to make this work, you would have to add code on both the parse and runtime sides to identify the type, convert it, and then do the same when being PRINTed or LISTed. You would also have to convert the value from its storage format to floating point every time one of these constants appears in an expression like PRINT A+10. It's not an expensive conversion, depending on how you store it, but it's still going to add up.

It's not a large amount of code, but likely would have eaten into that 780 bytes enough to offset any upside. On a machine with larger RAM, running larger programs like SST, then you are always going to win out doing this (by a lot in my experience, SST saves as much as 2k) but on the original 4k Altair there's not a whole lot of code to crunch down.

Line numbers

The item above is a tradeoff, whether or not it saves you memory overall is going to depend on the particulars of the program - ones with lots of numbers will end up with savings, and those without, not so much and the extra code might offset it.

But many of those non-0/1 numeric constants are line numbers. In SST for instance, there are 712 constants. Of those, only 43 are floats, leaving 669 ints. 101 of the ints are 0, 178 are 1, leaving 390 non-0/1 ints. Of those, 242 are line numbers. Line numbers average about 3.25 characters long (IIRC), so that's around 750 bytes.

In MS, the number at the front of the line is stored as a 16-bit value. But the ones in the line, after a GOTO or THEN, are stored as ASCII. So if we were to convert all of these to the same 16-bit format at parse time, we'd be saving maybe 250 bytes. Nothing to sneeze at. We would also speed up the runtime because we don't have to call the ASC-to-INT code when we branch, although we do have to add that call to LIST, so a slight slowdown there (but LIST is slow anyway). And as this would be an int value, the inaccuracy doesn't come into play, you're not going to see GOTO 1000.00001.

So for this one, the overall size of the interpreter code doesn't change, you save some bytes on the source side, and the programs run faster... Hmmm, what's the downside here?

I always wonder why no one did this, especially MS, which makes me think I'm missing some really obvious problem here.

Answer 3

Decimal number 0.1 has no exact representation in binary: it could be represented only as infinite binary expansion 0.0(0011) where digits in parentheses repeat indefinitely.

Thus, it can't be represented accurately in any binary float format.