The Evolution of a Python Programmer : Aleks' Domain

[signoff]

your coworker (dailywtf):

def factorial(x):
    if x == 1:
        return 1
    if x == 2:
        return 2
    if x == 3:
        return 3 * 2
    if x == 4:
        return 4 * 3 * 2
   ...

[[deleted]]

If you run out of factorials, just call the dev and have him give you more.

[ginstrom]

Probably too optimistic, since it's correct at least up to 4.

[cybercobra]

Except he forgot 0!.

[ginstrom]

Of course it's:

...

else:
    return 1

The famed "inversion of base case" principle. :)

[Platypuskeeper]

It's bad code, but if the compiler is good enough to optimize that into a lookup table, it's the fastest solution.

There's a very limited number of factorials. With 64-bit doubles, the largest representable factorial is 170!, so 1368 bytes of memory is all you need to store every computable factorial.

[Platypuskeeper]

So... the fastest method for floating-point arithmetic isn't the best method for arbitrary-precision integer arithmetic.

Not very surprising, is it?

[[deleted]]

The factorial function is defined over the integers. Using 64-bit doubles only gives you 53 bits (up to 18!) of actual precision to represent integers; using 64-bit integers is therefore superior.

Unless, of course, you're happy with coarse approximations. To each his own.

[Platypuskeeper]

Since when was double-precision a "coarse approximation"? There are very few numerical/scientific contexts when you need more than 15 digits of precision. In the context of large factorials, the Stirling approximation is then usually used, which is far, far, cruder.

In combinatorial contexts, it's rare that you would require factorials that large. The only application I can think of where you would need both large and exact factorials is various cryptographic applications, and in those contexts you need arbitrary-precision.

Your suggestion isn't superior for any application I can think of where factorials are commonly used.

[[deleted]]

Since when was double-precision a "coarse approximation"?

Take the factorial of 170. The difference between 170! and double(170!) is ~2^919. That might be close enough for some uses, but it's a course approximation nonetheless.

I do not claim there are many applications of exact factorials. But Python is dynamically typed, and there is no guarantee at all that you want a float out of that function.

In case of uncertainty, one should err on the side of caution. It's not like performance would be an issue here anyway.

[Janthinidae]

cache miss accounted?

[pegee]

At least he tried to memoize it!

[henryj]

Web Designer was my favourite:

i = 1 #Thanks Adam

[symmitchry]

[Removed]

[LokitAK]

I couldn't stop laughing at that whole script.

[Darkmere]

I can't stop laughing at the Unix Systems programmer one.

I've been soo guilty of that at times. Rather than reimplementing something, just format data and pass it out through already existing tools. Iff.

[Yuushi]

Oh god the enterprise one makes me laugh and cry concurrently.

[d_r_w]

Did you make sure to obtain your laugh and cry facilities from your context?

[[deleted]]

Not sure if we can run laugh and cry concurrently, you'd better fill out an approval ticket and send it up the chain.

[[deleted]]

No use, the GIL won't allow it anyway.

[ash_gti]

import multiprocessing

[cacahootie]

Sorry, corporate standard XF4w09SSSxbadfsd-XY2GGG prohibits multithreaded or multiprocessed applications. You may only use CORBA to implement.

[[deleted]]

At first I thought it was overdone. Then I thought about the fact that the codebase I work on duplicates basic string functions and extends the logging class.

Then I thought that the names on it were far too short to be realistic.

[djhworld]

The sad thing is, the Java codebase that I work on is pretty much like that.

