Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: Help with formula (revised question)
Replies: 7   Last Post: Nov 20, 2013 8:15 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
James Waldby

Posts: 374
Registered: 1/27/11
Re: Help with formula (revised question)
Posted: Nov 20, 2013 11:42 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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 non-zero, 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) + (1-n(x)),
where the product handles function values when x is non-zero 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) + 1-n(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) + (1-n(x)) expression.

--
jiw



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.