Jump to content
Banner by ~ The Wife of Rengoku
  • entries
    5
  • comments
    75
  • views
    607

Binary Math ("The Wrapping Point")


Splashee

112 views

In game development, maybe the most common way to time "events" is to use a delta time. The absolute time that is considered "now" minus the previous absolute time, gives you a delta time:

Quote

delta time = current time - previous time

You can then multiply this delta time with the events and physics of the game. This is very common but have a lot of problems that creep in later. One of those problems might appear out of nowhere, and is the wrapping point.

 

Consider you have an absolute time of 56670001 milliseconds, and your old absolute time was 54999198. That gives a delta time of 1670803. This delta time is positive. Since you know time always moves forward, the delta time will always stay positive. So you expect that to always be the case. What if that somehow changes? How do you deal with it? Should you deal with it?

 

Over many decades, milliseconds were stored as 32-bit binary values. If we do the math of converting the highest possible 32-bit value into the unit "days", we will get:

Quote

4294967295 / 1000 = 4294967.295 seconds

4294967.295 / 60 = 71582.78825 minutes

71582.78825 / 60 = 1193.04647 hours

1193.04647 / 24 = 49.71027 days

That means, after 49.7 days, the milliseconds counter will overflow, and wrap around back to 0 again.

 

That means, the absolute time that is considered "now", will be smaller than the previous absolute time, yielding in a negative delta time. All of a sudden, time is moving backwards. What that has as an effect depends on what the delta time is used for. But for that odd time stamp, that happens not that often, can cause real headache!

So what? Just add a check:

if (now < previous) delta = previous - now;
else if (previous <= now) delta = now - previous;

Does that solve the problem?

Or what about this:

delta = abs(now - previous);

Using the absolute number, does that solve the problem?

 

Spoiler

It might solve problems, but they are not needed as you can read below...

 

Binary Math has a way to solving the problem for us. It comes in the form of two's complement (read about it here: Binary Math (Subtraction and Negate)). Because negative values are just very large positive values, adding or subtracting such values will automatically overflow the numbers, auto wrapping them into a relative value for us.

Take the example of an absolute time for "now" being 5, and a previous time being 4294967291 (which is -5 in 32-bit). We now have the problem that if we subtract 4294967291 from 5, we will get -4294967286 which is a negative value, and time doesn't move in the negative direction.
But what if the value was wrapping around 4294967296? How can we test this? With modulo of course! Gotta love the modulo operator (not really, as we will get into later):

Quote

delta time = (5 - 4294967291) MOD 4294967296

As you might expect, you will get the result of -4294967286, the same as before. But sadly, using the modulo operator on a negative value to begin with will not give the result we need.

 

Because 32-bit values can only store 4294967296 unique numbers, -4294967286 is actually represented as 10. And if you just do the math 5 - (-5), you will get 10! 10 is positive, and time is moving forward again, even if the absolute time of "now" had wrapped over from 4294967291 to 5 with 10 units. Overflow just works!

So the correct code would still just be be (no need for checks):
 

delta = now - previous;

 

 

But there is a reason why I bring this up. We still have the problem of modulo. If computers just work, but modulo doesn't, then we do have a problem.

The modulus operator, most commonly done with the percentage sign in C derived languages, is the integer remainder of a division:

int dividend = 55;
int divisor = 9;

int quotient = dividend / divisor; // quotient == 6
int remainder = dividend % divisor; // remainder == 1

 

Quote

55           ÷           9              =        6              and       1

Dividend             Divisor               Quotient               Remainder

 

Modulo is mostly used to wrap random numbers, and for cryptography (usually with prime numbers), and we cannot live without that in our daily lives!

 

Modulo is defined as x - y * floor( x / y ) for any number. Somewhat... I wouldn't like to check if that is correct.

 

There is a problem, and I can easiest describe it with an analog clock of 60 minutes (having at least a minutes hand). If you have a time in minutes, any time, which will be a positive number, you can find which minute the minutes hand will be at, on that clock face. Since the clock wraps around every 60 minutes, the math is:
 

Quote

hand = minutes MOD 60

 

If we have the minutes of 16571886, then the minutes hand will be on minute 6.

