PDA

View Full Version : Can I program a variable number of loops in C?




Spanky Deluxe
Feb 19, 2007, 09:57 PM
I'm trying to write a program which has x number of loops. Now I know that after this program is done I'll need to write very similar programs but with y or z number of loops. Basically each loop iterates a different variable in order to find the "best values" for all the variables of a mathematical function.

What I'd like to be able to do is to do something like this:

case 1:

variables = 1
start loop_1
call function(variable 1)
end loop_1

case 2:

variables = 2
start loop_1
start loop_2
call function(variable 1, variable 2)
end loop_2
end loop_1

case 3:

variables = 3
start loop_1
start loop_2
start loop_3
call function(variable 1, variable 2, variable 3)
end loop_3
end loop_2
end loop_1

case 4:

variables = n
start loop_1
start loop_2
start loop_3
...
start loop_n
call function(variable 1, variable 2, variable 3, ..., variable n)
end loop_n
end loop_3
end loop_2
end loop_1

Does anyone know if there's a way to do this in straight C? I'm using XCode btw. The rest of my program is getting fairly hairy and I'd rather not have to split up my program into different versions for different numbers of variables because that would lead to debugging hell!! Any help would be greatly appreciated!!



mduser63
Feb 19, 2007, 10:07 PM
Oops...don't have a good answer after all as I didn't read your post carefully enough.

bbarnhart
Feb 19, 2007, 10:13 PM
Recursion? You may also want to rethink your design.


void do_loops(int i)
{
if (i == 0)
{
call function(...);
}

start_loop
do_loops(--i)
end_loop

}

ChrisA
Feb 19, 2007, 10:26 PM
I'm trying to write a program which has x number of loops. Now I know that after this program is done I'll need to write very similar programs but with y or z number of loops. .....

You may want to re-think your design. When stuff looks ugly normally if is the result of a not well thought out design or un-clear goals.

What exactly are you trying to do? I can't see a reason for this

OK here is my ugly idea that I hope you don't need. Get a variable to X and you get X nested loops but with hard coded maximum.

while(X>1) {
while(X>2) {
while(x>3) {
while(x>4) {
while(x>5) {
}}}}}

Spanky Deluxe
Feb 19, 2007, 10:38 PM
Doing a quick google on "recursion" looks promising, thanks bbarnhart.

ChrisA, the program I'm trying to write is trying to find a specific point in various functions that have various constants that you can change.

One function might be F(x) = Ax
Another function might be F(x) = Ax + Bx^2
Yet another function might be F(x) = Ax + Bx^2 - (sin(z))^C

Where A, B and C are constants that can change. I'd want my program to try different values of A, B and C in order to find the best fit of one of these functions to some experimental data. To do this, I'd want to iterate A, B and C. Its a scientific programming problem rather than a 'regular app' type problem.

I think recursion looks like a very positive way to go right now and could save me a lot of hassle later on.

Oats
Feb 20, 2007, 09:13 AM
sounds like you want to do some sort of linear or non-linear regression?

http://en.wikipedia.org/wiki/Linear_regression
http://en.wikipedia.org/wiki/Nonlinear_regression

it looks like you are attempting some sort of brute-force method, which though straightforward to program, will not find a solution efficiently. no need to re-invent the wheel, someone has probably already written some code to do this kind of thing, and if you search for just the right words (such as "regression code c++") you might find something close to what you need.

for example,
http://cliodhna.cop.uop.edu/~hetrick/c-sources.html

mufflon
Feb 20, 2007, 12:42 PM
you could also try to use numerical derivation, which should also work well and less guessing and more approximation....

ChrisA
Feb 20, 2007, 03:25 PM
ChrisA, the program I'm trying to write is trying to find a specific point in various functions that have various constants that you can change.

One function might be F(x) = Ax
Another function might be F(x) = Ax + Bx^2
Yet another function might be F(x) = Ax + Bx^2 - (sin(z))^C


You want to write a general purpose program where a user can type in any function and apply it to any data set? A hard problem. You will be a very popular person if you can get this to work.

A classic text is now available on-line. What you are doing is looking for a minima in multi-dimensional space. You look for the minima of the difference between a function and your data. Rather then use pure brute force you can look at things like gradents and so on. Take a look at section 15.5 here http://www.ma.utexas.edu/documentation/nr/bookcpdf.html

balamw
Feb 20, 2007, 03:34 PM
Take a look at section 15.5 here http://www.ma.utexas.edu/documentation/nr/bookcpdf.html
Chapter 10 of NR is also a good resource.

