Vieta Accelerated



#4

Hello Pi Enthusiasts,

In last June's Mathematics Magazine there was a great article about accelerating Vieta's formula. My first thought was to try this on my 50g and compare it to my other 50g Pi programs. Whether you're a C programmer or not you may still find my implementation, comments, and results interesting: Vieta Accelerated. NOTE: This is a small part of a much larger document (my HPGCC tutorial).

I wrote 90% of this in early July. My intent was to release on the "other Pi day", 22/7, but I got busy with life.

Edited: 1 Dec 2008, 1:49 a.m.


#5

Hello Egan,

Thanks for posting your interesting article on Viète acceleration. Your Pi shootout is excellent and the HPGCC tutorial is well worth reading for anyone interested in native code development for the 50g. Incidentally, do you know if there is now a way to perform the “S->EXE” transform on the PC rather than the calculator? This was always a problem for me since larger lumps of code would run out of memory for this transformation.

Also, I claim you only need k+1 numbers to calculate V(k,n). What you do, is fill out a k+1 array with V(0,n) .. V(0,n+k) and reduce this “row” k times with the recurrence relation until finally the first slot of the array is the value of V(k,n).

Take a look at this code which illustrates what im talking about. Im only using native doubles here in place of bignums, but the calculation should be the same.

double kreminski(int k, int n)
{
// create array of k+1 values
double* kc = new double[k+1];
int i;
int m;

double r = 0;
double t = 1;

// fill out V(0,n) for n to n+k
m = n + k;
for (i = 1; i <= m; ++i)
{
r = sqrt(r + 2);
t *= 2/r;
if (i >= n)
kc[i-n] = t;
}

// reduce table row by row until top
int j;
double k4 = 1;
m = k;
for (j = 0; j < k; ++j)
{
k4 *= 4;
for (i = 0; i < m; ++i)
kc[i] = (k4*kc[i+1] - kc[i])/(k4-1);

--m; // one shorter each time
}

t = kc[0]; // top left is answer!
delete [] kc;
return t;
}

is this a winner?

cheers,
-- hugh.


#6

Quote:
Thanks for posting your interesting article on Viète acceleration. Your Pi shootout is excellent and the HPGCC tutorial is well worth reading for anyone interested in native code development for the 50g.

Thanks.

Quote:
Incidentally, do you know if there is now a way to perform the “S->EXE” transform on the PC rather than the calculator? This was always a problem for me since larger lumps of code would run out of memory for this transformation.

No. I have looked into it, but not very hard, since this is not required with HPGCC3, I never really finished investigating it.
Quote:
Also, I claim you only need k+1 numbers to calculate V(k,n). What you do, is fill out a k+1 array with V(0,n) .. V(0,n+k) and reduce this “row” k times with the recurrence relation until finally the first slot of the array is the value of V(k,n).

Brilliant. I'll give it a go with decNumber and let you know the results (probably very late tonight). I do not expect it to be much faster because of the time spent computing V(0,n) .. V(0,n+k), but it will use a lot less memory. It'll still max out at k = 108, but I will not need to use the SD card, but then that was the whole point of the example, how to use libfsystem for large arrays. :-)
Quote:
is this a winner?

Probably. I'll post vieta4.c soon. Thanks again.

Forum Jump: