Meaningfulness of division by zero in computer science

You can talk about almost anything that you want to on this board.

Moderator: Moderators

Post Reply
User avatar
aa-dav
Posts: 153
Joined: Tue Apr 14, 2020 9:45 pm
Location: Russia

Meaningfulness of division by zero in computer science

Post by aa-dav » Fri Nov 27, 2020 10:51 pm

In recent theme I recall something holiwaric, but imho interesting.
There is simple unsigned integer binary division algorithm:

Code: Select all

N := dividend
D := divider
Q := 0 // result
R := 0 // remainder
for i := n − 1 .. 0 do // n - bits number
  R := R << 1           
  R(0) := N(i) ; operator(i) = i-th bit
  if R >= D then
    R := R − D
    Q(i) := 1
  end
end
In it's core it just the same as we do division on math lessons (so called long division) "column by column", but binary application is even simpler (like multiplication).
And it has interesting feature also: it can divide by zero. And this process has absolutely the same count of steps like with any other divider.
It produces results with all binary digits set to 1, that is 'closest to infinity'.
At the same time it produces remainder equal to dividend.
This is tricky thing because if we check result by formula of integer division check we get: (111...1111 * 0 + remainder = dividend) == true. :D
However such a remainder violates exact definition of math remainder, but algorithm do really tries to get as meaningful result as possible!

And yes, I know that real math doesn't allow division by zero under any circumstances (Numbephile youtube channel has good explanation why for example).

But my question is: could this answer be useful in computer applications?

One example: what if we calculate count of segments/lines of circle for CAD system with extreme and wrong zero size of segment: we'll get count of segments which cannot be allocated in all computer memory (size_t in C++ = MAX_UNSIGNED_INT), so it's not if ( zero ... ), but malloc function will fail and we'll get rid of one unncececery check/condition. Sounds self-consistent...

calima
Posts: 1298
Joined: Tue Oct 06, 2015 10:16 am

Re: Meaningfulness of division by zero in computer science

Post by calima » Sat Nov 28, 2020 2:45 am

Max uint is 4gb, which is a side meal of RAM for modern apps. Even allocating 16 exabytes (2^64) may succeed in places, since it's a virtual allocation and it all doesn't get used at the point of allocation.

User avatar
aa-dav
Posts: 153
Joined: Tue Apr 14, 2020 9:45 pm
Location: Russia

Re: Meaningfulness of division by zero in computer science

Post by aa-dav » Sat Nov 28, 2020 3:45 am

calima wrote:
Sat Nov 28, 2020 2:45 am
Max uint is 4gb, which is a side meal of RAM for modern apps. Even allocating 16 exabytes (2^64) may succeed in places, since it's a virtual allocation and it all doesn't get used at the point of allocation.
Ah, yes. Mess with int and long long on 64-bit platforms makes it impossible to use/control.
But legal allocations 2^64 seems bad API for me despite of vitual pages.

User avatar
rainwarrior
Posts: 8000
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Meaningfulness of division by zero in computer science

Post by rainwarrior » Sat Nov 28, 2020 5:15 am

aa-dav wrote:
Fri Nov 27, 2020 10:51 pm
I know that real math doesn't allow division by zero under any circumstances
That's not really true.

The default state of things, in math or computing, is that division by zero is "undefined". That means that in the general purpose case you really can't assign any meaningful value to X/0.

Whether that means it is disallowed entirely depends on the context. In many computing contexts it is disallowed by means of a hardware exception, that might crash your program or trigger an error handler if you divide by zero...

However, it doesn't have to be. There are tons of situations where it's useful to just allow it and define some behaviour for it. (There's even situations where it's useful to allow it and still not define a behaviour for it...) I believe there are contexts in mathematics where this is useful as well, but I know more about computer science, and there's definitely a lot of places it comes up there.

IEEE 754 floating points actually have a representation of +/- infinity, and define division by 0 to use it. (There is also a positive and negative 0 representation, by the way.) It can be made to trigger an exception, but it doesn't have to.

e.g. in C++ you can check for infinity: std::isinf

