-5
$\begingroup$

I am a Java developer building a web app that I will be deploying "in the cloud" (I hate that expression) in a few months. I'm trying to develop a function that will let me spawn and kill the right amount of "computing horsepower" (virtual machines) depending on the current load of the system (by "load" I mean traffic, # of users, etc.).

I have developed such a function, but because it's been so long since I cracked open any of my college mmathbooks, there's one component of it that I'm struggling with that could/should be re-written as it is a piecewise function.

Basically, I have an "outer"/main function c that maps a real (the load) to an integer (# of virtual machines I should have running to support the load):

c : L in the domain of reals --> z in the domain of integers
c(L) = A * t(L)

Where c(L) is the function that my Java code will call, L is a measure of the current load on the system (of type double since load could be 5.0 or 34.2094, etc.), A is a fairly-complicated function that doesn't concern this question (so I omitted it), and t(L) is the piecewise function I need help re-writing:

t(L) = {    0 : if L < 1
       {    L+1 : if L is an integer // 5.0 == 5
       {    ceil(L) : if L is not an integer // 5.5

I understand that the first and third piecewise rules sort of contradict each other, but the first one (0 : if L <1) trumps/overrides the last one (ceil(L) : if L not integer).

So, if L is less than 1, I need t(L) to always return 0. Otherwise, if its an integer, I need it to return L+1, or ceil(L) for any other reals.

So, some examples:

t(0.5) = 0
t(1) = 2 // 1 + 1 -> 2
t(1.5) = 2 // ceil(1.5) -> 2
t(2) = 3
t(57.39854) = 58

Note: L will always be non-negative (0+).

For the life of me I can't figure out how to re-write t(L) in such a way as to be "in-line" or normal (not containing if-else piecewise rules). Thanks for any and all help here!

  • 2
    The two last cases are just floor(L+1), aren't they?2012-07-06
  • 0
    Hey - great observation (+1) - thanks! However, although it certainly simplifies my "rules" from 3 to 2, ultimately I'm looking for a way to streamline this function definition so there's only "1 rule" (hence no need for piecewise if-else), etc. Thanks again!2012-07-06
  • 2
    I don't understand why a piecewise function is a problem.2012-07-06
  • 0
    Because the code that will be running this will be parallelized and running on many threads at the same time. If I can find a way to express this with only one function definition, then I don't need to add `if-else` logic that will fork and slow down my non-blocking algorithm. Concurrent code makes optimal use of the core its running on when it is CPU-bound, which `if-else` thwarts.2012-07-06
  • 2
    @zharvey: Do you have actual benchmarks telling you that a single conditional jump is going to be a performance bottleneck here? Most attempts to replace your expression with something that looks syntactically uniform will be much more expensive to compute. If you're talking massive SIMD (e.g., running on a GPU), then any such system with even a halfway-decent compiler should be able to handle local if-elses using selective disabling of data paths per instruction based on local condition flags.2012-07-06
  • 4
    Sounds like a programming problem to me, maybe more suitable for another site.2012-07-06
  • 1
    We're really getting off-topic here. This is a mathematics Q&A site, so I figured I could ask a mathematics question here and get help. This is a **math** problem I have posed here; I simply included the background story (my actual problem) so that no one said "this smells like a math HW problem" and closed my question. Please treat it as a math problem and not a programming problem. I am asking: **how do I streamline this 3-rule piecewise function into a single function?**2012-07-06
  • 2
    @zharvey: a piecewise function *is* a single function. You seem to be asking how to program it efficiently, which is out of the scope of this site. The function you described does not have a polynomial formula or anything like that. After reading everything I have voted to close as off-topic.2012-07-06
  • 0
    @Carl - point well made. I forget I'm on a math site and can't be so sloppy with semantics. I'm not sure what the correct terminology is here, so I'll just demonstrate it: instead of using a piecewise definition, I want **1** (non-conditional) definition, such as `c(L) = L mod floor(L)...` etc. Not `c(L) = 0 **if** L < 0, L+1 **if** L is an integer...` etc.2012-07-06
  • 1
    @zharvey: A definition by cases **is one definition**, and you have not written anything to suggest that you have _any reason at all_ to want not to have a definition by cases. If you insist that you want a **mathematical** answer, we will insist right back at you that mathematics does not consider definitions by cases to be less good definitions than any other way of writing down a definition.2012-07-06
  • 0
    A piecewise function is by definition a "definition by cases" where each case is a different "piece" of the function definition. From my original question: "`For the life of me I can't figure out how to re-write t(L) in such a way as to be "in-line" or normal (not containing if-else piecewise rules).`". Now at the time I was ignorant to the proper terminology (e.g. I referred to *cases* as "piecewise rules", etc.), but I could not have made the question any more clear.2012-07-06
  • 0
    What happened is that all the PhD's on this site got their noses out of joint because I mentioned concurrency and performance and then *everybody* lost site of what the original question was. I should have just posed the question sans the background story. Learning experience for next time.2012-07-06
  • 0
    The problem is that, while you've told as what you _don't_ want (piecewise definitions), you haven't told as what you _do_ consider acceptable. Apparently, `floor()` and `ceil()` are OK for you, even though they're discontinuous functions. So what about `abs()` (which is usually defined as "$x$ if $x > 0$, else $-x$", but can also be defined e.g. as $\sqrt{x^2}$)? Or the [Heaviside step function](http://en.wikipedia.org/wiki/Heaviside_step_function)? The [Kronecker delta](http://en.wikipedia.org/wiki/Kronecker_delta)? The [Iverson bracket](http://en.wikipedia.org/wiki/Iverson_bracket)?2012-07-06
  • 0
    If all you care about is "no cases", your function can be very easily written e.g. as $t(L) = \lfloor L \rfloor + [L \ge 1]$ or as $t(L) = \lfloor L \rfloor + 1 - \delta_{\lfloor L \rfloor}$.2012-07-06
  • 6
    @Adam: Now I don't understand why you are speaking as if this is your question. Are you the same person as zharvey? If so, are you congratulating yourself in [this comment](http://math.stackexchange.com/questions/167469/how-do-i-turn-this-piecewise-function-into-a-normal-function#comment385569_167528)? I'm only asking so I know how to address (the one or two of) you in future comments.2012-07-07
  • 1
    The accounts `Adam Tannon` and `zharvey` have been merged.2012-07-13

2 Answers 2

5

Would

L < 1 ? 0 : (int)L+1

be streamlined enough for you? I don't think there's any simpler way to write your function in Java.

Yes, this expression uses the ternary conditional operator ?:, which is essentially equivalent to an if–else clause except that it switches between expressions instead of blocks. Depending on how smart your compiler is, the resulting assembly code may or may not end up involving an actual conditional jump.

Still, I very much doubt that this expression will be the performance bottleneck in your application. In fact, if it's really going to be part of a load balancer, I doubt it will even make a measurable difference at all — if the calculation is done, say, once per second, a few nanoseconds lost to a branch misprediction will be like a drop in the ocean. Unless this code really makes up a major part of the inner work loop of your program, micro-optimizing it like this probably violates Knuth's rule on premature optimization:

"Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%."

  • 1
    Well, if one _really_ wants to avoid conditional jumps one could try `int t = (int)(L+1); t &= ~(t-2)>>31;` -- though that is pretty horrible and definitely shouldn't be used without benchmarking to justify the lost readability.2012-07-06
  • 0
    Or `int t = (int)L+1; t *= 2-(int)((t+1.0)/t);` If $t=1$, then $(t+1)/t = 2$, therefore $t$ will be multiplied by $0$ (note that both $1.0$ and $2.0$ can be represented exactly, so no rounding errors should occur in this case). In the other hand, for $t>1$, we have $1<(t+1)/t<2$ and therefore conversion to `int` gives $1$ (and we are far away from $2$, so rounding errors should again not create problems here). However if removing the conditional jump is for speed reasons, this is probably a bad idea.2012-07-06
  • 0
    Thanks @Ilmari but this is a **Java** solution to my problem. I am looking for a **mathematical** way to express these 3-rules.2012-07-06
  • 0
    Also, as a business case for this optimization, the better I optimize the business logic executing this task, the less resources I waste in the cloud vms and the more money we save.2012-07-06
  • 1
    I hope you're joking: saving a few microseconds when computing the number of tasks to be launched is absolutely negligible compared to actually launching a virtual machine instance... The only case where performance *might* matter is $L<1$, since it could be executed many times without actually launching anything. But even that seems completely negligible as compared to e.g. the cost of actually measuring the load.2012-07-06
  • 0
    Please see my answer; this is what I was looking for; **not** an interrogation into why my employer would want me to write this code in the first place.2012-07-06
  • 0
    Your question is absolutely fine if you're asking out of curiosity. But claiming (as you did) that it will directly save your company money is just wrong because this *cannot* be a performance-critical piece of code. There is no business case for this, period.2012-07-06
  • 1
    You have all mis-read my question. This function will help calculate how many virtual machines are running in our production environment; this is how all cloud-based pricing works: the more VMs ("horsepower") you're running, the more they bill you.2012-07-06
  • 3
    @zharvey: But what is the problem with the function being piecewise?2012-07-09
0

I figured it out:

t(L) = floor((3L+1)/(2L+2)) + floor(L)

Try it out:

t(0.6) = 0
t(1) = 2
t(1.6) = 2
t(5.8) = 6
t(50) = 51

Doesn't work when L < 0, but like I said that use case will never occur because L will always be non-negative. Achieves exactly what I asked as my original question.

  • 1
    What have you gained doing this? Now you have two multiplications, one division, several additions and two calls to floor().2012-07-06
  • 1
    Please see my comment to @Gerneric Human. Forget about the nastiness of the function (as you say, multiple floor calls, etc.). This function gives me the precise mapping of inputs to output that I was looking for in my original question; hence it is the answer. Whereas everybody jumped on the concurrency/optimization bandwagon (which was not in fact the problem mentioned in my original question), I was looking for a way to define `t(L)` without having to use piecewise "rules" (or whatever you math guys call them). The question was as simple as that.2012-07-06
  • 0
    Well done, sir. This is a classic example of what happens when "StackExchangers love answering the wrong question" meets the "mob mentality".2012-07-06
  • 0
    Well, congratulations for finding an answer you like. (Ps. If this is the kind of expression you're looking for, then `t(L) = floor(2L/(L+1)) + floor(L)` would arguably be even simpler.)2012-07-06
  • 0
    Thanks @IlmariKaronen - and I bet there are many variants of the first `floor`'s arguments that would achieve the same thing. This is what I was asking though, and its not about "finding an answer that **I like**", per se, it's about finding an answer to the actual question and not getting sidetracked with a different problem altogether!2012-07-06