newton-raphson evaluate

[bitdiv]

Hi,

I am writing a program to find the roots of any polynomial using the newton-rpahson method and I want to be able to give it a polynomial as an argument and then evaluate and differentiate it.

Is there an easy way of doing this (getting all the coefficients and powers in an array?) so an example argument might be x^4+2x^3+5x^2+8x-4=0
and I need a function to evaluate this for a particular value of x and a function to differentiate it...
I had a quick look for expression parsers but I couldn't find much.
Can anyone help?

Thanks,

Richard

[Laharl]

This is a slightly convoluted method, but it /should/ work.

The following functions will be of use in this, listed by header file:

cstring:
strtok - tokenizer - Google this for examples of use, it's kinda annoying
atoi - converts C-string of digits to an integer

ctype:
isdigit - boolean asking if the character is a digit 0-9

Basically, tokenize the input string with some delimiter, I think you can use multiple, so use + and - to break it up into terms, then x to split coefficients and powers. Then, using isdigit, remove all the non-digit characters and convert to integer with atoi. At this point, you can put the coefficients and powers into a function to differentiate, maybe using an array to store related coefficients and powers in adjacent indices...

EDIT: A simpler method came to me, sort of. After tokenizing for coefficients, put them in an array where their index is the power.

[bitdiv]

Thanks for your help, Is there a way to return two arrays from a function? Maybe return a pointer to an array containing pointers to both arrays?

Is there any c example code I can use for this?

Thanks,

Richard

[Ganon11]

You can pass both arrays as double pointers (e.g. int **array), and dereference them once every time you wish to use them. This way, you can deal with them like a single pointer, but any changes you make will be reflected back in main(). To call the method, you would use something like:

int *array;
// Do work to populate the array
myMethod(&array);

[arnaudk]

You might want to check out GSL which has a large collection of fast and efficient algorithms for numerical root finding.

Arnaud

[kaioshin00]

Hi,

I am writing a program to find the roots of any polynomial using the newton-rpahson method and I want to be able to give it a polynomial as an argument and then evaluate and differentiate it.

Is there an easy way of doing this (getting all the coefficients and powers in an array?) so an example argument might be x^4+2x^3+5x^2+8x-4=0
and I need a function to evaluate this for a particular value of x and a function to differentiate it...
I had a quick look for expression parsers but I couldn't find much.
Can anyone help?

Thanks,

Richard

Is there no way you could use something like Matlab for this? It would be a lot easier.


Anyhow, I'm no expert at C++ -- and I'm not sure if a regular expression library exists or how it's syntax works if it does exist. But if you can figure out this, you can use RegEx to do something like this (I'm basing this on how this works in perl)

result_array = split ( /\W/, expression);

This would split the expression based on any "non word" character, ie, splits based on things other than (0-9 a-z A-z)

So, in your example x^4+2x^3+5x^2+8x^1-4=0 the above code (if compatible with C++) should yield:

result_array[0] = x
result_array[1] = 4
result_array[2] = 2x
result_array[3] = 3
result_array[4] = 5x
result_array[5] = 2
result_array[6] = 8x
result_array[7] = 1
result_array[8] = 4
result_array[9] = 0

From these values, I think it would be easier to figure out the coefficients for the different terms, etc.

Then you could do

result_array2 = split ( /\d/, expression); //splitting based on any digit

For x^4+2x^3+5x^2+8x^1-4=0 this would yield
result_array2[0] = x^
result_array2[1] = +
result_array2[2] = x^
result_array2[3] = +
result_array2[4] = x^
result_array2[5] = +
result_array2[6] = x^
result_array2[7] = -
result_array2[8] = =


The odd elements of this array would tell you the order of additions and subtractions

Note: you would have to use 8x^1 instead of 8x for my above code to work

So yeah, in other words, I've found reg ex really helps when you need to parse something. If you can figure out how to work it with C++ then you could do something similar to the above or (and this is very likely) come up with a better solution than what I did.