Code for Chudnovsky Algorithm [or How to Translate an Equation into C++ Code]

[TechnoCat]

I was trying to find some code that would calculate an approximation of π, and I discovered a Java applet that uses the Chudnovsky algorithm and runs really fast, so I thought I'd use that. There's a formula on the Wikipedia article at http://en.wikipedia.org/wiki/Chudnovsky_algorithm ; how do I translate the equation on there into something that could be used in a C++ function?

[hamsterman]

(-1)^k becomes pow(-1, k)
(6k)! becomes fac(6*k) (you'll have to write fac() yourself )
Σ becomes for(int k = 0; k < number_of_terms; k++){ ... }

[TechnoCat]

So that becomes

	for (long k = 0 ; k < loops ; k ++ ) {
		piApprox += ( (-1) ^ (k) * factorial (6 * k) * (13591409 + 545140134 * k) )
		  / ( factorial (3 * k) (factorial (k) ) ^ (3) * (640320) ^ (3 * k + 1.5) ) ;
		}
	piApprox = 1 / piApprox ;

right? (piApprox was set to 0 at the beginning)

[TechnoCat]

Also, what's with the 12 before the Σ in the original formula?

[TechnoCat]

The code I just submitted got me a

‘factorial(((int)(k*3l)))’ cannot be used as a function

error. I split up the line the error was on, and isolated it to (factorial (k) ) (the last call to factorial (long num) in that formula) . That's weird because the file is entirely devoid of ‘3l’s, and the only ‘int’s are in int main (int argc, char * const argv [] ). The factorial function takes a long, and k was defined as a long. What's going on?

[simeonz]

Do you have some local identifier named factorial? Basically the compiler says that some identifier factorial that is not a function is available in some inner scope (closer to the call).

Regards

[TechnoCat]

I have a header file which has copies of all of the function declarations in it, and is included to every .cpp file. The call to factorial (long num) that generated the error is in a different file than the code for factorial. Does that answer your question?

[TechnoCat]

For some reason, when Xcode autocompletes a call to factorial, it autocompletes as factorial (<#int num#>) .

[simeonz]

Do you have the ability to find the declaration/definition that announces this signature? I mean, can you perform something like "go to declaration/definition" with Xcode?

[TechnoCat]

Yes; if I ⌥-double-click on a function call, I get an option to “view symbol declaration” .

[TechnoCat]

I found the error! factorial (3 * k) (factorial (k) ) should be factorial (3 * k) * (factorial (k) ). My mistake in translating the formula. Unfortunately, this created a new error:

Invalid operands of types ‘int’ and ‘double’ to binary ‘operator^’

, which I have isolated to (640320) ^ (3 * k + 1.5). I will try to figure this out, but if anyone can help speed this along, that would be much appreciated.

[simeonz]

Actually, the caret (^) is not exponentiation operator. It has different use - bit fiddling. What you need is to convert exponentiation expressions like x^y to pow(x, y).

http://www.cplusplus.com/reference/clibrary/cmath/pow/

[TechnoCat]

Okay, I fixed that error by replacing “1.5” with ‘3 / 2 ’ . This looks like the last one:

[linking error]
“factorial(int)” referenced from:
calculatePi(long) in calculatePi.o
calculatePi(long) in calculatePi.o
calculatePi(long) in calculatePi.o
Symbol(s) not found

[TechnoCat]

This seems to be causing more errors than it fixes, but okay:
[one error, detailed in previous post]
I changed all the carets to calls to pow. [two errors]
I included cmath. [three errors, detailed below]

[path to project]/calculatePi.cpp: In function 'double calculatePi(long int)':
[path to project]/calculatePi.cpp:38: error: call of overloaded 'pow(int, long int&)' is ambiguous
/Developer/SDKs/MacOSX10.6.sdk/usr/include/architecture/i386/math.h:343: note: candidates are: double pow(double, double)
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.2.1/cmath:373: note:                 long double std::pow(long double, int)
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.2.1/cmath:369: note:                 float std::pow(float, int)
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.2.1/cmath:365: note:                 double std::pow(double, int)
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.2.1/cmath:361: note:                 long double std::pow(long double, long double)
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.2.1/cmath:357: note:                 float std::pow(float, float)
[path to project]/calculatePi.cpp:38: error: call of overloaded 'pow(int, int)' is ambiguous
/Developer/SDKs/MacOSX10.6.sdk/usr/include/architecture/i386/math.h:343: note: candidates are: double pow(double, double)
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.2.1/cmath:373: note:                 long double std::pow(long double, int)
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.2.1/cmath:369: note:                 float std::pow(float, int)
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.2.1/cmath:365: note:                 double std::pow(double, int)
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.2.1/cmath:361: note:                 long double std::pow(long double, long double)
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.2.1/cmath:357: note:                 float std::pow(float, float)
[path to project]/calculatePi.cpp:38: error: call of overloaded 'pow(int, long int)' is ambiguous
/Developer/SDKs/MacOSX10.6.sdk/usr/include/architecture/i386/math.h:343: note: candidates are: double pow(double, double)
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.2.1/cmath:373: note:                 long double std::pow(long double, int)
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.2.1/cmath:369: note:                 float std::pow(float, int)
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.2.1/cmath:365: note:                 double std::pow(double, int)
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.2.1/cmath:361: note:                 long double std::pow(long double, long double)
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.2.1/cmath:357: note:                 float std::pow(float, float)

[simeonz]

See my previous post. Regarding this linking error, you need to compile the .cpp that implements factorial together with the .cpp that implements calculatePi. The syntax is IIRC:

g++ -o executable_file source1.cpp source2.cpp

Regards

[simeonz]

Compiler errors are not everything that matters ;)

[TechnoCat]

*Must* I launch Terminal? I've gone all day without having to. :P

[simeonz]

I have not had to work with Xcode, so I did give you the command approach. If you can add the file that implements factorial to your project in Xcode, then it should work. If the source file with the factorial implementation is already in the project I am not sure what the problem could be.

[TechnoCat]

(NB: They're both in the project) I think they're being compiled together, but I'm not 100% sure. All the errors are compile errors now, by the way.

[simeonz]

The linker wont be fired if the compiler does not succeed.