Over the Christmas break I was moved out of my old comfy office which was a converted storage room in the basement, to a room that is old lab space. I suppose this room does have the advantage (disadvantage?) that I actually get reception for my cell phone here. But rather ironically this room is probably the least accessible spot in the whole damn building. On top of the offices positional awkwardness, which I assure you is severe, my office doesn't appear at first glance to have a working door.
My office has two doors, one is clearly marked JFB 205 and the other is rather humorously marked "Utility Access". Judging from the exposed strut running down the middle of the room between the two doors I think it is plausible that once upon a time the utility access door actually was what it purports to be. At any rate the door actually marked as though it led to an office instead of a janitorial closet is now completely inoperable. When the work crew came in to install the desks for some reason they figured it would be best to keep the desks as close as possible to the door and as far away as possible from the far wall... I don't think they had quite worked out that the desks poke out into the room farther than the door is away from the wall. Thus if you try to access the room through the obvious entrance you find the door jams after opening about an inch and a half. Giving the impression that perhaps the occupants have barricaded the door in order to defend against the imminent zombie apocalypse.
Fortunately for me I had tried to access the room before the desks were actually installed and so was aware that the apparent janitorial closet right next to the office was in fact a secret entryway. I hope the desk placement stupidity isn't corrected too quickly since this will enevitably lead to other people being aware of how to enter the room.
Tuesday, January 12, 2010
Fermat Number Factorizations
Fermat once conjectured that all numbers of the form 2^(2^n) + 1 were prime. More or less this was based on the fact that the first few such numbers 3, 5, 17, 257, 65537 were all prime. This was the farthest out that the primality of such numbers could be tested in Fermats day since the very next number in the sequence is 4294967297 which rather understandably Fermat did not recognize as being 641*6700417.
So far as we know the only prime Fermat numbers are in fact the first few numbers known to Fermat to be prime. Primality testing of the Fermat numbers and more challengingly the factorization of Fermat numbers has become something of a past time in number theory especially since computers got into the fray.
I should take a moment to talk about just how large the Fermat numbers really are. It is convenient to think of fermat numbers as binary strings. The Fermat numbers in binary are 11, 1001, 10000001, 1000000000000001, 100000000000000000000000000000001, .... and so on. The formula for producing them being to make a string of 2^n zeroes and then replacing the first and last zero with 1's. Viola a binary expansion of the n'th Fermat number. Rather obviously these numbers grow very very large very very quickly. Because of the difficulty of factorization of large numbers and the phenomenal growth of these numbers we have managed to completely factor only the first 11 Fermat numbers. This may not seem like much of an accomplishment but consider that "unbreakable" RSA cryptography uses numbers of a few hundred digits. F11 has 2048 binary digits which translates to over 600 decimal digits. One should keep in mind of course that RSA uses numbers which are worst case for factorization algorithms so factoring a 600 digit RSA number would be much harder than factoring a 600 digit Fermat number.
F12 is a 4096 digit number in binary (1234 decimal digits) and so even after dividing out all the known factors 114689, 26017793, 63766529, 190274191361, and 1256132134125569 we are still left with the incredible task of factoring a number of over 1200(decimal) digits. Although finding these gargantuan factors for F12 is certainly a laudable feat we have barely scratched the surface of the problem.
So far as we know the only prime Fermat numbers are in fact the first few numbers known to Fermat to be prime. Primality testing of the Fermat numbers and more challengingly the factorization of Fermat numbers has become something of a past time in number theory especially since computers got into the fray.
I should take a moment to talk about just how large the Fermat numbers really are. It is convenient to think of fermat numbers as binary strings. The Fermat numbers in binary are 11, 1001, 10000001, 1000000000000001, 100000000000000000000000000000001, .... and so on. The formula for producing them being to make a string of 2^n zeroes and then replacing the first and last zero with 1's. Viola a binary expansion of the n'th Fermat number. Rather obviously these numbers grow very very large very very quickly. Because of the difficulty of factorization of large numbers and the phenomenal growth of these numbers we have managed to completely factor only the first 11 Fermat numbers. This may not seem like much of an accomplishment but consider that "unbreakable" RSA cryptography uses numbers of a few hundred digits. F11 has 2048 binary digits which translates to over 600 decimal digits. One should keep in mind of course that RSA uses numbers which are worst case for factorization algorithms so factoring a 600 digit RSA number would be much harder than factoring a 600 digit Fermat number.
F12 is a 4096 digit number in binary (1234 decimal digits) and so even after dividing out all the known factors 114689, 26017793, 63766529, 190274191361, and 1256132134125569 we are still left with the incredible task of factoring a number of over 1200(decimal) digits. Although finding these gargantuan factors for F12 is certainly a laudable feat we have barely scratched the surface of the problem.
Friday, January 8, 2010
Thursday, January 7, 2010
The Time Machine
I just watched the most recent version of "The Time Machine" I have watched both the old black and white version and the one produced in the sixties. I thought the movies were all right and of course it wouldn't seem right for me to not have seen them being the time travel fanatic that I am. This most recent movie is much much better than the other two though with the reason being that it doesn't quite follow the story line set out by H.G. Wells. Now I think the original story line of the time machine is decent but overall the plot is not what the story is about. The story is about time travel not about weena. I think I am going to have to buy this time machine movie. The time travel sequences are very pretty and the story is well done and even a bit original although the eloi and the morlocks are still at the center of the whole thing.
I have always been something of a time travel fanatic. I have fond memories of Kip Thorne's "Black Holes and Time Warps". I remember checking the book out of the library in 2nd or 3rd grade reading the first 40 pages or so. I had to check it out multiple times even to get that far. Mostly I would find some out of the way corner and I would sit musing and dreaming while holding the book instead of actually reading it. I would read a few lines or a paragraph or two until something was said that I didn't understand or that made me think of something else and I would close the book with my finger in the pages at the point where I was reading. I remember learning scientific notation from the book which kindly explained for non-technical readers that 6x10^100 meant a 6 with a hundred zeroes after it. I kept going back to that little passage and rereading it over and over again. It was because here there was some tiny glimmer of the workings of real science something of the mechanism that made physics and math really work. I admit that scientific notation is about as simple as you get but to a second grade version of me it was something I could fully understand with a little thought and that was exciting. If I had read it from an algebra book in school it would have perhaps been interesting but no reason to day dream about unlocking the secrets of the universe.
I have always been something of a time travel fanatic. I have fond memories of Kip Thorne's "Black Holes and Time Warps". I remember checking the book out of the library in 2nd or 3rd grade reading the first 40 pages or so. I had to check it out multiple times even to get that far. Mostly I would find some out of the way corner and I would sit musing and dreaming while holding the book instead of actually reading it. I would read a few lines or a paragraph or two until something was said that I didn't understand or that made me think of something else and I would close the book with my finger in the pages at the point where I was reading. I remember learning scientific notation from the book which kindly explained for non-technical readers that 6x10^100 meant a 6 with a hundred zeroes after it. I kept going back to that little passage and rereading it over and over again. It was because here there was some tiny glimmer of the workings of real science something of the mechanism that made physics and math really work. I admit that scientific notation is about as simple as you get but to a second grade version of me it was something I could fully understand with a little thought and that was exciting. If I had read it from an algebra book in school it would have perhaps been interesting but no reason to day dream about unlocking the secrets of the universe.
Wednesday, January 6, 2010
Combine Ball
A couple of years ago a team I was in made a half life 2 mod that was a kind of dodge ball game. You threw combine balls around with the gravity gun. It was actually pretty fun. I figured it was time to post the video
Course Evaluations are In
So I got my first course evaluations for the discussion sections I taught in the fall. On the overall I took away the message that I really do need to be more careful about being clear be more carefully prepared and do more discussion and less working of problems. Of course I actually got more complaints to the effect that I wasn't doing enough homework problems than complaints that I wasn't doing the discussion well. But the complaints that I was not working enough homework problems were completely groundless since I was in fact doing almost nothing but working homework problems. It requires much less preparation to show how a few homework problems are to be worked than to prepare a real discussion.
I think my first semester of teaching went less well than it might have but I think it has made me a better teacher. I was a much better discussion leader towards the end of the semester than towards the beginning. Partly because my discussion sections were held at 7:30 and 8:35 in the morning I lost a great deal of the people in my classes. Since there were more evaluations than there ultimately were students attending the discussions I am pretty sure that some of the more negative reviews of my teaching were from people who came two or three times and then never again. I'm eager to see how the discussion sections I will be teaching in the spring evolve. Hopefully the classes won't go from not very full to barely there. Of course there will be some natural attrition since a large number of people will decide that the discussion section is not worth their time no matter how good it is. Unfortunately I won't really be able to productively compare the sections I will be teaching in the spring to the ones I taught in the fall since I will be teaching 2020 discussion sections instead of 2220 sections. Very probably the attrition rate in the algebra based physics (2000 series) is going to be higher than the calculus based versions (2200 series).
I think my first semester of teaching went less well than it might have but I think it has made me a better teacher. I was a much better discussion leader towards the end of the semester than towards the beginning. Partly because my discussion sections were held at 7:30 and 8:35 in the morning I lost a great deal of the people in my classes. Since there were more evaluations than there ultimately were students attending the discussions I am pretty sure that some of the more negative reviews of my teaching were from people who came two or three times and then never again. I'm eager to see how the discussion sections I will be teaching in the spring evolve. Hopefully the classes won't go from not very full to barely there. Of course there will be some natural attrition since a large number of people will decide that the discussion section is not worth their time no matter how good it is. Unfortunately I won't really be able to productively compare the sections I will be teaching in the spring to the ones I taught in the fall since I will be teaching 2020 discussion sections instead of 2220 sections. Very probably the attrition rate in the algebra based physics (2000 series) is going to be higher than the calculus based versions (2200 series).
Tuesday, January 5, 2010
Playing Poker for a Living: Who are you playing against?
Because poker is played against other players instead of against the house you don't need to be phenomenally good at poker in order to have a positive expectation, you only need to be better than someone you are playing against. As the existence of casinos demonstrates many people are willing to lose money on average in order to have a chance to win some money. The fact is that a lot of people find it fun to gamble and even more people find it fun to fantasize about winning at gambling. So very good poker players simply end up taking money from players who are less good.
Online poker is the best way to try and make a living at poker. The cost of playing online poker is smaller than the cost of playing poker at a physical casino, also many players who do not have access to a casino are willing to play online. Online activity isn't bound to just one physical place and so it is different times for different players giving more uniform behavior over time.
There are a large number of people who play poker occasionally for fun and a few people who play poker constantly, some for a living. I would be willing to bet that the distribution of the number of players who play with a certain frequency roughly follows a power law. N(f) = a*f^k for some choice of constants a and k where N(f) is the number of players who play with the frequency f. I expect this to hold true mostly for relatively small frequencies. Obviously there are many more low frequency players than high frequency players which means that here we expect k to be negative.
Lets take a moment here to consider the question of what this sort of distribution would mean for who you are likely to be playing when you log in to a poker site. Higher frequency players play more often but there are a lot more lower frequency players. If the power law distribution holds (and there is some reason to think that it would) then a player which plays with a frequency f would have a chance of being picked with probability density proportional to f*N(f) since the probability of a particular player being picked is the combination of the probability of that player being on which is f and the number of players with that frequency. Normalizing this density we get
P(f) = (k+2)*f^(k+1).
taking this a step further we calculate the average frequency of play as
integral f*P(f) df = (k+2)/(k+3) = faverage
This of course isn't very helpful unless we have some idea of the value of k. As we already said k must be negative to make lower frequencies more common than higher frequencies. But this means that there is a singularity at f=0 and examination of the probability density that we just came up with suggests to us that if we want to keep the total number of people online at a given time finite we need a k which is greater than -1.
for the limiting values of 0 and -1 we get an average play frequency of 2/3 and 1/2 respectively. The middle values have values in between these. for the middle of the road k = -1/2 we get 3/5 rather obviously no player can be playing with frequency 1 and it is doubtful that the average player is playing 2/3 of their day since that would mean they just take out 8 hours to sleep and thats it. Even the low estimate of 1/2 is too high. Qualitatively though the point is that high frequency players are on more often than low frequency players. If we take these frequencies to be a fraction of the highest normal play frequency then these numbers make more sense. The highest realistic value for the top player frequency is probably about 1/2 which would correspond to playing 12 hours of poker every day. A regular 40 hour work week would correspond to a frequency of 5/21. Using this as a base line I would say the highest tier of poker players probably have a playing frequency of around 1/3. This gives much more realistic figures for the average frequency of around 2/9, 1/5, and 1/6 for values of k 0, -1/2, and -1 respectively.
At any rate this suggests that most people you play will be people who play a very significant fraction of their time. This however doesn't take into account the fact that people do not play at all times of the day evenly. Taking this into account will skew the distribution back towards low frequency players during peak times and towards high frequency players at off times.
Online poker is the best way to try and make a living at poker. The cost of playing online poker is smaller than the cost of playing poker at a physical casino, also many players who do not have access to a casino are willing to play online. Online activity isn't bound to just one physical place and so it is different times for different players giving more uniform behavior over time.
There are a large number of people who play poker occasionally for fun and a few people who play poker constantly, some for a living. I would be willing to bet that the distribution of the number of players who play with a certain frequency roughly follows a power law. N(f) = a*f^k for some choice of constants a and k where N(f) is the number of players who play with the frequency f. I expect this to hold true mostly for relatively small frequencies. Obviously there are many more low frequency players than high frequency players which means that here we expect k to be negative.
Lets take a moment here to consider the question of what this sort of distribution would mean for who you are likely to be playing when you log in to a poker site. Higher frequency players play more often but there are a lot more lower frequency players. If the power law distribution holds (and there is some reason to think that it would) then a player which plays with a frequency f would have a chance of being picked with probability density proportional to f*N(f) since the probability of a particular player being picked is the combination of the probability of that player being on which is f and the number of players with that frequency. Normalizing this density we get
P(f) = (k+2)*f^(k+1).
taking this a step further we calculate the average frequency of play as
integral f*P(f) df = (k+2)/(k+3) = faverage
This of course isn't very helpful unless we have some idea of the value of k. As we already said k must be negative to make lower frequencies more common than higher frequencies. But this means that there is a singularity at f=0 and examination of the probability density that we just came up with suggests to us that if we want to keep the total number of people online at a given time finite we need a k which is greater than -1.
for the limiting values of 0 and -1 we get an average play frequency of 2/3 and 1/2 respectively. The middle values have values in between these. for the middle of the road k = -1/2 we get 3/5 rather obviously no player can be playing with frequency 1 and it is doubtful that the average player is playing 2/3 of their day since that would mean they just take out 8 hours to sleep and thats it. Even the low estimate of 1/2 is too high. Qualitatively though the point is that high frequency players are on more often than low frequency players. If we take these frequencies to be a fraction of the highest normal play frequency then these numbers make more sense. The highest realistic value for the top player frequency is probably about 1/2 which would correspond to playing 12 hours of poker every day. A regular 40 hour work week would correspond to a frequency of 5/21. Using this as a base line I would say the highest tier of poker players probably have a playing frequency of around 1/3. This gives much more realistic figures for the average frequency of around 2/9, 1/5, and 1/6 for values of k 0, -1/2, and -1 respectively.
At any rate this suggests that most people you play will be people who play a very significant fraction of their time. This however doesn't take into account the fact that people do not play at all times of the day evenly. Taking this into account will skew the distribution back towards low frequency players during peak times and towards high frequency players at off times.
Ludum Dare #16 Voting Results
Much to my surprise after the voting happened for Ludum Dare 16 it turns out my game entry came in 12th overall!
Top 20 Entries
Considering there were 121 total entries, that this was my first game making competition and that quite a number of the people who enter in these competitions actually code or even make games for a living, I'd say that is reason to be proud. Also my game was the only game in the top 20 which didn't come with some sort of executable. Of course I would like to say that this was a major disadvantage because it means many fewer people ran my game than might otherwise have. But I suppose that it may also be an advantage since only people that really wanted to play my game would have run it.
I'm going to try and participate in the next LD too and this time I will not have to relearn python or learn pygame and assuming I can find a few hours to detatch it from my LD 16 entry I will have a rough game engine. This time I will spend a few hours before hand making sure that I can make an executable.
Top 20 Entries
Considering there were 121 total entries, that this was my first game making competition and that quite a number of the people who enter in these competitions actually code or even make games for a living, I'd say that is reason to be proud. Also my game was the only game in the top 20 which didn't come with some sort of executable. Of course I would like to say that this was a major disadvantage because it means many fewer people ran my game than might otherwise have. But I suppose that it may also be an advantage since only people that really wanted to play my game would have run it.
I'm going to try and participate in the next LD too and this time I will not have to relearn python or learn pygame and assuming I can find a few hours to detatch it from my LD 16 entry I will have a rough game engine. This time I will spend a few hours before hand making sure that I can make an executable.
Sunday, January 3, 2010
Stochastic Factorization Algorithms
There are a number of probabilistic algorithms for primality testing. Probabilistic primality tests are based on fermats little theorem and its relatives.
fermat's little theorem
basically there are properties of prime numbers that can be tested for in a computationally efficient manner. Thanks to this sort of test we can probabilistically "recognize" prime numbers.
Factorization on the other hand is a completely different story. Primality testing and factorization are both difficult problems but their difficulty comes in completely different packages. In primality testing we are trying to distinguish between just two different possibilities whereas in factorization there are a vast number of potential answers. Relatedly it is extremely easy to check a factorization solution we simply multiply our proposed prime factors together and if we have found the correct factorization of our number then the product of the prime factors will be that number. On the other hand if we are handed a number and told that it is prime checking that solution to the primality testing problem is no easier than or original problem.
Since knowing the factorization of a prime number is equivalent to knowing that number is prime the factorization problem cannot be any easier than primality testing. But since we know of no way to make factorization work in less than exponential time and probabilistic primality testing works in essentially constant time... this is not much of a restriction. Obviously it would be nice if we could make good probabilstic factorization work. Since factorizations are easy to check a correct factorization suggested by probabilistic methods would quickly become a known factorization.
What we want then is a way to look at a number and simply "recognize" its factors. For numbers written in our regular decimal system there are a few nice ways to simply recognize some of the factors of that number. For example if the last digit of a number is 0, 2, 4, 6, or 8 then one of the factors of the number is 2. Somewhat less trivially if the sum of the digits of a number is divisible by three then the original number is divisible by three. A test that you might not be familiar with is one for 11 if you alternately add and subtract the digits of a number divisible by 11 if the result is divisible by 11 then the number itself is divisible by 11.
Although we could come up with tricks like these for every prime number that wouldn't end up giving us a factorization procedure that was much more effective than just checking for factors by dividing by all the numbers less than the square root of the number we want to factorize, since we would have to perform procedures to recognize each divisor individually.
But this brings us to the question what if we could probabilistically test for divisibility by whole classes of divisors at a time? There must be a way that numbers which contain different classes of primes "look" different. I don't have a nice rigorous mathematical way to look at a number and test whether or not it contains say a twin prime or more usefully a 4n+1 prime nor for that matter any general category of prime. But it is reasonable to believe that there are statistically recognizable properties of numbers with primes of different types. I just spent a few hours coding and trying to find such properties but didn't find anything by hand.
Even so the question remains unanswered as to whether or not it might be possible to write a program which could learn good heuristics which would suggest factorizations for numbers. Rather obviously this sort of tactic wouldn't be much good for factoring numbers which are used in cryptography since those numbers are composed of two enormous primes and it is just not likely that any heuristic program no matter how good could realistically "recognize" the factors of such a number. Realistically in fact this sort of strategy probably only has a real chance of learning to quickly factor relatively small numbers say on the order of 20 digits. Which means that more normal sieve factorization methods will be more than capable of easily handling these same numbers. Despite the fact that nothing useful is likely to come out of it this conjecture has taken my fancy. I've already put some effort into actually working it out and I am actually going to put some mental muscle into this.
fermat's little theorem
basically there are properties of prime numbers that can be tested for in a computationally efficient manner. Thanks to this sort of test we can probabilistically "recognize" prime numbers.
Factorization on the other hand is a completely different story. Primality testing and factorization are both difficult problems but their difficulty comes in completely different packages. In primality testing we are trying to distinguish between just two different possibilities whereas in factorization there are a vast number of potential answers. Relatedly it is extremely easy to check a factorization solution we simply multiply our proposed prime factors together and if we have found the correct factorization of our number then the product of the prime factors will be that number. On the other hand if we are handed a number and told that it is prime checking that solution to the primality testing problem is no easier than or original problem.
Since knowing the factorization of a prime number is equivalent to knowing that number is prime the factorization problem cannot be any easier than primality testing. But since we know of no way to make factorization work in less than exponential time and probabilistic primality testing works in essentially constant time... this is not much of a restriction. Obviously it would be nice if we could make good probabilstic factorization work. Since factorizations are easy to check a correct factorization suggested by probabilistic methods would quickly become a known factorization.
What we want then is a way to look at a number and simply "recognize" its factors. For numbers written in our regular decimal system there are a few nice ways to simply recognize some of the factors of that number. For example if the last digit of a number is 0, 2, 4, 6, or 8 then one of the factors of the number is 2. Somewhat less trivially if the sum of the digits of a number is divisible by three then the original number is divisible by three. A test that you might not be familiar with is one for 11 if you alternately add and subtract the digits of a number divisible by 11 if the result is divisible by 11 then the number itself is divisible by 11.
Although we could come up with tricks like these for every prime number that wouldn't end up giving us a factorization procedure that was much more effective than just checking for factors by dividing by all the numbers less than the square root of the number we want to factorize, since we would have to perform procedures to recognize each divisor individually.
But this brings us to the question what if we could probabilistically test for divisibility by whole classes of divisors at a time? There must be a way that numbers which contain different classes of primes "look" different. I don't have a nice rigorous mathematical way to look at a number and test whether or not it contains say a twin prime or more usefully a 4n+1 prime nor for that matter any general category of prime. But it is reasonable to believe that there are statistically recognizable properties of numbers with primes of different types. I just spent a few hours coding and trying to find such properties but didn't find anything by hand.
Even so the question remains unanswered as to whether or not it might be possible to write a program which could learn good heuristics which would suggest factorizations for numbers. Rather obviously this sort of tactic wouldn't be much good for factoring numbers which are used in cryptography since those numbers are composed of two enormous primes and it is just not likely that any heuristic program no matter how good could realistically "recognize" the factors of such a number. Realistically in fact this sort of strategy probably only has a real chance of learning to quickly factor relatively small numbers say on the order of 20 digits. Which means that more normal sieve factorization methods will be more than capable of easily handling these same numbers. Despite the fact that nothing useful is likely to come out of it this conjecture has taken my fancy. I've already put some effort into actually working it out and I am actually going to put some mental muscle into this.
Friday, January 1, 2010
New Years Resolutions
New years resolutions are things that you come up with in order to inspire you to achieve them. Of course they also tend to be things that you ultimately decide to not go through with. With both of those characteristics in mind here are my new years resolutions.
- Learn general relativity
- Get up earlier than I absolutely have to
- Come up with a working theory of fractional dimensional spaces
- Prove the Riemann hypothesis (preferrably as a side effect of the theory of fractional dimensional spaces)
- figure out how to collapse Jupiter into a black hole
Subscribe to:
Posts (Atom)