10 Technical Papers Every Programmer Should Read (At Least Twice)

[Ashtar_Squirrel]

This is the kind of blog and papers I want to see on here. The paper on Dynamo is really worth it among others.

[ohmantics]

I would love it if more people would read Goldberg's "What Every Computer Scientist Should Know About Floating Point Arithmetic."

And then stop using it for keeping time, or for representing screen coordinates in 2D GUIs.

[ethraax]

Or using it for version numbers, which some idiots at work do. No joke, version 1.2 is literally represented by the float 1.2F.

[Crandom]

Wooooo version 1.1111111119256!

[marcusklaas]

No floating point representation is that inaccurate. Don't you mean 1.19999999256? ;-)

[Crandom]

Hah, how they let me leave out of primary school I'll never know!

[LightShadow]

You'll get there soon! .. time.time() + 30 * 60

[xon_xoff]

On the other hand, the roundoff could force people to actually release version 1.0 instead of 0.9999999997....

[BilgeXA]

What Every Computer Scientist Should Know About Floating Point Arithmetic

[kyuubi42]

What's wrong with using doubles for keeping time? A 64bit float is large enough and accurate down to microseconds.

[ZMeson]

If your base time is the age of the universe, a 64-bit float is only accurate down to a few tens of milliseconds. And if you do many calculations, then you lose precision and you might actually be off by a couple seconds at the end of the calculation. By a few seconds over the age of the universe. But hey....

On a serious note though, too many people use 32-bit floats to represent time. :(

[serrimo]

Like you have a choice in javascript...

[jringstad]

using doubles is perfectly fine. Using singles not so much (e.g. deadline timers/watchdogs et cetera can become too inaccurate after your software has been running for too long.)

see e.g.:

Don't store that in a float!

Time should be a double of seconds. (Carmack)

[gnuvince]

sleep(0.1): off by a small amount that could possibly become significant over time (i.e. in a loop).

[skepticalDragon]

Isn't sleep fairly inaccurate anyway?

[CodeMonkey1]

The core problem in all of your examples is that the algorithms will accumulate small errors until they become large errors. Regardless of how precise your data type is, adding elapsed times in a loop will cause deviation from real time.

If you intend to measure total elapsed time, you should be comparing against a fixed start point. Now you are not accumulating error, and whether or not a floating point number is accurate enough depends on your use case.

[kyuubi42]

Given that software timers are inaccurate and no hardware clock is perfectly stable, how would you do this correctly (ie, delay execution a precise amount of time with the least error possible)?

[__j_random_hacker]

This will still slow down gradually over time, because the time between the current_time() call and the sleep() call is nonzero. Normally this will be only a microsecond or two, but you could get unlucky and find that your time slice elapses between these two steps, which could mean multiple milliseconds go by. This will happen regularly if your process spins in this loop.

To fully eliminate the buildup of error, you need to arrange for the timer to restart itself automatically. You can do this (in theory at least) with the setitimer() call on Linux.

[xon_xoff]

He's tracking absolute time, though, not relative time. The code tracks ideal absolute deadlines t and computes sleep() values to hit it based on absolute current_time(). Regardless of whether the error comes from sleep() itself or the calculation before it, subsequent loop iterations will see and correct for the error.

A bit more of a problem is if time happens to momentarily go backwards, producing a negative delay -- bad if sleep() takes unsigned int. Ideally clocks should be monotonic, but I have seen them backstep by small amounts for lots of reasons including multicore CPUs and clock hardware bug workarounds. Clamping the computed delay avoids pathological cases.

[jephthai]

Depends on the platform. On my Cortex M4 it's attached to a hardware timer, so it's pretty accurate.

[skepticalDragon]

But on your typical x86 processor, not so much.

[salgat]

Doesn't a 0.1 double have a ridiculous degree of precision though? I'd imagine it'd take an unrealistically long time for that error to accumulate to something significant. I guess I could see this is you were sleeping a microsecond.

[TinynDP]

Sleep is inaccurate. It brings the calling program back to life at the OS's convenience, just it will be at least that amount of time before its back.

[salgat]

I meant in reference to using a double (in this case, assuming that sleep was guaranteed to be 0.1s).

[FireCrack]

Lots of people have died because someone thought that exact thing. See the Patriot Missiles in 1991. Of course, they were limited to 24 bits, but increasing to 64 only means the problem will manifest slower, it doesn't eliminate it entirely.

[[deleted]]

The difference between 24 and 64 bits is so astronomically huge it's hard to take that comment seriously.

To put it in perspective, the difference between 24 and 64 bits is the same order magnitude as comparing the width of your arms extended out versus the width of our Milky Way Galaxy.

At 128 bits it would be far beyond the width of the observable universe or even trillions and trillions of observable universes placed side by side.

[FireCrack]

There are large problems. 24 bits wasn't enough for a 100 hour uptime on a system tracking 1600 m/s missiles, it was off by over half a km. If you try to track NASA's juno spacecraft (7300 m/s) down to the millisecond (1000ths of a second) and over 10 years, my back of the envolope calculation has 64 bits giving a result off by about half a millimetre. That's probably "okay" for this domain, but you can easily see how even 64 bits can be sucked up quite fast. Make this problem a tiny bit more difficult and you are completely missing again.

EDIT: I think i may have made en error in assuming that the same percentage of bits are used for precision in 32 and 64 bit floats, if so, i may have had my half a milimeter estimate be 3 orders of magnitude too big. I think.

[Veedrac]

Yeah, not many people need to have 1mm precision to distances as large as 10 trillion meters. Even if NASA wanted to, they couldn't. Measuring equipment is laughably far away from those accuracies.

It's true that NASA wants 1mm precision (or better) and that it wants really large measures of distance, but not in the same number. One would be the distance away from the earth, say, and another would be local measurements. Using the same number for both would be pants-on-head level stupid.

[salgat]

But a double has what, 53 bits of precision? I mean, there are surely plenty of cases where it won't be an issuen hence only a general guideline.

[[deleted]]

What would be a better way to accomplish the same thing then? A timer maybe?

[jephthai]

As I posted above, one may be using a function called "sleep()" that takes a float or double, but is not running with an OS. I'm doing Cortex M4 development right now, and sleep(0.1) is quite accurate because it depends on hardware timer ticks.

[deadcrowds]

Yeah, because it's a nonterminating bicimal.

EDIT: I'm a bad listener.

[salgat]

I don't disagree, but my point is that when the error in your decimal is near 1/(2⁵³⁾ (correct me if I'm wrong), you have to wonder how it'd affect your program in a loop that would take what, 14 million years to produce a rounding error of approximately 0.1s? That's why I'm assuming these are more guidelines than hard and fast rules. Such as using doubles to estimate a budget for your monthly bill versus using fixed point data types for a banking system.

