大数运算求助：如何将一个超长的二进制字符串转换为十进制字符串

ecjtubaowp

回复 10# juffun


    不会啊，后面不是有一个m%=b吗，这么大的数量级就不是考虑什么算法了，而是考虑存储了。

Angus幻灭

做过大的，但是也没这么大的，早溢出了咋办？

juffun

回复 11# ecjtubaowp


    我看了半天也没看明白，能不能大概讲一下思路？

ecjtubaowp

回复 13# juffun


    举个例子吧：二进制字符串为1111

首先要知道一个常识：(a+b)%c=(a%c+b%c)%c;

那就好了

1111=1*2^3+1*2^2+1*2^1+1*2^0

a[1]=1,a[2]=1,a[3]=1,a[4]=1;a[0]=4//长度

对应上面的代码就是

(((m*2+a[1])*2+a[2])*2+a[3])*2+a[4]

后面的m%=b,就是用了上面这个常识。

yulihua49

比如2的2000次方这样数量级的，我想了办天也没想出来，请大家提提思路。
juffun 发表于 2010-11-25 23:04

1. u_int * d_to_b(n,cp,dp)
   
2. u_int n,*dp;
   
3. char *cp;
   
4. {
   
5. char *p;
   
6. u_int num[MAXNUMBER+1];
   
7. u_int tmp[MAXNUMBER+1];
   
8.         n_zero(n,dp);
   
9.         n_zero(n,num);
   
10.         for(p=cp;*p;p++) {
    
11.                 mul1(n,dp,10,tmp);
    
12.                 numcpy(n,dp,tmp);
    
13.                 num[0]=(*p - '0') % 10;
    
14.                 addm(n,dp,num);
    
15.         }
    
16.         return dp;
    
17. }
    
18. 
    
19. char *b_to_d(n,pb,d)
    
20. u_int n,*pb;
    
21. char *d;
    
22. {
    
23. u_int i,*ip0,*ip,*ip1,rem[MAXNUMBER+1],num;
    
24. u_int zero[MAXNUMBER+1];
    
25. u_int tmp[MAXNUMBER+1];
    
26. char *cp;
    
27.         cp=d;
    
28.         i=0;
    
29.         n_zero(n,zero);
    
30.         numcpy(n,tmp,pb);
    
31.         ip0=tmp,ip1=rem;
    
32.         while(numcmp(n,ip0,zero)) {
    
33.                 i++;
    
34.                 num=div1(n,ip0,10,ip1);
    
35.                 ip=ip0;
    
36.                 ip0=ip1;
    
37.                 ip1=ip;
    
38.                 *cp++=num+'0';
    
39.         }
    
40.         if(!i) *cp++='0';
    
41.         *cp=0;
    
42.         return strrevers(d);
    
43. }
    

复制代码

SDBC的大数运算库。

yulihua49

回复  juffun


    举个例子吧：二进制字符串为1111

首先要知道一个常识：(a+b)%c=(a%c+b%c)%c;

...
ecjtubaowp 发表于 2010-11-26 11:05

    m*2 改 m<<1,效率可提高。你这是二进制啊，太费力了。
我上边的例子用了div1,多位数除以1位数的除法，一次处理32bit效率似乎好些。

1. int div1(n,pa,b,pq)
   
2. u_int n,*pa,b,*pq;
   
3. {
   
4. int rem[2];
   
5.         if(b<2) {
   
6.                 if(b==1) numcpy(n,pq,pa);
   
7.                 else n_zero(n,pq);
   
8.                 return 0;
   
9.         }
   
10.         rem[0]=rem[1]=0;
    
11.         do {
    
12.                 n--;
    
13.                 rem[0]=pa[n];
    
14.                 rem[1]=diva(rem,b,pq+n);
    
15.         } while(n);
    
16.         return rem[1];
    
17. }
    

复制代码

里边用到单除法，在intel机器上，可以用asm做，一条指令得到余数和商，效率较高：64位汇编哦！

1.         .file   "diva.c"
   
2.         .text
   
3.         .p2align 4,,15
   
4. /*
   
5. unsigned long diva(unsigned long a[2],unsigned long c,unsigned long *rem);
   
6. */
   
7. .globl diva
   
8.         .type   diva, @function
   
9. diva64:
   
10. .LFB2:
    
11.         movq    (%rdi), %rax
    
12.         movq    %rdx, %r8
    
13.         movq    8(%rdi), %rdx
    
14.         divq    %rsi
    
15.         movq    %rdx, (%r8)
    
16.         ret
    
17. .LFE2:
    
18.         .size   diva, .-diva
    
19.         .section        .eh_frame,"a",@progbits
    
20. .Lframe1:
    
21.         .long   .LECIE1-.LSCIE1
    
22. .LSCIE1:
    
23.         .long   0x0
    
24.         .byte   0x1
    
25.         .string "zR"
    
26.         .uleb128 0x1
    
27.         .sleb128 -8
    
28.         .byte   0x10
    
29.         .uleb128 0x1
    
30.         .byte   0x3
    
31.         .byte   0xc
    
32.         .uleb128 0x7
    
33.         .uleb128 0x8
    
34.         .byte   0x90
    
35.         .uleb128 0x1
    
36.         .align 8
    
37. .LECIE1:
    
38. .LSFDE1:
    
39.         .long   .LEFDE1-.LASFDE1
    
40. .LASFDE1:
    
41.         .long   .LASFDE1-.Lframe1
    
42.         .long   .LFB2
    
43.         .long   .LFE2-.LFB2
    
44.         .uleb128 0x0
    
45.         .align 8
    
46. .LEFDE1:
    
47.         .ident  "GCC: (GNU) 4.1.2 20070115 (prerelease) (SUSE Linux)"
    
48.         .section        .note.GNU-stack,"",@progbits
    

复制代码

如果想可移植，可以用这个，效率稍差：

1. int diva(pa,b,pq)
   
2. u_int *pa,b,*pq;
   
3. {
   
4. unsigned long long tp,d,q;
   
5.         tp=((long long)pa[1])<<32;
   
6.         tp += 0XFFFFFFFF & pa[0];
   
7.         d=b;
   
8.         q=tp/d;
   
9.         *pq=q&0xFFFFFFFF;
   
10.         q=tp%d;
    
11.         return (u_int)q;
    
12. }
    

复制代码

ecjtubaowp

回复 16# yulihua49


    呵呵，优化肯定是有的，我这是最简单的例子了。