5

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.

9
  • 2
    Sounds to me like a very generic math question about number representation and accuracy Not so sure what the retro part is here - beside the fact that handling them has a long tradition dating back to the very first computer using Float, the Zuse Z1. Also, note that Microsoft BASIC used (at least) 3 different formats, 32 Bit (Altair) 40 Bit (Apple, PET) and 64Bit (Extended BASIC), so they will of course yield different brake off points.
    – Raffzahn
    Commented May 3, 2023 at 5:36
  • You may try looking at the conversion algorithm and coming up with something yourself. Commented May 3, 2023 at 7:29
  • 2
    A good explanation why ZX Spectrum basic stores constants both as ASCII and (its own 5-byte) float. When running a program, only latter value is always used.
    – lvd
    Commented May 3, 2023 at 11:13
  • 1
    @lvd - it stores BOTH? In the source? Interesting. Commented May 4, 2023 at 12:41
  • Yes, both. One can even mangle with a basic program by changing all numers' ASCII parts to nonsense values -- it won't affect a program until one try to edit it. Float parts are precalculated at the time of adding or changing a basic line.
    – lvd
    Commented May 6, 2023 at 16:49

3 Answers 3

6

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.

2
  • It's likely that Microsoft BASIC correctly parses 999999999.25, but it will only ever print 9 digits, so it can't output that number even if it can parse it. I'm looking for numbers that only have 9 significant figures yet still lose accuracy when parsed and re-printed. Commented May 3, 2023 at 23:09
  • No, look at the subtraction result. I also checked the underlying memory representation: 999999999.25 is parsed into 9e 6e 6b 27 fe, i.e. 3999999998 × 2⁻² = 999999999.5. Whereas 999999999+.25 evaluates to 9e 6e 6b 27 fd, which is 3999999997 × 2⁻² = 999999999.25. You might have a hard time finding a rounding error fitting those more specific criteria: even 2⁻¹²⁸ (which you have to write as 2↑-127/2, as 2↑-128 is rounded to zero) is printed as a pretty decently-rounded 2.93873588E-39. Commented May 4, 2023 at 6:23
1

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.

5
  • I thought that the tokenizer could use special tokens for these small-constant cases. However that really only works for integers; once you get into floating point, you pretty much have to store all 40 bits, because values that are simple in base 10 are usually not so simple in binary. So "0.1" probably requires 6 bytes, a "here comes a float" token, plus the 40 bits of the value itself. Commented May 4, 2023 at 20:43
  • I think MS BASIC's original 4K implementation is probably the reason for the unsophisticated approach to tokenizing constants. The parser doesn't do much besides convert keywords into tokens. In Applesoft, at least, unknown keywords and type errors aren't caught until run time. Commented May 4, 2023 at 20:46
  • The parser can't simply collapse numbers the same way it does with keywords because not everything that looks like a number actually is one. To parse LET X100=100 the parser would have to know that the thing after LET is a variable and that the first 100 is part of the variable's name. And it would have to make that same determination every place it sees X100, such as in expressions. Commented May 4, 2023 at 21:05
  • Unless it parses variable names to tokens as well, of course. Commented May 5, 2023 at 23:19
  • Sure, but then it needs to maintain a table of variable tokens. Pretty soon you've got Atari BASIC, which is great, but would never fit into 4K! Commented May 6, 2023 at 14:22
0

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.

2
  • 2
    Even if 0.1 can't be exactly represented in binary, the non-exact representation can still be printed in decimal exactly as 0.1, if you limit to say 7 decimal digits being converted to float32 and back to 7 digit decimal.
    – Justme
    Commented May 3, 2023 at 11:29
  • 3
    True, but this still works: PRINT STR$(VAL("0.1")) produces .1. Commented May 3, 2023 at 23:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .