探寻C/C++中更快的大数(自然数集)模板 - c++编程基础

gn operator * (const bign &b) { bign c;c.len=len+b.len; for (int i=0;i =0) g=0; else { g=1; x+=mod; } c.s[c.len++]=x; } c.clean(); return c; } bool operator < (const bign &b)const { if (len!=b.len) return len (const bign &b)const { return b<*this; } bool operator <= (const bign &b)const { return !(b>*this); } bool operator >= (const bign &b)const { return !(b<*this); } bool operator == (const bign &b)const { if (len!=b.len) return false; for (int i=0;i

修改对拍代码，发现使用压8位的long long 版大数从性能上确实要优于压4位的int版大数，虽然int版偶尔会稍快于long long版，但平均性能上long long版要比int版快20%~60%(包括IO)

数据生成代码：

#
#
# Author : fcbruce 
                                              
                                               
#
# Time : Fri 24 Oct 2014 06:33:17 PM CST
#
#

import random

T_T=100000
print T_T
for i in xrange(T_T):
  a=random.randint(0,1237648236422345678987655432349875934875632123131523784682932317237132418743972317);
  b=random.randint(0,12345678987623463824593658235543232123131238746239523172371376382423749824172324317);
  print a+b,a

标程代码：

#
#
# Author : fcbruce 
                                              
                                               
#
# Time : Fri 24 Oct 2014 06:38:52 PM CST
#
#

n=input()

for i in xrange(n):
  a,b=map(int,raw_input().split())
  print a+b,a-b,a*b

对拍代码：

#!/bin/bash
#
# Author : fcbruce 
                                              
                                               
#
# Time : Fri 24 Oct 2014 07:01:27 PM CST
#
#
while true; do
  python data.py > input
  python std.py < input > std_output

  begin_time_int=$(date "+%s%N")
  ./bign_int < input >bign_int_output
  end_time_int=$(date "+%s%N") 
  
  begin_time_longlong=$(date "+%s%N")
  ./bign_longlong < input >bign_longlong_output
  end_time_longlong=$(date "+%s%N") 

  use_time_int=$(expr $end_time_int - $begin_time_int)
  use_time_longlong=$(expr $end_time_longlong - $begin_time_longlong)

  echo "bign int"
  diff std_output bign_int_output 
  if [ $? -ne 0 ]; then 
    echo "Wrong Answer"
    break;
  else
    echo "Accepted"
    echo "run time : " $use_time_int
  fi

  echo

  echo "bign long long"
  diff std_output bign_longlong_output 
  if [ $? -ne 0 ]; then 
    echo "Wrong Answer"
    break;
  else
    echo "Accepted"
    echo "run time : " $use_time_longlong
  fi

  echo

  test $use_time_longlong -lt $use_time_int 
  if [ $? -ne 0 ] ; then
    echo "int faster"
  else
    echo "long long faster"
  fi

  echo
  echo

done

部分测试结果（运行时间单位：十亿分之一秒，测试环境：ubuntu10.04 ,编译开O2优化，gnu++0x，主频：2.26GHz × 2 ）：

参考资料：

《算法竞赛入门经典》―― 刘汝佳

探寻C/C++中更快的大数(自然数集)模板(二)