eb0ny
Level: Smiter

Rank Points: 484
Registered: 09-12-2007
IP: Logged

So, here's my problem: I know I want do Computer Science and I have been concentrating my studies on this subject. I have a rather well-developed algorithmic type of thinking, but only recently my lack of mathematical thinking has curbed me (I am trying to do problems on projecteuler.net, you see).

Since I know you guys are intelligent people (possibly with higher education), could you advise me how should I begin developing mathematical thinking? I am not asking for specific instructions that will turn me into a math-genius. I simply don't know where to start and which direction to go to, that's all.

____________________________

aztcg7
Level: Master Delver

Rank Points: 104
Registered: 03-08-2005
IP: Logged

I'm not exactly sure what you mean by mathematical thinking, but you say you have a good grasp on algorithms. A convenient way of thinking about algorithms are math problems that aren't closed, because you have to do a number of steps before you can analyze the answer.

If you are asking how to more efficiently solve the problems at Project Euler, the best way to decrease runtime is to split up the problem into subproblems, and try to solve the subproblems.

If you are asking how to think about math in general, I would suggest looking for patterns. Math is basically a way to describe connections that people see in a universal way.

Without more information, I'm not really sure what else to say. Good luck solving those problems.

____________________________
In other news, is a considerably more stylish way to express sarcasm than , because everybody uses and I am /indie/. INDIE, I TELL YOU.

eb0ny
Level: Smiter

Rank Points: 484
Registered: 09-12-2007
IP: Logged

aztcg7 wrote:
A convenient way of thinking about algorithms are math problems that aren't closed, because you have to do a number of steps before you can analyze the answer.

This is new to me. Could you elaborate, please?

____________________________

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

This is new to me. Could you elaborate, please?

Have you studied big-O? This is a way of abstractly analyzing the asymptotic running time of an algorithm. For example, consider the following three programs (functions) to reverse a string in common C/C++:





They all do basically the same thing which is to find the length of the string, and then walk along the string from both ends, switching characters until they get to the middle of the string. Then they stop.

Now, let's think about which how long each will take to run. Of course, if we have to reverse a really really really big string (say billions of characters long) the program is going to take longer to run simply because it has to switch more characters around. So we'll analyze the running time in terms of the length of the string, which we'll call N. (N = length of str).

Computer programs get turned into simple (machine) instructions. Each line of code usually corresponds to several machine instructions. Each machine instruction takes (approximately) an equal amount of time to execute, so all we have to do is figure out how many instructions we have and then multiply by the number of times we execute every instruction, then divide by the amount of time that an instruction takes to execute. The problem is that
1. it's really hard to tell from the high level code exactly how many instructions have to execute in order to make that code happen.
1a. Different compilers may compile the code differently
2. different computers execute instructions at different speeds.

We need a way to reason about efficiency a bit more abstractly.

Lets start by thinking about the different parts of the program. In program 1, we:
1. Compute the length of the string (basically, that's going to increment a counter once for each character in the string)
2. Go through the loop a bunch of times, each of which requires 3 steps. (well, actually, it requires 5 steps: switch the characters - three steps - then increment the variable and check the loop condition. Well, actually actually it takes more than that becuase in order to switch the characters, you have to do several arithmetic operations - ie adding subtracting etc, but basically theres a constant number of operations to be done each time through the loop.)

So we're going to count each character once - that's N operations (or some constant multiple of N) and we're going to switch characters N/2 times which requires N/2 operations (or some constant multiple of N/2). So basically, we have some constant number, C, of operations times N, the length of the string. So the running time of our program is CN.

What this means is that as the length of the string grows, the amount of time to reverse it grows linearly. This is as opposed to quadratically, or exponentially, or logarithmically (or any other basic math function you can think of).

Now, consider program 2. It's basically the same as program 1, but it has a slight improvement: it computes the length of the string, then divides it by 2 once so that we don't have to do that math op every time through the loop. Will this make our program faster? Yes! (or actually, probably... again it depends on how smart your compiler is. Your compiler may actually make that optimization automatically for you!) But how much faster? Well we still have to run through that loop N/2 times, and we still have to compute the length of the string, so we still have to do some constant, K, operations times the length of the string, N ==> KN.

How much time have we saved? Let's do it as a percentage:
% Time saved = (CN - KN) / CN = (C-K)/C.

Now remember, that C and K, vaguelly correspond to the number of instructions per character. We saved a couple of instructions out of maybe a couple hundred needed to do each loop or approximately 1%. No matter how big the string is, program 2 will run approximately 1% faster than program 1. Good, but not great.

Now, look at program 3. This has an inefficiency in that it calls strlen once every time through the loop. Remember that strlen looks at every character in the string once (ie it executes some instructions in a loop that gets run once for every character in the string). That means that for every character in the first half of the string, we're going to look at every character in the string. This will take N^2 (or a constant multiple of N^2) operations! Now, N^2 grows a lot faster than N. What do I mean by that? Well, suppose you knew that in program 1, C = 10,000. And that in program 3 you knew that the constant multiple would be K = 1 (This is unrealistic, but you'll see that it doesn't really matter how many instructions execute every time through the loop). Which program is faster? Well, for small values of N, program 3 will be faster. For example, suppose N = 10 (a reasonable length string). Program 1 will take 100,000 = 10,000*10 operations to complete. Program 3 will take only 100 = 1 * 10^2. But what about large strings? Say N = 1,000,000 characters. Program 1 will take 10,000,000,000 ops while program 3 will take 1,000,000,000,000 ops. All of a sudden program 1 is 100 times faster (ie 99% faster). To put this in perspective, a typical CPU these days can execute 1Billion ops per second. program 1 will take 10 seconds while program 3 will take 1000 seconds! But what about the small string? Well program 1 will take a bit longer than program 3 - .001 seconds vs .000001 seconds - but since the string is so short, you probably won't notice anyway!

So, what have we learned?
Well, program 1 and program 2 are essentially the same. They run in linear (which we usually refer to as O(n) - a constant times the size of the input) time. A small improvement, while not a bad thing, won't have a huge consequence on the efficiency of the program, no matter how big the input is.
But program 3 runs in quadratic time (O(n^2) - constant times the square of the input size). Now, that only gives us a vague notion of how long it will take (we don't know the constant). But we know that for sufficiently large input sizes, program 3 will always be slower than programs 1 and 2 no matter what their constants happen to be.



____________________________
Progress Quest Progress

---

[Last edited by stigant at 01-09-2009 01:28 PM]

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

Now, what does this have to do with project euler? Well, here's another example. I didn't get this one from project euler, but its the kind of thing they tend to ask.



Ok so here's a one way to do this (in sort of pseudo-c++):



How long is this going to take (remember that project euler problems should take less than a minute to run!!). Short answer: longer than the life of the universe (try it if you don't believe me!)

Why is it so innefficient? Well for one thing, it takes a long time to check if a number is a triangular number. Basically, the bigger n is, the longer it will take to check if n is triangular (becuase you have to add up more and more numbers). And remember, we're going to be calling this function for every integer between 1 and ... well I don't even know how much, because I can't be bothered to find out... but those calls are going to take longer and longer to execute the bigger the numbers get. Compare that to is_square_number. is_square_number executes a constant amount of instructions no matter how big n is (actually, that's not quite true, but its quite a bit more efficient than is_triangle_number). To put it in the terminology of the previous post, is_square_number is O(1) = C while is_triangle_number is O(n^(1/2) = K*n^(1/2)). No matter what the coefficients, C and K, are (suppose for example that sqrt(n) takes a large, but constant, number of instructions, while K is very small), is_square_number will be much faster than is_triangle_number for very large n.

Let's take a crack at making is_triangle_number more efficient. You might notice that Tk = k(k+1)/2 (example, T4 = 10 = 4*5/2). So to see if n is a triangular number, the equation n = k(k+1)/2 must have integer solutions. So rearranging gives
k^2 + k - 2n = 0
which has solutions (using quadratic formula)
k = (-1 +- sqrt(1 + 8n))/2
For example, if n = 10 then k = (-1 +- sqrt(1 + 8(10)))/2 = (-1 +- 9)/2 = 4 or -5 (of course, the negative solution is useless), showing us that T4 = 10 (and therefore showing us that 10 is a triangular number).
On the other hand if n = 9 then k = (-1 +- sqrt(73))/2 which is not an integer, so 9 is not a triangular number.
So the key is that whatever is inside the sqrt (ie 1 + 8n) must be a square number. Here's the new is_triangle_number:


Now we've made a significant improvement to the program. To compare, run change the program so that it looks for the first 5 square/triangle numbers instead of the first 20, and then try it with the new is_triangle_number function and the old one. The new one will run noticebly faster.

However, it's still not fast enough to run in the control time (1 minute). What's the problem here? Well, the "Good" numbers that we're looking for are spaced way way way apart. In fact, each number in the sequence 1, 36, 1225, 41616... is approximately 36 times bigger than the previous one! (1 * 36 = 36, 36 * 36 = 1296 ~= 1225, 1225 * 36 = 44100 ~= 41616 etc) So if it takes us 1 second to find the first 4 target numbers, then it will take us 36 seconds to find the next one, then nearly 20 minutes to find the next one, then almost 12 hours to find the one after that, then 18 days to find the next one, and then almost 2 YEARS to find the one after that. The next one will be found on your death bed, and your great-great-great (720 times over)-grand-children will be lucky if they see the program find the next one after that! And we still have to find 10 more!

So what could we do? Well, we could notice that we don't really have to check every integer if it's square and triangular. Instead, we could just look at the triangular numbers and see if they're square:



Ok, that's a lot better. In fact, since the triangular numbers are spaced out at O(n^2) compared to the integers, we just cut our running time by an exponent of 1/2 (ie we'll run in approximately the square root of the time we did before). Try this program out with finding the first 5 target numbers. It should be almost 6 times as fast as the previous program was. But it's still too slow! The indices of the triangle numbers (1, 8, 49, 288...) are each about 6 times the previous number. So, suppose it takes us 1 second to find the first 5 target numbers. It will take 6 seconds to find the next one, 36 seconds to find the next one, 3.6 minutes to get the next one, 21.6 minutes to get the next one, 2 hours for the next one, 5 days for the next one etc. It's better, but not good enough.

The real trick to solving this problem is to realize that the indices of the square numbers (1, 6, 35, 204, 1189 etc) have the following pattern:
6 = 1*6 - 0
35 = 6*6 - 1
204 = 35*6 - 6
1189 = 204*6 - 35
ie each number is 6 times the previous number minus the previous previous number.

Gn = 6*G(n-1) - G(n-2)

So this program:


Has a shot a finishing in our lifetime (in fact, it ought to finish relatively quickly (less than a minute unless I miss my guess) although you'll need to use a language with arbitrary length integers, for example Scheme)

But even that program isn't all that efficient. Consider that G(n) has to call itself a number of times and that we aren't caching previous results. In fact, if I asked for the first 40 good numbers instead, this would take a really really long time. Something like this would be much more efficient:





____________________________
Progress Quest Progress

---

[Last edited by stigant at 01-08-2009 10:53 PM]

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

So what's my point? Well I have a couple:

1. Programming correct solutions requires us to think algorithmically. In the previous problem, we came up with a simple way to find triangle numbers that were square numbers: Just start counting. See if each number is a square number and a triangular number, and if it is, then increment our counters. Then, go on to the next counter.

This is a great first step. This program will definitely find all the target numbers (eventually), it will definitely finish (eventually) and it will definitely give us the right answer (eventually). Unfortunately, "Eventually" is too long in this case.

2. Not programming unreasonable correct solutions to problems requires us to have an understanding of how long a program will run for. It doesn't have to be exact. In fact, it's usually better to just get a rough idea of the behavior of the program as the input gets larger. But we need to be able to determine when an algorithm will be too slow to be feasible. In general, we want to avoid exponential running time (unless the input is guaranteed to be VERY small), prefer linear to quadratic etc. If our algorithm can't possibly work in our lifetime... find a shortcut!

In our example, a bit of experimenting showed us that the size of the numbers was increasing exponentially. So counting all the way up to those HUGE HUGE HUGE numbers was infeasible, no matter how quickly we checked each one.

But all we've done is recognize that our first approach can't work. That hasn't helped us find a better approach.

3. Writing new, efficient, algorithms requires more than programming expertise. Usually, it requires domain-specific knowlege.

In this case, we needed to understand the MATH behind the problem, not just how to make that math happen (ie PROGRAMMING). Project Euler programs typically require you to see some sort of pattern in the numbers. In this case, we noticed that the indices on the square numbers had a particular recursive pattern. We used that AHA! moment to code a very fast program.

4. Breaking down into sub problems is something that we've barely scratched the surface on, but look at the last 2 programs I wrote. We were using a recursive function, G(n) = 6*G(n-1) - G(n-2).

Now, what does that mean? It means that if we can find 2 solutions (say the first 2 target numbers, 1 = S1 = T1 and 36 = S6 = T8), then we can find the next target number by doing simple calculations on these 2 solutions (ie 6*6 - 1 = 35 and 1225 = S35 = T49). Then we can use that one to find the next solution, and then that solution to find the next one.... Or more to the point, if I want the 37th target number, I can get it by finding the 36th target number which I can get by finding the 35th, which I can get by finding the 34th etc. I'll post another example of this next.

But there's more.
Let's break that into sub-calls for G(6):

G(6) = 6*G(5) - G(4).

So now we have to compute G(5) and G(4):

G(4) = 6*G(3) - G(2)

G(5) = 6* G(4) - G(3)

But that requires us to compute G(4) all over again! If we had cached the result of G(4), then we could just the saved result instead of computing it again! This can save a lot of time. Computing G(n) will take linear time (O(n)) instead of exponential time (O(2^n))

____________________________
Progress Quest Progress

---

[Last edited by stigant at 01-09-2009 12:05 AM]

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

Ok, so here's another example of solving sub-problems. It's a very famous problem called the "Towers of Hanoi" Basically, you have 3 poles. The first pole has 7 disks of decreasing size on it, and the other 2 poles are empty. The object is to move the disks from pole to pole, one at a time, and never placing a larger disk on top of a smaller disk, until you have reassembled the 7 disks on the 2nd pole:

Initial Position:
       |              |              |
      *|*             |              |
     **|**            |              |
    ***|***           |              |
   ****|****          |              |
  *****|*****         |              |
 ******|******        |              |
*******|*******       |              |
=====================================================

Final Position:
       |              |              |              
       |             *|*             |              
       |            **|**            |              
       |           ***|***           |              
       |          ****|****          |              
       |         *****|*****         |              
       |        ******|******        |              
       |       *******|*******       |              
=====================================================

Now, let's suppose that you have a robot that responds to commands like this:
Move Disk From 1 To 2
And that will make the robot move whatever disk is on the top of stack 1 to the top of stack 2. Your job is to program the robot, using the Move Disk From x To y command so as to affect the solution.

Let's do a smaller example with only 3 disks. You start with this picture:

*
**
***
=   =   =

and end with this:

    *
    **
    ***
=   =   =

Here's a sequence of moves that can work:
And here's the picture after each step:
Now, notice that to move 3 disks from 1 to 2, I first had to move the top 2 disks from 1 to 3, then move the bottom disk to 2, then move the top 2 disks from 3 to 2. If I had 4 disks instead of 3, I would have to move the top 3 disks from 1 to 3, then move the bottom disk from 1 to 2, and then move the top 3 disks from 3 to 2. This suggests that to solve a big problem (say with 7 disks) that I can solve a smaller problem (say with 6 disks), then do a simple step (ie move just one disk) and then solve another smaller problem (move 6 disks again). Let's see if we can write some code that helps us out. Let's start by assuming that we have a procedure that will move some number of disks from one pole to another. We don't know the details yet, but we do know that this procedure requires 3 pieces of input: How many disks to move, Which pole to start from, and which pole to finish on. Also, it won't return anything since it affects it's solution via side-effects:
Notice that I've gone ahead and written another procedure (usually, you call that "main()", but I've given it a more descriptive name) which calls the solve_sub_problem procedure to kick things off. In this case, the BIG PROBLEM (TM) is to move 7 disks from stack 1 to 2, so I've called ssp with the appropriate arguments (7, 1, and 2).

Now, let's think about how to solve some specific sub-problem (ie write the code for ssp). In our case, we need to move 7 disks from 1 to 2. Well, that would require that we move 6 disks from 1 to 3, then 1 disk from 1 to 2, then 6 disks from 3 to 2. If only we had some procedure to solve the problem of moving 6 disks from 1 to 3! But we DO! It's called Solve_Sub_Problem! We'll just call it with different arguments (6, 1, and 3 this time). Where did we get 6 from? Well, it was one less than the number of disks we actually wanted to move. Where did we get pole 1 from? That was the pole we're starting on. What about pole 3? Well, that's the third pole. I think we can compute that number by subtracting the other 2 poles from 6. Ok, so then we can call Move_One_Disk to move the bottom disk (that was provided for us, so we don't need to write that procedure). And then we can call SSP to move the 6 disks from pole 3 to pole 2! Here's the code:



