Counting

[DrJones]

Is anyone else here really interested in counting?

Not in the sense of counting on your fingers or anything, but the area of study in mathematics. Most people get a little introduction to the subject when the take a probability/statistics course. All that combinations and permutations stuff. It's really interesting stuff. Kind of helps you learn the definition of 'large.' It also kind of overlaps with some stuff, like little (or countable) vs big (or uncountable) infinity (really interesting stuff here, I can explain it if someone wants).

Here's a fun example.... which is larger, the number of atoms in the universe, or the number of unique images that could be represented on the computer monitor you are looking at right now.

[SlamMan]

Elaborate.

[DrJones]

Just to show some other fun uses. It also has applications in cryptography.

Most of you have probably download a file at some point and seen something listed with it that looks like this:

329238cd7c83e0251acaedf3cf4234f3

and it says something about an md5. Well, md5 is a type of hash that is able to take an arbitrary number of binary digits, and computes a 128 bit fingerprint. This means that you basically can get a unique md5 for every file or password you want.

Note: md5 makes a 128 bit binary fingerprint. What is shown is not binary, it's hexidecimal. The binary representation would look like this:

00110010100100100011100011001101011111001000001111 10000000100101000110101100101011101101111100111100 1111010000100011010011110011

but obviously that would be kind of hard to check, so they put it all in hex. Each 4 bytes=1 hex digit. it's pretty simple, take those 4 bytes and see what they are in binary, 0001=1, 0010=2, 00011=3, and so on. Hex works by having all the normal digits 0-9 as themselves, then 11-15 (1111=8+4+2+1=15) are A-F. So you can see from that example 0011=3.

So anyway, you can DL a file from the internet, and get the md5 for it, md5 will always give the same 'answer' for that file, regardless of when or where it is done.

So the interesting part of all this, and the part where counting kind of comes into play, is that any file or password (common uses of md5) can be "hashed" into a 32 digit hexidecimal string. Those strings are pretty much unique. Obviously they aren't really, because lots of files out there are bigger than 128 bits (like almost all of them). This means that there has to be 'collisions' where two files will hash into the exact same MD5 value. You simply can't represent all files bigger than 128 bits, with just 128 bits, if you think about it with 128 bits you can have 2^128 unique numbers, if you took all of those as individual files, then assigned a number to them in order "ie counted them" you would use them all. When you got to files with 129 bits, you would start overlaping.

Ok so obviously there is some overlap, theoritically. The interesting thing though (to me) is that it's pretty much (for all intents and purposes) impossible to find two series of digits that will overlap. I have over 1 million files on my computer, and none of them would overlap. If you set up your computer to just generate random files all day, and compute the md5 hashes of those files, then see if it already had that one, It could literally take thousands of years before you found one. Isn't that crazy?

It really is a cool system....

Just to kind of reinforce the concepts. If anyone can tell me what file that md5 above represents, I'll give free details to you and 10 of your closest friends. (Don't bother using google, it's not listed :D)

[DrJones]

Elaborate.

are you talking about the atoms/monitor problem?

