Weird thought - Comparison-free MAX function

[monkey0506]

While I was waiting for an interview today for 4 hours, I had to come up with 3 "professional employment references" so naturally I used my current manager as a reference. I just got his number this morning when he called my phone to ask me to come in early, so I wasn't familiar with the number. When I was writing it down I noticed the last 4 digits are very similar to the last 4 digits of my number.

On a whim I went to work, using my hand as a scratch pad. First I added the two 4-digit pairs together. Next I took (the absolute value of) the difference, and added that to the sum of the two pairs. Finally I divided the whole thing by two to average the numbers out. I was stunned when I got the last 4 digits of my phone number back.

So I did the same thing with the 3 digits prior, but this time I got the digits from my manager's number. This is about the time I realized that apparently the resulting figure was the larger of the two.

Apparently the maximum of any two values could be determined by averaging the sum and the (absolute value of the) difference. I had this much scratched on my hand:

Code: ags

((A + B) + ABS(A - B)) / 2 = MAX(A, B)

The next step was clearly finding a method of getting the absolute value of a number without using any comparison operators. I racked my mind trying to figure it out, but it wasn't until I got home from work and Wikipedia helped me out that I solved this dilemma.

The absolute value of a number can be determined by taking the square-root of the square of the figure. If the figure is negative, the negative is dropped by the squaring, and the square root brings us back to our original (but absolute) value.

So, not that it probably matters...but you could script a max function in AGS like this:

Code: ags

int abs(int i) {
  return FloatToInt(Maths.Sqrt(IntToFloat(i * i))); // square i then get the square root
}

int max(int a, int b) {
  return ((a + b) + abs(a - b)) / 2;
}

A float version would be as simple as:

Code: ags

float fabs(float i) {
  return Maths.Sqrt(i * i); // square i then get the square root
}

float max(float a, float b) {
  return ((a + b) + fabs(a - b)) / 2.0;
}

Now only to solve for the min function...

Edit: Nevermind, that's just the sum minus the absolute value of the difference! A complete guess...but I was right!?!

Code: ags

int min(int a, int b) {
  return ((a + b) - abs(a - b)) / 2;
}

[Gilbert]

Yes, the formulae are correct.

Simply let M = min(A, B), and D = abs (A, B) = max (A, B) - min(A, B).

Then max(A, B) = M + D, i.e. A + B = 2M + D.

So, we can see the results easier.

(A + B) + abs(A, B) = 2M + D + D = 2(M + D) = 2max(A, B)

(A + B) - abs(A, B) = 2M + D - D = 2M = 2min(A, B)


HOWEVER, what's the point of using this?

Obviously this offers no help in simplifying mental calculations.
For computational calculations, by 'without using comparison operations' I think it depends on how stuff are actually implemented in the programming language (compile/interpreter/etc.). Normally numbers are stored with the 2's complement format (I think), so to change the sign of a number (i.e. +ve <--> -ve, which is obviously needed for the abs() function) you have to do something like reversing all the bits and than add 1 (or something like that), together with the other addition/subtraction and division (ok, division by 2 can be done via shifting) operations I think it may not give performance boost when compared to the normal 'if (A>B) return A; else return B;' comparison method.


Worst of all, I just checked that actually there's no abs() function in AGS (at least not in V3.01), so you have to write your own implementation and I'll expect it won't be simpler if you insist on writing one 'without using comparison operations'. (Actually a normal implementation (by definition, 'if (A<0) return -A; else return A;') of the abs() function already contains comparison operations).

Edit: Alright, just see the abs() by square than square root part, but this should be even slower in general.

[monkey0506]

I didn't say there was a point to it...it was just some random thought I had today that lead to me discovering some mathematical formula for finding the max of two values.

Realistically you wouldn't want to use this. Simply using the comparison operators would make the whole thing much faster and easier. I just thought it was a significant personal discovery.

[OneDollar]

Wow. Just wow.

[Khris]

Heh, what about:

Code: ags

int max(int a, int b) {
  return (a>=b)*a + (a<b)*b;
}

Granted, this is no mathematical formula, but it'll work with most programming languages.

[InCreator]

Omg. Just omg.

People like walk around you on the streets and at the same time calculate square roots their head.
World is too scary for me.

Just stay away from power tools...

[scotch]