We know that, if we subtract 7 from 16571886, the minutes hand will be on minute 59. And that is exactly true:

Quote

16571886 - 7 = 16571879

16571879 MOD 60 = 59


It works!

 

Now try this one. You are on minutes 59, and you subtract 61 minutes. Try the math now. You know the result should be 58. Because if you move 60 minutes, you will on 59 again, and one more minute backwards ends you on 58. However, modulo cannot handle this!

Remember the value 16571879 above? It was 59 on the clock, so what if we subtract 61 from that?
 

Quote

16571879 - 61 = 16571818

16571818 MOD 60 = 58

So, that works. So there is a big problem. And that's why it is very difficult to do these wrapping point stuff that the computers do with binary numbers, with so called "real math". So how do we solve these problems with "real math" then? I am still working on a solution to this day, but it is much more complicated than that, when you try to do the above delta time, when using modulo on both absolute times in a similar way as the computer overflows binary numbers, automatically for you.

  • Brohoof 1
  • teacup 2

9 Comments


Recommended Comments

It looks to me more complicated than it should be. By the way, I think modulo for negative numbers has weird behavior.

This is a problem with other counters as well, for example how many bytes or packets were transferred. If you know that the counter can only go up then it is easy to detect when it wraps around and figure out the difference, though you have to have a separate check to see if the device has not restarted (since those counters are reset on reboot).

However, it leaves the problem of the counter overflowing multiple times between checks. For example, a 32bit counter of bytes transferred will overflow every ~34 seconds when the transfer rate is 1gbps. If you check it every minute, you'll get nonsense data because while it is possible to detect that the counter has overflowed, there is no way to know how many times it has overflowed (or even if it has overflowed if the new value if bigger than the old value).

Newer switches and such just use 64bit counters.

  • Brohoof 2
Link to comment

@Pentium100 Have you any idea how to "path up" modulo? I have seen and used a programming technique for a while, but while it works, I is not the solution I am looking for at the moment.
Like patching modulo by adding a bias to make the value go above minus, and then subtracting that bias later, seem to be one idea, but eventually you just try to do an emulation of two's complement on a value that already has two's complement, so you will overflow earlier. Also, I use wrapping mainly on values that have been subtracted, making them relative in any direction, negative and positive. That is where I get in trouble using modulo, but not if using bitwise AND (only works on power-of-two values).

34 seconds is a very small timing window for networking. Overflowing multiple times has always been a problem in digital electronics. Thankfully, larger registers, like 64-bit (which is ridiculously large) solves many of those problems. Same goes with delta times with 64-bit values, which are like in the 5 nanoseconds range and don't overflow for over 100 years or so.

 

Maybe @Metal Brony 42 has any ideas? Hopefully he sees this blog at some point.

  • Brohoof 1
Link to comment
2 hours ago, Splashee said:

34 seconds is a very small timing window for networking.

Definitely, though that specification was made at a time when 10mbps was really fast.

3 hours ago, Splashee said:

Have you any idea how to "path up" modulo?

What is wrong with changing what you are subtracting based on which value is bigger? I somehow don't think that it would be slower than a mod operation, then again, maybe for modern CPUs mod is faster.

  • Pondering 1
Link to comment
On 2021-07-29 at 9:07 PM, Pentium100 said:

What is wrong with changing what you are subtracting based on which value is bigger? I somehow don't think that it would be slower than a mod operation, then again, maybe for modern CPUs mod is faster.

Okay, so let's go back to the analog clock example. Since we only have 60 minutes before it overflows/underflows, that might not be too much to add/subtract a bias value so that negative values can be completely ruled out.

This time, let's do it in binary with logical AND. Since this will work for every value. Problem is, we need to have 64 minutes on the clock to make this work (since we can only do wrapping on power-of-two values).

If we have the minutes of 9605951 (hexadecimal 0x92933F), you can see where this is going? Subtracting a full hour of the clock + 1 minute (0x41) from this value, should result in the same example as the 59 to 58 minutes on the previous example (using modulo) in my post above:
 

Quote

(9605951 - 65) = 9605886

9605886 AND 63 = 62

We went from 63 minutes to 62, with a full hour rewind (where an hour is 64 minutes).

 

