快捷導(dǎo)航

python里大整數(shù)相乘相關(guān)技巧指南

更新時(shí)間：2014年09月12日 11:05:04 投稿：hebedich

對(duì)于大整數(shù)計(jì)算，一般都要用某種方法轉(zhuǎn)化，否則會(huì)溢出。但是python無(wú)此擔(dān)憂了。Python支持“無(wú)限精度”的整數(shù)，一般情況下不用考慮整數(shù)溢出的問(wèn)題，而且Python Int類(lèi)型與任意精度的Long整數(shù)類(lèi)可以無(wú)縫轉(zhuǎn)換，超過(guò)Int 范圍的情況都將轉(zhuǎn)換成Long類(lèi)型。

問(wèn)題

大整數(shù)相乘

思路說(shuō)明

對(duì)于大整數(shù)計(jì)算，一般都要用某種方法轉(zhuǎn)化，否則會(huì)溢出。但是python無(wú)此擔(dān)憂了。

Python支持“無(wú)限精度”的整數(shù)，一般情況下不用考慮整數(shù)溢出的問(wèn)題，而且Python Int類(lèi)型與任意精度的Long整數(shù)類(lèi)可以無(wú)縫轉(zhuǎn)換，超過(guò)Int 范圍的情況都將轉(zhuǎn)換成Long類(lèi)型。

例如：

>>> 2899887676637907866*1788778992788348277389943

5187258157415700236034169791337062588991638L

注意：前面的“無(wú)限精度”是有引號(hào)的。事實(shí)上也是有限制的，對(duì)于32位的機(jī)器，其上限是：2^32-1。真的足夠大了。

為什么Python能夠做到呢？請(qǐng)有興趣刨根問(wèn)底的去看Python的有關(guān)源碼。本文不贅述。

在其它語(yǔ)言中，通常用“分治法”解決大整數(shù)相乘問(wèn)題。

但是，這里提供一個(gè)非常有意思的計(jì)算兩個(gè)整數(shù)相乘的方法，算是做為大整數(shù)相乘的演示。

兩個(gè)整數(shù)相乘：阿拉伯乘法。關(guān)于這個(gè)乘法的詳細(xì)描述，請(qǐng)看：http://ualr.edu/lasmoller/medievalmult.html

解決（Python）

#!/usr/bin/env python
#coding:utf-8

#阿拉伯乘法
def arabic_multiplication(num1,num2):
  num_lst1 = [int(i) for i in str(num1)] #將int類(lèi)型的123，轉(zhuǎn)化為list類(lèi)型的[1,2,3]，每個(gè)元素都是int類(lèi)型
  num_lst2 = [int(i) for i in str(num2)]

  #兩個(gè)list中整數(shù)兩兩相乘
  int_martix = [[i*j for i in num_lst1] for j in num_lst2]

  #將上述元素為數(shù)字的list轉(zhuǎn)化為元素類(lèi)型是str，主要是將9-->'09'
  str_martix = [map(convert_to_str,int_martix[i]) for i in range(len(int_martix))]

  #將上述各個(gè)list中的兩位數(shù)字分開(kāi)：['01','29','03']-->[0,2,0],[1,9,3]
  martix = [[int(str_martix[i][j][z]) for j in range(len(str_martix[i]))] for i in range(len(str_martix)) for z in range(2)]

  #計(jì)算阿拉伯乘法表的左側(cè)開(kāi)始各項(xiàng)和
  sum_left = summ_left(martix)

  #計(jì)算阿拉伯乘法表的底部開(kāi)始各項(xiàng)和
  sum_end = summ_end(martix)

  #將上述兩個(gè)結(jié)果合并后翻轉(zhuǎn)
  sum_left.extend(sum_end)
  sum_left.reverse()

  #取得各個(gè)和的個(gè)位的數(shù)字（如果進(jìn)位則加上）
  result = take_digit(sum_left)

  #翻轉(zhuǎn)結(jié)果并合并為一個(gè)結(jié)果字符串?dāng)?shù)值
  result.reverse()
  int_result = "".join(result)
  print "%d*%d="%(num1,num2)
  print int_result

#將int類(lèi)型轉(zhuǎn)化為str類(lèi)型，9-->'09'

def convert_to_str(num):
  if num<10:
    return "0"+str(num)
  else:
    return str(num)

#計(jì)算阿拉伯乘法表格左側(cè)開(kāi)始的各項(xiàng)之和

def summ_left(lst):
  summ = []
  x = [i for i in range(len(lst))]
  y = [j for j in range(len(lst[0]))]
  sx = [i for i in x if i%2==0]
  for i in sx:
    s=0
    j=0
    while i>=0 and j<=y[-1]:
      s = s+ lst[i][j]
      if i%2==1:
        j = j+1
      else:
        j = j
      i = i-1
    summ.append(s)
  return summ

#計(jì)算阿拉伯乘法表格底部開(kāi)始的各項(xiàng)之和

def summ_end(lst):
  summ=[]
  y = [j for j in range(len(lst[0]))]
  ex = len(lst)-1
  for m in range(len(y)):
    s = 0
    i=ex
    j=m
    while i>=0 and j<=y[-1]:
      s= s+lst[i][j]
      if i%2==1:
        j = j+1
      else:
        j=j
      i = i-1
    summ.append(s)

  return summ

#得到各個(gè)元素的個(gè)位數(shù)，如果是大于10則向下一個(gè)進(jìn)位

def take_digit(lst):
  tmp = 0
  digit_list = []
  for m in range(len(lst)):
    lstm = 0
    lstm = lst[m]+tmp
    if lstm<10:
      tmp = 0
      digit_list.append(str(lstm))
    else:
      tmp = lstm/10
      mm = lstm-tmp*10
      digit_list.append(str(mm))
  return digit_list

if __name__=="__main__":
  arabic_multiplication(469,37)

您可能感興趣的文章: