Guide to multiplying large integers in python

For large integer calculations, they generally need to be converted in some way, otherwise they will overflow. But python has no such worries. Python supports "infinite precision" integers. Generally, there is no need to consider the problem of integer overflow. Moreover, the Python Int type and the Long integer class of arbitrary precision can be seamlessly converted. Anything exceeding the range of Int will be converted to the Long type.

Problem

Multiplication of large integers

Idea description

For large integer calculations, it is generally necessary to use some method to convert, otherwise it will overflow. But python has no such worries.

Python supports "infinite precision" integers. Generally, there is no need to consider the problem of integer overflow. Moreover, the Python Int type and the Long integer class of arbitrary precision can be seamlessly converted. Anything exceeding the range of Int will be converted into Long type.

For example:

>>> 2899887676637907866*1788778992788348277389943
5187258157415700236034169791337062588991638L

Note: The previous "infinite precision" is in quotation marks. In fact, there are limits. For 32-bit machines, the upper limit is: 2^32-1. It's really big enough.

Why can Python do it? Please check out the relevant source code of Python if you are interested in getting to the bottom of it. This article will not go into details.

In other languages, the "divide and conquer" method is usually used to solve the multiplication problem of large integers.

However, here is a very interesting method of calculating the multiplication of two integers, which can be used as a demonstration of the multiplication of large integers.

Multiplication of two integers: Arabic multiplication. For a detailed description of this multiplication, please see: http://www.php.cn/

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

The above is the detailed content of Guide to multiplying large integers in python. For more information, please follow other related articles on the PHP Chinese website!