Fastest Sigmoid Function

This is a discussion on Fastest Sigmoid Function within the Contests Board forums, part of the Community Boards category; The goal is to produce the smallest and/or fastest sigmoid function. The rules (updated) are: 1. The input is a ...

  1. #1
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189

    Fastest Sigmoid Function

    The goal is to produce the smallest and/or fastest sigmoid function. The rules (updated) are:

    1. The input is a 0.0f terminated array of double's between negative and positive infinity inclusive.
    2. The output is a 0.0f terminated array of doubles between -1.0 and +1.0 and must exhibit the classic properties of a sigmoid. Specifically it must have an S shaped curve and approach +- 1.0 as the input approaches +- infinity.
    3. You can use C, C++ or ASM. You can use any combination of those three.
    4. The result must be deterministic, i.e. it must produce the same output for the same input every time.
    5. For the purposes of testing all code must compile under VC++ 6.0
    6. Points will be given for the fastest (most iterations per unit of time). Score will be equal to the number of iterations per second.
    7. ASM only solutions will also recieve bonus points for smallest total bytes.
    8. For testing the specific processor is -

    Intel Xeon 3.20GHz Family F Model 4 Stepping 3 Revision N0
    MMX SSE SSE2 SSE3 EM64T
    Irwindale Socket 604 mPGA
    90 nm technology @ 2.048v

    9. No weasel code. This means you Rashakil.


    The test itself will be multiple runs testing 1 billion iterations of the routine with random inputs. If the top two or more entries have run times closer than 5% in duration, an extended test will be run on those entries only.
    Last edited by abachler; 07-10-2007 at 01:24 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.

  2. #2
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Could you be mathematically precise as to what you mean by "the classic properties of a sigmoid"? Be sure to keep in mind floating point precision (e.g. what exactly are the properties of an "inflection point" in a floating point context.)

    Also, you should be precise as to what the probability distribution of inputs will be as far as "random inputs" are concerned. Otherwise, victory could end up being luck-based.

    Edit: This should satisfy the rules you have given so far. It approximates the sigmoid function arctan(x)/((((((((100!)!)!)!)!)!)!)!) to the limits of double precision.

    Code:
    double sigmoid(double x) { return 0.0; }
    Last edited by Rashakil Fol; 07-09-2007 at 06:20 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.

  3. #3
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    What GPU? I presume it's legal to utilize your GPU ?

  4. #4
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by zacs7 View Post
    What GPU? I presume it's legal to utilize your GPU ?
    GPU is an 8800 GTX with 768MB. I suppose if we are going to have GPU entries I will have to provide the entire data set to make it fair. So, I will modify the rules to read -

    1. The input is a 0.0f terminated array of double's between negative and positive infinity inclusive.
    2. The output is a 0.0f terminated array of doubles between -1.0 and +1.0 and must exhibit the classic properties of a sigmoid. Specifically it must have an S shaped curve and approach +- 1.0 as the input approaches +- infinity.
    7. ASM only solutions will also recieve bonus points for smallest total bytes.
    9. No weasel code.


    Quote Originally Posted by Rashakil Fol View Post
    Could you be mathematically precise as to what you mean by "the classic properties of a sigmoid"?
    I believe a sigmoid is defined as having an S shaped curve, which means your function is worthless, but just to satisfy the anal retentive nature of some people, I respecced the rule to include infinity, so you cant weasel a win with return 0.0 .

    Be sure to keep in mind floating point precision (e.g. what exactly are the properties of an "inflection point" in a floating point context.)
    The last time I checked an inflection point is a fairly specific mathmatical concept regardless of whether you are representing the values in double precision floating point or chickens.
    Also, you should be precise as to what the probability distribution of inputs will be as far as "random inputs" are concerned. Otherwise, victory could end up being luck-based.
    The distribution will be cryptographically random. Every routine will recieve the same set of data. The data will NOT include either infinity, but MAY include one or both, so no weasel code.
    Edit: This should satisfy the rules you have given so far. It approximates the sigmoid function arctan(x)/((((((((100!)!)!)!)!)!)!)!) to the limits of double precision.

    Code:
    double sigmoid(double x) { return 0.0; }
    I was going to comment on this solution, but I couldnt come up with any responses that didnt contain explitives and involve a lot of eye rolling. For one, its output isnt sigmoidal in any way shape or form, even if you extend the precision from 64 bits to infinity.
    Last edited by abachler; 07-10-2007 at 09:15 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. #5
    Amazingly beautiful user.
    Join Date
    Jul 2005
    Location
    If you knew I'd have to kill you
    Posts
    254
    I'd like to compete, using some ASM, but I do not have an available copy of Windows.
    Can you extend compilers to allowing something GCC based (also pertains to the latest standard, as opposed to VC++ 6.0)?
    Programming Your Mom. http://www.dandongs.com/

  6. #6
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,230
    Quote Originally Posted by Rashakil Fol View Post
    Edit: This should satisfy the rules you have given so far. It approximates the sigmoid function arctan(x)/((((((((100!)!)!)!)!)!)!)!) to the limits of double precision.
    The traditional definition of sigmoid states that it must have either non-negative or non-positive slope everywhere, as well as a single inflection point. Your function doesn't fit that second part

  7. #7
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    My function approximates one with a single inflection point just fine.

    Anyway, here's an implementation that accurately represents the function 2arctan(x/(((((((100!)!)!)!)!)!)!)!))/pi, a sigmoid with one inflection point which has asymptotes -1 and 1:

    Code:
    double sigmoid(double x) { return 0.0; }
    The traditional definition of sigmoid states that it must have either non-negative or non-positive slope everywhere
    If you're mapping (-infinity, +infinity) monotonically into (-1,1) or [-1,1] using doubles, you're going to have either significant regions of slope zero, or multiple inflection 'points'. That's what you get when approximating functions' behavior, no matter what the function is. Suppose I wrote

    Code:
    double sigmoid(double x) { return atan(x); }
    What do you think the behavior of this function is for large and small values of x? There it's perfectly constant.

    Also, where do you think its inflection point is? And where's the inflection point of the following function:

    Code:
    double sigmoid(double x) {
      if (fabs(x) < -3.357e-10) {
        return x;
      }
      else {
        return atan(x);
      }
    }
    Last edited by Rashakil Fol; 07-10-2007 at 12:32 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.

  8. #8
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by CrazyNorman View Post
    Can you extend compilers to allowing something GCC based (also pertains to the latest standard, as opposed to VC++ 6.0)?
    Well, Ill be compiling it on a VC 6 machine. In truth, I dont think the function should be so complex that you require Linux specific OS calls.

    As for rashikil's lame attempts to prove his intelligence, Id say he has succeeded, although not in the way he probably intended.
    Quote Originally Posted by Rashakil Fol View Post

    Code:
    double sigmoid(double x) { return 0.0; }
    defines a line with slope 0.0 and zero inflection points. Since an input of infinity into your equation produces erronious results, it is hence disqualified.
    Last edited by abachler; 07-10-2007 at 01:14 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.

  9. #9
    Amazingly beautiful user.
    Join Date
    Jul 2005
    Location
    If you knew I'd have to kill you
    Posts
    254
    I was planning on using inline ASM. As not being part of the standard language, GCC and VC++ use a different syntax for inline ASM, plus GCC uses AT&T style ASM (src dst), while VC++ uses Intel style (dst src).
    Programming Your Mom. http://www.dandongs.com/

  10. #10
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    as long as you let me know that, and the code isnt too long, I think I can manage to touch it up for testing.
    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. #11
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by abachler View Post
    defines a line with slope 0.0 and zero inflection points. Since an input of infinity into your equation produces erronious results, it is hence disqualified.
    Now you're making up new rules that weren't in your original set of rules. Sigmoid functions are functions mapping the real line into a subset (a,b) of the real line; infinity is not part of the domain. It's a good idea to have all the rules of the contest listed, if you want the function to handle non-real doubles.

    But, if you insist...

    Code:
    double sigmoid(double x) { return (x > 0) - (x < 0); }
    This implements the function f(x) = 2atan(x*((((((((100!)!)!)!)!)!)!)!))/pi.

    Edit: Of course, this would have to be modified if the input is an array of numbers now.
    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. #12
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Well, im tired of you claiming this as an entry, so heres the deal. Return 0.0 does not compute a sigmoid. return (x > 0) - (x < 0) returns type bool or an integer depending on your compiler, so it violates rule #2 even as originally defined. Even if you recast it as a double, it would fail based on the requirement that the output exhibit 'the classical properties of a sigmoid'. i.e. a non-zero slope at all points.

    entry disqualified.

    Before you try to provide some other entry, please go read what a sigmoid function actually is. Its a very specific type of function that none of your entries even approximate as you claim.
    Last edited by abachler; 07-10-2007 at 03:01 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.

  13. #13
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by Rashakil Fol View Post
    Edit: Of course, this would have to be modified if the input is an array of numbers now.
    You can specify if you want the function to be called sequentially, or to be passed the array. The array is to make it fair for GPU entries, since they generally process several data points at once.
    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. #14
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,622

    omg optimized sigmoids

    I still find it confusing frankly. I can't help but feel that you are ignoring what Rakashil Fol is really attempting to say.

    If you're mapping (-infinity, +infinity) monotonically into (-1,1) or [-1,1] using doubles, you're going to have either significant regions of slope zero, or multiple inflection 'points'. That's what you get when approximating functions' behavior, no matter what the function is. Suppose I wrote

    Sigmoid functions are functions mapping the real line into a subset (a,b) of the real line; infinity is not part of the domain.
    Do you intend to ignore these, and the other points about floating point numbers? Fuzzy math will make correct entries wrong. I don't think anyone will want to participate if the contest judge - I hate the term - doesn't know what he's doing.

    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?

  15. #15
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    No, I use sigmoids all the time. Rashakil is trying to use 'return 0;' style weasel code and then claim it computes a sigmoid. It performs no calculation whatsoever, sigmoid or otherwise. 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. Yes I understand that a floating point number cant quantize infinite granularity. However the data set returned by ALL his entries fail on multiple points, and yet he refuses to accept that they are not valid entries. I changed the rules, not because they were flawed, but just to spell it out in really small words that even a retarded gorilla can understand that entries must actually compute a sigmoid, not just return a fixed value. Hey im sorry I didnt put in the rule about no weasel code up front. I honestly expected people to submit realistic entries, not to try to claim that since some specific subset of a function cannot be computed within the limits of the hardware, that therefor all attempts at computing any function of that type in hardware can be represetned by a single fixed value. so for those of you that want ot exploit the limitations of the hardware to avoid actual computation, here is a specific requirement of the function.

    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)
    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
    Last edited by abachler; 07-10-2007 at 03:53 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.

Page 1 of 3 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