Fastest Sigmoid Function

This is a discussion on Fastest Sigmoid Function within the Contests Board forums, part of the Community Boards category; The requirement only to exhibit the features of a sigmoid was intentionally left vague to allow for creative entries, not ...

  1. #16
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,709
    The requirement only to exhibit the features of a sigmoid was intentionally left vague to allow for creative entries, not to act as a loophole for rules lawyers.
    If the goal of the contest were to plot a sigmoid, then the fastest entry would not actually draw a sigmoid at all, but instead calculate where to plot. Nevermind whether doubles are appropriate for this purpose. Do you intend to write code that would draw a sigmoid curve based on the output, or will those kinds be disqualified also? Would that be weasel code?
    On the other hand, if the rules are so vague that even otherwise correct entries are wrong and can be disqualified if you're having a bad day, then there is no contest.

    Whatever, here's one.
    Attached Files Attached Files

  2. #17
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by abachler View Post
    For all sets of 3 points a , b , and c where a < b < c and all 3 points are in either the positive or negative domain ,the following three conditions must be met:

    1. f(a) < f(b) < f(c)
    This condition is impossible to meet.

    2. the slopes of the function of a , b , c (sa , sb , sc) must exhibit the quality of sa > sb > sc for sets of positive numbers

    3. the slopes of the function of a , b , c (sa , sb , sc) must exhibit the quality of sa < sb < sc for sets of negative numbers
    How are you defining the slope of a function that maps doubles to doubles?
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

  3. #18
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,243
    Quote Originally Posted by Rashakil Fol View Post
    How are you defining the slope of a function that maps doubles to doubles?
    I was wondering about that too. In typical applications of a sigmoid, it's required that the function be differentiable, and the value of its derivative is also used. You can of course approximate that with the definition of derivative, but it's better to have a true symbolic derivative available.

  4. #19
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by Rashakil Fol View Post
    This condition is impossible to meet.
    I know of several functions that meet all three conditions. In particular -

    (1 / (1 + e^-X))-0.5 The logistic function, with an offset

    as for defining slope, I believe slope is defined as the first order dirivative of a function. In the case of the limitations of the FPU it would then have to be the smallest measureable differencee between two neighboring values. Since doubles are translated into the 80 bit internal format, I would say the slope defined by a line between the points X-, f(x-) and X+ , f(X+) should suffice for purposes of this contest. Where X- is the largest value representable in 80 bits that is less than X and X+ is the smallest value greater than X. Im talking mathmatically greater or less than, not what the FPU will return, since values very close to one another will be reported as equal.
    Last edited by abachler; 07-11-2007 at 10:25 AM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  5. #20
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by abachler View Post
    Im talking mathmatically greater or less than, not what the FPU will return, since values very close to one another will be reported as equal.
    Then I submit the following as an implementation of f(x) = 2atan(x/((((((((100!)!)!)!)!)!)!)!))/pi.

    Code:
    void sigmoid(double* vals) {
    
      while (*vals != 0.0)
        *vals++ = 0.0;
    
    }
    The higher inputs produce results that are mathematically greater, albeit to the limits of what the FPU will return.
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

  6. #21
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by Rashakil Fol View Post
    Code:
    void sigmoid(double* vals) {
     
      while (*vals != 0.0)
        *vals++ = 0.0;
     
    }
    fails to meet the requirement f(a) < f(b) < f(c)
    fails to meet the requirement sa > sb > sc for sets of positive numbers
    fails to meet the requirement sa < sb < sc for sets of negative numbers

    disqualified
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  7. #22
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    In general, I agree with Rashakil Fol. Consider the possible entry:
    Code:
    double sigmoid(double y)
    {
    	double x = 1+y*y;
    	double xhalf = 0.5f*x;
    	long long i = *(long long*)&x;
    	i = 0x5fe6ec85e7de30da - (i>>1); 
    	x = *(double*)&i;
    	return x*(1.5f-xhalf*x*x)*y;
    }
    Instead of mathematically computing an accurate inverse square root, it approximates one. By shuffling some approximation in there, some performance is gained. Since you've allowed us to choose the function we're approximating, I fail to see how Rashakil Fol's approximation is less valid than any other entry.
    Last edited by pianorain; 07-11-2007 at 02:05 PM. Reason: Anyone else hate reading their own posts?
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  8. #23
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by abachler View Post
    fails to meet the requirement f(a) < f(b) < f(c)
    fails to meet the requirement sa > sb > sc for sets of positive numbers
    fails to meet the requirement sa < sb < sc for sets of negative numbers

    disqualified
    Show me an entry that wouldn't be disqualified.
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

  9. #24
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Also, tell me what the maximum allowable value of b is, for entries that approximate

    f(x) = 2atan(x/b)/pi.

    And give a reason why.

    Edit: And give a minimum allowable value of b, too.
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

  10. #25
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    There is no minimum or maximum allowable value for b so long as the output of the function meets the requirements. Since 100 ! ! ! ! ! ! ! ! ! ! ! fails to provide output that meets the requirements, that alone is what disqualifies it. This is the reason that I provided the hardware specifications in the first place. While the formulae that you wish to approximate is sigmoidal, the output of your function is not. Normally I woudlnt help a contestant with a particular solution, but to be fair I did change the data from a single double to a pointer to an array of doubles to help GPU entries.

    I would suggest you use the value of 1.0 for b.

    Because there are several optimizations that i can think of when using 1.0, and it produces meaningful output over the entire range of doubles.

    Minimum value of 1.0, maximum value of 1.0

    Values greater than 1.0 restrict the functions ability to approach +1.0 with large values of X on the hardware specified.

    Values lower than 1.0 produce hardware exceptions with large values of X
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  11. #26
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    I'm not trying to be a jerk or anything (well, maybe just a little), I'd like a clear set of rules which defines what functions are allowable, using concrete tests that are based off of solely the (double -> double) function.

    I would recommend stating your limitations in the following fashion: "There must exist a function f: R->R which is best approximated by your function (or maybe which is approximated by your function within the tolerances given by t(x,f(x)) where you supply t) which has the following properties: ..."

    Then put in "..." the properties of a sigmoid and whatever limitations on the derivative and second derivative (and third derivative? fourth?) that you deem appropriate to eliminate solutions which you find offensive.

    Edit: You still haven't shown me an example of a function which passes the requirements you have given.

    Okay, how about

    Code:
    double sigmoid(double x) { return x < -1.0 ? -1.0 : (x > 1.0 ? 1.0 : x); }
    Last edited by Rashakil Fol; 07-11-2007 at 02:51 PM.
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

  12. #27
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by citizen View Post
    Whatever, here's one.
    Question: What does the following give you?

    Code:
      double v1 = 83222687.6013975441455841064453125;
      double v2 = 83222686.0;
      double u1 = citizen_sig(v1);
      double u2 = citizen_sig(v2);
    
      printf("&#37;0.30f %0.30f \n %0.30f %0.30f\n", v1, v2, u1, u2);
    Isn't a sigmoid function supposed to be monotonic? On my computer, his entry is not.
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

  13. #28
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    I gave you an equation whose implementation woudl pass the requirements.

    1 / 1 + e^-X

    Code:
    void sigmoid(double* Input){
         double temp;
     
         while(Input[0] != 0.0){
              __asm fld2e;
              __asm fstp temp;
              temp = pow(2 , temp);
              temp = pow(temp , (0-X));
              temp += 1.0;
              Input[0] = pow(temp , -1.0);
              Input++;
              }
     
         return;
         }
    Quote Originally Posted by Rashakil Fol View Post
    Isn't a sigmoid function supposed to be monotonic?
    Wow, no it isnt. This article - Sigmoid Function should be of use to you.
    Last edited by abachler; 07-11-2007 at 03:36 PM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  14. #29
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by abachler View Post
    Wow, no it isnt. This article - Sigmoid Function should be of use to you.
    Are you pranking me? The Wikipedia definition states that it must be monotonic:

    Quote Originally Posted by Wikipedia
    In general, a sigmoid function is real-valued and differentiable, having either a non-negative or non-positive first derivative and exactly one inflection point
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

  15. #30
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    You could try giving an implementation for others that compiles on a modern compiler. Yours doesn't even compile on VC++ 2003.
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Compiling sample DarkGDK Program
    By Phyxashun in forum Game Programming
    Replies: 6
    Last Post: 01-27-2009, 02:07 AM
  2. Seg Fault in Compare Function
    By tytelizgal in forum C Programming
    Replies: 1
    Last Post: 10-25-2008, 03:06 PM
  3. Another syntax error
    By caldeira in forum C Programming
    Replies: 31
    Last Post: 09-05-2008, 01:01 AM
  4. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  5. const at the end of a sub routine?
    By Kleid-0 in forum C++ Programming
    Replies: 14
    Last Post: 10-23-2005, 06:44 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21