I've seen lots of wonderful and/or horrible things here, both on the main site and in this contest, and I think WTFs can be divided in two main categories, at least when talink about code: things that are just so utterly complicated and/or convoluted they could easily win an Obfuscated <Put Your Language Here> Contest, and things that are just simple, neat, to the point, and leave you screaming in horror and wanting to use some really heavy and/or really sharp tool on the programmer who created them.

I personally prefer the latter ones, and all my entries follow this pattern; I think a Real WTF(TM) should slam you in the face with the uttermost violence, instead of making you look, search and try to understand what at all is it all about. Also, simple (but powerful) WTFs have two added benefits: they can easily be understood by someone who doesn't even know the language they're written in, and they can be quickly shared with your friends; something like "hey, this guy's deleting an object from inside it, WTF?!?" or in "patching in-memory ASM code at runtime, now *that*'s crazy!", or even "wow, the calculator is executed on a network server to which the GUI connects and submits operations using XML, what had the programmer smoked?"; as opposed to "what the heck's going on in this 500-lines function who returns the sum of two numbers? Let's see... oh, that's a bitshift... ok, recursion... damn, what was that variable for? Argh, headache!".

What do you think about this? :-)

or even "wow, the calculator is executed on a network server to which the GUI connects and submits operations using XML, what had the programmer smoked?"

 How did you see my entry? ;-)

But yeah, I prefer the second type too, although throwing in some memory leaks, random crashes, and really bad error checking is always fun. 

burntfuse:

or even "wow, the calculator is executed on a network server to which the GUI connects and submits operations using XML, what had the programmer smoked?"

How did you see my entry? ;-)

I had the same idea, and I would indeed have used it if the contest was .NET based... but I just hate C-based Win32 APIs.

But yeah, I prefer the second type too, although throwing in some memory leaks, random crashes, and really bad error checking is always fun.

My fist entry shouts something along the lines of "you're not allowed to do this!" if you try to use decimal or negative numbers... it's just too much pain to handle those when your calculator is based on manipulating strings.

Massimo:

My first entry shouts something along the lines of "you're not allowed to do this!" if you try to use decimal or negative numbers... it's just too much pain to handle those when your calculator is based on manipulating strings.

My fist entry shouts something along the lines of "you're not allowed to do this!" if you try to use decimal or negative numbers... it's just too much pain to handle those when your calculator is based on manipulating strings.

I handled them easily. I just pass the number through the string-to-float and float-to-string functions I wrote (which did about 30 times more calculations than the calculator itself) until I've got numbers I can work with.  Basically, I just ignored problem characters.  0.6 * 5 = 30.  Negative numbers work for addition.  For multiplication, though... well... an hour wasn't enough for it to complete on a Core 2 Duo system.

Oh, when you said "handle" them you meant handle them correctly.  My bad.

macavenger:

Tell me about it...I never realized just how hard subtraction actually is until I tried to break it down to work on strings, character-by-character.

This is mine:

char* DoSub(char* op1,char* op2)
{
 static char result[256];
 
 // Return zero if operands are the same
 if(IsGreater(op1,op2) == Undefined)
  return(zero);

 char buf1[256];
 char buf2[256];
 
 // Prepare buffers
 // Can't trust memset() here
 for(int i = 0;i < 256;i++)
 {
  buf1[i] = '0';
  buf2[i] = '0';
 }
 
 // Copy operands in buffers with right alignment
 for(int x = strlen(op1),y = 255;x >= 0;x--,y--)
  buf1[y] = op1[x];
 for(int x = strlen(op2),y = 255;x >= 0;x--,y--)
  buf2[y] = op2[x];
 
 //Find greater operand
 char *greater = NULL;
 char *lesser = NULL;
 
 if(IsGreater(op1,op2) == True)
 {
  greater = buf1;
  lesser = buf2;
 }
 else
 {
  greater = buf2;
  lesser = buf1;
 }
 
 // Prepare result
 result[255] = '\0';
 
 int borrow = 0; // Will be used to handle borrow

 // Standard right-to-left, subtract-with-borrow algorithm
 for(int i = 254;i >= 0;i--)
 {
  int c1 = (int) (greater[i] - '0');
  int c2 = (int) (lesser[i] - '0');

  int r = c1 - c2 - borrow;

  if(r >= 0)
  {
   result[i] = ((char) r) + '0';
   borrow = 0;
  }
  else
  {
   result[i] = ((char) r + 10) + '0';
   borrow = 1;
  }
 }
 
 // Insert leading minus sign if needed
 if(IsGreater(op2,op1) == True)
 {
  int i = 0;

  while(result[i] == '0')
   i++;
  
  result[i - 1] = '-';
 }

 // Remove leading zeroes
 while(result[0] == '0')
 {
  for(int i = 0;i < 255;i++)
   result[i] = result[i + 1];
 }

 // Return result
 return(result);
}