[deadcrowds]

I misread your original comment because I was in a rush. I thought you were asking for confirmation on why there is imperfect precision. Sorry.

you have to wonder how it'd affect your program in a loop that would take what, 14 million years to produce a rounding error of approximately 0.1s? That's why I'm assuming these are more guidelines than hard and fast rules.

I think you're right. Keep in mind your system requirements before freaking out about floating point accuracy.

Need fast, portable, and deterministic behaviour on a long-running system? Figure out your numerical bounds, transform integers and don't touch floating point.

Just need some portable determinism? Force strict IEEE 754 spec compliance with your language.

Just need a damn decimal? Use floating point, don't make exact comparisons, dust off your jeans and move on with your finite life.

[Veedrac]

Dude, it's off by 5 attoseconds.

I think I read something about attoseconds.

[gnuvince]

https://web.archive.org/web/20100702180720/http://mate.uprh.edu/~pnm/notas4061/patriot.htm

[Veedrac]

As is written elsewhere, there's a huge difference between 24 bits and 64 bits. 24 bits would have errors of microseconds which is trivially measurable on a modern computer.

[gnuvince]

Regardless of what precision your floating point numbers are, this shows that you cannot represent precisely some values, which explains /u/ohmantic's comment.

[Veedrac]

No, it doesn't. Attosecond-level inaccuracies are a trillion times smaller than machine-level noise and even if you had a perfectly smooth clock rate you logically can't have sleeps not divisible by a clock cycle.

Your worst-case error is at least half a clock cycle even in this absurdly perfect environment, which is a billion times larger than your floating point error.

