So I want to get into programming.

GreyHuge

Hi Forums,
I've been wanting to learn how to program for a while now and have decided to learn C++. I have decided that the project I want to work on is a dynamical systems simulator. I would like to know (1) What C++ compiler the forum recommends, and (2) What algorithm you would suggest for simulating second order systems.
Love,
Asnabel

WindUpBird

Relevant to my interests.

Andrew

Forget learning C++ as your first language. I recommend Python, or if you really want to Java as a first language. Any good first year CS program at a respected university uses these two and most use this book if they are using Python. It's called How to Think Like a Computer Scientist. Forget about making anything complicated your first time as it will only lead to frustration and you'll give up on your project.

GreyHuge

Forget learning C++ as your first language. I recommend Python, or if you really want to Java as a first language. Any good first year CS program at a respected university uses these two and most use this book if they are using Python. It's calledHow to Think Like a Computer Scientist. Forget about making anything complicated your first time as it will only lead to frustration and you'll give up on your project.

I'll give that a try, but why would I want to do something else? The C++ came after I decided that I wanted to model dynamical systems. After I couldn't solve the problem analytically I figured I would solve it numerically. Hence the request for an algorithm. Also, the dynamical system does have an analytical solution, as Mathematica tells me, it is however not in the classical functions.
EDIT:So what exactly does using Python require?

Dr. Timo

Hence the request for an algorithm.

Algorithms for numerically solving dynamical systems depend a lot on the nature of the system. In general you can always discretize and linearize the differential equations of motion, but optimal discretization (how you slice time and space) is very important for minimizing computation time and can depend on the system in general or even the specific state the system is in.

Apreche

I've been wanting to learn how to program for a while now and have decided to learn C++. I have decided that the project I want to work on is a dynamical systems simulator. I would like to know (1) What C++ compiler the forum recommends, and (2) What algorithm you would suggest for simulating second order systems.

You're doing it wrong. Allow me to translate your post into a way that makes your error more obvious.

I've been wanting to learn cabinetmaking for a while now and have decided to learn how to use a hammer. I have decided that the project I want to work on is a 6-drawer dresser. I would like to know what hammer the forum recommends and what nails you would suggest.

Your first problem is that you are deciding before you learn. You are saying you don't know how to program, but apparently you feel like you know enough to be making all sorts of decisions. Think about that for a second. You admit you know nothing, but you are making decisions. Not much more needs to be said on that.

Let me put you on the right track.

First, is your primary goal to learn programming, or is it to solve your math problem? If your primary goal is to learn programming, you need to learn the fundamentals first. You can't just wake up one day and start doing calculus. You need to start in Kindergarten with addition and subtraction.

If your primary goal is to solve the problem, then you only really need to ride on the backs of programmers who came before you to get to the finish line as quickly and easily as possible. You can go around the Internet and find existing code you can just reuse and recombine into what you need. scipy and bioperl are great examples of libraries that scientists can use to do useful things without being excellent at programming.

Lastly, your request for an algorithm is quite silly. A program is an algorithm. Programming is the act of writing new algorithms. If an algorithm already exists, then that means the software you want already exists. If the software you want does not exist already, then you have to figure out the algorithm. That's what programming is.

I do always suggest that people have a project in mind if they want to start programming, but choosing something that is incredibly advanced as your first program is a sure way to fail. There's a big gap between hello world and advanced simulation you need to cross.

Dr. Timo

Lastly, your request for an algorithm is quite silly. A program is an algorithm. Programming is the act of writing new algorithms. If an algorithm already exists, then that means the software you want already exists.

An algorithm is a, possibly optimal, stepwise solution to a mathematical problem. This is not equivalent to a computer program. "Hello World" is not an algorithm, neither is Photoshop (although there are several implementations of algorithms in Photoshop).

Also, existence of an algorithm does not imply existence of an implementation of that algorithm, I can think of at least a dozen different list sorting algorithms, none of which exists as computer programs (very few apart from these do).

Regardless of these semantics, it is still silly to ask for an algorithm if you don't specify the problem beyond "second order dynamical problem".

Apreche