TheFeshy:

I handled them easily. I just pass the number through the string-to-float and float-to-string functions I wrote...

macavenger:

For my case, at least, manipulating strings means manipulating ONLY strings...no converting to floats allowed, however self-written and WTF'y the conversion is :)

You're absolutely right.

I take them from the calculator's display, operate on them and print the result out without ever using any "true" number.

Massimo:

macavenger:

Tell me about it...I never realized just how hard subtraction actually is until I tried to break it down to work on strings, character-by-character.

This is mine:

[snip...]

Here is mine:

char *DoSub(char *op1, char *op2)
{
    //TODO return the difference between op1 and op2

    static char TheResult[BUFFERSIZE];
    Move(TheResult, &Zero);

    char Sign = Compare(op1, op2) == Less ? Subtraction : Addition;
    if (Compare(op1, op2) == Less)
        *(long*)&op1 ^= *(long*)&op2 ^= *(long*)&op1 ^= *(long*)&op2;

    char *PointerTo_op1 = EndOf(op1);
    char *PointerTo_op2 = EndOf(op2);
    char *PointerToTheResult = TheResult;
    bool BorrowTheOne = false;

    while (PointerTo_op1 >= op1)
    {
        char *RightOp = PointerTo_op2 >= op2 ? PointerTo_op2-- : &Zero;

        if (*PointerTo_op1 == Nine && *RightOp == *PointerTo_op1)
            *PointerToTheResult++ = BorrowTheOne == true ? *PointerTo_op1 : Zero;
        if (*PointerTo_op1 == Nine && *RightOp == Eight)
        {
            *PointerToTheResult++ = BorrowTheOne == true ? Zero : One;
            BorrowTheOne = false;
        }
        if (*PointerTo_op1 == Nine && *RightOp == Seven)
        {
            *PointerToTheResult++ = BorrowTheOne == true ? One : Two;
            BorrowTheOne = false;
        }
       

... Snipped a couple hundred lines of similiar code

        if (*PointerTo_op1 == Zero && *RightOp == Two)
        {
            *PointerToTheResult++ = BorrowTheOne == true ? Seven : Eight;
            BorrowTheOne = true;
        }
        if (*PointerTo_op1 == Zero && *RightOp == *PointerTo_op1)
            *PointerToTheResult++ = BorrowTheOne == true ? Nine : *PointerTo_op1;
        if (*PointerTo_op1-- == Zero && *RightOp == One)
        {
            *PointerToTheResult++ = BorrowTheOne == true ? Eight : Nine;
            BorrowTheOne = true;
        }
    }

    *PointerToTheResult = End;
    PointerToTheResult = Reverse(TheResult);
    while (*PointerToTheResult++ == Zero && *PointerToTheResult != End);
        --PointerToTheResult;
    if (Sign == Subtraction)
        *Move(PointerToTheResult + 1, PointerToTheResult) = Sign;

    return PointerToTheResult;
}

I picked a faux client-server approach.  I drew a lot of inspiration from the front page WTFs on this fine website.  Here are the steps to calculating 1 + 1 in my calculator.

1.  The Front End is a text widget that does not allow interaction (you can only talk to it via an input palette).  The Front End retains a string in memory instead of reading off of the text widget, so using the text box is a futile affair.  Entering "1+1=", at this point, causes the string "1+1" to be created.
   
2. When the user presses '=', the Middle End (part 1) is forked off by the Front End.  The Front End then prints the string to a pipe, where the middle end (part 1) redirects stdin and stdout to files.  They would have been pipes, but that never worked.  So the middle end copies the pipe to a file, opens an output end, and executes bison parser #1.  The parser's only job is to transform "1+1" into something the Back End will understand: a string of the form 'it = "1"+"1"; print it;".  This is, of course, sent off on to a pipe to Middle End (part 2).
   
3. The Middle End (part 2) used to be an experiment in piping to bison, but once it started working, I found it easier to interact with that than the Back End.  So its sole purpose in life is to talk to the Back End in a way it understands.  It does nothing but move what's printed on its pipe to a different file, and fork & exec the Back End.
4. The Back End parses the string expressions, passing them to libGMP in a leaky and useless manner, and then prints to what it believes is stdout.
5. Instead of trying to simulate a reply, I got lazy and used the Front End to open up the last file in the chain and read it, appending the contents to the text widget.
   