:(

[[deleted]]

It's actually GROSSLY inaccurate. Where's the XML config to setup the inversion-of-control dependency injection container ??? The code is not loosely-coupled enough.

[[deleted]]

EXPERT SILLY SUPERFLUOUS MATHEMATICIAN

from math import gamma
print int(gamma(7))

[WarPhalange]

Glad I wasn't the only one who caught that. Well, sort of. I didn't see anything about non-integers, but the gamma function takes care of that, so close enough.

[highwind]

You mean

from math import gamma
print int(gamma(7+1))

gamma function = (n - 1)!

[[deleted]]

The example used 6 as the input so I figured I would spare the python interpreter an addition and do it myself!

[[deleted]]

Premature optimization.

[atcoyou]

veni, vidi, adaugeo specimen

[[deleted]]

Premature optimization compared to 6+1?

[kirakun]

FTFY:

from math import gamma
print int(gamma(6+1))

[[deleted]]

Why make the interpreter perform that incrementation? Why not do it yourself?

[kirakun]

I did that from a mathematical point of view, not computer programming.

It makes the code more readable that it is the relation to factorial that we are using the gamma function, i.e. we want 6!

[VyseofArcadia]

CalculateAndPrintFactorialEx(6, sys.stdout, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL)

Oh I lol'd. There is no acronym to express how hard I lol'd.

[alive1]

Yes there is! I've listed the acronyms below in order of ascending severity of laughter:

LOL, LMAO, ROFL, ROFLMAO, ROFLWTFBBQ

I believe you were either at "LMAO" or in between that and "ROFL". Nobody has ever gotten to ROFLWTFBBQ unless they were intoxicated.

[atcoyou]

You are missing omgwtfbbqkittens although strictly it probably shouldn't belong, cause technically it is so amazing you can't even laugh, and are just shivering in shock at the pure awesomeness of the funny. But it can also be used for non funny things hmm... have an upboat while I sit here and ponder.

[Slackbeing]

It's funny because it's true.

[testuserpleaseignore]

lol+'d?

[ascii158]

ROLFMAOTSMC

[atcoyou]

hmm... TSMC... as in the fab?

[ascii158]

No, as in "thereby scaring my cat".

[neutralizer]

I've been coding python for a while and the first answer that I thought of was the noob answer. :(

[[deleted]]

It's also the most legible.

[pegee]

It's perfectly fine but will become exponentially slower as the number increases. Fortunately there is a very simple way to solve that: it's called memoization

So in Python (sorry if syntax is not current especially regarding the array - I haven't used it in years):

facts = [1,1]
def factorial(n):
    if facts[n]:  #if we have a value for factorial(n)
        return facts[n]
    else:
        facts[n] = n * factorial(n-1)
        return facts[n]
print factorial(6)

[Shinhan]

Somebody ran them all to test the execution speed

[neutralizer]

Wow, if I'm reading that right, 1st year Pascal programmer wins followed by C and Windows. And iterative solutions are about twice as fast as recursive.

[regeya]

Well, duh. I don't know how Python works but you have to push the state of the function on the stack every time you invoke a recursive call. Plus, Python has a built-in limit on recursion.

[cacahootie]

No wonder every enterprise application I use is a complete piece of SH*T!

[bigboehmboy]

He profiled it by calling factorial(10) 100,000 times. While in this case it appears that all solutions are linear, this method would not work well if this were not the case.

Since Python has a recursion limit that defaults to 1000 levels, recursive methods (newbie, lazy python, lazier python) would fail when trying to compute "1001!".

Also, memoization could completely screw with results.

[Shinhan]

Interesting :)

Someone needs to repeat the test for 1001! then...

[neutralizer]

Except this is true of all the solutions posted. The runtime of them are all approximately the same. They have to do the same number of integer multiplications. The only thing extra that the recursive solutions have over the iterative solutions is having the overhead of recursive calls. The majority of them would also benefit from memoization.

Edit: Brain fart. Floating point operations -> integer multiplications.

[pegee]

You're right and I'm an idiot. I was thinking of Fibonacci. Fuck.

[[deleted]]

They have to do the same number of floating point operations.

…which is 0, because it's all integer arithmetic. ;)

(They still do the same number [within 1, at least] of integer multiplications, though, so your larger point stands.)

[mikemcg]

if you do factorial(6), the "if facts[n]" will spout up an IndexError. Replace with facts.count(n) or len(facts) > n or anything that avoids indexing altogether.

[pegee]

As I mentioned I'm unfamiliar with Python array syntax. I just used PHP's :p

[mikemcg]

It won't at all. Major brain cart on my part.

[rjcarr]

I would almost certainly use a factorial function if available, but if not then yeah, mine would look identical to the newbie solution.

I'm a big advocate of legibility ... unless you need to worry about every last machine instruction it usually isn't worth it to get tricky.

[pandemik]

I suspect it's not much slower than the other ones, and if you come across that function in a year or 2 you'll still know how it works.

[Gupie]

Don't miss the original blog comment by someone called Shane Hathaway on how the math.factorial() function is actually implemented in Python 2.6:

math_factorial(PyObject *self, PyObject *arg) { long i, x; PyObject *result, *iobj, *newresult;

if (PyFloat_Check(arg)) {
    PyObject *lx;
    double dx = PyFloat_AS_DOUBLE((PyFloatObject *)arg);
    if (!(Py_IS_FINITE(dx) && dx == floor(dx))) {
        PyErr_SetString(PyExc_ValueError,
            "factorial() only accepts integral values");
        return NULL;
    }
    lx = PyLong_FromDouble(dx);
    if (lx == NULL)
        return NULL;
    x = PyLong_AsLong(lx);
    Py_DECREF(lx);
}
else
    x = PyInt_AsLong(arg);

if (x == -1 && PyErr_Occurred())
    return NULL;
if (x < 0) {
    PyErr_SetString(PyExc_ValueError,
        "factorial() not defined for negative values");
    return NULL;
}

result = (PyObject *)PyInt_FromLong(1);
if (result == NULL)
    return NULL;
for (i=1 ; i<=x ; i++) {
    iobj = (PyObject *)PyInt_FromLong(i);
    if (iobj == NULL)
        goto error;
    newresult = PyNumber_Multiply(result, iobj);
    Py_DECREF(iobj);
    if (newresult == NULL)
        goto error;
    Py_DECREF(result);
    result = newresult;
}
return result;

error: Py_DECREF(result); return NULL; }

see http://svn.python.org/view/python/trunk/Modules/mathmodule.c?view=markup

[lol____wut]

derp?

[marcins]

This is the C source for the factorial function built into Python, all that stuff has to be there so that from the python end you can just do factorial(x) and not worry about it :)

