Programming Challenge

Anything and Everything about Uplink

Moderators: bert_the_turtle, jelco, Chris, Icepick, Rkiver

Captain Chickenpants
level1
level1
Posts: 55
Joined: Tue Apr 22, 2003 2:51 pm
Location: Uk
Contact:

Postby Captain Chickenpants » Wed May 21, 2003 1:49 pm

As their has been a lot of programming related discussion of late I thought I would suggest a programming challenge.

Estimate Pi, to as many decimal places as you can in 20,000 iterations. There are several ways of estimating Pi so it would be interesting to see which one is better (I have no idea).

CC.
Make something idiot proof, and someone will invent a better idiot.
------------------------------------------------------
http://uplink.stewsburntmonkey.com/profile.php?Captain%20Chickenpants
ReflectingGod
level5
level5
Posts: 2725
Joined: Sun Mar 17, 2002 4:40 pm
Location: W. Australia

Postby ReflectingGod » Wed May 21, 2003 1:56 pm

Yeah, I'd probably be up for that.

Would you want us to submit the source, or just an exe, or what?

Any preference as to language used?

Any other "rules" I should be aware of?
ME!

Procrastination - Hard work often pays of after time, but laziness always pays off now!

**Bibo ergo sum!**
Captain Chickenpants
level1
level1
Posts: 55
Joined: Tue Apr 22, 2003 2:51 pm
Location: Uk
Contact:

Postby Captain Chickenpants » Wed May 21, 2003 2:10 pm

As their is no prize (excepting our undying admiration)and cheating would be kind of pointless as it is merely a test for yourself, simply describe/name the method used , and the accuracy of your result.
So any language you like really!

CC
Make something idiot proof, and someone will invent a better idiot.
------------------------------------------------------
http://uplink.stewsburntmonkey.com/profile.php?Captain%20Chickenpants
ReflectingGod
level5
level5
Posts: 2725
Joined: Sun Mar 17, 2002 4:40 pm
Location: W. Australia

Postby ReflectingGod » Wed May 21, 2003 2:18 pm

Cool. I'll get on to it right away ;) 20,000 iterations, yeah?
ME!



Procrastination - Hard work often pays of after time, but laziness always pays off now!



**Bibo ergo sum!**
Captain Chickenpants
level1
level1
Posts: 55
Joined: Tue Apr 22, 2003 2:51 pm
Location: Uk
Contact:

Postby Captain Chickenpants » Wed May 21, 2003 2:48 pm

Yep.
Make something idiot proof, and someone will invent a better idiot.
------------------------------------------------------
http://uplink.stewsburntmonkey.com/profile.php?Captain%20Chickenpants
User avatar
Phydaux
level5
level5
Posts: 1615
Joined: Tue Feb 26, 2002 3:00 am
Location: Cardiff, UK
Contact:

Postby Phydaux » Wed May 21, 2003 6:08 pm

Code: Select all

[size=17]pi# = 4
FOR i& = 3 TO 40000 STEP 2
 Â  pi# = (pi# * -1) + (4 / i&)
NEXT i&
PRINT ABS(pi#)[/size]


I did that in qbasic.

it's just

4 - 4/3 + 4/9 - 4/11 ...

which gives 3.141542653589821 (as deep as QBASIC will go)
with (just under) 20000 itterations it's accurate to 4dp :(

but looping 1,073,741,823* times gives a more accurate number :) but takes ages.

there is probably a better way to code this in QB but i'm rushing :)

* because of the nature of my code the value of i& cannot excede 2,147,483,647, as i'm going in steps of 2 1,073,741,823 is the number of loops
User avatar
Jackmn
level5
level5
Posts: 1378
Joined: Thu Feb 07, 2002 5:21 pm

Postby Jackmn » Wed May 21, 2003 8:42 pm

Just usin' Ramanujan's algorithm.

Can only do 49 iterations before breaking the max value of a double with a pow operation.

In order to do more iterations, I would need to set up my own math funcs to do math with arrays, and arrays to be able to store large values.

Gives 3.1415926535897931, a very accurate approximation of pi.

Code: Select all

#include <math.h>
#include <stdio.h>
double fact(double num) {
double result=1;
for(double i=2;i<=num;i++)
result*=i;
return result;
}
int main(int ARGC, char* ARGV) {
double xrec=0;
for(double i=0; i<42; i++)
xrec += (fact(4*i)*(1103+26390*i))/(pow(fact(i),4)*pow(396, 4*i));
xrec *= sqrt(8)/9801;
xrec = 1/xrec;
printf("%.20f", xrec);

return 0;
}



Edit:
Bleh, tabs not displaying. I'm certainly not converting them to spaces.

(Edited by Jackmn at 8:44 pm on May 21, 2003)
ReflectingGod
level5
level5
Posts: 2725
Joined: Sun Mar 17, 2002 4:40 pm
Location: W. Australia

Postby ReflectingGod » Wed May 21, 2003 9:26 pm

I can so as accurate as you like in one iteration, using Machin's fomula. This is accurate to 16 dp, the most you can get with type double.

----------------------------------------------------------------------

//PI.CPP ---- Calculating pi

#include <math.h>
#include <stdio.h>


//double one = 1;
//double twothreenine = 239;
double X = 0.2;
double Y = one/twothreenine;

double arctanX;
double arctanY;
double pi;