Massimo:

I've seen lots of wonderful and/or horrible things here, both on the main site and in this contest, and I think WTFs can be divided in two main categories, at least when talink about code: things that are just so utterly complicated and/or convoluted they could easily win an Obfuscated <Put Your Language Here> Contest, and things that are just simple, neat, to the point, and leave you screaming in horror and wanting to use some really heavy and/or really sharp tool on the programmer who created them.

I personally prefer the latter ones, and all my entries follow this pattern; I think a Real WTF(TM) should slam you in the face with the uttermost violence, instead of making you look, search and try to understand what at all is it all about. Also, simple (but powerful) WTFs have two added benefits: they can easily be understood by someone who doesn't even know the language they're written in, and they can be quickly shared with your friends; something like "hey, this guy's deleting an object from inside it, WTF?!?" or in "patching in-memory ASM code at runtime, now *that*'s crazy!", or even "wow, the calculator is executed on a network server to which the GUI connects and submits operations using XML, what had the programmer smoked?"; as opposed to "what the heck's going on in this 500-lines function who returns the sum of two numbers? Let's see... oh, that's a bitshift... ok, recursion... damn, what was that variable for? Argh, headache!".

What do you think about this? :-)

I think you're right about the Ugly Code rule.  I think it's going to disqualify a significant number of entries.  I'm hoping mine is not one of those, although I went and abused the Ugly Code rule, as my entry is kind of a hybrid.  There's Ugly Code in there, but that's not the Real WTF.  The Real WTF is the clean code I wrote to make the Ugly Code work. 

Hmm, I think I just gave everything away.  That little tidbit combined with the my other recent posts probably gives away what I did.  I'm still not going to be explicit. 

Massimo:

macavenger:

For my case, at least, manipulating strings means manipulating ONLY strings...no converting to floats allowed, however self-written and WTF'y the conversion is :)

You're absolutely right.

I take them from the calculator's display, operate on them and print the result out without ever using any "true" number.

But looking at your DoSub() code I noticed you are using ints in your for loops. In my code I do not use any numbers, not even for counting loops. It is all done with text strings.

In my code I do not use any numbers, not even for counting loops. It is all done with text strings.

for (char i = 'a', i < 'a' + NUM_ITERATIONS; i++) ?  Or is it something worse?

Massimo:

I've seen lots of wonderful and/or horrible things here, both on the main site and in this contest, and I think WTFs can be divided in two main categories, at least when talink about code: things that are just so utterly complicated and/or convoluted they could easily win an Obfuscated <Put Your Language Here> Contest, and things that are just simple, neat, to the point, and leave you screaming in horror and wanting to use some really heavy and/or really sharp tool on the programmer who created them.

burntfuse:

In my code I do not use any numbers, not even for counting loops. It is all done with text strings.

for (char i = 'a', i < 'a' + NUM_ITERATIONS; i++) ?  Or is it something worse?

This is my DoMul() function. LoopCounter is the loop controller:

char *DoMul(char *op1, char *op2)
{
    //TODO return the product of op1 and op2

    static char TheResult[BUFFERSIZE];
    Move(TheResult, &Zero);

    char LoopCounter[BUFFERSIZE];
    Move(LoopCounter, &Zero);
    while (Compare(LoopCounter, op2) == Less)
    {
        Move(LoopCounter, DoAdd(LoopCounter, &One));
        Move(TheResult, DoAdd(TheResult, op1));
    }

    return TheResult;
}

I used only while loops in my code, there are no for loops at all.

Chicken Little:

burntfuse:

In my code I do not use any numbers, not even for counting loops. It is all done with text strings.

for (char i = 'a', i < 'a' + NUM_ITERATIONS; i++) ?  Or is it something worse?

This is my DoMul() function. LoopCounter is the loop controller:

[snip..]

I used only while loops in my code, there are no for loops at all.

 

macavenger:

Massimo:

My first entry shouts something along the lines of "you're not allowed to do this!" if you try to use decimal or negative numbers... it's just too much pain to handle those when your calculator is based on manipulating strings.