B

AlmostThere
Feb 20, 2007, 03:39 PM
Chapter 10 of NR is also a good resource.

B

Seconded - for the practically minded, this is a well written explanation of some complex subjects.

Spanky Deluxe
Feb 20, 2007, 05:05 PM
Hmmm, I'll have a look at NR. ChrisA, its only a certain number of equations that I need to fit to data but some of them are quite different. I've already got a decent solution for one or two of the equations but I want to make it a bit 'cleverer'. Its not as inefficient a brute force method as such that I've been working on so far.
If only looking for one constant for example, the program tries say 10 different values for that constant in a range, then finds the point which has a minima between the generated data and the source data, it then picks the points either side of that minima and sets them to the minimum and maximum values over which to try 10 more values, so on and so on until the best minimal point is found. Obviously my program uses more than 10 values and the functions tend towards obvious minimums.

Thanks for all the help guys!! :)

lazydog
Feb 20, 2007, 06:37 PM
I'm not entirely sure what you need to do but I was wondering if you could make use of the cpp macro processor in some way.

For example the following code allows you to call an equation with up to 3 parameters. You pass the equation as the last parameter to EQUATIOn.


#define EQUATION1( A, EQ ) \
for ( int a = 0 ; a < A ; ++ a ) \
EQ ; ;

#define EQUATION2( A, B, EQ ) \
for ( int b = 0 ; b < B ; ++ b ) \
EQUATION1( A, EQ )

#define EQUATION3( A, B, C, EQ ) \
for ( int c = 0 ; c < C ; ++ c ) \
EQUATION2( A, B, EQ )



float value = 0.0f ;
EQUATION3( 3, 6, 9, value += a + b + c )


float value = 0.0f ;
EQUATION2( 3, 6, value += a * b )



It's probably not what you want or that the above code is of any real use but I thought it might be a technique that may be of interest.

b e n

AussieSusan
Feb 20, 2007, 07:03 PM
.....and I'd rather not have to split up my program into different versions for different numbers of variables because that would lead to debugging hell!! Any help would be greatly appreciated!!

I don;t think anyone has addressed the 'varying number of parameters in the function' part of your question, so here goes...

