# Coding Challenge I

Pages: 1 2 3 4 5 6 7 8 9

### Solution from TE

```#include &lt;stdlib.h&gt;
#include &lt;stdio.h&gt;

/*
for unknown reasons, MSVC 6 implements div(), using 2 IDIV.

using a single IDIV accelerates ComputePi(10000 digits)
from ~39.5 sec to 24.4. seconds

Yet another meaningless benchmark – 90% of it’s running time
depending on a single (or 2) DIV instructions.

*/

div_t __forceinline __fastcall quick_div(unsigned num, unsigned denom)
{
//	*prem = num % denom;
//	return  num / denom;
__asm {
mov eax, num;
xor edx,edx;
div denom;
// return eax:edx
}
}

void ComputePi(int numdigits, char* pi)
{
int alength = 10 * numdigits / 3;
int* a = (int*) malloc(alength * sizeof(int));
int piLength = 0;
int nines = 0;
int predigit = 0;
int i, j;
for(i = 0; i &lt; alength; ++i)
a[i] = 2;

for (j = 0; j &lt; numdigits; ++j)
{
unsigned int q = 0;
unsigned int p = 2 * alength – 1;
for (i = alength; –i &gt;= 0; )
{
// unsigned int x = 10*a[i] + q*(i+1);

// a[i] = x % p;
// q = x / p;

div_t div_result;

div_result = quick_div( 10*a[i] + q*(i+1), p );

a[i] = div_result.rem;		// x % p;
q    = div_result.quot;		// x / p;

p -= 2;
}

a[0] = q % 10;
q /= 10;
if (q == 9)
++nines;
else if (q == 10)
{
int k;
pi[piLength] = (char) (predigit + 1 + ‘0’);
for (k = 1; k &lt;= nines; ++k)
pi[piLength+k] = ‘0’;
piLength += nines + 1;
predigit = 0;
nines = 0;
}
else
{
int k;
pi[piLength] = (char)(predigit + ‘0’);
predigit = q;
for (k = 1; k &lt;= nines; ++k)
pi[piLength + k] = ‘9’;
piLength += nines + 1;
nines = 0;
}
}
pi[piLength] = (char)(predigit + ‘0’);
pi[piLength+1] = ‘\0’;

free(a);
}

int main(int argc, char** argv)
{
int numdigits;
char* pi;
extern unsigned long __stdcall GetTickCount(void);

unsigned start;

if (argc &lt;= 1)
{
fprintf(stderr, “usage: pi #DIGITS [FILE]”);
return 1;
}

numdigits = atoi(argv[1]);
pi = (char*) malloc(numdigits+2);

start = GetTickCount();

ComputePi(numdigits, pi);

printf(“milliseconds used  – %u\n”, GetTickCount() – start);

if (argc &gt; 2)
{
FILE* fp = fopen(argv[2], “w”);
if (fp == NULL)
{
fprintf(stderr, “Cannot open %s\n”, argv[2]);
return 2;
}
fputs(pi, fp);
fputc(‘\n’, fp);
fclose(fp);
}
else
if (numdigits &lt; 2000)
{
printf(“\n”);
puts(pi);
}

free(pi);

return 0;
}
```

Pages: « Prev   1 2 3 4 5 6 7 8 9   Next »