[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [ProgSoc] Programming! Code!
On Thu, 2006-10-19 at 14:28 +1000, John Elliot wrote:
> This is the function signature:
>
> Int32 fn( Int32 )
>
> Knowing nothing more about the 'semantics' of the function beyond this
> signature we know that there are 2 ^ 32 possible inputs each mapped to
> any one of 2^32 + 1 possible outputs (the '+1' being 'exception', lets
> assume only one 'exception type').
>
> So... that is 2^32 * (2^32+1) possible functions. Right?
Not even close.
Consider the truth table:
- It has 2^32 rows, that being the number of possible input values.
- It has 32 columns, that being the number of bits in the possible
output value. (I'm disregarding the +1 for the moment as it is
immaterial and complicates the algebra. Putting the +1 back is left as
an exercise for the reader.)
- So, it is a rectangle with 2^32 * 32 = 2^37 positions on it.
- The number of possible truth tables (implementations) is 2^(number of
positions in the truth table) = 2^(2^37) which is somewhere around
googol^6.
- Raz
-
You are subscribed to the progsoc mailing list. To unsubscribe, send a
message containing "unsubscribe" to progsoc-request@xxxxxxxxxxxxxxxxxxx
If you are having trouble, ask owner-progsoc@xxxxxxxxxxxxxxxxxx for help.