The new forums will be named Coin Return (based on the most recent vote)! You can check on the status and timeline of the transition to the new forums here.
The Guiding Principles and New Rules document is now in effect.
Need some Mathematicians, maybe Programmers
The Hero
__BANNED USERS regular
__BANNED USERS regular
I need help finishing up a function.
Lets say I have some positive numbers, some 0s, and some negative numbers as different inputs. Language is C++.
If a number input is positive, I want to return a 1. If a number is negative, I want to return a -1, and if a number is 0, I want to return a 0. I want to do this mathematically, no conditionals, because I'm convinced it could probably be faster that way (for our purposes). Am I technically correct in this line of thinking?
Unfortunately, when looking at a graph of this function, it looks kind of like something of a piece wise function. So I have no idea if a clean function can be created to return these outputs.
Some relevant info, the inputs will always be greater than or equal 3 or less than or equal to -3, unless it's 0.
One of my ideas was doing something with binary representations.
Lets say I have some positive numbers, some 0s, and some negative numbers as different inputs. Language is C++.
If a number input is positive, I want to return a 1. If a number is negative, I want to return a -1, and if a number is 0, I want to return a 0. I want to do this mathematically, no conditionals, because I'm convinced it could probably be faster that way (for our purposes). Am I technically correct in this line of thinking?
Unfortunately, when looking at a graph of this function, it looks kind of like something of a piece wise function. So I have no idea if a clean function can be created to return these outputs.
Some relevant info, the inputs will always be greater than or equal 3 or less than or equal to -3, unless it's 0.
One of my ideas was doing something with binary representations.
The Hero on
0
Posts
Edit:
Seriously though, don't try to be cute. Compilers are very good at optimizing this sort of thing these days, so all you'll really be doing is making your code unreadable and possibly buggy. Your binary tricks will have to take into account stuff like the size of an integer on your machine, and that can get tricky in a hurry and result in more code than if you had just done it the simple way in the first place.
Heh, that is an embarrassing oversight! I forget how negative numbers work with C++ and bitwise operations, but what if you took the input and did a bitwise AND with the number 1?
What about a bitwise & 10...01 for everything. The only downside is you do get two results for your negatives and they wont be 1,0,-1.
well... not sure you'd AND it against number 1, you'd probably AND it against the max signed int value after checking the most significant bit to see if it's 0 or 1. Then you'd just AND the rest of it and if you get all 0's then the original number was 0 otherwise the original number was anything else.
I'm really not sure this is going to end up any faster or better than just using you're standard conditionals and < and > checks, though. There's still going to be conditionals in this method to determine if it was 0 or otherwise, if negative or otherwise, etc. In other words, technically possible but otherwise pointless unless there's a lot more to this app and this is just a very dumbed down and incomplete example of what is being done.
Unless he's throwing the program on a microcontroller and intends to process several thousand requests per second, he should be content with C++. That, and it looks like he has to use the language for his task.
As for compiling, would dividing by 0 produce an undefined result, or would you just crash your program at that point?
1.) Carry flag set -> Negative
2.) Zero flag set -> Zero
3.) Positive
None of this fancy mathematical stuff. Just one bit shift, and the information's there.
Even floating point numbers have their sign bits, if in IEEE representation.
But anyway, back to the problem at hand:
Are you sure you want to do this mathematically? Because if you're returning 1, 0 and -1 from a function it sounds to me that you're going to be using the results in a conditional manner anyway. What you might want to do is make your function inline, turn on optimisations, and let the optimiser handle it.
If not, move onto your +/- check logic which could be mathematical based.
The graph of a function could look something like a flat line at y =1 when x > 3, a flat line at y=-1 when x < -3, and in the area between 3 and -3 there is simply a line that can do anything but it must cross 0.
There MUST be an equation for that, it passes the definition of a function.
Can't believe this.
I guess I'll have to use a conditional. If input is 0 return 0 else, return Input divided by absolute value of input.
But that blows
Are you familiar with the conditional operator in C++? You could write it as
I'm not convinced that this will compile to code that will be faster than simple if statements. But I have read that it generally won't use branches when compiled.
Why is it so important that this code be as fast as possible? I have a feeling it won't matter as much as you think.
Edit: Actually I forgot probability of a 0 case happening is less than a 1 or -1 case, so really its:
return ( (n < 0) ? -1 : ((n > 0) ? 1 : 0) ) ;
But now I'm gonna have to store n in memory...
But if I don't store n in memory the final complete function can look something like
int8 s(char x){
return ( (((x-4)*(x-8)) < 0) ? -1 : ((((x-4)*(x-8)) > 0) ? 1 : 0) );
}
Speed is important because it will be run by small machines with low bandwidth across the internet, tens of thousands of times, possibly per second.
I get the feeling that you're missing the forest for the trees here. Your program must be doing something other than this transformation, whether it's writing the results to a file or sending them over the internet or using them internally for some other purpose. Whatever's happening, those other things are going to be using far more processor time than a simple function like this. There's an axiom that 90% of the time is spent in 10% of your code, and thus if you optimize at all (often it's best not to, as you end up spending too much time for too little gain) you should focus on that 10%. I feel pretty confident in saying that this function is not what you should be focusing on.
Why don't you benchmark to see which is faster? See if it makes any difference at all?
Do, say, one million iterations with one method (e.g. divide by absolute value), another million with another (e.g. conditional) and so on, and measure it.
We can talk all day about it, but talk is cheap. Measurements mean a bit more.
As far as the whole idea of optimizing this function, you should really make sure this is where your slow down is. Regardless of how you optimize this function, beyond a traditional if then else you are talking about saving a handful of nanoseconds per execution. You wouldn't see any speed increase unless you were executing this function hundreds of thousands or maybe even millions of times, and then you are talking about saving only a handful of seconds, which is probably a very small fraction of your total run time.
Honestly, with the result caching, the two subtractions and the mult in the latter example, I'm not convinced it won't run slower than the former. straight n < 0? is a single cycle instruction on many architectures.
In an unoptimized setting, the conditional block will produce different code than the ternary operator. Consider the snippet:
#include <math.h> int f1(int x) { if (x > 0) { return 1; } else if (x < 0) { return -1; } else /* x == 0 */ { return x; } } int f2(int x) { return (x > 0) ? 1 : ((x < 0) ? -1 : x); } int f3(int x) { if (x == 0) { return x; } else { return abs(x) / x; } }Compiling this with VC++ 2005 (/Zi) gives you the following assembly:
?f1@@YAHH@Z: 10001030: 55 push ebp 10001031: 8B EC mov ebp,esp 10001033: 83 7D 08 00 cmp dword ptr [ebp+8],0 10001037: 7E 09 jle 10001042 10001039: B8 01 00 00 00 mov eax,1 1000103E: EB 12 jmp 10001052 10001040: EB 10 jmp 10001052 10001042: 83 7D 08 00 cmp dword ptr [ebp+8],0 10001046: 7D 07 jge 1000104F 10001048: 83 C8 FF or eax,0FFFFFFFFh 1000104B: EB 05 jmp 10001052 1000104D: EB 03 jmp 10001052 1000104F: 8B 45 08 mov eax,dword ptr [ebp+8] 10001052: 5D pop ebp 10001053: C3 ret ?f2@@YAHH@Z: 10001060: 55 push ebp 10001061: 8B EC mov ebp,esp 10001063: 83 EC 08 sub esp,8 10001066: 83 7D 08 00 cmp dword ptr [ebp+8],0 1000106A: 7E 09 jle 10001075 1000106C: C7 45 FC 01 00 00 mov dword ptr [ebp-4],1 00 10001073: EB 1B jmp 10001090 10001075: 83 7D 08 00 cmp dword ptr [ebp+8],0 10001079: 7D 09 jge 10001084 1000107B: C7 45 F8 FF FF FF mov dword ptr [ebp-8],0FFFFFFFFh FF 10001082: EB 06 jmp 1000108A 10001084: 8B 45 08 mov eax,dword ptr [ebp+8] 10001087: 89 45 F8 mov dword ptr [ebp-8],eax 1000108A: 8B 4D F8 mov ecx,dword ptr [ebp-8] 1000108D: 89 4D FC mov dword ptr [ebp-4],ecx 10001090: 8B 45 FC mov eax,dword ptr [ebp-4] 10001093: 8B E5 mov esp,ebp 10001095: 5D pop ebp 10001096: C3 ret ?f3@@YAHH@Z: 100010A0: 55 push ebp 100010A1: 8B EC mov ebp,esp 100010A3: 83 7D 08 00 cmp dword ptr [ebp+8],0 100010A7: 75 07 jne 100010B0 100010A9: 8B 45 08 mov eax,dword ptr [ebp+8] 100010AC: EB 0F jmp 100010BD 100010AE: EB 0D jmp 100010BD 100010B0: 33 C0 xor eax,eax 100010B2: 83 7D 08 00 cmp dword ptr [ebp+8],0 100010B6: 0F 9F C0 setg al 100010B9: 8D 44 00 FF lea eax,[eax+eax-1] 100010BD: 5D pop ebp 100010BE: C3 retHowever, throwing in optimizations (/O2) yields:
Note that, when optimized, f1 and f2 are identical. Abs() is inlined in f3 for performance's sake, but it still suffers from a single jump to cover the x == 0 case and a nasty division to make the magical calculation. In any case, we're talking about a handful of instructions here between each of the possible solutions. Hopefully there are bigger fish to fry in terms of perf in your code.
As far as the readability of the ternary operator, you'll find that (as with most stylistic things) its a matter of taste. My take with this particular example is that since we're conditioning on the return value, the ternary operator says succinctly (always a good thing) what we're trying to express than the tri-way if-else block. Depending on the context, of course, it may or may not be the "best" way to express your intent.
I know that, that's why I wanted to avoid having a conditional completely. Would have been nice to have a straight up math equation. But I guess it just wasn't possible. For my tastes, a ternary block is fine.
Assembly optimization will only be looked at after the whole project has been finished in C++.
As it currently stands, I don't know how the entire program works so I can't tell you if there is more important optimizations to be made elsewhere, and if there are then they are not my responsibility. I am only responsible for my parts, and I am the only one who knows how my area truly works. In fact no one man in the project probably knows how the whole thing works, everyone simply knows bits and pieces which get put together into a big picture.
Will the compiler make the optimization of storing the product of those differences in a register instead of computing it twice? I've never actually looked at the assembly that gets produced when I write something like C++.
Also, it'd be nice to know your target architecture since the discussion is performance and it seems to be a specialized piece of software.