Guide pour multiplier de grands entiers en Python

Pour les calculs de grands nombres entiers, ils doivent généralement être convertis d'une manière ou d'une autre, sinon ils déborderont. Mais python n'a pas de tels soucis. Python prend en charge les entiers de « précision infinie ». Généralement, il n'est pas nécessaire de considérer le problème du dépassement d'entier. De plus, le type Python Int et la classe d'entiers longs de précision arbitraire peuvent être convertis de manière transparente. au type Long.

Problème

Multiplication de grands entiers

Explication des idées

Pour les calculs de grands entiers, il est généralement nécessaire d'utiliser une méthode de conversion, sinon cela va déborder. Mais python n'a pas de tels soucis.

Python prend en charge les entiers à « précision infinie ». Généralement, il n'est pas nécessaire de considérer le problème du débordement d'entier. De plus, le type Python Int et la classe entière Long de précision arbitraire peuvent être convertis de manière transparente. La plage de Int sera convertie en type Long.

Par exemple :

>>> 2899887676637907866*1788778992788348277389943
5187258157415700236034169791337062588991638L

Remarque : La "précision infinie" précédente est entre guillemets. En fait, il y a des limites pour les machines 32 bits, la limite supérieure est : 2^32-1. C'est vraiment assez grand.

Pourquoi Python peut-il le faire ? Veuillez consulter le code source pertinent de Python si vous souhaitez en savoir plus. Cet article n'entrera pas dans les détails.

Dans d'autres langues, la méthode « diviser pour mieux régner » est généralement utilisée pour résoudre des problèmes de multiplication de grands nombres entiers.

Voici cependant une méthode très intéressante de calcul de la multiplication de deux entiers, qui peut servir de démonstration de la multiplication de grands entiers.

Multiplication de deux entiers : multiplication arabe. Pour une description détaillée de cette multiplication, veuillez consulter : http://www.php.cn/

Solve (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)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!