Coding Challenge I

Pages: 1 2 3 4 5 6 7 8 9

Solution from TE

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

/*
  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 < alength; ++i)
        a[i] = 2;

    for (j = 0; j < numdigits; ++j)
    {
        unsigned int q = 0;
        unsigned int p = 2 * alength – 1;
        for (i = alength; –i >= 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 <= 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 <= 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 <= 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 > 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 < 2000)
			{
			printf(“\n”);
			puts(pi);
			}

    free(pi);

    return 0;
}

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

Discuss (16 comments)