Have a look at the 'stdargs.h' OR the 'varargs.h' stuff - they let you have a varying number of arguments passed to a function (but with different macros so don't mix them!). The restriction is that they have to all be of the same type.

There are a number of examples on the net, but one I found quickly is http://www.unet.univie.ac.at/aix/libs/basetrf2/varargs.htm - look at the examples section.

Susan

lazydog
Feb 20, 2007, 07:54 PM
I think if the functions that need to be evaluated are simple enough so that they can be passed as arguments to EQUATIONn then I guess it will handle the variable number of arguments thing. To use the OP's equations as examples:

EQUATION2( 10, 12, a*x + b*x^2 )

or

EQUATION3( 3, 9, 5, a*x + b*x^2 - (sin(z))^c )

I don't know what needs to be done with the value of the equations but whatever it is the code would be part of macro EQUATION1. Same goes for the logic for iterating over the variables in macros EQUATION2-n.

I can imagine though that it would be a bit unwieldy to actually implement anything remotely useful this way!

b e n

Spanky Deluxe
Feb 21, 2007, 08:30 AM
Thanks guys for the suggestions. I think the recursive techniques working. By using global arrays and recursion I've already got something set up that feeds a function numbers as if they had been iterated through an arbitrary number of loops.

Here's basically where I'm at, I think its going ok right now, fingers crossed. I really need to start commenting this a bit more. Most of the code though is simply defining variables!! The low step number and the printf function are just there for testing right now btw.

#define VAR_MAX 10
double var_min[VAR_MAX];
double var_max[VAR_MAX];
double var_stepnumber[VAR_MAX];
double var_currentvalues[VAR_MAX];

// The equation that I'm using to fit
double equation1 (a, b) {
...
}

// Another equation I'll want to fit
double equation2 (a, b, c) {
...
}

double evaluator (double var_currentvalues) {
// In here will go the code that calls the equation functions above. There will be a global variable that states which equation to use. The main bulk of the calculations will go in here too.
}

// The recursion function
double looping (int variables, int current_variable) {
int step;
double stepsize;
if (current_variable == 0) {
return;
}

stepsize = (var_max[current_variable - 1] - var_min[current_variable - 1]) / var_stepnumber[current_variable - 1];
var_currentvalues[current_variable - 1] = var_min[current_variable - 1];

for ( step = 0; step < var_stepnumber[current_variable - 1]; step++) {

if (current_variable == 1) {
printf("%i %e %e %i\n", current_variable, var_currentvalues[current_variable - 1], var_currentvalues[current_variable - 1 + 1], step);

}

looping(variables, current_variable - 1);
var_currentvalues[current_variable - 1] = var_currentvalues[current_variable - 1] + stepsize;
}
}

int main (int argc, const char * argv[]) {

int variables = 2;

var_min[0] = 0;
var_max[0] = 16.459;
var_min[1] = 2.7193 * pow(10, 16);
var_max[1] = 2.6523 * pow(10, 11);
var_min[2] = 1;
var_max[2] = 10;

var_stepnumber[0] = 2;
var_stepnumber[1] = 2;
var_stepnumber[2] = 2;

looping(variables, variables);

return 0;
}

I'll post back to let you know how it goes. :)

GeeYouEye
Feb 21, 2007, 01:42 PM
I was tackling a similar problem a while ago, having to do with side-length-n n-dimensional arrays and populating them, where n cannot be known until runtime, and I'd have preferred it to have no maximum. ie, n = 4:
int i[4][4][4][4];
n= 6:
int i[6][6][6][6][6][6];


AFAICT, there was no way to do it in C generically. LISP almost certainly could (though I'm not so sure about the memory mapping abilities of LISP). But what I ended up with was the Io programming language. (http://www.iolanguage.com) Limited me to n<=7 however as I wasn't well-enough versed to figure out how to put that in an mmap, but the solution was ELEGANT. One of the prettier pieces of code I've seen.

balamw
Feb 21, 2007, 02:03 PM
I was tackling a similar problem a while ago, having to do with side-length-n n-dimensional arrays and populating them, where n cannot be known until runtime, and I'd have preferred it to have no maximum. ie, n = 4:
int i[4][4][4][4];
n= 6:
int i[6][6][6][6][6][6];


AFAICT, there was no way to do it in C generically.
Couldn't you just convert the array and indices to a one dimensional vector? i.e just allocate a one dimensional n^n array and address it as i[a_n*n^(n-1)+a_n-1*n^(n-2) ... a_2*n +a_1].

I guess it depends on what you need to do with the arrays once you've populated them how onerous that would be,

B

Spanky Deluxe
Feb 21, 2007, 06:19 PM
Ok, I've been working on this all afternoon and evening now and... it works. I mean, it really does work. For very different equations with different numbers of constants to find. I've so far tested it on equations with 2 to 4 constants and as far as I can tell, the program will work for as many constants as you want (although obviously cpu time becomes a big issue the more things you're trying to find). Right now 3 constants takes about a minute to find, 4 constants take about 10 minutes, 5 would take roughly 100 minutes.
The next step I'd like to try is to optimise the code to spread the work over multiple cores. This *is* a Mac Pro I'm running this on so I might as well try to use them all and this kind of brute force thing should theoretically scale linearly. Instead of 100 minutes, 5 constants could take 25 minutes to find. Should be fun!!

balamw
Feb 21, 2007, 11:52 PM
This *is* a Mac Pro I'm running this on so I might as well try to use them all and this kind of brute force thing should theoretically scale linearly. Instead of 100 minutes, 5 constants could take 25 minutes to find. Should be fun!!
Having this kind of fun is a great way to learn, but you might really want to give one of the Numerical Recipes approaches a try. Optimization/minimization/curve fitting is a place where brute force scaling rarely can compete with one of the more advanced methods.

I'm particularly partial to the routine they call amoeba, which quickly samples a broad part of your parameter space and quickly settles in on a local minimum. I've found it to work much more effectively than other routines.

B

GeeYouEye
Feb 22, 2007, 11:14 AM
Couldn't you just convert the array and indices to a one dimensional vector? i.e just allocate a one dimensional n^n array and address it as i[a_n*n^(n-1)+a_n-1*n^(n-2) ... a_2*n +a_1].

I guess it depends on what you need to do with the arrays once you've populated them how onerous that would be,

B

Yes I thought about that. But the indicies themselves matter in addressing and populating it, so it would quickly become unwieldily (especially with no integer exponentiation operator in C) and once you get past n = 7, you run out of address space and memory on a 32-bit machine without an mmap.

Thought about using hash tables of hash tables for it, but that would just be reinventing the mmap, and would still be rather difficult to address easily, since I'd need that arbitrary amount of link traversal.

Llywelyn
Feb 22, 2007, 11:19 AM
Doing a quick google on "recursion" looks promising, thanks bbarnhart.

ChrisA, the program I'm trying to write is trying to find a specific point in various functions that have various constants that you can change.

One function might be F(x) = Ax
Another function might be F(x) = Ax + Bx^2
Yet another function might be F(x) = Ax + Bx^2 - (sin(z))^C

Where A, B and C are constants that can change. I'd want my program to try different values of A, B and C in order to find the best fit of one of these functions to some experimental data. To do this, I'd want to iterate A, B and C. Its a scientific programming problem rather than a 'regular app' type problem.

I think recursion looks like a very positive way to go right now and could save me a lot of hassle later on.

There are a lot of fitting equations out there that have significantly better accuracy and algorithmic complexity than the proposed solution, could you simply use one of them?

Multidimensional rootfinding would be another approach that may be slightly more general. You can either use a multidimensional equation for this or an update step and just perform it iteratively (I've had good luck with this approach on a particularly hairy MLE before).

savar
Feb 22, 2007, 02:13 PM
I was tackling a similar problem a while ago, having to do with side-length-n n-dimensional arrays and populating them, where n cannot be known until runtime, and I'd have preferred it to have no maximum. ie, n = 4:
int i[4][4][4][4];
n= 6:
int i[6][6][6][6][6][6];


You can do this -- not only in C but in any practically any other mainstream language.

The problem you experienced is a limitation of syntax. You can't programmatically add square brackets at runtime.

But an array is really just contiguous memory referenced by a pointer: int[] is really just int*. If you use pointer syntax instead of array syntax you can solve any problem that can be done by a Turing machine.

ChrisA
Feb 22, 2007, 05:29 PM
Hmmm, I'll have a look at NR. ChrisA, its only a certain number of equations that I need to fit to data but some of them are quite different. I've already got a decent solution for one or two of the equations but I want to make it a bit 'cleverer'. Its not as inefficient a brute force method as such that I've been working on so far.
If only looking for one constant for example, the program tries say 10 different values for that constant in a range, then finds the point which has a minima between the generated data and the source data, it then picks the points either side of that minima and sets them to the minimum and maximum values over which to try 10 more values, so on and so on until the best minimal point is found. Obviously my program uses more than 10 values and the functions tend towards obvious minimums.

Thanks for all the help guys!! :)

Then you have a manageable problem. If there are N equations then it is not harder than writing N programs, You can apply a search technique specialized to each equations. In the case where the user can enter the equation, user could enter some very nasty ill-behaved equations. Also the job is easier because the maximum number of constants is known. and there is code reuse. You can even find published code for search an n-parameter space. Not much left for you to write if you use that. There are many published techniques, brute force, starting with course grid and then making the grid smaller ad smaler (kind of like a binar search in n-space) and gradient walking. there must be many more You re really just finding the maxima of a "goodness" function

Picking a goodness function is not easy. How do you define "fit"? There is not one good answer

Llywelyn
Feb 23, 2007, 03:04 PM
You can do this -- not only in C but in any practically any other mainstream language.

The problem you experienced is a limitation of syntax. You can't programmatically add square brackets at runtime.

But an array is really just contiguous memory referenced by a pointer: int[] is really just int*. If you use pointer syntax instead of array syntax you can solve any problem that can be done by a Turing machine.

If you are working with objects you can also use a composite pattern with only a single array.

GeeYouEye
Feb 23, 2007, 05:46 PM
You can do this -- not only in C but in any practically any other mainstream language.

The problem you experienced is a limitation of syntax. You can't programmatically add square brackets at runtime.

But an array is really just contiguous memory referenced by a pointer: int[] is really just int*. If you use pointer syntax instead of array syntax you can solve any problem that can be done by a Turing machine.

That may be true, but populating required knowledge of the subscripts... calculating it each time would be an ugly mess of an algorithm, and one that I couldn't elegantly recurse with without passing a stack or list. Not to mention the need to have a function call with its own for-loop for every single addressing (and there were a LOT).

Hmm... I wonder if anyone's ever written a C interpreter... and actually, now that I think about it, PHP is pretty close to that... I wonder if I can actually do this in PHP. If memory serves, there's also a PHP compiler somewhere... I need to investigate this.

lazydog
Feb 23, 2007, 06:21 PM
Hmm... I wonder if anyone's ever written a C interpreter...

Ch (http://www.softintegration.com)

b e n