關於大數相乘,有何有效方法?

Question

假設有兩個數,每一個數的長度都有10000位,要得到這兩個大數相乘的結果,如何去做?
網上有人講用豎式算法,模擬相乘結果,但那樣也是非常之慢
另有人說將這兩個大數理解成兩個n進制的數進行相乘,再結合豎式相乘法,減小循環次數.
第2個方案聽上去好像是可行的,但大數本來是以字符串形式存在的,如何將其轉換為一個n進制的數啊?
有誰對大數相乘有研究,請上來說說,說錯沒有關係.

Answer 1

可以模拟成为2^32位数进行计算。大概的逻辑如下：
设：
  A=Sum[i=0 to p](A[i]*0x100000000**i)
  B=Sum[i=0 to q](B[i]*0x100000000**i)，p>=q
  C=Sum[i=0 to n](C[i]*0x100000000**i)=A*B显然：
  C=Sum[i=0 to q](A*B[i]*0x100000000**i)
  而(A*B[i]*100000000**i)=Sum[j=0 to p](A[j]*B[i]*0x100000000**(i+j))
  所以C=Sum[i=0 to q](Sum[j=0 to p](A[j]*B[i]*0x100000000**(i+j)))因此：
  C[i]=Sum[j=0 to q](A[i-j]*B[j])+carry[i-1]-carry[i]*0x100000000
  其中carry[-1]=0
  carry[i]=(Sum[j=0 to q](A[i-j]*B[j])+carry[i-1])/0x100000000
  n=p+q-1，若carry[n]>0，则n=n+1，C[n]=carry
这种做法的速度是比较快的，我验证过。

Answer 2

字符串转变成大数，也就是用乘法做的，如果字符串是十进制表示的话，先转换成byte[]，然后过程如下：
    输入：str
    X=0
    FOR i=0 TO n
      X=X*10
      X=X+(int)(str[n]-48)
    RETURN X