Java-Gaming.org Hi !
Featured games (91)
games approved by the League of Dukes
Games in Showcase (799)
Games in Android Showcase (237)
games submitted by our members
Games in WIP (865)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Math: Inequality properties  (Read 15793 times)
0 Members and 1 Guest are viewing this topic.
Offline Wiki Duke

?





« Posted 2015-09-30 16:06:05 »

A gentle introduction to the properties of inequalities.

The goal is to give a basic understanding of the basic properties of inequalities.  For more in depth treatment, see the references.  We will only consider mathematical integers and reals and not their computer equivalent (integer and floating-point) to not need to consider issues related to overflow and underflow.  I'm also going to toss in how these are related to geometric operations. (A change of coordinates doesn't change the problem).  The Wikipedia article was the base template for this.  I wanted to say some of the same things but in a different way.  This route allow for comparing the two, which might be helpful for some.

For visualization purposes we can think of the values as being points on a number line and the inequality states how they are ordered on that line.

We start with the basic inequalities:
  • a < b
  • b > a
  • a <= b
  • b >= a

The first two are called strict inequalities and the second two are non-strict.  Note that the values 'a' and 'b' represent arbitrary expressions.  The first says that 'a' is to the left of 'b' on the line. The second says that 'b' is to the right of 'a'. The second pair allow for touching on the line.

By reading the inequalities above from right-to-left we get the converse property:
  • b > a
  • a < b
  • b >= a
  • a <= b

So each pair strict/non-strict are really the same. Where there is no difference in behavior between strict and non-strict, then the non-strict equivalent will be used.  Differences will be explicitly stated.

addition/subtraction
If we add or subtract a value from both sides, it's equivalent to translating the pair and it does not effect the relation.  Given: a >= b, then:
  • a+c >= b+c

comparing against zero
Since we can subtract a value from both sides, we can convert the inequality into a comparison against zero.  Given: a >= b, we can subtract both sides by 'b' or subtract both by 'a', which respectively yield:
  • a-b >= 0
  • 0 >= b-a

multiplication/division
The comparing against zero form converts the relation such that its result only depends on the sign of the expression.  So if we were to multiply by a positive non-zero value c, then the relation doesn't change since the sign does not change. Likewise for division by non-zero positive c.  Given: a >= 0 and c >= 0, then:
  • ac >= 0
  • a/c >= 0

If c is negative then the sign flips and requires inverting the inequality. Given: a >= 0 and c < 0, then:
  • ac <= 0
  • a/c <= 0

Combined with the addition-subtraction property we have:
Givenmultiplydivide
a >= bc>0ac >= bca/c >= b/c
a >= bc<0ac <= bca/c <= b/c

Note this is equivalent to a scaling of the system.

additive inverse
Given: a >= b, Subtracting by both by the LHS and then by the RHS or by multiplying by -1 we get:
  • -a <= -b

This is equivalent to point inversion.

Taking the above results we could list the multiplicative inverse properties, but the main interest here is to reduce the computational complexity of a comparison.  These are listed on Wikipedia.

Applying a function to both sides
This is where shit starts to get Real, baby. Using the above properties allow eliminating redundant computations and nuking divisions.

We gotta use a little bit of math-speak, here are some informal definitions:

Interval: we're going to talk real numbers, so the legal range of values in the inequality. [min,max]

A Monotonic function f(x) is a function that preserves order (Wikipedia, MathWorld).

This implies that the slope (first derivative) of f(x) never changes sign.  (wait for it)

If f(x) has the properties: given a<=b then f(a)<=f(b) for all 'a' and 'b' on the interval, then f(x) preserves order and is monotonically increasing on the interval.

This means that the slope is always positive or zero across the interval. If you scan the graph of f(x) from the low end of the interval (min) to the high end (max) then the 'y' value is always greater than or equal all points below the current 'x'.  Or if we were to think of this function as being how some point moves up and down in time (where x represents time), then as time increases the point is either moving up or not moving.  It never moves down.

If f(x) has the properties: given a<=b then f(a)>=f(b) for all 'a' and 'b' on the interval, then f(x) preserves order (reverses it) and is monotonically decreasing on the interval.

So the slope is always negative or zero across the interval.  Scanning the graph from low to high..y is always smaller or the same than all to the left.  The point in time is always moving down or stationary.