void main()
{
arctanX = atan(X);
arctanY = atan(Y);

pi = 4*((4*arctanX) - arctanY);

printf("%.16f", pi);


}

----------------------------------------------------------------------
ME!



Procrastination - Hard work often pays of after time, but laziness always pays off now!



**Bibo ergo sum!**
Captain Chickenpants
level1
level1
Posts: 55
Joined: Tue Apr 22, 2003 2:51 pm
Location: Uk
Contact:

Postby Captain Chickenpants » Wed May 21, 2003 9:48 pm

Hehe, well as everyone else seemed to be using series I thought I would give the monte-carlo method a go. I suspected it would be quite pants, and it was.

Code: Select all

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>


int main(int argc, char* argv)
{
double x,y;
double pi;
int n;
int hits=0;

srand( (unsigned)time( NULL ) );
for(n=0;n<20000;n++)
{
x=((2.0*rand()/RAND_MAX) - 1);
y=((2.0*rand()/RAND_MAX) - 1);
if( ((x*x)+(y*y)) < 1.0 )
hits++;
}
pi=4.0*hits/20000.0;
printf("%f\n",pi);
return 0;
}


The accuracy varies each run as a different seed is used, but the best I saw out of it was  3.146 which you can beat with the good old 22/7. The accuracy does not seem to improve much either if you increase the iterations.
Nice range of solutions so far :-)
CC
Make something idiot proof, and someone will invent a better idiot.
------------------------------------------------------
http://uplink.stewsburntmonkey.com/profile.php?Captain%20Chickenpants
chris97b
level1
level1
Posts: 45
Joined: Sun May 18, 2003 8:39 am

Postby chris97b » Wed May 21, 2003 9:54 pm

Actually, in school I had to write the same program, using the random numbers. I found if you have a VERY fast comp (2Ghz+) and are running nothing but your compiler, you can do around 500,000 iterations, and get 3.14159 pretty consistenly. Took ages though :)
"Had I succeeded, The Germans would claim me a German citizen, and the French would claim me a citizen of the world. Had I failed, the French would claim me a German, and the Germans would claim me a jew." -Albert Einstein
Captain Chickenpants
level1
level1
Posts: 55
Joined: Tue Apr 22, 2003 2:51 pm
Location: Uk
Contact:

Postby Captain Chickenpants » Wed May 21, 2003 10:05 pm

With 50000 iterations it is better, 3.1416 but still not as accurate as using one of the other non probabilistic algorithms.

I think you could produce a far more accurate answer if you made it completly non random and simply tried all the numbers from -1,-1 to 1,1 with a step size which would give you x number of iterations.

I have just this week upgraded my machine to 2.4Ghz :-0 I am a happy chappy!
Make something idiot proof, and someone will invent a better idiot.
------------------------------------------------------
http://uplink.stewsburntmonkey.com/profile.php?Captain%20Chickenpants
User avatar
The GoldFish
level5
level5
Posts: 3961
Joined: Fri Mar 01, 2002 9:01 pm
Location: Bowl / South UK
Contact:

Postby The GoldFish » Wed May 21, 2003 10:26 pm

well, for a start trignometry is cheating, at least in my books. It's a theorum basically based on Pi. 4 arctan 1 = pi, after all

Anyway, I used VB (dont laugh :P) and used the trapezium rule to estimate the area under a quarter circle of radius 1. given the total area = Pi r^2, r = 1 so the total area is just Pi. Times the output by 4 and you get Pi, or rather a decent approximation of it. Basically I got:

3.14159223790874

Which is alright, I think :)

I'm refining it now, so I reckon I can get even closer... hehe
-- The GoldFish - member of former GIT and commander in chief of GALLAHAD. You could have done something, but it's been fixed. The end. Also, play bestgameever!
ReflectingGod
level5
level5
Posts: 2725
Joined: Sun Mar 17, 2002 4:40 pm
Location: W. Australia

Postby ReflectingGod » Thu May 22, 2003 8:19 am

How DARE you call me a cheat ;)

It wasn't said we could use trig to get pi, and therefore mine is not only legal, but also  the best as it get pi exactly in one iteration.

You just can't take losing ;)

Oh, and I wrote a "Monte Carlo" one for my maths teacher. They are utter shite....
ME!



Procrastination - Hard work often pays of after time, but laziness always pays off now!



**Bibo ergo sum!**
User avatar
The GoldFish
level5
level5
Posts: 3961
Joined: Fri Mar 01, 2002 9:01 pm
Location: Bowl / South UK
Contact:

Postby The GoldFish » Thu May 22, 2003 3:39 pm

Actually your method of getting pi using trig is shite.

4 * arctan 1

is just a tad less complicated :P
-- The GoldFish - member of former GIT and commander in chief of GALLAHAD. You could have done something, but it's been fixed. The end. Also, play bestgameever!
Proxy Blue
level1
level1
Posts: 18
Joined: Wed May 14, 2003 1:14 pm
Contact:

Postby Proxy Blue » Thu May 22, 2003 3:45 pm

Pointless Thread.

The programming challenges have been done so many times now, whats the point in calculating Pi to X amount of decimal places.

Go make yourself some mods for Uplink if you want a programming challenge, lets have a competition on them rather than crappy Pi related garbage
Proxy Blue Gamer                                                                                                                Who is Proxy Blue  

Return to “General”

Who is online

Users browsing this forum: No registered users and 2 guests