mersenneforum.org Minimize maximum error
 Register FAQ Search Today's Posts Mark Forums Read

 2011-03-04, 10:20 #1 Joshua2     Sep 2004 13·41 Posts Minimize maximum error I reduced my problem to this almost linear program: minimize max ( abs(a*1+b*3-c), abs(a*2+b*5-c), abs(a*3+b*7-c), abs(a*5+b*11-c), abs(a*7+b*14-c), abs(a*8+b*15-c), abs(a*10+b*19-c) ) on ax + by = c I can get rid of the abs, minimize max ( a*1+b*3-c, -a-3b+c a*2+b*5-c, -2a-5b+c a*3+b*7-c, -3a-7b+c a*5+b*11-c, -5a-11b+c a*7+b*14-c, -7a+14b+c a*8+b*15-c, -8a-15b+c a*10+b*19-c, -10a-19b+c ) on ax + by = c How do I get rid of the max? Someone said the answer is: min z s.t. z >= a*x_i + b*y_i - c, 1<=i<=T z >= c - a*x_i + b*y_i, 1<=i<=T Thanks! Last fiddled with by Joshua2 on 2011-03-04 at 10:21
2011-03-07, 22:26   #2

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts

I don't see how you can get rid of the max function, or something functionally equal to it, as long as your goal is, as your title says, "minimize maximum error". How else is the "maximum error" to be determined?

You can use some algorithm that avoids using "max" by using comparisons and conditional branches ... but that's just what the max function does, so all you accomplish that way is to pretend that you're not using a "max" function just because the character string ("m", "a", "x") doesn't appear in your code.

Inside the max function, what goes on is just comparisons and conditional branches to assignment statements.

function max(a,b);

if a > b then return a else return b;

function max(a,b,c);

if a > b then {if a > c then return a else return c}
else {if b > c return b else return c};

. . .

Quote:
 Originally Posted by Joshua2 Someone said the answer is: min z s.t. z >= a*x_i + b*y_i - c, 1<=i<=T z >= c - a*x_i + b*y_i, 1<=i<=T
All that's doing is hiding ("m", "a", "x") while doing just the same comparisons and conditionals.

z
s.t. z >= a*x_i + b*y_i - c, 1<=i<=T
z >= c - (a*x_i + b*y_i), 1<=i<=T

is just

z = -infinity;

for i = 1 to T by 1;
m = a*x_i + b*y_i - c;
if m > z then z = m;
if -m > z then z = -m;
end for;

return z;

Last fiddled with by cheesehead on 2011-03-07 at 22:59

2011-03-08, 11:34   #3
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

10,243 Posts

Quote:
 Originally Posted by cheesehead Inside the max function, what goes on is just comparisons and conditional branches to assignment statements. function max(a,b); if a > b then return a else return b;
Unless you write it something like this:
Code:
#include <stdint.h>

int32_t max (int32_t a, int32_t b)
{
return b - (a-b) * ((a-b) >> 31);
}
I think that's right --- I typed it in without compiling and testing.

Moral 1: there is more than one way to skin a cat.
Moral 2: there is a long history behind writing straight-line code to be found within the SIMD machine community, which is where I learned this kind of trick. CUDA coders aiming to squeeze every drop of performance try really hard to have uniform program flow and uniform memory accesses in their kernels.

Paul

Last fiddled with by xilman on 2011-03-08 at 11:36 Reason: Fixed a sign error

 2011-03-08, 18:11 #4 lavalamp     Oct 2007 London, UK 1,307 Posts Shouldn't that be (a-b) for the first bracket? Nice trick btw. Edit: Or add it rather than subtract it to keep both brackets the same. Last fiddled with by lavalamp on 2011-03-08 at 18:16
2011-03-08, 18:21   #5

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts

Quote:
 Originally Posted by xilman Unless you write it something like this: Code: #include int32_t max (int32_t a, int32_t b) { return b - (a-b) * ((a-b) >> 31); }
So, if a = 56 and b = 2, it returns

2 - (56-2)*((56-2)>>31)

= 2 - (54)*((54)>>31)

= 2 - (54)*(0)

= 2

?

Moral 3: One of us has failed to either compile or test correctly before publishing our result. If >> is not a right shift, it's me.

 2011-03-08, 18:31 #6 lavalamp     Oct 2007 London, UK 1,307 Posts Ah, maybe it was meant to be a at the start then. All equivalent: Code:  return b - (b-a) * ((a-b) >> 31); return b + (a-b) * ((a-b) >> 31); return a - (a-b) * ((a-b) >> 31); The last two being probably being a bit quicker because (a-b) can be stored in a register and used again.
2011-03-08, 18:37   #7
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

1024310 Posts

Quote:
 Originally Posted by cheesehead Moral 3: One of us has failed to either compile or test correctly before publishing our result. If >> is not a right shift, it's me.
That's exactly how I documented it.
Quote:
 I typed it in without compiling and testing.
As lavalamp noted, the first '-' should be a '+'.

Still, at least two of us think it's a nice trick.

At least one of us (me) thinks its a lousy way to write code unless you really need that last drop of performance. Almost all the time it takes longer to write, test and debug the code in the first place than you ever get back at runtime.

Paul

 2011-03-08, 18:58 #8 cheesehead     "Richard B. Woods" Aug 2002 Wisconsin USA 170148 Posts If I hadn't tested, I wouldn't have moralized about it. :-) Last fiddled with by cheesehead on 2011-03-08 at 18:59
2011-03-09, 06:39   #9
CRGreathouse

Aug 2006

5,923 Posts

Quote:
 Originally Posted by xilman At least one of us (me) thinks its a lousy way to write code unless you really need that last drop of performance. Almost all the time it takes longer to write, test and debug the code in the first place than you ever get back at runtime.
It's a good way to write library code. It's a bad way, generally, to write most anything else.

2011-03-09, 20:06   #10
R.D. Silverman

Nov 2003

1D2416 Posts

Quote:
 Originally Posted by xilman Unless you write it something like this: Code: #include int32_t max (int32_t a, int32_t b) { return b - (a-b) * ((a-b) >> 31); } I think that's right --- I typed it in without compiling and testing. Moral 1: there is more than one way to skin a cat. Moral 2: there is a long history behind writing straight-line code to be found within the SIMD machine community, which is where I learned this kind of trick. CUDA coders aiming to squeeze every drop of performance try really hard to have uniform program flow and uniform memory accesses in their kernels. Paul
Note also:

max(a,b) = [abs(a+b) + abs(a-b)]/2
min (a,b) = [abs(a+b) - abs(a-b)]/2

2011-03-15, 13:19   #11
ppo

Aug 2004
italy

11310 Posts

Quote:
 Originally Posted by R.D. Silverman Note also: max(a,b) = [abs(a+b) + abs(a-b)]/2 min (a,b) = [abs(a+b) - abs(a-b)]/2
This is working only for non-negative values for a and b.
To allow also negative values:

max(a,b) = (a+b+abs(a-b))/2
min (a,b) = (a+b-abs(a-b))/2

 Similar Threads Thread Thread Starter Forum Replies Last Post a1call Information & Answers 93 2016-09-10 17:34 willmore Software 4 2009-10-14 02:45 Mini-Geek Lounge 9 2008-07-14 22:45 Andi47 GMP-ECM 13 2007-05-11 14:29 HiddenWarrior Math 7 2004-03-10 13:39

All times are UTC. The time now is 05:52.

Thu Sep 24 05:52:41 UTC 2020 up 14 days, 3:03, 0 users, load averages: 1.21, 1.26, 1.26

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.