Great! But not perfect. We have a small problem. SSP(7,1,2) is going to call SSP(6,1,3) which will call SSP(5,1,2) which will call SSP(4,1,3) which will call SSP(3,1,2) which will call SSP(2,1,3) which will call SSP(1,1,2) which will call SSP(0,1,2) which will call SSP(-1,1,3)... Notice that each time, the number of disks that we move decreases by 1, but that it will never end! This is bad. Let's think about what SSP(0,1,2) would mean. Remember that SSP moves some number of disks from one pole to another. In this case, SSP(0,1,2) moves 0 disks from pole 1 to pole 2. Well, how much work is there to do if we only have to move 0 disks? Right! No work at all. We need to catch this once particular case directly:



And that should take care of it. Here's a c/c++ program that will print out what to do (ie take the place of the robot actually moving one disk from pole to pole):


____________________________
Progress Quest Progress

---

[Last edited by stigant at 01-09-2009 12:45 AM]

eb0ny
Level: Smiter

Rank Points: 484
Registered: 09-12-2007
IP: Logged

I just realized I was looking in the wrong place for the source of my problems. I am aware of the big-O and apparently I wasn't approaching the problems with the right mindset. I don't lack mathematical thinking - I lack math theory in some areas and some determination to come with the best possible solution.

Well, thank you for a nudge in the right direction. Somehow I thought that if I can't optimize my solution more, it's because of my lack of math skills.

