Solved
PI algorithm
Posted on 1998-10-18
I have been working on a PI algorithm that I got off the internet a long time ago. I am not sure what is called or anything, but I have a few questions. First, here is the code (a little MFC):
// Global variables (this WILL BE REDESIGNED).
const long d1 = 239, d = 25;
long m; // m = m_NumDigits + 2
long i2, i3; // These variables are busy, but not like th ones shown below:
long i, r, v; // These variables are all very busy all the time...
// Other Functions:
void div_acst (char *&, int &);
void a_is_afromp (char *&, char *&);
// ....
char *a = (char *) malloc (sizeof (char) * (unsigned long) 1000000);
char *p = (char *) malloc (sizeof (char) * (unsigned long) 1000000);
char *t = (char *) malloc (sizeof (char) * (unsigned long) 1000000);
int divisor;
long counter;
time_t orgtime;
time (&orgtime);
if (a == NULL || p == NULL || t == NULL)
{ MessageBox ("Not enough memory :-(");
return;
}
UpdateData (TRUE);
// Reduce priority of this to idle time:
AfxGetApp ()->SetThreadPriority (THREAD_PRIORITY_IDLE);
// Minimize the window:
POINT pt;
GetCursorPos (&pt);
SendMessage (WM_SYSCOMMAND, SC_MINIMIZE, pt.y << 16 | pt.x);
AfxGetApp ()->m_pMainWnd->SendMessage (WM_SYSCOMMAND, SC_MINIMIZE, pt.y << 16 | pt.x);
m_Results = "";
CWaitCursor cursor;
m = m_NumDigits + 2;
i2 = (3 * m / 8) * 4 + 3;
i3 = (i2 / 14) * 4 + 3;
/* COMPUTE PROCEDURE */
i = i2;
/* DIV32IA */
a[0] = (char) (3 / i);
r = 3 % i;
v = r * 10 + 2;
a[1] = (char) (v / i);
r = v % i;
for (counter = 2; counter <= m; counter++)
{ v = r * 10;
a[counter] = (char) (v / i);
r = v % i;
}
/* DIVAD */
divisor = d;
div_acst (a, divisor);
for (i = i2 - 2; i >= 3; i -= 2)
{ /* DIV32IP */
p[0] = (char) (3 / i);
r = 3 % i;
v = r * 10 + 2;
p[1] = (char) (v / i);
r = v % i;
for (counter = 2; counter <= m; counter++)
{ v = r * 10;
p[counter] = (char) (v / i);
r = v % i;
}
/* SUBA */
a_is_afromp (a, p);
/* DIVAD */
div_acst (a, divisor);
}
/* SUBT32A */
t[0] = 3;
t[1] = 1;
for (counter = 2; counter <= m; counter++)
{ t[counter] = 9 - a[counter]; }
i = i3;
/* DIV4IA */
a[0] = (char) (4 / i);
r = 4 % i;
for (counter = 1; counter <= m; counter++)
{ v = r * 10;
a[counter] = (char) (v / i);
r = v % i;
}
/* DIVAD1 */
divisor = d1;
div_acst (a, divisor);
/* DIVAD1 */
div_acst (a, divisor);
for (i = i3 - 2; i >= 3; i -= 2)
{ /* DIV4IP */
p[0] = (char) (4 / i);
r = 4 % i;
for (counter = 1; counter <= m; counter++)
{ v = r * 10;
p[counter] = (char) (v / i);
r = v % i;
}
/* SUBA */
a_is_afromp (a, p);
/* DIVAD1 */
div_acst (a, divisor);
/* DIVAD1 */
div_acst (a, divisor);
}
/* SUB4A */
a[0] = 3;
for (counter = 1; counter <= m; counter++)
{ a[counter] = 9 - a[counter]; }
/* DIVAD1 */
div_acst (a, divisor);
/* SUBT */
for (counter = m; counter >= 1; counter--)
{ a[counter] = t[counter] - a[counter];
if (a[counter] < 0)
{ a[counter] += 10;
a[counter - 1]++;
}
}
CString temp;
temp.Format ("pi =\t3.");
m_Results += temp;
for (counter = 1; counter <= m_NumDigits; counter++)
{ temp.Format ("%1i", a[counter]);
m_Results += temp;
if (counter % 5 == 0)
{ m_Results += " "; }
if (counter % 50 == 0)
{ temp.Format ("\t%li\r\n\t", counter);
m_Results += temp;
}
}
time_t currenttime;
time (¤ttime);
temp.Format ("Time took in seconds: %lu", currenttime - orgtime);
m_Results += temp;
// Get thread running again:
AfxGetApp ()->SetThreadPriority (THREAD_PRIORITY_NORMAL);
// Restore the window:
GetCursorPos (&pt);
SendMessage (WM_SYSCOMMAND, SC_RESTORE, pt.y << 16 | pt.x);
AfxGetApp ()->m_pMainWnd->SendMessage (WM_SYSCOMMAND, SC_RESTORE, pt.y << 16 | pt.x);
UpdateData (FALSE);
free (a);
free (p);
free (t);
void a_is_afromp (char *&a, char *&p)
{ long counter;
for (counter = m; counter >= 0; counter--)
{ a[counter] = p[counter] - a[counter];
if (a[counter] < 0)
{ a[counter] += 10;
a[counter - 1]++;
}
}
}
void div_acst (char *&a, int &divisor)
{ long counter;
r = 0;
for (counter = 0; counter <= m; counter++)
{ v = r * 10 + a[counter];
a[counter] = v / divisor;
r = v % divisor;
}
}
Questions:
1) How to find out how much memory I need? I know it is based on the number of digits, but quite frankly I can't figure this algorithm out, hence I am not sure how much memory I need to allocate. If I take the number of digits and add 5, that is not enough in case that is any indication.
2) Is the algorithm efficient? How can it be sped up? The amount of time it takes to calculate more digits seems to go up non-linearly (the curve on the graph gets sharper the more digits you want to calculate). Note that I am going to redesign the functions so I do NOT need the global variables. This program was written a VERY long time ago, hence the C architecture and everything else that is poor by today's standards. That is why I am curious if this algorithm is indeed very efficient. I have not had any experience with any other PI calculating programs.
If you can answer one of the above questions, but not the other, I will post a separate question worth 50 points. If you can help with both, I will give you 100. Thank you!