
Re: Help with formula (revised question)
Posted:
Nov 20, 2013 11:42 AM


On Wed, 20 Nov 2013 00:50:59 0700, Robert Crandal wrote: [snip] > Here is the new data set: > X Y >   > 0.0 1 > 0.1 1 > 0.5 1 > 0.9 1 > 1.0 1 > 1.03 2 > 1.5 2 > 1.8 2 > 2.0 2 > 2.3 3 > 3.0 3 > 3.2 4 > > X is a positive real number greater than or equal > to zero (or 0.0). Y is an integer as seen in the > second column above. > > Can this data be represented with a formula > that only uses either addition, subtraction, > multiplication, division, modulus, or the power (^) > function, or any combination of these? [...]
Except for f(0), f(x) = ceil(x), a function that [as Jussi Piitulainen noted] can be expressed in terms of a mod function by ceiling(x) = x + ((x) mod 1). To handle f(0), define an indicator function for nonzero, such that n(x) = 0 if x=0, else 1. With eps > 0 the expression n(x) = ceil(x/(x+eps)) will work, as will also 1  0^x if we have 0^0 = 1. Then your Y values can be gotten from X by f(x) = n(x)*ceil(x) + (1n(x)), where the product handles function values when x is nonzero and the rest handles the zero case. For example, the following python code produces results that match your table and it uses only addition, subtraction, multiplication, division, and modulo ops.
def c(v): return v + (v)%1 def n(x): return c(x/(x+.5)) def f(x): return n(x)*c(x) + 1n(x) xa = (0, .1, .5, .9, 1, 1.03, 1.5, 1.8, 2, 2.3, 3, 3.2) for x in xa: print '{:6} {:6}'.format(x, f(x))
If your interest is academic, well and good. However, if you are developing C code that is supposed to run fast, use the expression (x>0) in place of an n(x) function. On x86 systems, the boolean expression (x>0) [which has a value of 0 or 1] typically will compile without any jumps or branching or pipeline disruption, by use of the cmovge conditional move instruction, as explained fairly clearly at <http://stackoverflow.com/a/11237235/837847>. Note, the C expression "return x>0? ceil(x) : 1;" when compiled by gcc also typically uses instructions like cmovge so avoids jumps/branching/pipeline disruption as well as using one less multiply, add, and subtract than does the n(x)*ceil(x) + (1n(x)) expression.
 jiw

