网站 › 『 编程之美 』 › 关于大数乘法

Nisy 发表于 2009-9-22 00:48:42

关于大数乘法

.

学习下小齐的代码 简单的雷构一个

纯模拟乘法运算了 未作任何优化

该雷人的代码仅作抛砖引玉 欢迎大家一起分享一些源码 共同提高

#include <string.h>
#include <stdlib.h>
#define MAX 100000

int main(int argc, char* argv[])
{
        void ShowNum(int * num,int len);
        int * num = (int *)malloc(sizeof(int)*100);
        memset(num,0,sizeof(int)*100);
        int len = num = 1;       
        for(int i=2;i<=100;i++)
        {
                int temp = 0;
                for(int j=0;j<len;j++)
                {
                        num = num*i + temp;
                        temp = num / MAX;
                        num %= MAX;
                }
                num += temp;
                if(num)
                        len++;
        }
        ShowNum(num,len);
        return 0;
}

void ShowNum(int * num,int len)
{
        if(!num)len--;
        printf("%d",num);
        len--;
        for(int k=len;k>=0;k--)
        {
                printf("%05d",num);
        }
        printf("\r\n");
}

Nisy 发表于 2009-9-22 00:50:27

经小齐授权 发一份小齐写的算法含部分优化（10倍数）的代码

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <windows.h>
#define MAX 100000

int condition(int n)
{
    if (n < 1)
    {
      printf("对不起，程序计算的范围之内 !\r\n") ;
      return 0;
    }
   
    if (n > 20000)
    {
      printf("别玩了，这么大的数算来也没什么用呀！\r\n") ;
      return 0;
    }
    return 1;
}

// count 后面零的个数
void display(int *p, int len, int count)
{
    int   i = len - 1;
    printf("%d", *(p+i)) ;
    for (i--; i >= 0; --i)
    {
      printf("%05d", *(p+i));
    }
    for (i = 0; i < count; ++i)
    {
      printf("0") ;
    }
    printf("\r\n");
}


int getLen(int n)
{
    int   i,
            len ;
    doublebit = 1.0 ;
   
    for (i = 1; i <= n ; ++i)
    {
      bit += log10(i) ;
    }
    // 一位整形保存5位，所以除5,多加二位，防止溢出
    len = (int)bit / 5 + 2;
    return len ;
}

void compute(int n)
{
    int   i ,
            j ,
            k,
            len,
            size,
            count,
            state;
    int   *p ;
    DWORD   begin = GetTickCount() ;
   
    size = getLen(n) ;
    p = (int *)malloc(sizeof(int)*size) ;
    memset(p, 0, sizeof(int)*size) ;
    p = len = 1 ;
    count = 0;
    //state = 0 ;
    begin = GetTickCount() ;
    for (i = 2; i <= n; ++i)
    {
      // 优化10的倍数,如果是10的话，不参加运算，直接count+1
      // 也可以自己取出2、5来配对减少乘的次数
      state = 0;
      for (k = i; k % 10 == 0 && k >= 10; k /= 10)
      {
            ++count ;
      }
      if (k == 1)
      {
            continue;
      }
      for (j = 0; j < len; ++j)
      {
            p = p * k + state;
            state = p / MAX ;
            p %= MAX ;
      }
      p += state ;
      if (p)
      {
            ++len;
      }
      if (len >= size)
      {
            printf("OverFlow!\r\n") ;
            return ;
      }
    }
    display(p, len, count) ;
    free(p) ;
    printf("used time: %ld ms\r\n", (GetTickCount() - begin)) ;
}

int main(int argc, char **argv)
{
    int n;
   
    while (scanf("%d", &n) > 0 && condition(n) == 1)
    {
      compute(n) ;
    }
    return 0;
}

ttdsxf 发表于 2009-9-22 12:02:37

查看完整版本: 关于大数乘法