An algorithm is a, possibly optimal, stepwise solution to a mathematical problem. This is not equivalent to a computer program. "Hello World" is not an algorithm, neither is Photoshop (although there are several implementations of algorithms in Photoshop).

It is the equivalent of a computer program, you just have to examine it on the lowest level. Hello world in BASIC might not resemble an algorithm. But if you look lower, the BASIC parser/interpreter is an algorithm that combines many sub-algorithms. And of course you go down to the hardware level and so forth.

Also, which sorting algorithms do not exist in software? Is it because they are inefficient and useless, or it is because implementation with only binary logic is not possible?

GreyHuge

Algorithms for numerically solving dynamical systems depend a lot on the nature of the system. In general you can always discretize and linearize the differential equations of motion, but optimal discretization (how you slice time and space) is very important for minimizing computation time and can depend on the system in general or even the specific state the system is in.

An algorithm is a, possibly optimal, stepwise solution to a mathematical problem. This is not equivalent to a computer program. "Hello World" is not an algorithm, neither is Photoshop (although there are several implementations of algorithms in Photoshop).

Also, existence of an algorithm does not imply existence of an implementation of that algorithm, I can think of at least a dozen different list sorting algorithms, none of which exists as computer programs (very few apart fromthesedo).

Regardless of these semantics, it is still silly to ask for an algorithm if you don't specify the problem beyond "second order dynamical problem".

Okay, What I want to do is simulate celestial mechanics in a two dimensional universe that bears a resemblance to our own. It is 2-dimensional and flat, and all matter and force is confined to its plane. This turns the inverse square law into the inverse law, significantly changing how gravitational potential works. Instead of being proportional to r, it is proportional to log(r). This makes escape (to r=infinity) velocity unreachable. I worked out the two-body problem using Mathematica and it turned out to involve the erf function. Now I have decided I will go with a numerical solution for the n-body problem, this means I might have to learn to program, something I have desired to do for some time now. What do you think would be the best approach Timo?

George Patches

You're doing it wrong. Allow me to translate your post into a way that makes your error more obvious.

I've been wanting to learn cabinetmaking for a while now and have decided to learn how to use a hammer. I have decided that the project I want to work on is a 6-drawer dresser. I would like to know what hammer the forum recommends and what nails you would suggest.

Your first problem is that you are deciding before you learn. You are saying you don't know how to program, but apparently you feel like you know enough to be making all sorts of decisions. Think about that for a second. You admit you know nothing, but you are making decisions. Not much more needs to be said on that.

I'm not one to agree with Scott just cause, but he has a very good point. Since you seem to be after doing math, I'd suggest you look for a language to do just that. C++ is setup to build programs that work in a computer sort of way, not really a people sort of way. For this it would be similar to having a nail to nail in, and bashing it with the end of a screw driver. It'll work, but it's not ideal, and a slightly miss could cause you a great deal of anguish.

GreyHuge

I'm not one to agree with Scott just cause, but he has a very good point. Since you seem to be after doing math, I'd suggest you look for a language to do just that. C++ is setup to build programs that work in a computer sort of way, not really a people sort of way. For this it would be similar to having a nail to nail in, and bashing it with the end of a screw driver. It'll work, but it's not ideal, and a slight miss could cause you a great deal of anguish.

Well then, what would be ideal? I have minimal knowledge of what computer languages are out there, which one should I use? I have that Python book Andrew directed me too, is that the language I should use? Or is there another language that is better?

George Patches

Well then, what would be ideal? I have minimal knowledge of what computer languages are out there, which one should I use? I have that Python book Andrew directed me too, is that the language I should use? Or is there another language that is better?

Good questions I don't have the answers to as I've never needed to make a computer do hardcore math on my behalf.

GreyHuge

Good questions I don't have the answers to as I've never needed to make a computer do hardcore math on my behalf.

Are you saying that you never needed a computer to do it, or that you have never needed to do it?

George Patches

Good questions I don't have the answers to as I've never needed to make a computer do hardcore math on my behalf.

Are you saying that you never needed a computer to do it, or that you have never needed to do it?

I've never been given a really hard math problem that would really be solved best by a computer. I had Calculus and Physics in college, but not on the level you're attempting.