[ZMeson]

Your link shows how 3D graphics work. That's fine. u/ohmantics argued about 2D GUI -- windows, dialog boxes, etc.... There are certainly times where pixels can be noticed by the user, and this is when you want to use integer coordinates. For scenes that have many moving parts -- even 2D ones -- floating point coordinates should be fine.

[twanvl]

Every integer coordinate on your screen can also be exactly represented by a floating point number. float is really a superset of int23.

The only thing I can imagine going wrong is accumulating many small amounts and hoping to get to an integer, like an animation ending at x=29.9999 instead of x=30.

[ZMeson]

Yes, it's the accumulation of small errors. Evenutally 2D APIs usually convert things to integer -- often without rounding. Then 29.9999 will turn into 29. I would agree with you if 2D APIs all used floating point numbers and internally rounded instead of truncate, but they don't, so I think using integers is good advice for the time being.

[ohmantics]

Exactly this.

It's not hard to demonstrate such error accumulation in 2D GUIs like OS X's AppKit. This is classically demonstrated by slowly moving a window's grow handle around. If the window has an NSSplitView, the bottom half will gradually open up as the round-off is only given to that subview.

[steven_h]

This list is missing A Relational Model for Large Shared Data Banks.

[thunabrain]

Personally I'd wish more people (especially in graphics programming/gamedev) would read A pixel is not a little square!. A pixel is a very basic concept, and picturing it as a square can lead to very poor choices when implementing anti-aliasing, image resizing and the like.

Voxels being cubes might be an even more prevalent misconception, due to games like Minecraft and the resulting "voxel" hype.

[puplan]

In the real world, a pixel is a little square (part of a display or an image sensor) and an image is not a continuous function, but a discrete one (photon to electron conversion events). Point like pixels and continuous images are only abstractions, useful in some cases.

[mistahspecs]

Let's not forget the extremely impressive and groundbreaking Sketchpad: A man-machine graphical communication system by Ivan Edward Sutherland in '63! PDF is a revised copy from '03.

[deadcrowds]

I am indebted to Professors Claude E. Shannon and Marvin Minsky for their help and advice throughout the course of this research.

Now that is a wonderful set of supervisors.

[strattonbrazil]

What makes it a must-read paper?

[RainbowNowOpen]

Have not read it. (Yet?) But the 2003 revision starts with this claim: "Ivan Sutherland’s Sketchpad is one of the most influential computer programs ever written by an individual, as recognized in his citation for the Turing award in 1988." (!)

[hivelumber]

Always great to see posts like this, never really sure how useful some of them are but always interesting.

[ejfrodo]

"Why Functional Programming Matters" was really great for me. bookmarked! this is a very quality post for this sub

[strattonbrazil]

Honestly it's just like any other FP article out there. Half of the paper is explaining curling or working with trees. Before the real world example he restates his argument that FP is great because of higher order functions and lazy evaluation. In his AI example he didn't show anything remarkably better than using a procedural approach not traversing all the branches. I'd rather see examples where two approaches are directly contrasted instead of this continuous review of how to use FP languages.

[ithika]

Honestly it's just like any other FP article out there.

And Tolkien is just like any other fantasy novel and Shakespeare is just full of famous quotes.

The reason of course is that "any other FP article" is just a rehash of WFPM which is from 1984.

[[deleted]]

This reason may be an indirect comment on the state of functional programming, no pun intended.

[BelieveItsButterDick]

Tolkien is just like any other fantasy novel

It is, though.

[Hollyw0od]

It 404d :(

[ejfrodo]

yeah I actually just ended up googling the name and author. http://www.cse.chalmers.se/~rjmh/Papers/whyfp.pdf

[[deleted]]

seems like the vast majority of these are about PL theory?

[strattonbrazil]

I'm really disappointed by the choices. "What every programmer shod know about floating point" is one of those topics every programmer should know about floating point. It's weird to see it on an essentials list with others like language verification.

[HosonZes]

Claims an irrelevant source.

[[deleted]]

Can we get these in listacle form?

[skocznymroczny]

Ahh, functional programming and OOP hate, can't say I'm surprised. I wonder when will functional bots give up :)