20110304, 10:20  #1 
Sep 2004
13·41 Posts 
Minimize maximum error
I reduced my problem to this almost linear program:
minimize max ( abs(a*1+b*3c), abs(a*2+b*5c), abs(a*3+b*7c), abs(a*5+b*11c), abs(a*7+b*14c), abs(a*8+b*15c), abs(a*10+b*19c) ) on ax + by = c I can get rid of the abs, minimize max ( a*1+b*3c, a3b+c a*2+b*5c, 2a5b+c a*3+b*7c, 3a7b+c a*5+b*11c, 5a11b+c a*7+b*14c, 7a+14b+c a*8+b*15c, 8a15b+c a*10+b*19c, 10a19b+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 20110304 at 10:21 
20110307, 22:26  #2  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·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:
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 20110307 at 22:59 

20110308, 11:34  #3  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10,243 Posts 
Quote:
Code:
#include <stdint.h> int32_t max (int32_t a, int32_t b) { return b  (ab) * ((ab) >> 31); } Moral 1: there is more than one way to skin a cat. Moral 2: there is a long history behind writing straightline 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 20110308 at 11:36 Reason: Fixed a sign error 

20110308, 18:11  #4 
Oct 2007
London, UK
1,307 Posts 
Shouldn't that be (ab) 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 20110308 at 18:16 
20110308, 18:21  #5  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
Quote:
2  (562)*((562)>>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. 

20110308, 18:31  #6 
Oct 2007
London, UK
1,307 Posts 
Ah, maybe it was meant to be a at the start then.
All equivalent: Code:
return b  (ba) * ((ab) >> 31); return b + (ab) * ((ab) >> 31); return a  (ab) * ((ab) >> 31); 
20110308, 18:37  #7  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10243_{10} Posts 
Quote:
Quote:
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 

20110308, 18:58  #8 
"Richard B. Woods"
Aug 2002
Wisconsin USA
17014_{8} Posts 
If I hadn't tested, I wouldn't have moralized about it. :)
Last fiddled with by cheesehead on 20110308 at 18:59 
20110309, 06:39  #9 
Aug 2006
5,923 Posts 
It's a good way to write library code. It's a bad way, generally, to write most anything else.

20110309, 20:06  #10  
Nov 2003
1D24_{16} Posts 
Quote:
max(a,b) = [abs(a+b) + abs(ab)]/2 min (a,b) = [abs(a+b)  abs(ab)]/2 

20110315, 13:19  #11 
Aug 2004
italy
113_{10} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Minimize n2^x*3^y over the integer  a1call  Information & Answers  93  20160910 17:34 
Maximum memory for P1 in XP 32bit  willmore  Software  4  20091014 02:45 
Maximum theoretical MPG  MiniGeek  Lounge  9  20080714 22:45 
Maximum B1 for P+1 = 4294967295?  Andi47  GMPECM  13  20070511 14:29 
Good way to minimize factoring algoritm twice?  HiddenWarrior  Math  7  20040310 13:39 