____________________________

aztcg7
Level: Master Delver

Rank Points: 104
Registered: 03-08-2005
IP: Logged

Wow. Stigant went into some crazy awesome depth, and said everything better than I ever could have.

____________________________
In other news, is a considerably more stylish way to express sarcasm than , because everybody uses and I am /indie/. INDIE, I TELL YOU.

Pekka
Level: Smiter
Rank Points: 302
Registered: 09-19-2007
IP: Logged

eb0ny wrote:[H]ow should I begin developing mathematical thinking? I am not asking for specific instructions that will turn me into a math-genius. I simply don't know where to start and which direction to go to, that's all.

George Polya (Pólya) wrote a well-regarded book titled How to Solve it? Here is a summary:
http://www.math.utah.edu/~pa/math/polya.html

Wikipedia has a page on it too:
http://en.wikipedia.org/wiki/How_to_Solve_It

If you think this approach looks promising, you should read the whole book. It'll probably help you.

---

[Last edited by Pekka at 01-10-2009 12:37 PM]

eb0ny
Level: Smiter

Rank Points: 484
Registered: 09-12-2007
IP: Logged

Pekka wrote:
If you think this approach looks promising, you should read the whole book. It'll probably help you.

Thanks, I'll take a look.

____________________________

zex20913
Level: Smitemaster