We can apply a monotonically increasing function (on the interval) to both sides of a non-strict inequality without changing the result.
We can apply a monotonically decreasing function (on the interval) to both sides of a non-strict inequality without changing the result if we change to the opposite comparison.

If f(x) has the properties: given a<b then f(a)<f(b) for all 'a' and 'b' on the interval, then f(x) preserves order and is strictly monotonically increasing on the interval.

If f(x) has the properties: given a<b then f(a)>f(b) for all 'a' and 'b' on the interval, then f(x) preserves order (reverses it) and is strictly monotonically decreasing on the interval.

These are simply more strict versions of the increasing/decreasing above.  They disallow the slope to ever be zero (expect at the end-points of the interval).  A strictly increasing function (on the interval) can be applied to both sides of either a strict or non-strict inequality.  And likewise for a strictly decreasing function when you change to the opposite comparison.

We can take the properties above and express them as applying a function to both sides:
Property      FunctionConstraintsSlopeType
addition/subtraction f(x)=x+Knone       f'(x)= 1 strictly increasing
additive inverse     f(x)=-x none       f'(x)=-1 strictly decreasing
multiplication       f(x)=Kx K>0        f'(x)=K  strictly increasing
multiplication       f(x)=Kx K<0        f'(x)=K  strictly decreasing
division             f(x)=x/KK>0        f'(x)=1/Kstrictly increasing
division             f(x)=x/KK<0        f'(x)=1/Kstrictly decreasing

NOTE: that the properties from the first part of this (including the multiplicative inverse that I blew off) can also be use to transform an expression into a form where we apply a function to both sides.  Specifically by changing the interval of the function to where it has one of the properties listed above.

Some example named inequalities
https://en.wikipedia.org/wiki/Triangle_inequality
https://en.wikipedia.org/wiki/List_of_triangle_inequalities

References
This wiki entry has had 1 revisions with contributions from 1 members. (more info)
Offline Roquen

JGO Kernel


Medals: 518



« Reply #1 - Posted 2015-09-30 16:06:45 »

Incomplete first pass.  Feedback desired.
Offline Stranger
« Reply #2 - Posted 2015-10-01 11:07:25 »


addition/subtraction
If we add or subtract a value from both sides, it's equivalent to translating the pair and it does not effect the relation.  Given: a >= b, then:
  • a+c >= b+c

Given the previous we can convert to comparing against zero (subtract b from both sides):
  • a-b >= 0

subtract b+c from both sides (?)

Anton
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen

JGO Kernel


Medals: 518



« Reply #3 - Posted 2015-10-01 13:32:27 »

Thanks for the feedback.  Yeah that isn't very clear.  Reworked it and a couple a similar cases and added some more details.

Offline theagentd
« Reply #4 - Posted 2015-10-01 15:08:40 »

You can use sqrt() as an example for a function that can be removed on both sides of an inequality.

Myomyomyo.
Offline Roquen

JGO Kernel


Medals: 518



« Reply #5 - Posted 2015-10-01 17:47:09 »

Yeah, I've started some (read one) examples that basically walks through the inequalities used in the "case studies" thread to use actual properties rather than hand-waving.
Pages: [1]
  ignore  |  Print  
 
 

 
Riven (201 views)
2019-09-04 15:33:17

hadezbladez (4909 views)
2018-11-16 13:46:03

hadezbladez (1810 views)
2018-11-16 13:41:33

hadezbladez (5183 views)
2018-11-16 13:35:35

hadezbladez (1024 views)
2018-11-16 13:32:03

EgonOlsen (4387 views)
2018-06-10 19:43:48

EgonOlsen (5228 views)
2018-06-10 19:43:44

EgonOlsen (2972 views)
2018-06-10 19:43:20

DesertCoockie (3875 views)
2018-05-13 18:23:11

nelsongames (4307 views)
2018-04-24 18:15:36
Java Gaming Resources
by philfrei
2019-05-14 16:15:13

Deployment and Packaging
by philfrei
2019-05-08 15:15:36

Deployment and Packaging
by philfrei
2019-05-08 15:13:34

Deployment and Packaging
by philfrei
2019-02-17 20:25:53

Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08

Deployment and Packaging
by gouessej
2018-08-22 08:03:45
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!