Python での大きな整数の乗算に関連するテクニックのガイド-Python チュートリアル-php.cn

Python での大きな整数の乗算に関連するテクニックのガイド

WBOY

リリース： 2016-06-16 08:42:03

オリジナル

1261 人が閲覧しました

質問

大きな整数の乗算

アイデアの説明

大きな整数の計算の場合、通常、何らかの方法で変換する必要があります。変換しないとオーバーフローします。しかし、Python にはそのような心配はありません。

Python は「無限精度」の整数をサポートしており、通常、整数のオーバーフローの問題を考慮する必要はありません。また、Python の Int 型と任意精度の Long 整数クラスは、Int の範囲を超えるものはすべてシームレスに変換できます。 Long型に変換されます。

例:

>>> 2899887676637907866*1788778992788348277389943

5187258157415700236034169791337062588991638L

ログイン後にコピー

注: 前述の「無限の精度」は引用符で囲まれています。実際、32 ビットマシンの場合、上限は 2^32-1 です。本当に十分な大きさです。

なぜ Python でそれができるのでしょうか? Python の詳細に興味がある場合は、Python の関連ソースコードをチェックしてください。この記事では詳細には触れません。

他の言語では、通常、大きな整数の乗算の問題を解決するために「分割統治」法が使用されます。

しかし、ここでは 2 つの整数の乗算を計算する非常に興味深い方法を紹介します。これは、大きな整数の乗算のデモンストレーションとして使用できます。

2 つの整数の乗算: アラビア語の乗算。この乗算の詳細については、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类型的123，转化为list类型的[1,2,3]，每个元素都是int类型
  num_lst2 = [int(i) for i in str(num2)]

  #两个list中整数两两相乘
  int_martix = [[i*j for i in num_lst1] for j in num_lst2]

  #将上述元素为数字的list转化为元素类型是str，主要是将9-->'09'
  str_martix = [map(convert_to_str,int_martix[i]) for i in range(len(int_martix))]

  #将上述各个list中的两位数字分开：['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)]

  #计算阿拉伯乘法表的左侧开始各项和
  sum_left = summ_left(martix)

  #计算阿拉伯乘法表的底部开始各项和
  sum_end = summ_end(martix)

  #将上述两个结果合并后翻转
  sum_left.extend(sum_end)
  sum_left.reverse()

  #取得各个和的个位的数字（如果进位则加上）
  result = take_digit(sum_left)

  #翻转结果并合并为一个结果字符串数值
  result.reverse()
  int_result = "".join(result)
  print "%d*%d="%(num1,num2)
  print int_result

#将int类型转化为str类型，9-->'09'

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

#计算阿拉伯乘法表格左侧开始的各项之和

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

#计算阿拉伯乘法表格底部开始的各项之和

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

#得到各个元素的个位数，如果是大于10则向下一个进位

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)

ログイン後にコピー