大数运算

基于内存的有效运用，程序语言中规定了各种不同的数据类型，因此变量所可以表达的最大整数受到限制，例如123456789123456789这样的数就不可能存储在long型的变量当中（例如c/c++），我们称大数运算。

解法
一个变量无法表示超长整数，则就使用多个变量，当然这使用数组最为方便，假设程序语言的最大数据类型可以存储至65535的数好了，为了计算方便及符合使用十进制的习惯，让每一个数组元素可以存储四个位数，也就是0到9999的数，例如：


像300！这样的数（当然在Ruby中不存在问题，在其他的语言中可能就存在问题，这里主要是想说明这个方法），解法就是使用程序中的乘法函数，至于要算到多大，就看需要

require 'mathn'
class BigNumber

    def self.add(a,b)
    carry=0
    c=[0]*a.size
    t=(a.size-1)
  until t==-1
      c[t]=a[t]+b[t]+carry
      if(c[t]<10000)
        carry=0
      else
        c[t]-=10000
        carry=1
      end
      t-=1
  end
    c
  end

  def self.subtract(a,b)
     borrow=0
    c=[0]*a.size
    t=a.size-1
    until t==-1
      c[t]=a[t]-b[t]-carry
      if(c[t]>=0)
        borrow=0
      else
        c[t]+=10000
        borrow=1
      end
      t-=1
    end
    c
  end


  def self.multiply(a,b)

    borrow=0
    c=[0]*a.size
    t=a.size-1
   until t==-1
      tmp=a[t]*b+carry
      c[t]=tmp % 10000
      carry=tmp / 10000
      t-=1
  end
    c
  end

  def self.divide(a,b)
    remain=0
    c=[0]*(a.size)
    t=a.size-1
   until t==-1
      tmp=a[t]+remain
      c[t]=tmp / b
      remain=(tmp%b) * 10000
      t-=1
    end
    c
  end
end

a = [1234, 5678, 9910, 1923, 1124]
b = [1234, 5678, 9910, 1923, 1124]

c = BigNumber.add(a, b)
p c
for i in 0..(c.size-1)
  print c[i]
end

评论

2 楼 googya 2009-11-06  

貌似乘法 除法的程序写的不正确哦

1 楼 googya 2009-11-06  

自己先顶一个！
这里的循环使用的是until，本想使用range的，可是range不支持由大到小的范围，后来试了一下downto，好像又有点问题。所以就用了until，这个其实也很不错的。不过就是要注意它的结束条件，否则很容易出错