theknoxinator

Well then, what would be ideal? I have minimal knowledge of what computer languages are out there, which one should I use? I have that Python book Andrew directed me too, is that the language I should use? Or is there another language that is better?

Good questions I don't have the answers to as I've never needed to make a computer do hardcore math on my behalf.

I also have never really done any hardcore math using computers. It just doesn't interest me to do math that I can't do with just pen and paper. To kind of go back to Scott's point a bit, there is no language that is "better". You generally choose a language that fits best for what you are trying to do. So the correct question is, what language is "best for this problem?" When it comes to math algorithms, the two main factors are speed and memory management. In both of these aspects, a lower level language would work best for optimizing math algorithms. As such, C/C++ is used more often for these problems than higher level languages like Python or Java.

Apreche

I also have never really done any hardcore math using computers. It just doesn't interest me to do math that I can't do with just pen and paper. To kind of go back to Scott's point a bit, there is no language that is "better". You generally choose a language that fits best for what you are trying to do. So the correct question is, what language is "best for this problem?" When it comes to math algorithms, the two main factors are speed and memory management. In both of these aspects, a lower level language would work best for optimizing math algorithms. As such, C/C++ is used more often for these problems than higher level languages like Python or Java.

This is true in general, but are the problems he is trying to solve really that computationally intensive? I doubt it. The performance loss of using a higher level language will be insignificant next to the time spent trying to write something like this in C.

Also, I have a feeling that existing libraries like numpy and scipy already have much of the math already implemented.

Andrew

When it comes to math algorithms, the two main factors are speed and memory management. In both of these aspects, a lower level language would work best for optimizing math algorithms. As such, C/C++ is used more often for these problems than higher level languages like Python or Java.

It depends on the data size and the type of calculations. Higher level languages these days are good enough at memory management that the types of optimizations you would get out of using a lower level language would be negligible unless you are working on some sort of difficult problem like graph partitioning or approximating NP-Hard solutions.

Dr. Timo

An algorithm is a, possibly optimal, stepwise solution to a mathematical problem. This is not equivalent to a computer program. "Hello World" is not an algorithm, neither is Photoshop (although there are several implementations of algorithms in Photoshop).

It is the equivalent of a computer program, you just have to examine it on the lowest level. Hello world in BASIC might not resemble an algorithm. But if you look lower, the BASIC parser/interpreter is an algorithm that combines many sub-algorithms. And of course you go down to the hardware level and so forth.

Well there is really no formally agreed upon definition of what an algorithm is. You say any set of stepwise instructions is an algorithm, whereas I maintain that there are additional qualifiers, such as generality and existence of a well defined logical problem. So it's is more a matter of opinion I guess.

For example, I would say that the set of instructions to get out of a hedge maze from a specific point, is not an algorithm. The set of sets of instructions to get out of a hedge maze from any point in the maze is not an algorithm. The instruction set "Walk forwards, At dead ends turn around, At crossings always turn right" is an algorithm for getting out of any hedge maze, from any point within he hedge maze.

Also, which sorting algorithms do not exist in software? Is it because they are inefficient and useless, or it is because implementation with only binary logic is not possible?

