tsahyt

Writing a toy ray tracer is something that I'd recommend to everyone who's interesting in becoming a better programmer. Once you get deep enough into it you'll encounter so many interesting problems (e.g. data structures, software architecture, some linear algebra, etc.) to hone your skills on. It's almost up there with "write your own compiler" as a learning experience in my opinion and you get the added benefit of creating some pretty pictures in the process.

I do. I've got the server counterpart set up on a Linode and sync my task lists across all devices. That's quite nifty because I usually think of things that I should be doing while I'm on the go. At the moment I need this kind of organization to get anything done, and out of all the solutions I've tried this one is by far the best. The feature I use the most is probably the scheduling feature. After dinner I'll sit down for a moment and contemplate which of the tasks I've still got open I will do the next day and schedule them accordingly. The next morning I do a `scheduled:today` query and I've basically got half the day laid out in front of me already. The best part of it though is that by running my own task server (at no additional cost because the same box doubles as my mail server), all the data belongs to me instead of relying on a third party.

I came across this yesterday. Not necessarily just exploiting a Windows security hole though.

http://media.ccc.de/browse/congress/2013/30C3_-_5476_-_en_-_...

The beauty about Linux (and a lot of well-maintained open source software) is that security flaws are usually patched rather quickly -- with the possible exception of the disaster that is X, but Wayland is coming along nicely.

Same here, although I somehow wanted it to win, so I could finally at least see the mythical 2048 tile that everyone seems to be speaking of.

I'm running dwb, version 2013.08.03 (either the maintainer for Fedora is slightly lazy or there hasn't been a new version in a while) on Fedora 20. It reports Safari 538 and OSX as the operating system. I've also got cookies disabled and it reports that I have them enabled, which is strange.

Many NP-hard or NP-complete problems have (infinitely many) instances that are "easy" to solve. It is quite straight forward to write up a procedure that produces infinitely many instances of 3-SAT that can be solved in polynomial time by the DPLL algorithm. But it is important to note that a problem is actually a set of instances.

Your observation basically boils down to "how rare is the worst case?". There are actually algorithms with exponential worst case complexity that are used all over the place because - on average - they perform really well. The simplex algorithm for linear programming is an example for such. Every version of this algorithm comes with a worst case problem such that the algorithm has exponential runtime. However, on average it is quite a fast algorithm that can handle millions of variables and corresponding constraints on modern hardware. Still, that doesn't change the fact that linear programming is - from a theoretical point of view - still hard enough that we cannot generally solve it faster than in exponential time. As is the case with DPLL, good heuristics can speed up an algorithm a lot without changing worst case complexity. Other examples are all over the place in AI. It's also in AI where the concept of pruning is probably encountered most often. This the practice of discarding whole subtrees of the search tree by some sort of heuristic or deductive reasoning.