If so... your screen has pixels, each pixel can represent a color, different combinations of pixels and colors will give different images. The screen is made up of atoms, LOTS of them (if you've had chemistry and learned about Moles this should make sense). ie a mole is 6.022 x 10^23, and a mole is like a counting unit. It's not a unit like a foot or a galon, but more just like an ammount, you can have a mole of anything. A mole of water molecules is 18 grams of water (at sea level under standard conditions). So 18 grams of water (not very much) has 6.022 x 10^23 h20 molecules in it.

To put this into some perspective: Scientists have dated the Earth as approximately 4.5 x 10^9 years old. This is about 1.4 x 10^17 seconds. So the Earth is not even one mole seconds old. (more info http://www.maths.mq.edu.au/numeracy/tutorial/mole.htm)

from http://www.lcusd.net/lchs/mewoldsen/BC-Mole-alot.htm:
-If there were a mole of rice grains, all the land area in the whole world would be covered with rice to a depth of about 75 meters.
One mole of rice grains is more grains than all the grain that has been grown since the beginning of time.
-One mole of rice would occupy a cube about 120 miles on an edge!
-Computers can count at the rate of over 800 million counts per second. At this rate it would take a computer over 25 million years to count to 6.02 x 1023.
-A mole of marshmallows would cover the United States to a depth of 600 miles
-In order to put a mole of rain drops in a 30 meter (about 100 feet) diameter tank, the sides of the tank would have to be 280 times the distance from the Earth to the Sun.
-A mole of hockey pucks would be equal to the mass of the Moon.
Assuming that each human being has 60 trillion body cells (6.0 x 1013) and the Earth's population is 6 billion (6 x 109), the total number of living human body cells on the Earth at the present time is 3.6 x 1023or a little over half of a mole.
-If one mole of pennies were divided up among the Earth's population, each person would receive 1 x 1014 pennies. Personal spending at the rate of one million dollars a day would use up each persons wealth in about three thousand years. Life would not be comfortable because the surfaceof the Earth would be covered in copper coins to a depth of at least 400 meters.
-If you had a mole of pennies and wanted to buy kite string at the rate of a million dollars per inch, you would get your money's worth. After stretching your string around the Earth one million times, and to the Moon and back twenty-five times, you would have enough string left over to sell back at a penny an inch (a decided loss) to gain enough money to buy enery man, woman and child in the US a $5000 automobile and enough gasoline to run it at 55 mph for a year. After those purchases, you would still have enough money left over to give every man, woman, and child in the whole world $6136.

So obviously there are a TON of molecules in your computer monitor, then think of how many there are in all of the computer monitors in the world, then all of the world, then compare the size of the earth to the size of the sun, how many atoms must be in the sun... then think about all of the solar systesm and galaxies in the universe, and how many atoms that might be.

then compare it to the number of images you can see on your computer screen (which is made up of atoms)

[djet820]

Oh wow....

I like math but I don't htink I can get into stufff that deep.

[DrJones]

Oh wow....

I like math but I don't htink I can get into stufff that deep.


Sure you can. If you really like math then you should even enjoy it.

Doesn't anyone want to take a guess on the monitor vs atoms problem?

[SpeedStar91]

Universe-how do you count unknown amount of space?

[DrJones]

Universe-how do you count unknown amount of space?

Well it's not really counting the 'space' but more counting the number of atoms. Yes, you can't actually count them all, but you can make some approximations. The number of atoms they have in the universe has been calculated several different ways, while they don't all agree 100% with eachother, they are very close to oneanother.

if your really interested....


First of all, by "the universe" I'll assume we're talking
about the _observable_ universe, which is necessarily much smaller than the entire physical volume of space (which for all we know could be infinite). The size of the observable universe is basically spherical, with radius about equal to the "Hubble radius", d_H = c/H_0 ~ 4e9 pc = 1e28 cm ~ ct_0 (where 0 denotes present values). In fact, when you allow
for the expansion of the universe, the better value is more like 2d_H. I hesitate to bother you with such factors, but we are after all going to cube this. Anyway, the volume of
the observable universe is just that of a sphere with r=2d_H, or about 3e85 cm^3. The microwave background photons have T=2.728 K, and Planck tells you that this gives n_gamma = 411 photons/cm^3, so there are about 1e88 photons in the observable universe (not far from a googol in some sense, though 12 orders of magnitude is not negligible, even for astrophysics).

There are comparable numbers of each neutrino species.
Finally, big bang nuke (that's me) sez that the baryon to photon ratio in the universe is about n_b/n_gamma = 3e-10 (i.e., the photons and nu's outnumber [but not outweigh]
the measley baryons by a hefty factor) so the baryon number of the universe is about 3e78. So this is 21.5 or so orders of magnitdue off from a googol, but in some sense it's not so far off.

I'm sparing you worries over the dependence on various cosmological parameters; this just gives the basic ballpark figure.

As for the mass of the (observable) universe, this again needs some clarification, it turns out. If we are interested in just the (nonrelativistic) _matter_ (including dark matter), then it looks like Omega_matter = rho_matter/rho_crit ~ 0.3, so that M_matter = 0.3 M_crit = 3e21 M_sum = 6e51 kg. On the other hand, since the microwave background now gives strong evidence that Omega_tot = 1, then it looks like there is another component
to the universe, the "dark energy" (or cosmological
constant). If we include this too, then we don't need the factor of 0.3, and we get more like 2e52 kg.


(from http://van.hep.uiuc.edu/van/qa/section/Stuff_about_Space/The_Rest_of_the_Universe/982241844.htm)

Or if you interested in a totally different way of calculating it, but still gives generally the same answer, look at http://pages.prodigy.net/jhonig/bignum/qauniver.html

[David]

but only about 20% of the matter in the universe is made out of atoms. Rest is dark energy and dark matter;)

[DrJones]

but only about 20% of the matter in the universe is made out of atoms. Rest is dark energy and dark matter;)

Maybe so, but it's much harder to count that stuff.... there are a lot of atoms though....

On another board it only took about 20 mins for someone to post the answer. I know someone here knows how to do it. We already have the number of atoms in the universe, just need how many unique images can be displayed on a computer monitor. It's a fairly simple calculation.

[john]

No. Too hard on my mushy brain. :)