A trivial example might be when you're looking for an angle via an arctangent calculation from just a slope value. Having +/- infinity there gives you a way to hit those two perfectly valid straight up and down angles.

User avatar
aa-dav
Posts: 153
Joined: Tue Apr 14, 2020 9:45 pm
Location: Russia

Re: Meaningfulness of division by zero in computer science

Post by aa-dav » Sat Nov 28, 2020 5:47 am

Oh, I forgot to mention that I mean integer divisions only (as algorithm in the beginning). And mostly in context of 8/16-bit calculations due to algorithm application.
I know that FPUs use special values to propagate errors / special conditions. Yes, it really has rationale in calculation processing.
But integers don't have special values - we just get value that integer algorithm gives and I question: isn't it safe to use it as is?

tepples
Posts: 22274
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Meaningfulness of division by zero in computer science

Post by tepples » Sat Nov 28, 2020 10:03 am

aa-dav wrote:
Fri Nov 27, 2020 10:51 pm
And it has interesting feature also: it can divide by zero. And this process has absolutely the same count of steps like with any other divider.
It produces results with all binary digits set to 1, that is 'closest to infinity'.
At the same time it produces remainder equal to dividend.
This is tricky thing because if we check result by formula of integer division check we get: (111...1111 * 0 + remainder = dividend) == true. :D
However such a remainder violates exact definition of math remainder, but algorithm do really tries to get as meaningful result as possible!

And yes, I know that real math doesn't allow division by zero under any circumstances (Numbephile youtube channel has good explanation why for example).
True of real numbers R. In the projectively extended real line, denoted R ∪ {∞}, division of any nonzero number by 0 produces the number ∞. And on ARM, if your platform provides division as a software interrupt, you can use the instruction swine (oink oink) to divide only if a comparison or other result is nonzero, loading the approximation to ∞ otherwise.
aa-dav wrote:
Fri Nov 27, 2020 10:51 pm
But my question is: could this answer be useful in computer applications?
Tying into what rainwarrior mentioned: I have found it useful in 3D math on a platform without floating-point hardware (the Game Boy Advance), as zero vertical distance from the horizon in a floor plane corresponds to infinite distance from the camera. Perhaps the connection to perspective projection is why it's called projective infinity.

As for safety: It's safe if you know how to handle infinity-like values without unsafe wrapping.

User avatar
Nikku4211
Posts: 377
Joined: Sun Dec 15, 2019 1:28 pm
Location: Bronx, New York
Contact:

Re: Meaningfulness of division by zero in computer science

Post by Nikku4211 » Sat Nov 28, 2020 10:15 am

It's necessary if, for example, you make a program to find out the domain of a certain function.

For example, to find out the domain of y=6/x-5, you might need to find the value of x that results in the denominator being 0 so that you can know that it's not a part of the domain since it's complex infinity.

Just something I learned in high school algebra...
Last edited by Nikku4211 on Mon Dec 07, 2020 2:07 am, edited 1 time in total.
I have an ASD, so empathy is not natural for me. If I hurt you, I apologise.

User avatar
rainwarrior
Posts: 8000
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Meaningfulness of division by zero in computer science

Post by rainwarrior » Sat Nov 28, 2020 2:01 pm

Thinking about it, I think this is the situation where it's come up the most often for me:

Normalizing a 2D or 3D vector. e.g. when I want a direction from one point to another.

So it's multiplying (x,y,z) by 1/sqrt(x^2+y^2+z+2)... but when they end up in the same position it's a division of 0 by 0. One tiny case in the space of all the rest, but a single invalid calculation might be all it takes to ruin the whole thing.

So a lot of the time I've defined this particular 0/0 to be 0 i.e. a "direction" vector of (0,0,0). Other times when I still needed a direction I might have defaulted it to (1,0,0) or perhaps whatever the last valid direction was. In some cases the 0/0 case didn't matter so I just left it undefined.

User avatar
Ben Boldt
Posts: 749
Joined: Tue Mar 22, 2016 8:27 pm
Location: Minnesota, USA

Re: Meaningfulness of division by zero in computer science

