Re: Already answered
"More than half a billion?"
Yep. Easily, even if it were technically possible.
Let's accept their estimate of 80% usage. That means that whatever range you replace it with is effectively a class A range. This network connects a lot of networks that require access to the Internet, so whatever range you use must be in RFC1918. SO, the easiest option is to use 10.x.x.x.
OK, that's the easy bit out of the way, to enable communications across this network, it is your task to organise and re-number the internal networks of every government department, every local council, school, police authority, fire service etc. etc. so that they do not use any 10.x.x.x address internally (to ensure that they can reach any and all services on the network) and then go round and do the same for all the private companies that have a need for direct communications with any aspect of government.
If you can do that for less than half a billion and within a time-scale so that the whole exercise isn't pointless I'll buy you that pint to the left!