Prior to January's "stab of the month", I was trying to figure a way for limiting bot movement in KodeKombat - without the if-elif-else constructs. This class of program control constructs like if-elif-else, switch case, translate to branch instructions in machine language which can, in theory and in practice, slow down your code.
Pipelining, a feature responsible for modern processors' high throughput, is achieved by instruction prefetch. Knowing the branch that must be taken apriori is handled by inferences drawn from statistical observation and other techniques. However guessing can only take thus far.
Is there any alternative? More importantly, can there be one?
Well, consider the task of generating random numbers in the range [0-49]. Straightforward way to do it:
Method 1:
GEN: var=rand()
if(var E [0-49] )
return var
goto GEN
An alternative way to do the same, sans if-elif-else:
Method 2:
return rand()%50
There are 2 glaringly obvious issues in the alternative, that need immediate attention.
- Is the %(modulus) operator faster than the overhead from a wrong branch? Don't know and don't care. The objective of this endeavor is to figure out whether or not _if_ can be eliminated. So lets chuck complexity away, at least for a while.
- Side-effects. The modulus operator classifies the entire set of integers into one of 50 equivalence classes. Result your (pseudo-)random number generator may not behave all that randomly!
ceiling[x/(1+x^2)] + floor[x/(1+x^2)]
How the deuce should the floor and ceiling functions be implemented w/o if-else construct?
To state the problem differently(as Mr. Thm 8.3 put it): We want to express a discontinuous function as a continuous one. Now there we have a problem.
Fourier transform of a square wave from time domain to frequency domain does something along those lines. May be one could adapt it to this problem, but it is an infinite series.
But tell me something, to put a 32 bit number into one of 2 or 3 buckets characterized by 2/4 bits do we need an infinite series?
I would like to hear your opinion on this and any mistakes I have made.
1 comment:
...results of operations like ceiling[x] + floor[x] can be achieved by exploiting the features of a language like C using conditional statements without the if-else construct...(? :: statement)
now some compilers along with certain target machines might generate the same machine level code for the above line as generated for the if-else statements...then ur argument "seems" to be valid...
but there is a possibility tat some compliers generate a different machine code for the use of such one line conditional statements..u gotta check out the difference if there's any between these 2 codes...then u might really not need to use infinite series to find if a number is +ve or -ve..
hope it helps...
Post a Comment