Now let's do the same thing but being on 63 minutes. We are going into the negative values now. But logical AND always works correctly:

Quote

(63 - 65) = -2

-2 AND 63 = 62

It works, because of two's complement.

 

Here comes my solution for modulo. This always works too, if we go by the math above:

int wrapped_value = (9605951 - 65); // wrapped_value == 9605886
wrapped_value %= 64; // Just remember, AND 63 and MOD 64 has the same effect on positive numbers!    wrapped_value == 62

if (wrapped_value < 0) wrapped_value += 64; // This is my fix for negative numbers. This is also why I am using code, since we need an if statement

 

Link to comment

The post above bugged out, so I am continuing here:

And now for the negative values. This also works with modulo because of the if statement I introduced:

int wrapped_value = (63 - 65); // wrapped_value == -2
wrapped_value %= 64; // wrapped_value == -2

if (wrapped_value < 0) wrapped_value += 64; // wrapped_value == 62

 

So everything is cool! We now use a divide operation which is slower, than the logical AND, for the exact same result. But things are not so fun when we start introducing values that are also wrapped with the same formula as before.... Yes, we just happen to be on minute 62. That is still in the range of being wrapped at 64. So this math always work as well:

Quote

((9605951 AND 63) - (65 AND 63)) = 62

 

This works with modulo as well if all the modulo operations do that if statement.

 

BUT, what do we need modulo for? We need it when we don't use power-of-two values, such as when the clock has 60 minutes. Now we introduce the wrapping problem that I cannot solve:

Quote

(59 MOD 60) - (61 MOD 60) = 58

Okay, I have no idea why that worked....? I never thought of using MOD on the arguments to the subtraction before. I will need some time to think about this. My examples are very basic compared to what I use wrapping for, so this might still not solve my problems just because this worked.

 

What I was going for is the fact that CPU register values still wrap on power-of-two values, and we introduce two wrapping points incompatible with each other, one for modulo, and one for all the bits of the CPU register we are using.

The wrapping point of 60 will not wrap perfectly subtracting below 0, because we also had an automatic AND of the register size, like for 32-bit (0xFFFFFFFF).

4294967296 / 60 = 71582788,266666666666666666666667

If the register wrapped at (71582788 * 60) == 4294967280 (0xFFFFFFF0), and going below that value would be -1, -2, and so on, then all my problems would be solved.

Link to comment
Pentium100

Posted (edited)

So, what you are trying to do is not just ignore when the counter wraps around (so the difference always stays positive), but you are actually interested in the modulo of the difference and not the difference itself? Did I understand this correctly? 

Can you have a 64bit temporary variable? IF so, you could do something like this to always get a positive diffference.

if ( newts < oldts ) { //assuming that if both values are equal it means the counter wrapped around.
                 dif=newts-oldts;
                  } else {
                    dif=(newts+(((uint64_t)1) << 32))-oldts;
                  }

 

 

Edited by Pentium100
  • Brohoof 1
Link to comment
7 minutes ago, Pentium100 said:

but you are actually interested in the modulo of the difference and not the difference itself? Did I understand this correctly?

Yes! Because it has a very useful attribute to it, bit I don't want to introduce that yet, since it is slightly over complicated.

 

Currently I am working with JavaScript that doesn't support 64 bit values :ButtercupLaugh:
But for my C++ projects, I will see if a 64 bit temporary variable can solve my problem. Not a bad idea!

Link to comment
Pentium100

Posted (edited)

I used this for my mpegts segmenter (one value behaves like a counter, but is 33 bits, so I had to use a 64bit variable to hold it anyway).

If you cannot use 64bit variables, you can probably do something like this:

if (newts < oldts) {
			dif=UINT_MAX - oldts;
  			dif=dif + newts + 1;
} else {
  dif=newts-oldts;

 

Edited by Pentium100
  • Brohoof 1
Link to comment

I'm gonna do some tests today, and see if these 64-bit fixes can be used. I will also try to pinpoint the "real problem" with the wrapping that I am using, which I haven't correctly analyzed yet. That modulo on each absolute value before subtraction into a relative value had an effect, but I know it doesn't work for my task, so I better look into why that is.

Link to comment

Join the conversation

You are posting as a guest. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Add a comment...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...