Fastest Sigmoid Function

[whiteflags]

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.

[Rashakil Fol]

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?

[brewbuck]

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.

[abachler]

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.

[Rashakil Fol]

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.

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.

[abachler]

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

[pianorain]

In general, I agree with Rashakil Fol. Consider the possible entry:

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.

[Rashakil Fol]

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.

[Rashakil Fol]

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.

[abachler]

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

[Rashakil Fol]

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

double sigmoid(double x) { return x < -1.0 ? -1.0 : (x > 1.0 ? 1.0 : x); }

[Rashakil Fol]

Whatever, here's one.

Question: What does the following give you?

  double v1 = 83222687.6013975441455841064453125;
  double v2 = 83222686.0;
  double u1 = citizen_sig(v1);
  double u2 = citizen_sig(v2);

  printf("%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.

[abachler]

I gave you an equation whose implementation woudl pass the requirements.

1 / 1 + e^-X

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;
     }

Isn't a sigmoid function supposed to be monotonic?

Wow, no it isnt. This article - Sigmoid Function should be of use to you.

[Rashakil Fol]

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:

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

[Rashakil Fol]

You could try giving an implementation for others that compiles on a modern compiler. Yours doesn't even compile on VC++ 2003.