I’ve been wanting to create a game that uses randomly generated dungeons for a while now but didn’t have a good idea about what kind of game to make. Recently though I decided “so what if I don’t have an idea for what to DO with the dungeons, I can figure that out after I make them.” So I set out to make some code that will generate random dungeons.
In my last post I talked about finding the number of zeroes at the end of , and I said that there was room for improvement. I thought about it a little bit and found a couple things to speed it up.
The first has to do with the relationship between the quantity of fives and the quantity of twos. The lower quantity in the prime factorization of is how many zeroes it will have at the end. If I would have thought a little more about it though I would have seen that counting the twos is pointless in this situation.
Even the prime factorization of has the information in there: there will always be more twos than fives. Counting from 1 to 10:
- Multiples of 2: 2, 4, 6, 8, 10
- Multiples of 5: 5, 10
This means that all we really need to keep track of is the quantity of fives in the prime factorization of . Which leads to the second optimization: we only need to get the prime factorization of multiples of five.
A while back I was looking at the different maximum values that the different integer data types (uint8, short, int, long, etc) have throughout a couple languages I’ve been using and noticed that none of them ended in zero. I wondered why that was but then relatively quickly realized that it is because integer data types in computers are made up of bytes and bits.
An 8-bit (1-byte) integer has a max value of , a 16-bit (2-byte) integer has a max value of, etc. In fact since any integer in a computer is made of bits it will have a maximum value of . The prime factorization of an n-bit integer is in the notation, it is n 2s all multiplied together. Like so:
In order for something to end in a zero it must be a multiple of 10, and the prime factorization of 10 is 5 * 2, and the prime factorization of will never contain a 5. Case closed. That was fun.
That got me thinking about figuring out how many zeroes are at the end of a number if all you have is the prime factorization. Using my basic arithmetic skills I found out that:
It appears (although isn’t proof) that the lowest quantity between twos and fives dictates how many zeroes are at the end of a number when you’re looking at its prime factorization. I tried this with many more combinations and it worked with every one of them.
So what can we do with this information?
A factorial is a number written as where for any value , . For example and . The Wikipedia page for factorials shows that . That’s a big number, over a googol. You can see the whole thing here on WolframAlpha.
This blog is going to be a collection of math, programming, physics, etc. things that I’ve looked into, thought about, or find curious. Every now and then I see something or ask a question that starts me down a path of research and sometimes my curiosity leads me to program things, or try to discover principles, or do stuff in short. Up until now these things wind up in a lost computer file or sheets of paper that wind up in a drawer or the trash. These are things that I’ve put varying amounts of time into, and not only do I want to keep them around for that reason, but also if I found them interesting enough to pursue them, maybe somebody else will find them interesting enough to read them.So that’s what this blog is about, and I’m going to try to keep it focused on those things.
What I’m going to try to keep out of it are posts where the entirety of the content is photos of vacations, food I ate, music I like, etc. If I wanted to post things like that I’d just use a Facebook account.