Sorry to add to this terrifying nerdathon, but even if you were doing it for fun, avoiding branches absolutely is sometimes important on modern CPUs and GPUs (if you're writing native code) because there are relatively large penalties in some cases. The original abs method is probably impractical as noted, because it uses expensive operations, and anywhere where branches are such a huge problem (like in graphics shaders or SIMD units) there are special abs instructions.

If you want to do this fast on a computer you can use bitwise operations. A floating point value can simply have its top bit dropped, but signed integers are not so simple. Without getting into assembly language, one approach could be to work out both answers and index them with the sign bit

Code: ags

inline int abs(int x) {
    int abss[2] = { x, -x };
    return abss[x>>31];
}

which is a bit like what a graphics shader compiler that doesn't support branches would do when it was forced to simulate a branch.

Interestingly, on my Athlon X2 and VC++, that method is slightly slower than the standard conditional implementation "return x<0?-x:x;" when you run it over a list of numbers which are all positive or all negative. However it is noticably faster when working on a list with random signs. Just goes to show how big a deal branch prediction is these days. The other thing to note is the standard library "abs()" beats them both using a non branching assembly language trick. Trying to outsmart the compiler fails yet again.

branching, positive:   6 secs
branching, random:    11 secs
indexing, positive:    7 secs
indexing, random:      7 secs
abs(), positive:       6 secs
abs(), random:         6 secs

edit: Based off what the compiler tries, I made this more portable version which beats the compiler's method on my system. Perhaps it's not so futile after all.

Code: ags

inline int abs_mask(int x) {
    unsigned int mask = x>>(sizeof(x)*8-1); // fill the mask with the sign bit
    return (x ^ mask) - mask; // two's complement if mask is set
}

[monkey0506]

I understand how the bitwise operations work and would be much faster, but I rarely ever think in terms of binary data like that. The square root of the square method was presented on Wikipedia and definitely works, so that's what I used.

And I suppose that the whole reason I even did this was kind of a weird personal obsession with relations between apparently random numbers...kind of like The Number 23. I tend to use completely random operations to try and arrive at a conclusion that I can convolute into a result that seems terrifyingly suspicious. The fact that I actually discovered anything about any real relations between numbers and/or about mathematical theory was completely coincidence...or was it?

[Andail]

please hold my hand, somebody

[ThreeOhFour]

I followed the initial post as far as "First I added the two numbers together"

I'm bookmarking this page so that I can read a sentence of it every year and then spend the rest of that year figuring out what that sentence means.

Apologies for the OT

[DazJ]

How about this one people:

2 x 5 = ?

I've been pondering on this for MONTHS.

[Buckethead]

meh a thread with MAX function in the title should be about 3ds max imo  :

[paolo]

Whoo, maths!

I haven't checked whether Gilbot V7000a's formulae are equivalent to the following, but I would have thought a simpler proof of this formula for finding the maximum value of two numbers would be:

If a > b, then abs(a - b) = a - b, so [a + b + abs(a - b)] / 2 = 2a / 2 = a. Replace > with < (or swap a and b) to show that the result works the other way round too. When a = b, abs(a - b) = 0 and the mean is equal to both numbers.

Taking squares and square roots just to avoid using comparison operators is using a sledgehammer to crack a nut, of course, but this is the sort of exercise that top-notch universities put in entrance exams for applicants to their maths and computing courses. The classic example for computing courses is to build various logic gates from NAND gates, or something like that.

And don't even think of suggesting the square and square roots method if you are applying for a job in the video games industry... square roots take up too many clock cycles and are usually approximated using a look-up table or some other faster workaround.

[Khris]

Here's another entrance exam exercise:

There's a rectangular cake, and somebody already cut out a piece:

  ________________ 
 |                |
 |                |
 |   __           |
 |  |  |          |
 |  |  |          |
 |  |  |          |
 |__|  |__________|

The rest of the cake is supposed to be shared among two people, each of them wants the exact half of the rest.
But: they try to divide the cake using one cut only. How?
(Cutting at half the height parallel to the cake's plate is a nice way to do it but not allowed here.)

[olafmoriarty]

Does the two pieces have to have the same shape? Are the two people allowed to use a ruler?

[Khris]

No, they only have to have the same volume/weight/surface area.
About the ruler: don't focus on picky rules, there's an easy way to eyeball the cut and that's what's in demand.

[Babar]

Just cut it horizontally (from the view shown in the drawing) parallel to the inside edge created by the 1st cut?

I ares the winner!

[Khris]

Well, you aresn't

Little hint: imagine a flat donut with its hole being a little off-center. How'd you cut that in half?

[scotch]

Spoiler

When there's nothing missing, any way of cutting the cake straight through the middle point will guarantee equal halves (like any rectangle). If you pick the line that goes through the middle of the cake, as well as the middle of the missing slice, then each side gets half the cake - half the missing rectangle?

[close]

Quite a fun question. I'd have no chance if it required making formulas. Also I probably wouldn't have thought about cutting it along the other axis, heh.

Also, I don't think sqrt is usually super slow. It's very often faster than a LUT would be nowadays, but yeah, I expect an examiner would like to see you thinking lower level.

[Babar]

I ares right! I checked! The top bit is 3 wide 16 long, and the bottom is 4 wide 12 long. 48=48!