[David]

what is your definition of a unique image? technically you would need an infiniate ammount of pixles to make a true "unique" image

[DrJones]

Here I'll get you started. You probably learned this at some point so it should seem familiar.

We have 2 dice (6 sided and independant of one another). If we roll them both at the same time, how many different ways can they come up togeather (order matters, having a 1 on the first dice and a 2 on the second, is not the same as having a 2 on the first and one on the second).

the first dice can be a 1,2,3,4,5,6 the second can be a 1,2,3,4,5,6. If we look at all the combinations of taking a number from the first one, with a number from the second one, ie 1st is a 1, 2nd is a 1,2,3,4,5 or 6, then do the same with 2,3,4,5,6 on the 1st one. and you get 6*6 or 36 possible combinations.

Do the same thing, but this time we have 3 coins (2 sided, independant). if H is heads and T is tails, all the possible combinations are:

HHH
HHT
HTH
HTT
THH
THT
TTH
TTT

that makes 8, or 2*2*2 or 2^3.

now can someone figure it out?

Since I don't think many people have worked with graphics.... if your computer runs in 32 bit color, that means that each pixel is made up of 32 bits. In our case (for windows and most applicatoins) this means you get 8 bits for the red chanel, 8 for the green, and 8 for the blue (the last 8 are alpha and not really used in what you see). Each of these 8 bits can have a value of 0-255, 0 means none of that color, 255 means all of that color. Because of the colors chosen, each different combination of those colors, will yield a different color for the overall pixel. This means in a sense you have 24 bits that you can use to see what color you get for the pixel, and every combination of those 24 bits yields a different color.

This should but people on the right track. (Next step is to see how many unique colors can be shown in a single pixel)

[DrJones]

what is your definition of a unique image? technically you would need an infiniate ammount of pixles to make a true "unique" image


Unique means that there are no repeats in the set. If we just had 2 colors (black and white) and 3 pixels, then the unique images would be:

BBB
BBW
BWB
BWW
WBB
WBW
WWB
WWW

where each line is a unique image. It doesn't matter what order they come in, just how many they are.

Note: For this problem it's likely that our eyes are not sensitive enough to detect all the unique images, but as long as one pixel is a different color, than it is a different image than all the others.

[David]

32 ^ P

P= # of Pixles

?

[DrJones]

32 ^ P

P= # of Pixles

?

very close. The part in the 32 should be the number of colors that each pixel can take on. 32 bits kind of makes it seem like there are 32 colors, but computers haven't used 32 colors for a long time. You kind of have to know a little bit about graphics to understand all of it, so it's an ok mistake.

The number of colors that each pixel can take on, in 32 bit color mode, is equal to 2^24. 2 because each bit can be 1 or 0, and 24 because only 24 of those 32 bits are used to determine the color.

This means each pixel on the screen can be one of 16,777,216 colors. Now you just have to raise that number to the number of pixels on your screen, which is easy to calculate (based of your screen resolution 640 x 480 means that each row has 640 pixels, and there are 480 rows)