Those things aside, I think what we should be looking at from a theoretical point of view is when it makes sense to consider the average case complexity over the worst case complexity. This brings us back to "how rare is the worst case". Quicksort for instance is said to be an O(n log n) algorithm but it has O(n^2 ) worst case complexity (trivially so). However, it can be decided in O(n) whether this case actually occurs and hence a good sorting implementation could switch to a different algorithm once this has been detected (something similar happens in the std::sort function that's been implemented in the STL). This is definitely a case where it makes sense to "forget" worst case complexity.

For SAT, researchers have actually worked up statistics on how hard certain instances are in terms of the number of clauses and the number of symbols. It turns out that there is a range of ratio between the two where problems are the hardest (roughly between clauses/symbols is between 4 and 6). I don't have a source right now but googling "satisfiability threshold conjecture" might turn up some results.

As such, yes, not all instances of NP-hard problems are actually hard to solve, but there are infinitely many that are. Encountering such problems in practice one can usually make use of the special problems of the instance (or class of instances) one actually encounters and devise an algorithm that performs rather well on average.

This might come across as quite harsh but the article could have been much shorter.

NP is the class of decision problems that can be solved by a non-deterministic Turing machine in polynomial time. A problem is called NP-hard when there is a polynomial-time reduction of 3-SAT to said problem. A problem is called NP-complete if it is both NP-hard and in NP. Since TSP is not a decision problem, it is not in NP, therefore it cannot be NP-complete. However, it is NP-hard.

One can call this a minor nitpick. I still point it out every now and then when I hear people talking about such things. However, the really important thing is that we haven't found a way to solve NP-hard (and hence of course NP-complete) problems efficiently on a deterministic Turing machine (and hence computers as we can actually build them). An informal way of saying the same thing is "TSP is really really hard to solve".

Either way, I'm always surprised at how many problems we encounter in our every day lives are actually NP-hard. Every decent puzzle game for instance is usually NP-hard. Goes to show that we don't really enjoy solving easy problems.

EDIT: Of course there's also a decision version of TSP, as others have pointed out. This one is NP-complete of course.

I thought the hash was in fact used for ensuring data integrity. That's pretty much what Linus stated when he said you have a guarantee that the data you put into your repository is exactly the data you get out of it.

I'm no expert but as far as I understand, the signature would be valid as long as the hash stays the same. If the commit has been tampered with in such a way that the hash does not change, the signature would still appear valid.

I'd be interested in learning Rust. I've been learning Haskell last year and I'm absolutely loving it.

But, wasn't the drama exactly the point of the article?

No specific examples, but all of my best optimizations as in biggest-speedup were of algorithmic nature that actually improved asymptotic complexity.

In terms of my favorite ones, it's probably a piece of C code using SSE intrinsics to speed up intersection checking for a voxel raytracer I've been playing with last summer. After about 1.5 days of hacking I've managed to shave about 50% off the rendering time per frame. Nice learning experience but completely pointless in the end. Since it was still way too slow for any practical use, I started rewriting it and eventually stopped halfway through.

There's a lot going on and that's the way it has been for quite a while now but as someone who's working with databases only marginally at the moment, I'm left wondering: What's wrong with RDBMS? Sure it's nice to have a simple Key-Value Store for applications that don't need much more than this but bottom line, the relational model is very powerful, albeit quite abstract, and most data we need to deal with can be made to fit into this model. We have a working, declarative query language that Just Works(TM), for which we have written very good optimizers. The various instances of such DMBS range from small-scale use (for example, SQLite) to really-huge (Postgres, Oracle, etc). So, to sum it up: Exactly why should we abandon this?

I used to strive for clever solutions. The shorter the better. I still like to look at them but I want them as far away as possible from my code base. Sure, if a solution is clever and efficient, while still readable, maintainable and easy to understand when documented properly, I'd use it. However, my general rule of thumb these days is: "Write this code, so an utter idiot can read it". Because that's what's going to happen: One day I'll have to read it again, and I'll feel like an idiot, trying to understand what once went through my brain.

That's something that took me way too long to learn and I feel that novice programmers should embrace that more. We all like to feel like Einstein sometimes, but a big code base is not the place for solutions only we can understand... temporarily.

That's really all there is to it, isn't it? I've never understood why some people feel the urge to modify the same variable multiple times in the same statement. It doesn't help readability, it's harder to reason about and worst of all leads you directly into the land of undefined behavior, where everything that can go wrong, will go wrong.

I know what you mean but it's early in the morning here and I feel like being a bit pedantic: As far as we can tell neither of the algorithms actually terminates for arbitrary inputs. If we could show that, we'd have proven the Collatz conjecture. Therefore the notion of asymptotic performance doesn't make a lot of sense, since we want to give an upper bound on how long the algorithms takes to terminate. However, if we found such an upper bound, it would be equivalent to solving the problem itself, because the runtime depends on how long a given sequence is, and putting it into a closed form. At that point we'd trivially have an O(1) algorithm.

What we can do, is measure complexity empirically and extrapolate something from there. I haven't done a lot of tests with this code but to me it seemed like it would scale the same as the original one but had a much lower constant.

chas explained it very well already, I'd just like to add that this is called a "lambda function" (or lambda expression) or an anonymous function, just in case you want to look it up. There's more on it here: http://www.haskell.org/haskellwiki/Anonymous_function

I've already posted this on /r/haskell on reddit but since the article turned up here as well, I might just as well post this again. Since we're talking optimization I had a short look at the C code and found it to be a very naive implementation and have managed to cut the execution time quite a bit by employing a sort of memoization. Once you get to a number of the sequence which you have already seen before, the length from there to 1 remains the same as before.

So here is the code: http://lpaste.net/96397

Here are my measurements:

    time ./original 1000000
    (329, 837799)

    real   0m0.183s
    user   0m0.180s
    sys    0m0.001s

    time ./new 1000000
    (329, 837799)
    
    real   0m0.017s
    user   0m0.015s
    sys    0m0.001s

not a problem of the paradigm

Correct. The main problem I see with OOP is that some people advocate it as the only correct way to write maintainable code, which, of course is completely wrong. In fact, OOP doesn't translate well to some problems. There are also problems where FP doesn't work as nicely as other paradigms. In short, there is no silver bullet and advocates of any paradigm should be more open about that.

I keep in touch with mine just fine without Facebook. I use my phone every now and then for actual phone calls and sometimes even meet them. In short, I do what people have been doing years before Facebook and I don't feel like I'm missing out on anything. But then again, what works for me doesn't have to work for everyone.

You can also add this line to .inputrc which will give you vim keybindings in everything that uses the readline library (for instance, ghci, ipython or gdb). However, I found that it breaks a few things in gdb though.

In fact I think everybody who's interested in the subject should try to roll their own crypto for the experience and fun in it. They shouldn't use it in the real world though.

Or the original Halo on the first Xbox. If I remember correctly that game alone promoted the console for a lot of customers. Valve could give HL3 a head start of a couple of months on SteamOS and release it on other platforms after that. It would be less annoying that being fully exclusive. Besides, all the PC gamers could just go and dual boot SteamOS on they PC. It's free after all.

I haven't bought a Steam game either. In fact, I don't even have an account. For the past couple of years I've been locked into the MS ecosystem with the Xbox 360. I will not buy the Xbox One though. I don't need a surveillance machine in my living room. I was never a fan of the PlayStation. For a while it looked like I had to build a PC and have it run the system I dislike the most, just for the sake of gaming.

Seriously, I'd buy (or build) a SteamMachine in a heartbeat. It's the most sensible option for me at this time.

I'd be open to something new if it serves the purpose but I wouldn't mind getting a mouse and keyboard in my living room if that happens to be the best way to play a game. But that's probably just me.

Is there any reason for switching to LLVM/CLANG from GCC other than the licensing?

Artists can't take care of themselves without the dollars though.

I was thinking the same thing and was wondering how exactly that would look like as the page loaded. In a way I was disappointed. It's still a pretty cool feature though.

When I set up my first server I was thoroughly surprised at the amount of login attempts. By now I've got most of Asia on a blacklist for port 22 (which doesn't matter, since I'm not going to connect to my server from an Asian IP in the foreseeable future). That throttled it down to about 30 attempts/week, which is manageable in terms of log reading.