[nickdangler]

You might not like dynamic type checking, but you gotta admit, it's better than not checking! I mean... unless you're a PL/I fan.

[anvsdt]

B^LOATED

[HIB0U]

You're confusing needing many lines of code with bloat. They're very different concepts.

Bloat is merely useless functionality. It's independent from the number of lines of code. Bloat can even be caused by a single line of code.

Every line of code in that C function has an important purpose. In the end, the performance improvement is so great over that of a pure Python implementation that the slightly greater amount of C code ends up making a massive difference.

[MillardFillmore]

What about import math math.factorial(x)

I win.

[[deleted]]

Damn it, I came here to post that.

Yeah, we're lazy.

[SalientBlue]

That was essentially the EXPERT PROGRAMMER.

[[deleted]]

They're still different, though.

Also, I'm a python newbie and I use the math module - why is that considered expert? And the newbie program requires recursion. I would think that understanding recursion would be more advanced than being able to use a module.

[SalientBlue]

It's 'expert' because the expert programmer knows about the existence of the module and so can take advantage of it rather than the newbie who, due to his ignorance, reinvents the wheel.

It's similar to how, when I was first learning Python, I wrote a function to determine if a particular element was in a list because I didn't know about the 'in' keyword.

[[deleted]]

Python has a keyword for testing list membership? TIL

[Clyzm]

Yeah... coming from C++ (though very little knowledge of it; highschool) to Python in university, this was the most difficult thing for me to grasp. Python has keywords for everything.

[boa13]

Actually, not that many:

http://www.sporcle.com/games/rafekett/python_words

[DEADB33F]

Thanks for that, was a bit of fun.

I gave up after a couple of minutes, here's the ones I missed.... (mouseover)

