to infinity and beyond
I’m doing something really stupid now. This shouldn’t completely surprise the regular readers of the blog, but this time, I feel I may well have outdone myself.
I am attempting to run a (non-trivial) pairwise computation on 138354 words. Essentially, each word will have a possible (138354 - 1) calculations … That’s, if my math mojo works, factorial 138354 calculations. The only online calculator I could find, Javascript based, was here. That gives up on the number and says “infinity”. Not altogether unsurprising; but then, the Javascript calculator also gives up on the measly number 2000 and says “infinity”. Hmph.
I have three machines (well, 4 - but I want my laptop to be free) to devote to this task. I’ve partitioned the search space out so that I can farm it out in blocks. Right now, I’ve been running the experiment for about half an hour and I’ve processed 400+ pairs. On a single machine, mind you. But at this pace, the heat death of the universe may happen sooner than my calculation - clearly not a good thing if I hope to graduate in this century.
Well, brute force calculations are always the fallback. I’ve now bought myself at least a week where I can dodge requests to write errant pieces of Powerpoint and reports. (“ooh, I’d love to, but my machines are busy, you see” in a tone of pseudo-sincere regret should do nicely, I think). I’m actually trying to calculate the maximum distance between nodes in a large (really large) tree. Now to actually do something (hopefully) clever like a tree walk. Onwards and upwards.
Update (3 hours later): Well, 92k lines processed (from 138k). This is just the first pass. Since this calculation I need to perform is quite dependent on external factors, the number of valid calculations is also very small: currently only 155 valid results from 92k. Incidentally, Google functions as a calculator. Although I haven’t figured out if it does factorial (I suspect not), an approximation of the number of calculations to be performed is the square of 138354. Which is only about 19 billion or so. Hey, that doesn’t sound like a lot, does it ?
On 03-Oct-05 at 6:57 pm,
Splee wrote:
That sounds like a hell of a lot of calculations. Is there no way you can approximate or build an algorithm that can get the answers without doing every single calculation? I know you must have thought about it, but I thought I’d point out the blinkin obvious
On 03-Oct-05 at 7:34 pm,
drac wrote:
Oh, yes.. I think there is a way to approximate things… but the brute force method was pretty much half an hours work to write - so I started down that route just in case my approximations failed.
And the incidental benefit is that I get to (sorta) dodge all sorts of other administrivia while the numbers are being crunched - that’s possibly worth more than the test data I’m accumulating with the brute force method. Even if I don’t do the entire set, I can apply some handwavy statistics (confidence metrics) and infer an answer.
And I’m quite enthralled with the idea of doing such a large number crunch, to be honest. My bit towards global warming
On 05-Oct-05 at 2:06 pm,
The Lair » easy words for hard ideas wrote:
[...] to infinity and beyond | Home [...]