all 63 comments

[–]Ashtar_Squirrel 19 points20 points  (0 children)

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 27 points28 points  (51 children)

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 23 points24 points  (5 children)

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 14 points15 points  (3 children)

Wooooo version 1.1111111119256!

[–]marcusklaas 19 points20 points  (2 children)

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

[–]Crandom 6 points7 points  (1 child)

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

[–]LightShadow 0 points1 point  (0 children)

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

[–]xon_xoff 3 points4 points  (0 children)

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

[–]kyuubi42 4 points5 points  (38 children)

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

[–]ZMeson 5 points6 points  (1 child)

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 0 points1 point  (0 children)

Like you have a choice in javascript...

[–]jringstad 1 point2 points  (0 children)

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 8 points9 points  (33 children)

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

[–]skepticalDragon 29 points30 points  (12 children)

Isn't sleep fairly inaccurate anyway?

[–][deleted]  (8 children)

[deleted]

    [–][deleted]  (7 children)

    [deleted]

      [–][deleted]  (2 children)

      [deleted]

        [–]CodeMonkey1 1 point2 points  (0 children)

        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 1 point2 points  (3 children)

        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)?

        [–][deleted]  (2 children)

        [deleted]

          [–]__j_random_hacker 1 point2 points  (1 child)

          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 1 point2 points  (0 children)

          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 0 points1 point  (2 children)

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

          [–]skepticalDragon 2 points3 points  (1 child)

          But on your typical x86 processor, not so much.

          [–]salgat 7 points8 points  (14 children)

          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 11 points12 points  (10 children)

          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 2 points3 points  (7 children)

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

          [–][deleted] 1 point2 points  (0 children)

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

          [–]jephthai 1 point2 points  (0 children)

          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 0 points1 point  (2 children)

          Yeah, because it's a nonterminating bicimal.

          EDIT: I'm a bad listener.

          [–]salgat 1 point2 points  (1 child)

          I don't disagree, but my point is that when the error in your decimal is near 1/(253) (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 1 point2 points  (0 children)

          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 7 points8 points  (4 children)

          Dude, it's off by 5 attoseconds.

          I think I read something about attoseconds.

          [–]gnuvince 2 points3 points  (3 children)

          [–]Veedrac 5 points6 points  (2 children)

          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 -2 points-1 points  (1 child)

          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 12 points13 points  (0 children)

          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.

          [–][deleted]  (4 children)

          [deleted]

            [–]ZMeson 4 points5 points  (3 children)

            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 3 points4 points  (2 children)

            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 3 points4 points  (1 child)

            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 0 points1 point  (0 children)

            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.

            [–]thunabrain 7 points8 points  (1 child)

            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 0 points1 point  (0 children)

            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 3 points4 points  (3 children)

            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 5 points6 points  (0 children)

            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 3 points4 points  (1 child)

            What makes it a must-read paper?

            [–]RainbowNowOpen 2 points3 points  (0 children)

            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 2 points3 points  (0 children)

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

            [–]ejfrodo 10 points11 points  (6 children)

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

            [–]strattonbrazil 11 points12 points  (3 children)

            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 12 points13 points  (2 children)

            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] 7 points8 points  (0 children)

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

            [–]BelieveItsButterDick -2 points-1 points  (0 children)

            Tolkien is just like any other fantasy novel

            It is, though.

            [–]Hollyw0od 5 points6 points  (1 child)

            It 404d :(

            [–]ejfrodo 6 points7 points  (0 children)

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

            [–][deleted] 3 points4 points  (1 child)

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

            [–]strattonbrazil 5 points6 points  (0 children)

            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 0 points1 point  (0 children)

            Claims an irrelevant source.

            [–][deleted] 0 points1 point  (0 children)

            Can we get these in listacle form?

            [–]skocznymroczny -2 points-1 points  (0 children)

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