# Code Kata 3: My Solution

4 February 2008

Kata 3 has to do with estimation. The full questions are on Dave’s blog.

How Big?

*Roughly how many binary digits (bit) are required for the unsigned representation of:*- 1,000 :
**10** - 1,000,000 :
**14** - 1,000,000,000 :
**18** - 1,000,000,000,000 :
**22** - 8,000,000,000,000 :
**25**

- 1,000 :
*My town has approximately 20,000 residences….**Let’s allow 100 characters for a name, 150 for an address, and 15 characters for a phone number. 165 * 20000 = 310000 characters**I’m storing 1,000,000 integers in a binary tree….***I don’t know much about binary trees, but I would expect it to have ln 1,000,000 levels. Based on my answer above, that’d be about 14, yielding 2^14 nodes. As for space, each number could be stored in 14 bytes, which would be 14 MB for a million numbers.**

How Fast?

*My copy of Meyer’s Object Oriented Software Construction…***I’m going to guess about 120,000 words. Let’s say the average word in a technical text is 5 characters long, so that’s 600,000 letters. With formatting, I’d budget 900kb for plain text. This jives with my recollections of Project Gutenburg novels.***My binary search algorithm…***It should go exponentially, so a hundredfold increase in entries caused a 1.5ms increase. The next one is another hundredfold, so that would be 1.5ms x 1.5 ms, or 2.25mS. So, I say 7.75ms.***Unix passwords are stored using a one-way hash function…***Well, that would be 96! / (96 – 16)!, which is 96 * 95 * … * 80, or about 88^16, or about 7700^8, or about 670000^4, or about 44×10^8 ^2, or about 176×10^16 ms. There’s 1.5×10^9 seconds per year, so it would take millions of years to crack the algorithm. My answer is no. 🙂**

See also my previous Kata posts: Kata 1, Kata 2

Advertisements

No comments yet