Post by Ben Boldt » Mon Dec 07, 2020 12:39 am

0/0 is a special case of undefined number, considered indeterminate.

From what I understand (which is often subject to error) an undefined number very broadly might not have a value or it might have multiple values, or infinite values. An indeterminate number is more specific, where it is known to have a value, but there is not enough information provided to know what the value is.

User avatar
rainwarrior
Posts: 8000
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Meaningfulness of division by zero in computer science

Post by rainwarrior » Mon Dec 07, 2020 2:38 am

aa-dav wrote:
Sat Nov 28, 2020 5:47 am
But integers don't have special values - we just get value that integer algorithm gives and I question: isn't it safe to use it as is?
No, in many contexts it is not safe to allow any division by zero. In some contexts, defining it as all bits set like that is perfectly fine. It always depends on the situation.

That's the whole point of it being undefined for the general case. There's no rule for how it should behave that is universally applicable.

User avatar
aa-dav
Posts: 153
Joined: Tue Apr 14, 2020 9:45 pm
Location: Russia

Re: Meaningfulness of division by zero in computer science

Post by aa-dav » Mon Dec 07, 2020 2:46 am

rainwarrior wrote:
Mon Dec 07, 2020 2:38 am
No, in many contexts it is not safe to allow any division by zero. In some contexts, defining it as all bits set like that is perfectly fine. It always depends on the situation.
I have suspicion that in 8-bit world '11....111' answer is always correct in every possible application.
So I question: where I could be wrong? What possible application gives wrong behaviour?

User avatar
aa-dav
Posts: 153
Joined: Tue Apr 14, 2020 9:45 pm
Location: Russia

Re: Meaningfulness of division by zero in computer science

Post by aa-dav » Mon Dec 07, 2020 2:51 am

Ben Boldt wrote:
Mon Dec 07, 2020 12:39 am
0/0 is a special case of undefined number, considered indeterminate.
Technically if we divide by zero we could produce two answers: +inf and -inf.
And they are opposite of each other by more than infinity.
That is wrong in any sense.
We could get it in some application in floating point numbers of -+zero and so on, but this is not answer in any way.
It's just a way to say we had error.

User avatar
aa-dav
Posts: 153
Joined: Tue Apr 14, 2020 9:45 pm
Location: Russia

Re: Meaningfulness of division by zero in computer science

Post by aa-dav » Mon Dec 07, 2020 2:56 am

P.S.
And again: I do not say that '111....111'' answer is correct in mathematical way.
I question: isn't it behaves correctly?
That is: giving out of memory error as is?

User avatar
Dwedit
Posts: 4408
Joined: Fri Nov 19, 2004 7:35 pm
Contact:

Re: Meaningfulness of division by zero in computer science

Post by Dwedit » Mon Dec 07, 2020 8:53 am

I'm with rainwarrior on the Normalizing a Vector thing, with magnitude 0, and you want to get magnitude 1 by dividing, you should stay with magnitude 0.
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!

User avatar
rainwarrior
Posts: 8000
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Meaningfulness of division by zero in computer science

Post by rainwarrior » Mon Dec 07, 2020 12:56 pm

aa-dav wrote:
Mon Dec 07, 2020 2:46 am
So I question: where I could be wrong? What possible application gives wrong behaviour?
Well, in most applications doing division by 0 is invalid, so in all of those cases there is no possible wrong behaviour. Any result is equally valid, even crashing. So, yes this algorithm is just fine for that, as is any other.

If you want a special case only where 0/0 = 0, like the example I mentioned above, that all 1s result isn't helpful. However, checking for 0 as a special case is usually fairly benign, and you could still use the algorithm for the other cases.

I agree that there are lots of applications where clamping "infinity" to MAX_INT could be useful, and I agree that for the majority of other cases it isn't "wrong" but only in the way that division by 0 will already be avoided. It's a good division algorithm, suitable for many purposes. Is it okay for every application? No. However, I must admit I don't want to go to the trouble of finding/constructing another example to prove this to you at the moment, so you can take or leave my assertion.

Post Reply