1

I presently have a clock app that calculates from scratch at every iteration. This means O(1) corrupt bits in my doubles and heavy object creation and deletion as well.

I am wary of running indefinite calculations with doubles or any other floats because O(n) corrupt bits normally accompany every step.

I would like to know if there is an alternate way (in an iOS app) to transform and position clock hands with O(1), or maybe O(log n), corrupt bits after n steps.

In particular, I was wondering what the corruption would be for "At each step, rotate each hand back to the zero position, meaning an affine rotation transformation of -1 * the last rotation the hand received, and then rotate forward by the new angle the hand should have at this step." In Objective-C's floating point arithmetic, is it ever not the case (excluding exceptions like a value indicating a number is corrupt) that x - x != 0.0 exactly? The cases I've seen illustrating floating point corruption bits include Python saying that 1.1 + 1.1 + 1.1 - 3.3 != 0.0; I haven't seen textbook examples of the form x - x != 0.0.

This is not exactly the question of whether a raster image transformed by angle x and then by angle -x is its original self; it may be that the preceding suggestion would work fine for O(1) error on angles but usual corruption in the image drawn and transformed.

What is the minimum "corruption complexity", meaning fewest corrupt bits at end of n calculations, for rendering a clock? Are there O(1) or O(log n) approaches?

Thanks,

Improve this question
2
  • 2
    You are using Big-O notation, which is used for algorithmic complexity analysis, but you seem to be worrying about (propagation of) uncertaincy. You might want to remove the misleading notation. Could you also explain why you have to use doubles (versus integers), and why you doing a full recalculation every x iterations isn't viable (thus limiting the errors)? Commented Oct 12, 2013 at 23:18
  • 1
    I'm very confused why loss of precision would be an issue. If you are making a clock, you're translating the current time into the radial position of a hand. You shouldn't need to feed each iteration into the next, so there's no loss of precision there. For the second hand, there are 3600 potential positions. This is much more coarsely grained than a double. Commented Oct 13, 2013 at 0:16

1 Answer 1

Reset to default
3

For computations like this you really need not care. At least not much.

Just make sure that you don't accumulate the error over too many iterations. Here, too many means something like millions. It takes ages before the error gets close to 0.1%. In in doubt, use double rather than float.

I would like to know if there is an alternate way (in an iOS app) to transform and position clock hands with O(1), or maybe O(log n), corrupt bits after n steps.

Don't think about corruption and bits. There's some numerical error and there are some not exactly simple rules for bounding it. Concerning the absolute error you're safe unless you deal with very large numbers or divide by something close to zero. So you're safe.

is it ever not the case (excluding exceptions like a value indicating a number is corrupt) that x - x != 0.0 exactly?

I've never seen Objective-C, but I'm perfectly sure that x - x == 0.

Python saying that 1.1 + 1.1 + 1.1 - 3.3 != 0.0

Yes, that's fine. Rule 1: Never ever compare two floating point numbers for equality. There's always some error. Rule 2: The error is very small. In this example it's 4.44e-16 (it's using double rather than float). Now imagine what terrible impact this can have on your clock hands.

What is the minimum "corruption complexity", meaning fewest corrupt bits at end of n calculations, for rendering a clock? Are there O(1) or O(log n) approaches?

I guess there's no O(1) approach, unless you can convert it somehow into fixed point arithmetic as otherwise there's always the possibility of the error increasing due to rounding.

I guess, the normal and stupid way (assuming you're doing rotations via matrix multiplications) increases the error like O(n). So after 1e9 iterations you get an error like 4.44e-7. Nothing to worry about.

Improve this answer
2
  • Wish I could give more than one upvote. Commented Oct 13, 2013 at 11:05
  • (and O(n) numerical error corresponds roughly to O(log n) bits, even if you've advised me not to think in those terms.) Commented Oct 13, 2013 at 11:13

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.