Tell me about it...I never realized just how hard subtraction actually is until I tried to break it down to work on strings, character-by-character. In my code, I managed to eliminate ints entierly... makes for some fun lines like char buffer[`~']; :p

static void minus(node_t *l, node_t *r)
{
        int n, i, b = 0;
        char *res;
        /* Recursive reduction of parsetree to values */
        reduce(l);
        reduce(r);
        /* Degenerate cases */
        if(l->e || r->e)
        {
                l->e = 1;
                zap(r);
                return;
        }
        if(r->s)
        {
                r->s = 0;
                plus(l, r);
                return;
        }
        n = fixsize(l, r);  /* Need same sized operands */
        res = (char *)xmalloc(n+2);
        for(i = 0; i < n; i++) /* Subtract */
        {
                int ch = l->v[i] - r->v[i] + '0' - b;
                b = 0;
                if(ch < '0')
                {
                        ch += 10;
                        b++;
                }
                res[i] = ch;
        }
        if(b) /* 2's complement if borrowed (negative) */
        {
                node_t *o = (node_t *)xmalloc(sizeof(*o));
                node_t *p = (node_t *)xmalloc(sizeof(*p));
                node_t *q = (node_t *)xmalloc(sizeof(*q));
                char *c = (char *)xmalloc(n+2);
                memset(c, '0', n);
                c[i] = '1';
                p->v = c;
                q->v = res;
                minus(p, q);
                res = p->v;
                xfree(p);
        }
        else
                while(i > 1 && res[i-1] == '0')
                        res[--i] = 0;
        l->s = b;
        zap(r);
        xfree(l->v);
        l->v = res;
}

BsAtHome:

But subtraction is so simple in ASCII BigEndian BCD as in O(n) for positive results and O(2n+1) for negative results:

O(n) and O(2n+1) are the same thing. 

asuffield:

O(n) and O(2n+1) are the same thing.

They are, because their durations both depend linearly on N.

At the same time, they are not, because O(2n) will always take two times the time of O(n).

Massimo:

asuffield:

O(n) and O(2n+1) are the same thing.

They are, because their durations both depend linearly on N.

At the same time, they are not, because O(2n) will always take two times the time of O(n).

No, you have to understand what O() actually means. It's not just a rough measurement of the algorithm's performance, nor is it a measurement of how many steps the algorithm actually takes, it has a specific definition. Informally:

An algorithm is O(f(x)) if and only if there exists two constant values C and x0 such that the time/steps/whatever taken to complete the algorithm is always less than C * f(x) for all x > x0. Note that this means O() notation is concerned only with the performance of the algorithm for extremely large values, and describes some expression that is always slower than the algorithm.

If a function is O(n), then it always takes less than C1*n; if it's O(2n), then it always takes less than C2*2n; C1 is therefore equal to C2*2, so the properties O(n) and O(2n) are precisely identical - any function that is O(n) is also O(2n) and vice versa.

If the O() function is polynomial (contains nothing larger than terms of the form "x raised to the power y", so no factorials or anything like that) then you can always throw away all constant factors and all terms except those with the highest power in the function, and you'll still have exactly the same property. You can also add any constant factors or lower-power terms without altering it. (Proving this is a little subtle but any CS postgraduate student should be able to do it; I believe you can find the proof in CLR somewhere)

Similarly, since O() says only that the algorithm is always faster than the expression given (for sufficiently large input data), any O(n) algorithm is also O(n^2) (but obviously, the reverse is not true).

 
While on the topic of subtraction using strings, here's mine:

 

// Change the string to an equivalent numeral by shifting the characters to a lower level
void outlevel(char** input)
{
    // Do most using simple string replaces
    *input =    replace(
                    replace(
                        replace(
                            replace(
                                replace(
                                    *input,
                                    "V","IIIII"),
                                "X","VV"),
                            "L","XXXXX"),
                        "C","LL"),
                    "D","CCCCC");
//    *input = replace(*input,"M","DD");

    // Search through the string looking for letter Ms
    char *temp;
    int inputlength = strlen(*input);
    bool matched = false;
    for (int a = 0; a < inputlength && !matched; a++)
    {
        if ((*input)[a] == 'M'/* && (*input)[b+1] != 'M'*/)
        {
            // If a letter M is found, remove it and put two Ds at the end
            (*input)[a] = ' ';
            strcat_s(*input,RN_MAX_LENGTH,"DD");
            // Mark the change as done
            matched = true;
        }
    }   
}

// Subtract two roman numerals
char* RomSub(char* op1, char* op2)
{
    // Remove subtractive notation
    op1 = RemSubNot(op1);
    op2 = RemSubNot(op2);
    int count = 0;
    // Continue loop until the second input is equal to zero
    while (ToInt(op2) != 0)
    {
        // Get the lengths of the two strings
        int length1 = strlen(op1);
        int length2 = strlen(op2);
        // Cycle through each character of both strings
        for (int a = 0; a < length1; a++)
        {
            for (int b = 0; b < length2; b++)
            {
                // If the character appears in both strings, remove it
                if (op1[a] == op2[b])
                {
                    op1[a] = ' ';
                    op2[b] = ' ';
                }
            }
        }
        // Simplify out by one level
        outlevel(&op1);
    }
   
    // Bubble sort etc
    int strlength = strlen(op1);
    bool move_made = true;
    char temp;
    for (int a = 0; a < strlength - 1 && move_made; a++)
    {
        move_made = false;
        for (int b = a + 1; b < strlength; b++)
            if    (ToInt(&op1[a]) < ToInt(&op1[b]))
            {
                temp = op1[b];
                op1[b] = op1[a];
                op1[a] = temp;
                move_made = true;
            }
    }

    // Simplify result by summation of internal numerals:
    op1 =    replace(
                replace(
                    replace(
                        replace(
                            replace(
                                replace(
                                    op1,
                                    "IIIII","V"),
                                "VV","X"),
                            "XXXXX","L"),
                        "LL","C"),
                    "CCCCC","D"),
                "DD","M");

    // Convert too and from an integer so that all the spaces and things are removed
    op1 = ToRoman(ToInt(op1));
    return op1;
}

Only really uses ToInt for the loop (because == "N" didn't work and I couldn't be stuffed making it work), tiding up the output (which doesn't even change anything) and for the bubble sort (Though in this case, ToInt always returns 0 for some reason). :D I love this contest <3

asuffield:

Massimo:

asuffield:

O(n) and O(2n+1) are the same thing.

They are, because their durations both depend linearly on N.

At the same time, they are not, because O(2n) will always take two times the time of O(n).

No, you have to understand what O() actually means.

I understand it quite clearly, and I know saying "O(2n)" isn't "right" when talking about the strict theoretical meaning of that notation; I've always found it, anyway, quite useful to make distinctions between "real" algorithms, where having one operation completed in 30 minutes instead of 120 because O(n) is faster than O(4n) actually means something. I know that lowering the O() of an algorithm is the best possible optimization, but, when this is impossible, lowering some coefficient can indeed have its utility.

Massimo:

I understand it quite clearly, and I know saying "O(2n)" isn't "right" when talking about the strict theoretical meaning of that notation; I've always found it, anyway, quite useful to make distinctions between "real" algorithms, where having one operation completed in 30 minutes instead of 120 because O(n) is faster than O(4n) actually means something. I know that lowering the O() of an algorithm is the best possible optimization, but, when this is impossible, lowering some coefficient can indeed have its utility.

O(n) is not faster than O(4n) no matter how many times you say it. If you want to say that algorithm A is four times faster than algorithm B, there is already a perfectly adequate way to say that: "algorithm A is four times faster than algorithm B". O() notation is talking about something entirely different and mixing the two up can only lead to confusion and error.

You might as well say that while strictly, black means black and white means white, you find it convenient to assume that black means white and white means black. It would make about as much sense.

asuffield:

O(n) is not faster than O(4n) no matter how many times you say it.

 Leave it to ivory tower academics who have never written a useful program in their miserable lives to invent a measurement that is useful to no one but themselves.
 

Chemisor:

asuffield:

O(n) is not faster than O(4n) no matter how many times you say it.

 Leave it to ivory tower academics who have never written a useful program in their miserable lives to invent a measurement that is useful to no one but themselves.
 

If you don't understand the usefulness of big-O notation you probably don't understand its proper use. 

Chemisor:

asuffield:

O(n) is not faster than O(4n) no matter how many times you say it.

 Leave it to ivory tower academics who have never written a useful program in their miserable lives to invent a measurement that is useful to no one but themselves.
 

The purpose of Big O notation is not to measure the running time of a program.

The purpose of Big O notation is to measure how the running time of a program scales with different size inputs.

The actual running time of the program strongly depends on the platform it runs on, since different operations take different numbers of clock cycles on different processors, and so forth.  The "hidden constant" attached to the scaling factor from Big O notation is a seperate, but equally important matter.  However, it is never correct to say O(4n), because Big O notation only measures scaling, not the total time or number of operations an algorithm takes.
 

th0mas:

Chemisor:

asuffield:

O(n) is not faster than O(4n) no matter how many times you say it.

 Leave it to ivory tower academics who have never written a useful program in their miserable lives to invent a measurement that is useful to no one but themselves.
 

If you don't understand the usefulness of big-O notation you probably don't understand its proper use. 

asuffield:

Massimo:

I understand it quite clearly, and I know saying "O(2n)" isn't "right" when talking about the strict theoretical meaning of that notation; I've always found it, anyway, quite useful to make distinctions between "real" algorithms, where having one operation completed in 30 minutes instead of 120 because O(n) is faster than O(4n) actually means something. I know that lowering the O() of an algorithm is the best possible optimization, but, when this is impossible, lowering some coefficient can indeed have its utility.

O(n) is not faster than O(4n) no matter how many times you say it. If you want to say that algorithm A is four times faster than algorithm B, there is already a perfectly adequate way to say that: "algorithm A is four times faster than algorithm B". O() notation is talking about something entirely different and mixing the two up can only lead to confusion and error.

You might as well say that while strictly, black means black and white means white, you find it convenient to assume that black means white and white means black. It would make about as much sense.

Ok, I started this discussion by indicating the complexity of my implementation of minus()... You are both right. Strictly, O(f(x)) says merely something about complexity and not timing. It is a description in which both O(n) and O(xn) are equally complex and thus the same. This is the formal use of O(). There are though some suggestions as to state the constants because they say something about the actual efficiency of the implementation.

 
Now then, there is a conditional acceptance to use the O() notation in a comparative sense translated to timing. My case, O(n) vs. O(2n+1) is a comparative case because it is the same function that is described by both indications of complexity. The former indicating positive result from the subtraction and the latter describing any negative result from the subtraction. The comparison is valid because a negative result in the algorithm requires a 2's complement to be calculated (and calls minus() recursively). The complexity of the minus() function with negative result is arguably not twice the complexity of the same function yielding a positive result. Now, the timing of the function can be deduced from the complexity because it is the same function they describe. The function is over twice as slow for negative results than for positive results.

So why did I bother to describe this... Well, it is obviously an interesting feature of the implementation.

The other complexities (approx) which I implemented:

• plus() O(n)
• multiply() O(n*m)
  
• divide() O(4*log2(10)*(|n-m|+1)^2)
  

If you want the formal versions, you can simply choose to strip the constants and set n == m and everybody is happy. Also please note that the original post states the approximate complexity of the functions. I did not want to go through all the formals and just give an indication of what is happening.

JCM:

If string subtraction is hard, why didn't you just do it in ten's compliment addition?

 Perhaps because hundreds of other people did that in their entries.
 

Chemisor:

asuffield:

O(n) is not faster than O(4n) no matter how many times you say it.

 Leave it to ivory tower academics who have never written a useful program in their miserable lives to invent a measurement that is useful to no one but themselves.

The importance of O() notation is specifically that many complicated algorithms can be described only in terms of O() properties - they are too complicated for anybody to prove anything more useful about the running time of the algorithm. This is not the case here, and the use of O() in this context is simply wrong.

O() also has the significant advantage that it permits incomplete proofs - there are many known algorithms which are believed to run in O(n) or O(log n) time, but which have so far only been proven to run in O(n^2) or O(n log n) time. This is part of why it is so critically important to understand that O() is only an upper bound on the running time, not a measurement of the actual running time. Certain unsolved problems, such as prime factoring, can be discussed only in terms of O() bounds because nobody has any idea what the lower limits are.

The use of O() notation indicates a conscious decision on the part of the speaker to avoid describing anything more specific, probably because it would be too difficult and/or unnecessary to do so. Which is why it is so completely wrong to randomly throw an O() around more specific descriptions. 

BsAtHome:

Now then, there is a conditional acceptance to use the O() notation in a comparative sense translated to timing.

NO THERE IS NOT. THIS IS SIMPLY WRONG. STOP DOING IT.

Just because a specific error is made by a significant number of uneducated or stupid people does not mean that it stops being an error. Neither mathematics nor computer science is a democracy.

 

So why did I bother to describe this... Well, it is obviously an interesting feature of the implementation.

The other complexities (approx) which I implemented:

• plus() O(n)
• multiply() O(n*m)
  
• divide() O(4*log2(10)*(|n-m|+1)^2)
  

If you want the formal versions, you can simply choose to strip the constants and set n == m and everybody is happy. Also please note that the original post states the approximate complexity of the functions. I did not want to go through all the formals and just give an indication of what is happening.

Then describe it as such. Do not randomly throw an O() into your description when it is not what you are talking about. It has got nothing to do with what you are trying to say. (Also, this is not 'complexity', it's just estimated running time; 'complexity' is a specific term related to O() bounds)

asuffield:

NO THERE IS NOT. THIS IS SIMPLY WRONG. STOP DOING IT.

There is no reason to start shouting here. It does not really support your position and makes people just want to ignore you.

asuffield:

BsAtHome:

If you want the formal versions, you can simply choose to strip the constants and set n == m and everybody is happy. Also please note that the original post states the approximate complexity of the functions. I did not want to go through all the formals and just give an indication of what is happening.

Then describe it as such. Do not randomly throw an O() into your description when it is not what you are talking about. It has got nothing to do with what you are trying to say. (Also, this is not 'complexity', it's just estimated running time; 'complexity' is a specific term related to O() bounds)

But the whole point is that you can see what the formal results will be. Here look: minus(): O(n), plus() O(n), multiply() O(n^2) and divide() O(1) (arguably O(n) for borderline cases). There you have your formal versions. For all who are interested in it can read from 1890's see Bachmann and see Landau.

The usefulness of the O() paradigm is that it can say something about algorithmic complexity that correlates to the number of steps in the algorithm or how much time it takes. Formally, for any function f(), the fastest growing term determines the order (hence O). But, it does not say anything in a practical sense when you are analysing the same function which has the same order, but two well defined paths. So if you are so freaking upset about the character O, then lets change that and take, well, N. I'll just move on, ignore you, and continue in a more pragmatic way.

BsAtHome:

I'll just move on, ignore you, and continue in a more pragmatic way.

And that, folks, is how we get "worse than failure". 

asuffield:

Just because a specific error is made by a significant number of uneducated or stupid people does not mean that it stops being an error. Neither mathematics nor computer science is a democracy.

On the contrary, both of them are democracies. You can invent whatever terms you want to describe your work, but it still takes consensus among your peers to make them standard. Scientific concepts do not change, of course, but the language mapped to those concepts can change at anybody's whim. Politicians do it all the time. Scientists usually don't, preferring to use already existing terms even if they aren't very appropriate (such as covariant/contravariant designations for tensors, which really ought to be switched in meaning).

Creation of a word for a specific concept is necessarily guided by utility. If you use a concept frequently, it certainly makes sense to invent a word for it. If you don't, a descriptive phrase would be more appropriate than a new word. The O(n) notation was created by computer scientists for algorithm analysis, where it may have figured frequently in their calculations as a pseudo-objective selection criterium. Real programmers never analyse algorithms that way. Sure, we notice if it's O(n) or O(n^2), but nobody ever puts it in those terms because it is blindingly obvious. Any competent developer can tell at a glance which is which in most cases, and the more complex ones simply never happen outside the academia. In the real world, the question everyone asks about the algorithm is "how fast is it?", and that is the only important question because that is what the user will see. Your academic O(n) is of minimal utility in answering that question, so we have stolen it and assigned it another meaning. If you want to steal it back, you are welcome to try. However, there are far more of us than there are of you, so your chances are quite poor. So go suck on it.

Chemisor:

Scientific concepts do not change, of course, but the language mapped to those concepts can change at anybody's whim.

Wrong.  The point of language is to communicate; if everyone used existing terms to mean whatever they liked it would be impossible to know what anyone was saying. 

Chemisor:

Politicians do it all the time.

Wow.  Do you seriously think that's a valid argument in favour of, well, anything?

Chemisor:

Scientists usually don't, preferring to use already existing terms even if they aren't very appropriate (such as covariant/contravariant designations for tensors, which really ought to be switched in meaning).

That's somewhat unfortunate, but it's far better than using words to mean the EXACT OPPOSITE of what everyone else already understands them to mean. 

Chemisor:

Creation of a word for a specific concept is necessarily guided by utility. If you use a concept frequently, it certainly makes sense to invent a word for it. If you don't, a descriptive phrase would be more appropriate than a new word.

Creating new words is fine, as long as you let people know what they mean.  Hijacking widely known, well-defined existing terms is entirely different. 

Chemisor:

The O(n) notation was created by computer scientists for algorithm analysis, where it may have figured frequently in their calculations as a pseudo-objective selection criterium.

So if it's useful for computer scientists, why are you so determined to take it away from them?  Rather selfish of you, don't you think? 

Chemisor:

Real programmers never analyse algorithms that way.

Quite a generalisation there.  But even if it's true, than said "real programmers" simply have no need for the O notation.  That's no reason for them to use it for something else that it's not supposed to mean.  It would be like saying that you have no need for the French language, therefore it's OK to start using existing French words to mean whatever you feel like making them mean.

Chemisor:

In the real world, the question everyone asks about the algorithm is "how fast is it?",

"Everyone"?  Really? Got proof of that?  Or are you "stealing" the word and "redefining" it to mean "everyone who agrees with me"? 

Chemisor:

and that is the only important question because that is what the user will see.

You mean it's the only question that YOU care about. If the other questions weren't important to anyone, they wouldn't have asked them in the first place.

Chemisor:

 

Your academic O(n) is of minimal utility in answering that question, so we have stolen it and assigned it another meaning. If you want to steal it back, you are welcome to try. However, there are far more of us than there are of you, so your chances are quite poor. So go suck on it.

If the O notation doesn't mean what YOU want, then you are quite welcome to come up with your own, unambiguous notation that does.  (Whether anyone else will care is another matter.)  However, the world does not revolve around you, so you have absolutely no right to destroy something that other people use, just because it doesn't happen to satisfy YOUR needs.

Chemisor:

Your academic O(n) is of minimal utility in answering that question, so we have stolen it and assigned it another meaning.

I'm betting that there is going to be a donkey involved soon. 

Chemisor:

Your academic O(n) is of minimal utility in answering that question, so we have stolen it and assigned it another meaning.

Just like how computers have stolen the meaning of common SI prefixes to mean something else, leading to incredible confusion, and even inconsistencies?

 Outside of the imperial measurement system (really, how much volume is a gallon? Oh, you mean I have to say "imperial gallon" or "US gallon"?), the IT field is where one word can mean two different things (one is right, much to everyone's annoyance), and it's not easy determining which because everybody mixes them up.

 Example the first - how big is a kilo of something? A kilogram (kg) is 1000 grams. A kilometer (km) is 1000 meters. A kilobit  (kb) is 1000 bits. A kilobyte (kB) is... 1024 bytes? WTF? (The correct meaning is a kilobyte (kB) is 1000 bytes. A kibibyte (kiB) is 1024 bytes.)

Example the second, a megagram (Mg) (1000 kilograms, improperly as 1 kilo-kilogram), aka a tonne, is 1,000,000 grams. A gigagram (improperly mega-kilogram) is 1,000,000,000 grams. Or a megaohm is 1,000,000 ohms. A megabit is 1,000,000 bits. A megabyte is... 1,048,576 bytes? (Incorrect. A megabyte is 1,000,000 bytes. A Mebibyte (MiB) is 1,048,576 bytes). Ethernet comes in 10/100/1000megabit/s rates, or 10,000,000, 100,000,000 and 1,000,000,000 bits/sec...).

Thus, stolen words make life very confusing. In fact, if you have a floppy drive in your computer, you'll find it's taken the worst - a 1.44"MB" floppy is 1,440 kiB in size. So it's technically a 1.44kilo-kibibyte disk. Also why better operating systems now use the  proper prefixes (e.g., Linux has migrated to using binary prefixes as appropriate, and SI prefixes when talking about "human" numbers). It's never confusing what units are used on Linux as it'll say "MiB" or "kiB" when it means base-2, and "MB"/"kB" when it means base-10. Heck, even Microsoft Windows Explorer can use a mix of SI, SI/binary, binary prefixes when displaying filesizes.

 

I'm just waiting until Godwin's Law is invoked. This thread is developing in a way that would suggest it is getting there.

BsAtHome:

I'm just waiting until Godwin's Law is invoked.

Why, so you can redefine it? 

th0mas:

BsAtHome:

I'm just waiting until Godwin's Law is invoked.

Why, so you can redefine it? 

So, let's get with this one.  All the people who think that they can just repossess Big-O notation are communists.

Now, all you communists, get with the redefining and invoke Godwin's Law on me. 

EDIT: Yes, I'm trolling.  Yes, I'm just messing with you guys.
 

BsAtHome:

I'm just waiting until Godwin's Law is invoked. This thread is developing in a way that would suggest it is getting there.

Hitler tried to ensure that all words had a specific, un-malleable meaning once...

Whiskey Tango Foxtrot? Over.:

BsAtHome:

I'm just waiting until Godwin's Law is invoked. This thread is developing in a way that would suggest it is getting there.

Hitler tried to ensure that all words had a specific, un-malleable meaning once...

Carnildo:

Whiskey Tango Foxtrot? Over.:

Hitler tried to ensure that all words had a specific, un-malleable meaning once...

He did?  I thought that was Orwell.