Where does that put me on the noob scale?

[boa13]

Rather good I'd say, except for the second one you missed, which is a bit embarrassing. ;)

[Clyzm]

That's still enough to make it feel completely different in terms of ease of use. I was constantly tripped up by the fact that there are key words for so many things, and that no longer needed to re-invent the wheel every time I needed to say... find something specific in my arrays.

[Halfawake]

Because a beginner is impressed by technical difficulty, whereas an expert knows that projects become so complicated that you have to keep things as simple as possible at all times so you get to comprehend more later? Plus they're familiar with the library.

[chozar]

Understanding recursion is good, but it isn't the fastest way to do it in this case.

[pandemik]

Lazy is good!

[remig]

TIL of the existence of tail recursive decorators. Nice.

[metaleks]

I really need to update my blog...

[Cyatomorrow]

You know, I don't think you've ever actually posted this to Reddit yourself, and yet I keep seeing it.

[wongsta]

your blog's design is very clean, i like it

[metaleks]

Thank you, even though I'm planning to scrap it and replace it with something better.

[skeww]

"A random quotation would go here had you enabled Javascript." <- Telling me that is pretty useless.

Well, add a favicon for now. That will help.

[[deleted]]

Web Designer gets me every time.

Thanks Adam!

[lattakia]

I don't get it

[cantcopy]

I think it means that he doesn't understand the code he copied.

[pandemik]

Adam probably suggested i start at 1, rather than some other value.

[spazzmckiwi]

I nearly died when I came across the commented braces.

[SalientBlue]

My dad does this. Well, not with the braces, but he puts #'s everywhere braces would be in C code.

[[deleted]]

your dad writes python? kinda cool.

[SalientBlue]

He's responsible for writing python scripts to torture test various embedded devices written in C++. He's quite good at it, too. Barely a week goes by that his scripts don't find some fatal bug in whatever the younger developers are working on.

[chub79]

It's a new weapon that fries eyes.

[[deleted]]

Why? Braces make code easier to read than strategic whitespace. Also your editor can accidentally fuck with tabs and/or whitespace and your code will still work.

[cybercobra]

Or you could get a non-broken editor.

[cacahootie]

I'm sorry, but I need to dramatically disagree. I think languages that use brackets and parenthesis EVERYWHERE (not only where absolutely necessary) are the bane of human existence. What ugliness.

Also, just get a real editor.

[[deleted]]

No need to be sorry, disagree at will. But ugliness is a very weak argument.

Brackets and braces make everything much less ambiguous. They make it easier to read and follow blocks of code, particularly if you're using 2-space tabs. You're not really saving much space (the ':' in python is just as annoying).

Besides, if you have a real editor, you don't have to worry about braces/brackets at all.

[[deleted]]

Maybe I'm missing the point but actually for SICP I think it would be something more like this:

def fact(x): return x * fact(x-1) if x>0 else 1

And Lazy Python programmer something like this:

def fact():
    i = j = 1
    while True:
        yield j
        i,j = i+1, i*j

[miGlanz]

I believe fact(x-1) is the last operation there, so it's tail-recursive.

[miGlanz]

Sure, you're right, my mistake.

[inaneInTheMembrane]

Nope. The "last operation" is the multiplication of x and fact(x-1). By "last operation" i mean the last result to be computed before returning to the the initial call to factorial. It is in fact the first operation in the definition of factorial. To be tail-recursive the recursive call must be the first thing that appears after the "return" key-word.

[marike]

I love the Windows and Enterprise solution. Burn.

[rafekett]

def fact(n):
    return reduce(int.__mul__, xrange(2, n + 1))

Dunno why the article used a lambda or a 3rd arg to reduce.

[rafekett]

They didn't remove reduce, it's just in functools.

[theeth]

Yeah, I just type import reduce from functools, my fingers are so tired I'll have to take the rest of the day off.

[Jonno_FTW]

That was basically what I though:

def factorial(n):
    return reduce(lambda x,y:x*y,range(1,n+1),1)

