[ create a new paste ] login | about

Link: http://codepad.org/kWVLtEjL    [ raw code | fork ]

C, pasted on Nov 7:
#include <stdio.h>
#include <string.h>

#define MBI_DATA_NUM 10001

typedef struct tag_mbi_t
{
	unsigned short data[MBI_DATA_NUM];
	int top;
}mbi_t;


void mbi_zero(mbi_t *mbi)
{
	memset(mbi, 0, sizeof(mbi_t));
}


void mbi_copy(mbi_t *a, const mbi_t *b)
{
	memcpy(a, b, sizeof(mbi_t));
}


// !注意! アドレス r==a または r==b が成り立つときはうまく計算できません
void mbi_mul(mbi_t *r, const mbi_t *a, const mbi_t *b)
{
	int i, j, j_max=0;
	long temp, carry;

	mbi_zero(r);
	for(i=0;i<=b->top;i++)
	{
		j_max=MBI_DATA_NUM-1-i;
		if(j_max>a->top) j_max=a->top;

		carry=0;
		for(j=0;j<=j_max;j++)
		{
			temp=carry+a->data[j]*b->data[i]+r->data[i+j];
			r->data[i+j]=temp%10000;
			carry=temp/10000;
		}
		for(;carry && i+j<MBI_DATA_NUM;j++)
		{
			temp=carry+r->data[i+j];
			r->data[i+j]=temp%10000;
			carry=temp/10000;
		}
		r->top=i+j-1;
	}
	for(i=r->top;i>0;i--)
	{
		if(r->data[i]) break;
	}
	r->top=i;
}


void mbi_print(const mbi_t *mbi)
{
	int i;

	i=mbi->top;
	printf("%d", mbi->data[i]);
	for(i--;i>=0;i--)
	{
		printf("%04d", mbi->data[i]);
	}
	printf("\n");
}


int main(void)
{
	static mbi_t result, base, temp;
	int m=10000, n=10000;

	base.data[0]=m;
	result.data[0]=1;
	for(;n>0;n>>=1)
	{
		if(n & 1)
		{
			mbi_copy(&temp, &result);
			mbi_mul(&result, &temp, &base);
		}
		mbi_copy(&temp, &base);
		mbi_mul(&base, &temp, &temp);
	}
	mbi_print(&result);

	return 0;
}


Create a new paste based on this one


Comments: