Microsoft not patenting enough

Bill, in his BBC article, writes of Microsoft: “In 2004 Ballmer announced that Linux infringed 228 Microsoft patents; in 2007 company lawyer Brad Smith said it was 235.”

Are Microsoft really seriously suggesting that in 3 years they only developed 7 patents that covered stuff in Linux? Are they asleep at the wheel or something?

Brake with your left foot

The driving manual has one recommended procedure where you should brake using your left foot:

After fording you should keep your right foot on the accelerator (to avoid stalling) and test your brakes with your left foot.

Needless to say, do this gently and after informing other people in the car that you are about to test your brakes using your left foot.

Awesome Shell Power: stupid z trick

Say you want to move all the files in the current directory down into a new directory called “awesome”.

Instead of:

mkdir awesome
mv * awesome

which is likely to complain: “mv: rename awesome to awesome/awesome: Invalid argument” (though it does in fact work), you might try:

mkdir z
mv *
mv z awesome

This “works” when the newly created directory, called “z”, comes at the end of the list that “*” expands to. You weren’t in the habit of creating files beginning with z were you?

Lisp: coerce float to rational

Since all floats are mathematical rationals you might expect to be able to coerce a float to a rational. But you can’t:

* (coerce 1d0 'rational)

debugger invoked on a SIMPLE-TYPE-ERROR:
  1.0d0 can't be converted to type RATIONAL.

Here’s a function which does what (coerce x 'rational) might do:

(defun coerce-float-to-rational (x)
  (declare (type float x))
  (let ((b (float-radix x)))
    (multiple-value-bind (signif e s) (integer-decode-float x)
      (* s signif (expt b e))))) 

[Edit on 2007-07-12: jaoswald points out that this functionality is provided by the function rational. So my code could be (part of) an implementation of rational.]

Example:

CL-USER> (coerce-float-to-rational 3.141592653589793)
13176795/4194304                                                                
CL-USER> (coerce-float-to-rational 3.141592653589793d0)
884279719003555/281474976710656                                                 

Numbers that are mathematical integers (which includes all sufficiently large ones) come out as integer objects. Note that for very large numbers you quickly exhaust the precision of the underlying float type:

CL-USER> (coerce-float-to-rational 1e10)
10000000000                                                                     
CL-USER> (coerce-float-to-rational 1e20)
100000002004087734272                                                           

The smallest number

SBCL doesn’t correctly read this number:

* 2.4703282292062328d-324

0.0d0

Bad Lisp. To your room and no snacks.

Python does:

>>> 2.4703282292062328e-324
4.9406564584124654e-324

The reason Python reads «2.47…» but then prints «4.94…» is because the value that it converts the input to is the smallest positive number in IEEE 754 double precision. As I pointed out whilst I was badmouthing the C# standard this is 2^-1074. The number immediately below 2^-1074 in the double type is +0 and the number immediately above it is 2^-1073. Thus for x such that 2^-1075 < x < 3*2^-1075, x gets converted to 2^-1074 because that’s the nearest member of the double type.

The shortest way to write this number (which I suggest is best) is 5e-324. But because the relative input error is so large for this denormal, we can use anything from 3e-324 to 7e-324 (we don’t even have a single digit of precision when our denormals get this small).

Reading the Common Lisp Hyperspec I’m a bit shocked. There doesn’t seem to be any discussion of the meaning of a number when it is read. In other words whilst the spec says that reading «1.1» results in a number, it doesn’t say what number it is (does it? It wouldn’t be the first time that I’ve missed something obvious). It doesn’t say this even for integers. For integers we can take the stunningly obvious as read: an integer when read is converted internally to an integer that has the same mathematical value as its external representation. For reals it’s not so clear. In most (all?) implementations the real number 1.1 will not be representable exactly, we’ll have to choose some number to approximate it. A sensible thing to do is to choose the member of the target type that is closest to the mathematical value of the decimal number. This allows (as long as printing is good enough) floating point numbers to be printed and read without loss.

It seems like an argument could be made that when the reader underflows a number to 0 (as SBCL did with my first example) then it should signal a floating point underflow error. “Should” in the sense of “at safety level 3”. SBCL doesn’t signal an error for this code: «(progn(declare(optimize(safety 3)))(expt 2d0 -1075))», so I don’t hold out much hope of seeing the reader signal an error.

Of course, SBCL is perfectly capable of representing and printing the smallest number:

* (expt 2d0 -1074)

4.9406564584124654d-324

I guess I’ll have to read that Clinger paper after all.

Stop Press: CLHS doesn’t, strictly speaking, support floating point formats that use denormals. Bad standard.

Python: poor printing of floating point

See how Python prints a simple decimal number:

>>> 94.8
94.799999999999997
>>>

[edit on 2010-01-26: allegedly this is all fixed in Python 3.1. Please skip article if that’s okay with you]

In an attempt to dispell comments on the lines of “floating point doesn’t produce exact answers”, I should point out that I know:

• Floating point is tricky; and,
• 94.8 is not exactly representable as a floating point number.

Without delving into the arcane details of floating point let’s lay out some basics. Each floating point value is some exact real number, in fact a rational number. I’m ignoring NaNs and infinities because they’re not important for this discussion. There are only finitely many floating point values.

With regards to input and output of floating point numbers what is reasonable?

Reasonable input requirement

Every decimal number has some floating point number that is nearest (possibly two if it lies midway between two adjacent floating point numbers). It seems reasonable to me that when converting decimal numbers to floating point numbers (as Python does when it reads 94.8 in the program) it should pick the nearest floating point number to represent it internally (and if there are two such nearest, then pick one). (For very large magnitude numbers you might want to return infinity or throw an exception; doesn’t matter for this article.)

Reasonable output requirement

When converting a number from internal floating point format to decimal (as Python does when printing) it seems reasonable to print one of the decimal numbers whose nearest floating point number is the one we are printing. In other words we would like to print a number that when read according to the reasonable input requirement (above) we get the same internal floating point number. Note that there are infinitely many decimal numbers with a given nearest floating point number (because there are only finitely many floating point numbers); once you’ve printed enough decimal digits to zoom in on the desired floating point number you can keep on printing whatever digits you like, generating lots of different decimal numbers all of which share the same nearest floating point number.

Python certainly meets our reasonable output requirement. 94.799999999999997 and 94.8 share the same nearest floating point number.

Desirable output requirement

Consider the two number 94.799999999999997 and 94.8. By our reasonable output requirement above, they’re both good numbers to print out, but the shorter one is easier to read and think about for humans. It also satisfies an elegant principle: Don’t print out any more digits than you need to.

So a desirable requirement for printing out numbers is that we print out a number that meets the reasonable requirement, and is the shortest possible of all such numbers.

If you need a bit of persuading that shorter is better, then this argument might help you: Consider π (pi). An approximation to 18 decimal places is 3.141592653589793238. Now imagine you have written a Python program to compute π as accurately as it can. It prints 3.1415926535897931. That last digit is wrong. It’s not so much wrong as unnecessary, 3.141592653589793 represents the same floating point number:

>>> 3.141592653589793 == 3.1415926535897931
True

By printing that extra garbage digit Python is misleading you as to how many digits of precision it has.

Can we be desirable?

So how easy is it to generate reasonable output and desirable output? Well it turns out to be a bit trickier than you might think on first blush, and it requires bignums. On the other hand, this stuff was all sorted out about 30 years ago, and every reasonable machine is large enough to do bignum arithmetic without busting a gut. Unfortunately the gurus Steele and White didn’t publish the algorithm until 1990 (see [SW1990]). To quote them: “Why wasn’t it published earlier? It just didn’t seem like that big a deal; but we were wrong.” Boy were they wrong. Even 17 years after publication, modern implementations of modern languages running on modern hardware still get it wrong.

[Political rant: I’m inclined to think that one the contributory factors is that the article was published by the (“we love dead trees”) ACM. It just doesn’t seem helpful to lock all this knowledge away and charge for it. I happen to have a photocopied version of this article on paper (I guess that makes me lucky, and able to write this blog article), but in 2007 I can hardly believe that I have to resort to paper copies to do research.]

Bottom line: 94.8 should print out as 94.8.

Python’s excuse will no doubt be that it relies on the platform’s C library. C has an excuse. C targets tiny platforms where it would be ridiculous to suggest that the printing routines use 320 bytes of RAM to store intermediate computations (on a platform I recently had the pleasure to program, this would’ve been about 10% of the entire RAM). On the other hand any platform where I’m actually likely to use double I almost certainly have enough space for both for code and the bignum arithmetic it requires to get the right answer. Certainly, on my MacBook the C implementation has no excuse.

It’s no coincidence that Steele had a hand in writing the 1990 paper and also a hand in designing two of the languages that actually bother to say something sensible about converting internal numbers to external format. Scheme says that reading what you print will yield the same number, and this shall be done using the minimum number of digits. Java says “as many, but only as many, more digits as are needed to uniquely distinguish the argument value from adjacent values of type double”. Curiously, Common Lisp doesn’t seem to actually state anything like that, but possibly I just can’t find it. Common Lisp implementations, of course, get it right, because they’re invested with the spirit of Do The Right Thing. I had a look to see what Haskell said on the matter, but apart from noting with amusement that a literal number did not denote an internal number object I couldn’t find anything. ECMAScript also specifies the Right Thing, but then, Wikipedia reckons that Steele edited the first edition.

Python has automatic memory management, bignums, strings. It feels like a big language, abstracted and distant from the silicon. It’s time for Python to grow up and specify that repr for float returns a decimal string the mathematical value of which is closer to the argument than any other float, and it returns a string with the fewest number of digits.

The trickiest thing about Steele and White’s algorithm is the bignums. Python has bignums. It turns out to be very easy indeed to implement Steele and White’s algorithm in Python. We can then use this algorithm to create conversion routines in the style of ECMAScript or Java. And I have done so. The implementation isn’t very large, but it is too large to contain in the margins of this article. If you want the code then go to, yet another dead before it began sourceforge project, flopri.

Appendix A – Other Stuff I Found On The Way

Comparison with other languages

Compare Python with similar codes in shell, awk, C, and Lisp:

$ printf ‘%.20f\n’ 94.8
94.80000000000000000278
$ awk ‘BEGIN{printf”%.20f\n”,94.8}’
94.79999999999999715783
$ echo ‘#include <stdio.h>
int main(void){printf(“%.20f\n”,94.8);}’ > t.c
$ cc t.c; ./a.out
94.79999999999999715783
$ sbcl –noinform –eval ‘(progn(format t “~,20f~%” 94.8d0)(sb-ext:quit))’
94.80000000000000000000

Bit of a mixed bag isn’t it? At least Lisp gets it right.

Blind Alleys

Python has a module called fpformat which sounds like it might be the sort of place to find optimal floating point formatting routines, but its useless. “unneeded” as its own documentation avers. pprint is no good either; pretty, but no smarts.

Python’s Tutorial

The Python Tutorial, good in many ways, has what I think is a very weak appendix on this matter: Appendix B – Floating Point Arithmetic: Issues and Limitations (warning: fragile looking URL). It reads more like an apology than justification and varies between patronising, annoying, wrong, and helpful. It contains mistakes like:

Stop at any finite number of bits, and you get an approximation. This is why you see things like:
>>> 0.1
0.10000000000000001

As discussed above, 0.1 is a perfectly good approximation to the floating point value that 0.1 becomes on input, so approximation itself is not the reason that Python prints so many digits (don’t believe me, then try evaluating «0.1 == 0.10000000000000001»). The appendix goes on to recommend str if you want prettier output. I think this is the wrong fix for the problem; if Python used a different printing routine for repr then people wouldn’t be driven to str.

“You’ll see the same kind of thing in all languages that support your hardware’s floating-point arithmetic”. No I won’t. Java, ECMAScript, Lisp all get it right.

REFERENCES

[SW1990] “How to Print Floating Point Numbers Accurately”; Guy L. Steele Jr., Jon L White; ACM SIGPLAN’90 Conference on Programming Language Design and Implementation; 1990-06

C#: Not a careful standard

I don’t know why, but I did. I guess I was just curious. I looked at the C# standard, ECMA 334 (now an ISO standard).

A few seconds in I notice the following:

Section 11.1.6 describes the set of values in the double type:

“The finite set of non-zero values of the form s × m × 2^e, where s is 1 or −1, and for double, 0 < m < 2⁵³ and −1075 ≤ e ≤ 970.”

It also says that double is represented using the 64-bit double precision IEC 60559. Now of course I can’t actually get a copy of that standard, but it’s well known that the exponent for double precision is 11-bits wide with a bias of 1023. That means that the smallest (positive) normalised number is 2^-1022; the smallest denormal is 2^-52 times that value: 2^-1074. Still, the C# boys nearly got it right. They’re off-by-one on the top end too, the largest finite double is (2⁵³-1) × 2⁹⁷¹.

Like a boy with a new toy (I discovered Python’s struct module a few days ago), I can check the math with Python:

>>> struct.unpack(‘d’, struct.pack(‘Q’, 1))[0]
4.9406564584124654e-324
>>> 2**-1074
4.9406564584124654e-324

Further on in the same section the standard says: “The double type can represent values ranging from approximately 5.0 × 10⁻³²⁴ to 1.7 × 10³⁰⁸ with a precision of 15–16 digits.” At least they get the range right in decimal. I still find this slightly misleading because down in the denormal range you don’t get 15-16 digits of precision (consider, 3e-324 == 7e-324). It would be more accurate to say “The double type can represent values ranging from approximately 5.0 × 10⁻³²⁴ to 1.7 × 10³⁰⁸, with a precision of 15–16 digits when the magnituitude is greater than approximately 2.2 × 10^-308.”

These are tedious details; some might think them a little bit dull, but they’re details that a standard should get right. After all, if the guy writing the standard isn’t going to get them right, who is? Your vendor? (mwahaha) It’s sloppy and makes me wonder what else might they have got wrong. Am I encouraged to continue reading? No.

Sorry, wrong category because wordpress thinks C, C++, and C# are all the same. Meh.

Python: sign of nothing

Whilst writing a rather longer article related to floating point, and having recently been sensitized to these sorts of issues, I note the following behaviour:

>>> x=-0.0;y=0.0;print x,y
-0.0 -0.0

To my mind this is beyond bonkers, but I’ve been convinced by others before that behaviour I used to think was bonkers may in fact be sensible. The behaviour is obviously caused by the compiler caching the constant values.

Anyone care to defend it?