Rank Points: 1723
Registered: 02-04-2003
IP: Logged

Huh. Zex is late to a math discussion.

But it does involve math, and it's pretty hard for me to avoid jumping in on it, and currently developing some of my own theories on it. Plus, the Towers of Hanoi is pretty awesome and deep, even beyond the coding.

First, some theory (not necessarily widely supported, I don't know) based on my experiences, and the experiences of teaching others.

Logic and mathematics are highly intertwined. I think that math is one of the best ways to develop one's logos--logical thinking. We have a set of rules, and operations, and so long as what we build is consistent, we can always place another piece.

Seeing what others have seen may take time, and eventually will take effort. I don't believe that there are any mathematicians (aside from potentially Gauss) who have never struggled with some concept at some point. The question is, when you hit that wall, do you have the drive to go over it by looking at how others have gotten over the wall. Oftentimes, the classroom experience (in America) introduces the wall, and attempts to show one way that the teacher has gotten (or, sadly, has been told how to get) over the wall. My wall was algebraic topology, and even though I got an A in the course, I feel like I don't understand it. Someday, though, I will return to it.

Additionally, the more you see mathematics, the more quickly you understand it and can apply it to new situations. One of the reasons that I love the SAT math is that there are always new problems that seem challenging, but can be twisted to yield a solution. I'm finding with multiple clients (job change by the way--I'm more of a private math teacher than a public one, now), that the mentality towards math is also a large factor. If you have an internal inkling towards mathematics, you like devouring as much as possible. If the internal motivation is not there, fun can be a big lubricant towards developing internal motivations, and having somebody who knows many ins and outs of the topic can be a tremendous boost towards your own learning.

I think that's enough shoddy philosophizing for now. As to the Towers, here are some interesting things that you can do with them:

1. Find the most efficient algorithm (if you haven't already) and a formula for the number of moves it will take to move a tower with n discs.

2. Figure out which tile you will move on any given turn. (modulus introduction)

3. Organize the towers in a triangle, and observe how the discs move (coloring every other disc may speed this process.)

4. See if there is a pattern for more towers--that is, if there are 4 possible locations, is there an efficient algorithm for that?

There is also some mathematical thinking in these problems (aside from the obvious math overtones.) Things that mathematicians like to do is

1. Find patterns.

2. Find more patterns from the patterns you've found previously.

3. Change your viewpoint/approach, and see if other patterns develop.

4. Generalize the patterns in a formula.

Okay. That's enough. Shutting up now.

____________________________