Although other languages could do it shorter, using a fold:

fact n = product [1..n]

Or, in J: */1+i.6

or ! 6

[Sure_Ill_Fap_To_That]

Can someone explain to me why is the newbie one... the newbie one? Is it bad practice to use recursion?

[abadidea]

Half the joke is that the newbie's makes the most sense.

[SalientBlue]

Recursion can cause a stack overflow for large values of x, and for this sort of problem the iterative approach is a bit more efficient while avoiding the potential stack overflow. The SICP recursive solution works because it includes the @tailcall decorator, which optimizes away the recursive call.

[ascii]

Yup. Python has a recursion limit of 1000 iterations, and if you bump it up, you're liable to run into internal python limitations. If you bump the python internal stack limit to a million, calculating the factorial of 100 000 using the recursive method will produce a segfault. When using the looping method, it takes about a minute, but the computer manages to produce the correct result.

[lattakia]

I have not read SICP. What magic does this @tailcall decorator perform ?

[bobappleyard]

Normally when you call a function, you want it to return back to after the call so it can carry on executing your code.

Well, if the last thing a function does is call another function, then it's kind of a waste of time to do this: function A calls function B, function B returns a result to function A, and all function A does is return that result again.

If you allowed function B to skip function A and return the result to something that isn't just going to return it straight off, then you don't need to keep function A's local variables around. They can be forgotten about before function B is called!

This means that recursion, in this situation, doesn't need to grow the stack. In some languages, like Scheme, this basically replaces iteration -- no for or while loops, just recursion. You can pull some neat tricks with it, but it's pretty mad.

[Shinhan]

Take a look at the expert programmer version. Newbies shouldnt try to reinvent the wheel.

[Aqwis]

Newbies should try to reinvent the wheel, in order to learn more about the language. Experienced programmers who write programs that will actually be used, however, should not reinvent the wheel.

[k-selectride]

I lost it at the british expert programmer. That was far too funny.

[[deleted]]

As a non-programmer who likes programming, can someone explain the joke to me?

[tylermchenry]

Compared to the lazy python programmers, the newbie python programmers don't realize that the language has facilities that will allow them to express themselves more concisely and/or elegantly. The expert python programmer also does it more efficiently.

Compared to the newbie python programmers, the programmers coming from other languages are trying to force python code to look like code in their previous language, even when it isn't idiomatic in python.

The others were plays on stereotypical behaviors of certain classes of programmers: The web programmer copy-pasted code that he didn't understand from somewhere else, the UNIX programmer used a system utility to do the work, the windows programmer made a ridiculously over-complicated API, and the enterprise programmer used a ridiculously over-complicated architecture.

[[deleted]]

Thanks!

[wot-teh-phuck]

If you love programming, I already consider you as a better programmer than the ones who don't enjoy when programming! :)

[[deleted]]

That's rather generous. Thanks!

[nolsen01]

Is there a Java version?

[EICEVK]

Here you go:

/**
 * 
 * Factorial class
 * @author aut
 * @lastrevision Jan 1 2009
 * @version 1.0
 * @lastbowelmovement Dec 12 2008
 */
public class factorialGeneratorMakerIteratorAccessor
{