I was talking about the former case (I'm quite sure the latter would win me some sort of prize), e.g., quicksort but after each switch there is a step to google my name and before each pivot selection roll 2d20. This is an algorithm (by the most general definition at least), but I am very certain that it does not exist as a computer program anywhere (at least until you decide to code it ^_- ).

Apreche

I was talking about the former case (I'm quite sure the latter would win me some sort of prize), e.g., quicksort but after each switch there is a step to google my name and before each pivot selection roll 2d20. This is an algorithm (by the most general definition at least), but I am very certain that it does not exist as a computer program anywhere (at least until you decide to code it ^_- ).

I'll get right on that.

GreyHuge

So the consensus is that I should use Python?

Apreche

So the consensus is that I should use Python?

Too much planning, not enough doing. Go try stuff out and see what works best for you.

Churba

So the consensus is that I should use Python?

Use your python for great justice.

Dr. Timo

Okay, What I want to do is simulate celestial mechanics in a two dimensional universe that bears a resemblance to our own. It is 2-dimensional and flat, and all matter and force is confined to its plane. This turns the inverse square law into the inverse law, significantly changing how gravitational potential works. Instead of being proportional to r, it is proportional to log(r). This makes escape (to r=infinity) velocity unreachable. I worked out the two-body problem using Mathematica and it turned out to involve the erf function. Now I have decided I will go with a numerical solution for the n-body problem, this means I might have to learn to program, something I have desired to do for some time now. What do you think would be the best approach Timo?

For each particle (unique body) with coordinates (x,y) and velocity (vx,vy) calculate the potential at (x,y), the directional derivative of the potential yields the force which gives you the acceleration a. Use x=x0+vt+.5at^2 and v=v0+vt to get new values of (x,y) and (vx,vy) for a time step t. Rinse and repeat.

There are two problems you're going to run into:
1) If there are a lot of particles (n) in your system, the calculation of the potential will take O(n^2) time.
2) If the distance particles travel in one time step becomes large compared to the distances between particles and / or compared to the distance over which the potential changes significantly.

Solving these two problems algorithmically is a much harder task, especially if you want to do it optimally. If you only model two blobs moving around each other you will not encounter problem 1) and you can solve problem 2) by making the time slice proportional to the distance between the bodies.

EDIT: if you get this done, you have to post a video (or didn't happen ;-) ).

GreyHuge

Okay, What I want to do is simulate celestial mechanics in a two dimensional universe that bears a resemblance to our own. It is 2-dimensional and flat, and all matter and force is confined to its plane. This turns the inverse square law into the inverse law, significantly changing how gravitational potential works. Instead of being proportional to r, it is proportional to log(r). This makes escape (to r=infinity) velocity unreachable. I worked out the two-body problem using Mathematica and it turned out to involve the erf function. Now I have decided I will go with a numerical solution for the n-body problem, this means I might have to learn to program, something I have desired to do for some time now. What do you think would be the best approach Timo?

For each particle (unique body) with coordinates (x,y) and velocity (vx,vy) calculate the potential at (x,y), the directional derivative of the potential yields the force which gives you the acceleration a. Use x=x0+vt+.5at^2 and v=v0+vt to get new values of (x,y) and (vx,vy) for a time step t. Rinse and repeat.

There are two problems you're going to run into:
1) If there are a lot of particles (n) in your system, the calculation of the potential will take O(n^2) time.
2) If the distance particles travel in one time step becomes large compared to the distances between particles and / or compared to the distance over which the potential changes significantly.

Solving these two problems algorithmically is a much harder task, especially if you want to do it optimally. If you only model two blobs moving around each other you will not encounter problem 1) and you can solve problem 2) by making the time slice proportional to the distance between the bodies.

I've been looking at Runge-Kutta, but it appears to only work for first order systems, is there anything similar for second order systems? Aside from the polynomial solution you provided.

lackofcheese

This is true in general, but are the problems he is trying to solve really that computationally intensive? I doubt it. The performance loss of using a higher level language will be insignificant next to the time spent trying to write something like this in C.

Also, I have a feeling that existing libraries like numpy and scipy already have much of the math already implemented.

With regards to the programming language, I'd argue that because of ease of use you should go with Python with Numpy and Scipy over C++. Last semester I did a course (Engineering Analysis II at UQ) whose goal was to teach numerical analysis methods with computer programming tools, and that's what we used. I can attest to how powerful a package Numpy/Scipy is, and I've used MATLAB a lot so that is not something I say lightly. Sure, MATLAB, the expensive bitch that it is, has a lot of extras and some stuff you pretty much won't find in open-source software just yet, but that is outweighed by the fact that Python is just so much better as a programming language.

For any numerical problem, if performance isn't such an issue then high-level language features and stuff like full mathematical vector/matrix manipulation are invaluable. MATLAB, Octave, and Python with Numpy and Scipy are extremely good tools for this kind of thing, and since you also want to learn something of programming in the process, Python is a clear winner.

Lastly, your request for an algorithm is quite silly. A program is an algorithm. Programming is the act of writing new algorithms. If an algorithm already exists, then that means the software you want already exists. If the software you want does not exist already, then you have to figure out the algorithm. That's what programming is.

