一道高精度计算题

网友Mutalisk给的一道题目,
计算 (1+2^0)*(1+2^1)*(1+2^2)…(1+2^32)

今晚赶回家了,花了几十分钟写好了代码,计算结果和Mutalisk的一样。运行时间为10毫秒,当然,是在我PIII 900Mhz的机子上,基本上一闪就出结果。
我的结果是160位,
41900194778866063098
69616409977680717118
75372548418310142014
25167533420258842344
35351687855236795051
88646940175563375578
68147135401121187966
16074978167792968750

源代码下载
 


内容:

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

struct big_number{
	int d[64];	// 4*64 256λ
	int len;
}exp2[40], ans;


void print( big_number & b )
{
	int i, j;
	for( i=b.len-1; i>=0; i-- ){
		for( j=1000; j>=1; j/=10 )
			if( !(i==b.len-1 && j>1 && b.d[i]<j ) )
				printf("%d", (b.d[i]/j)%10 );
	}
}

void mul( big_number & b, int a )
{
	int i, r;
	r = 0;
	for( i=0; i<b.len; i++ ){
		r = r + b.d[i] * a;
		b.d[i] = r % 10000;
		r /= 10000;
	}
	//ÏÂÃæÑ­»·¿ÉÒÔÓÅ»¯
	while( r>0 ){
		b.d[b.len++] = r % 10000;
		r /= 10000;
	}
}

void mul2( big_number &a, big_number &b )
{
	int i, j, k, p, r;
	big_number c;	//result
	memset( &c, 0, sizeof(c) );
	for( i=0; i<b.len; i++ ){
		p = b.d[i];
		for( k=0, j=i, r=0; k<a.len; k++, j++ ){
			r = r + a.d[k] * p + c.d[j];
			c.d[j] = r % 10000;
			r /= 10000;
		}
		//ÏÂÃæÑ­»·¿ÉÒÔÓÅ»¯È¥µô
		while( r>0 ){
			r = c.d[j] + r;
			c.d[j] = r % 10000;
			r /= 10000;
			j ++;
		}
		c.len = j;
	}
	a = c;
}

void add( big_number & a, big_number & b )
{
	int i, r;
	r = 0;
	a.len = a.len<b.len ? b.len : a.len;
	for( i=0; i<a.len; i++ ){
		r = r + a.d[i] + b.d[i];
		a.d[i] = r % 10000;
		r /= 10000;
	}
	//ÏÂÃæÒ»²œ¿ÉÒÔÓÅ»¯
	while( r>0 ){
		a.d[a.len++] = r % 10000;
		r /= 10000;
	}
}

int is_bigger( big_number & a, big_number & b )
{
	if( a.len > b.len )
		return 1;
	else if( a.len < b.len )
		return 0;
	int i;
	for( i=a.len-1; i>=0; i-- ){
		if( a.d[i] > b.d[i] )
			return 1;
		else if( a.d[i] < b.d[i] )
			return 0;
	}
	return 0;
}

//ŒÆËã2µÄ·œ
void prepare()
{
	int i,j;
	memset( &exp2[0], 0, sizeof(big_number) );
	exp2[0].d[0] = 1;
	exp2[0].len = 1;
	for( i=1; i<=32; i++ ){
		exp2[i] = exp2[i-1];
		add( exp2[i], exp2[i-1] ); //ŒÓ·š±È³Ë·š¿ì
		//mul( exp2[i], 2 );
	}
}

//ŒÆËã (1+2^0)*(1+2^1)*(1+2^2)...(1+2^32)
void work()
{
	int i;
	big_number t;
	memset( &ans, 0, sizeof(ans) );
	memset( &t, 0, sizeof(t) );
	t.d[0] = 1;
	t.len = 1;
	ans.d[0] = 1;
	ans.len = 1;
	for( i=0; i<=32; i++ ){
		add( exp2[i], t );	// + 1
		mul2( ans, exp2[i] );
	}
	print( ans );
}

int main()
{
	int n=GetTickCount();
	prepare();
	work();
	printf("\nTime used: %dmm\n", GetTickCount()-n );
	system("pause");
	return 0;
}


一道高精度计算题》有16个想法

  1. Mutalisk

    哈哈,还是你的方法好啊。家里的机器的浏览器好像有问题,你的文章都看不全,只能看一小半

    回复
  2. Mutalisk

    比起你的来,我的那个就太冗余了,400+行代码。

    虽然也只用了16ms。但是毕竟我的机器比较好

    回复
  3. me

    struct big_number{
    int d[64]; // 4*64 256位
    int len;
    }exp2[40], ans
    从这里可以看出ans最大表示2^256-1的数。但是(1+2^0)*(1+2^1)*(1+2^2)…(1+2^32) > (2^0)*(2^1)*(2^2)…(2^32)=2^(32*33/2)=2^528.

    回复
  4. weeklybuilds

    阿阿。菜鸟我也边学边写个python的,看来结果和你一样的,写对了

    hp@debian:~/Desktop$ time python ./aa.py
    4190019477886606309869616409977680717118753725484183101420142516753342025884234435351687855236795051886469401755633755786814713540112118796616074978167792968750

    real 0m0.019s
    user 0m0.016s
    sys 0m0.004s

    回复

回复 me 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据