Rosio Pavoris a blog

Presented without comment

February 23rd, 2009 at 12:47 am in Miscellany

Leisure Suit Larry Wall

Permalink 2 Comments

Here’s a math problem for you

February 20th, 2009 at 7:58 pm in Mathematics

\frac{64^8!}{64^{8n}(64^8-n)!}=\frac{1}{2}

Solve for n.

Edit: This is basically the reverse birthday problem, with the fixed probability being 50%. Just applying that approximating formula is a bit easier than working out the problem above:

n(p)\approx\sqrt{2\times 64^8\times \ln\left(2\right)}\approx 19753662

Which is much lower than I expected and also crap. It means that the algorithm I’m using for my work-in-progress distributable tripcode searcher is broken. There are some obvious ways to fix it, but finding a way that’s both good and not likely to slow things down too much1 (though obviously the bottleneck is still going to be crypt itself) requires some thought.

1 Right now it’s running at about 330,000 tripcodes per second on my laptop, which is over four times the speed of tripper+ and over sixteen times the speed of my Haskell tripcode implementation, so I guess some slow-down wouldn’t kill it.
Though Asztal claimed 4 million tripcodes per second with Tripcode Explorer on his machine, so I suppose there’s still room for improvement, too.

Permalink 6 Comments