True, but implementing a well-known algorithm from a mathematical or English description is very helpful in learning to program. I believe that what Asnabel is asking for is some mathematical background and a hint as to the category of algorithm to use, so he can implement it himself.

Okay, What I want to do is simulate celestial mechanics in a two dimensional universe that bears a resemblance to our own. It is 2-dimensional and flat, and all matter and force is confined to its plane. This turns the inverse square law into the inverse law, significantly changing how gravitational potential works. Instead of being proportional to r, it is proportional to log(r). This makes escape (to r=infinity) velocity unreachable. I worked out the two-body problem using Mathematica and it turned out to involve the erf function. Now I have decided I will go with a numerical solution for the n-body problem, this means I might have to learn to program, something I have desired to do for some time now. What do you think would be the best approach Timo?

What you have is a system of ordinary differential equations. Presumably, if you want a simulation, you will input a set of initial conditions and let it run. This is called an Initial Value Problem (IVP). You will probably want to use an explicit Runge-Kutta method.

You will probably learn the most if you stick with something like Euler's method. Is that enough, Asnabel?

As far as getting a solution to the problem is concerned, Scott is correct - SciPy includes ode solvers. Obviously, you would still need to work out how to translate your problem into something SciPy will be able to use. However, in order to do that it would be best if you actually understand what an ode solver is doing behind the scenes.

lackofcheese

I've been looking at Runge-Kutta, but it appears to only work for first order systems, is there anything similar for second order systems? Aside from the polynomial solution you provided.

Quoting Wikipedia,

Any differential equation of order n can be written as a system of n first-order differential equations

Dr. Timo

I've been looking at Runge-Kutta, but it appears to only work for first order systems, is there anything similar for second order systems? Aside from the polynomial solution you provided.

The solution I provided, Euler's method, is the most straight forward way of doing this and the only difference with Runge-Kutta is that RK looks at the potential and it's derivatives in a different place (several places if you use RK4).

The problem with RK is that it takes more calculations per time step, so regulating the size of the step becomes more important. However, since the method is more complex, it is much harder to optimize the step size. Overall, you may be better off using a simpler method where the step size is easier to optimize.

All in all it depends on the details of your simulation, but if this is a "for fun" project, using RK is overkill.

EDIT: and the solution to using RK in your scenario is to do it first for the velocity (vx,vy) from the potential/acceleration (this is a first order problem) and then the coordinates (x,y) from the velocity (again a first order problem).

Dr. Timo

One more thing that recommends Python is that it is the control language for Sage which, if I didn't have access to the latest Mathematica, is what I would use for math.

GreyHuge

The solution I provided, Euler's method, is the most straight forward way of doing this and the only difference with Runge-Kutta is that RK looks at the potential and it's derivatives in a different place (several places if you use RK4).

The problem with RK is that it takes more calculations per time step, so regulating the size of the step becomes more important. However, since the method is more complex, it is much harder to optimize the step size. Overall, you may be better off using a simpler method where the step size is easier to optimize.

All in all it depends on the details of your simulation, but if this is a "for fun" project, using RK is overkill.

EDIT: and the solution to using RK in your scenario is to do it first for the velocity (vx,vy) from the potential/acceleration (this is a first order problem) and then the coordinates (x,y) from the velocity (again a first order problem).

Thanks for your help, I'm sure I'll figure it out. Though it would be neat if I could incorporate other impulses (Tsiolkovsky equation should still work in two dimensions), but I'm going to focus on one or the other for now. I'll start learning Python today.
*applies nose to grindstone*
EDIT: Also, should I use Python 2.6.4 or 3.1.1?

Dr. Timo

Though it would be neat if I could incorporate other impulses (Tsiolkovsky equation should still work in two dimensions), but I'm going to focus on one or the other for now.

You do not want to go there! Classical mechanics with variable particle masses is an abomination unto Newton!

GreyHuge

You do not want to go there! Classical mechanics with variable particle masses is an abomination to Newton!

What do you mean? Do I have to abandon the F=m*a simplification for the F=m*a+m' *v? Also, what effect would that have on the rocket equation?