Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Misusing Floating-Point Arithmetic for Fun and Profit

December 14, 2011

Last week , I promised to tell you how the SPITBOL compiler used the fourth floating-point register.

You may recall that this compiler worked on System/360 , a line of computers with four floating-point registers, one of which it used for all floating-point computation, and two others of which it used to count how many statements had executed. Strange though that technique may seem, it is nothing compared with how the compiler used the fourth register: It initialized the register to zero and never changed it.

It turns out that there were several distinct reasons to keep zero in a floating-point register.

The most obvious reason was that occasionally it was useful to be able to set a floating-point value to zero, either in memory or in another register, and having zero already in a floating-point register made it easier to do so.

A less obvious reason was that, as on most computers, the usual representation of floating-point zero is the same bit pattern as fixed-point zero, namely all bits zero. Therefore, the compiler could use the floating-point register to store a fixed-point zero in memory. Of course, a fixed-point register could have been used for this purpose, but this particular compiler did so little floating-point arithmetic that it was more convenient to use a floating-point register.

However, the real point of keeping zero in a floating-point register was to make it easier to do address comparisons. This notion is so weird that it warrants an explanation.

System/360 was introduced to the world in 1964. At the time, its designers felt that 16 megabytes of memory would be enough for the foreseeable future, so they gave the machine 24-bit addresses and 32-bit integer registers. As a result, it was common for programs — including the SPITBOL compiler — to store an address in the low-order 24 bits of a word along with other information in the high-order 8 bits. In general, instructions that dealt with addresses would disregard those high-order 8 bits.

Suppose you have a linked list in which each link consists of a 24-bit address with 8 high-order bits that are not part of the address. How would you figure out whether you had come to the end of the list? The answer, of course, is that you would check whether the address part of the link is zero.

However, this check was not as easy as it looks. Although using a word as an address disregarded the high-order bits, there was no instruction to compare addresses. Instead, a program would have to

  1. Load the entire word into a register
  2. Execute a separate instruction to turn off the high-order 8 bits
  3. Check whether the result was zero

This operation would require three instructions, and would also need a register devoted to it.

What the SPITBOL compiler did instead was to use a short-precision floating-point compare instruction to compare the word to the register that it kept permanently zero. Short-precision was 32 bits; long-precision was 64 bits. This comparison would work because of the nature of the System/360 floating-point format: The low-order 24 bits of a short-precision floating-point number were the fraction, and a floating-point value is zero if and only if every fraction bit is zero. In other words, the high-order 8 bits, which the program wanted to ignore, corresponded to the sign bit and the exponent, which a floating-point comparison would disregard.

As a result of this technique, every place in which the compiler followed a linked list could execute a single floating-point compare instruction, instead of executing the three instructions. In either case, the instruction(s) would be followed by a conditional jump.

This code makes me cringe every time I think about it — although on reflection, I am not sure why. At least the first objections that come to mind don't apply:

  • System/360 floating-point arithmetic is precisely defined, so there is no question about whether the technique works in all cases: It does.
  • It's not reasonable to object that the technique is nonportable: The compiler is in assembly language, so it's not portable anyway!
  • Although the technique is tricky enough that I would not have come up with it myself, it was well documented: Once you've read the documentation, it isn't particularly hard to understand.

So this is probably one more of those circumstances in which a programming technique that looks truly awful at first glance turns out to be the best way to solve its particular problem.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video