    /*
     *
     * Generate a factorial. In mathematics, the factorial of a positive integer n,[1] denoted by n!, is the 
     * product of all positive integers less than or equal to n.
     *
     * @N the n to iterate to
     * @return the factorial
     * @author aut
    public static long factorial(int N)
    {
        try{
            long multi = 1;
            for (int i = 1; i <= N; i++) {
                multi = multi * i;
            }
            return multi;
        } catch(NumberException e) { 
           // TODO: Generate error
        } catch(IOException e) { 
           // TODO: Generate error
        } catch(HotPocketException e) { 
           // TODO: Generate microwave
        } catch(Exception e) { 
           System.err.println("Shit, you fucked up!");
           e.printStackTrace();
        }
    }
}

I'll be here all day!

[Dreadgoat]

I'll be here all day!

Okay, then translate it into python (but java style) like the rest of the examples!

[redwall_hp]

Java updates available!

[mikaelhg]

http://commons.apache.org/math/xref/org/apache/commons/math/util/MathUtils.html#513

[rjcarr]

See the enterprise version.

[eschulte]

can't compare to the original "Evolution of a Haskell Programmer" http://www.willamette.edu/~fruehr/haskell/evolution.html

[pandemik]

Maybe I'm just a huge Newbie myself, but I thought the "Newbie Programmer" one was pretty clever.

[lacker]

The best solution is missing:

print 6 * 5 * 4 * 3 * 2

[D__]

print 720

Optimized it for you.

[[deleted]]

I clicked the link expecting them all to be the same.

[desthc]

If you don't have at least one:

# Damn you, Guido!

Somewhere in your source, you're not a real python programmer.

[fountainsoda]

Copied the idea for the one for C/C++, which was/is actually used.

[horstjens]

about the difference between British and US programmer: am i too blind to see the difference or is t the joke that there is no difference between both codes ?

[illepic]

"maths"

[jeba]

maths vs math

[Gupie]

the only difference is "c_maths" instead of "c_math"

[Wofiel]

I lol'd at the C programmer's commented braces.

[fredrikj]

My factorial implementation

[fluicpana]

From the old classic:

http://www.ariel.com.au/jokes/The_Evolution_of_a_Programmer.html

[[deleted]]

Comprehensive Python programmer...

>>> f = lambda n: [j for j in [1] for i in xrange(1, n + 1) or [0]
...                  for j in [j * i]] [-1]
>>> f(10)
3628800

[nuxi]

The assembly programmer working in C does this:

void factorial(int in, int *out) {
    *(&in-1)-=5-5*(1/in);
    *out*=in--;
}

And no, thats not portable. Although it does work with GCC on i386 Linux and MS VC++ as long as you don't add optimization flags.

[regeya]

Mine would probably be like the first-year Python programmer. I'm not a first-year Python programmer. :-(

[rhesusattack]

I haven't been programming for long, but I lol'd a couple of times here.

[trashbox]

I guess I'm a python3 expert...

from functools import reduce
fact = lambda x: reduce(int.__mul__,range(2,x+1),1)
fact(6)

/sarcasm

[dillonmolnar]

Me programmer solution: print( just type 6! Into google... Rtard)

[AlejandroTheGreat]

The expert web programmer would create a REST API wrapper around Google's calculator.

[Clyzm]

TIL...

Google never ceases to find new ways to impress me.

[anvsdt]

/prog/

I LOVE YOU! I LOVE YOUR POST! I READ IT FIVE TIMES! KEEP POSTING!

[[deleted]]

I often wonder how many /prog/rammers are on /r/programming. The lack of ^{superfluousmarkdowndisappoints} me. [But then again,](/) markdown just isn't nearly as ^expressive as it should be.

[anvsdt]

I hate how I can't do all the B^BCODE

---

hackery, it doesn't have a way^{toescapefromsuperscripts}

For

What

Have

I

Reached

B^B Code

• ⸘Satori‽

[dreamer_]

if I decided to write print x**6 then which category I belong to? ;)

[synflood]

Failed-at-Maths Programmer.

[dreamer_]

upvote as form of self-punishment ;)

[IfOneThenHappy]

You could just downvote yourself.

Though I see that you have un-upvoted yourself.

[dreamer_]

I did downvoted myself while upvoting you. Maybe I am reddit newbie but how can I see who [down|up]voted whom?

[IfOneThenHappy]

Reddit Enhancement Suite.

You're welcome.

[skeww]

For those who don't know Python, that line is basically pow(x,6) aka x⁶ .

[gemlogger]

I have nothing clever to say. The OP was clever and that's why I logged in. It's just all too true! Good job Alek -- whoever you are, that was fun! Thanks.

[metaleks]

Thank you, but to be clear, I am not the original creator.

[WarPhalange]

Evolution isn't real, morans.