mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2011-03-04, 10:20   #1
Joshua2
 
Joshua2's Avatar
 
Sep 2004

53310 Posts
Default 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
Joshua2 is offline   Reply With Quote
Old 2011-03-07, 22:26   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

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 View Post
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
cheesehead is offline   Reply With Quote
Old 2011-03-08, 11:34   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

1025610 Posts
Default

Quote:
Originally Posted by cheesehead View Post
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
xilman is offline   Reply With Quote
Old 2011-03-08, 18:11   #4
lavalamp
 
lavalamp's Avatar
 
Oct 2007
London, UK

130710 Posts
Default

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
lavalamp is offline   Reply With Quote
Old 2011-03-08, 18:21   #5
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Talking

Quote:
Originally Posted by xilman View Post
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);
}
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.
cheesehead is offline   Reply With Quote
Old 2011-03-08, 18:31   #6
lavalamp
 
lavalamp's Avatar
 
Oct 2007
London, UK

1,307 Posts
Default

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.
lavalamp is offline   Reply With Quote
Old 2011-03-08, 18:37   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

281016 Posts
Default

Quote:
Originally Posted by cheesehead View Post
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
xilman is offline   Reply With Quote
Old 2011-03-08, 18:58   #8
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

If I hadn't tested, I wouldn't have moralized about it. :-)

Last fiddled with by cheesehead on 2011-03-08 at 18:59
cheesehead is offline   Reply With Quote
Old 2011-03-09, 06:39   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×52×79 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2011-03-09, 20:06   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by xilman View Post
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
Note also:

max(a,b) = [abs(a+b) + abs(a-b)]/2
min (a,b) = [abs(a+b) - abs(a-b)]/2
R.D. Silverman is offline   Reply With Quote
Old 2011-03-15, 13:19   #11
ppo
 
ppo's Avatar
 
Aug 2004
italy

113 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
ppo is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Minimize |n-2^x*3^y| over the integer a1call Information & Answers 93 2016-09-10 17:34
Maximum memory for P-1 in XP 32-bit willmore Software 4 2009-10-14 02:45
Maximum theoretical MPG Mini-Geek Lounge 9 2008-07-14 22:45
Maximum B1 for P+1 = 4294967295? Andi47 GMP-ECM 13 2007-05-11 14:29
Good way to minimize factoring algoritm twice? HiddenWarrior Math 7 2004-03-10 13:39

All times are UTC. The time now is 08:11.

Sun Sep 27 08:11:26 UTC 2020 up 17 days, 5:22, 0 users, load averages: 1.06, 1.40, 1.37

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

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.