问题

大整数相乘

思路说明

对于大整数计算，一般都要用某种方法转化，否则会溢出。但是python无此担忧了。 Python支持“无限精度”的整数， 一般情况下不用考虑整数溢出的问题，而且Python Int类型与任意精度的Long整数类可以无缝转换，超过Int 范围的情况都将转换成Long类型。例如：

  1. >>> 2899887676637907866*1788778992788348277389943
    2.   3. 5187258157415700236034169791337062588991638L

注意：前面的“无限精度”是有引号的。事实上也是有限制的，对于32位的机器，其上限是：2^32-1。真的足够大了。为什么Python能够做到呢？请有兴趣刨根问底的去看Python的有关源码。本文不赘述。在其它语言中，通常用“分治法”解决大整数相乘问题。但是，这里提供一个非常有意思的计算两个整数相乘的方法，算是做为大整数相乘的演示。两个整数相乘：阿拉伯乘法 。关于这个乘法的详细描述，请看：http://ualr.edu/lasmoller/medievalmult.html

解决（Python）

  1. #!/usr/bin/env python
    2. #coding:utf-8
    3.   4. #阿拉伯乘法
    5. def arabic_multiplication(num1,num2):
    6.     num_lst1 = [int(i) for i in str(num1)]  #将int类型的123，转化为list类型的[1,2,3]，每个元素都是int类型
    7.     num_lst2 = [int(i) for i in str(num2)]
    8.   9.     #两个list中整数两两相乘
    10.     int_martix = [[i*j for i in num_lst1] for j in num_lst2]
    11.   12.     #将上述元素为数字的list转化为元素类型是str，主要是将9-->'09'
    13.     str_martix = [map(convert_to_str,int_martix[i]) for i in range(len(int_martix))]
    14.   15.     #将上述各个list中的两位数字分开：['01','29','03']-->[0,2,0],[1,9,3]
    16.     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)]
    17.   18.     #计算阿拉伯乘法表的左侧开始各项和
    19.     sum_left = summ_left(martix)
    20.   21.     #计算阿拉伯乘法表的底部开始各项和
    22.     sum_end = summ_end(martix)
    23.   24.     #将上述两个结果合并后翻转
    25.     sum_left.extend(sum_end)
    26.     sum_left.reverse()
    27.   28.     #取得各个和的个位的数字（如果进位则加上）
    29.     result = take_digit(sum_left)
    30.   31.     #翻转结果并合并为一个结果字符串数值
    32.     result.reverse()
    33.     int_result = "".join(result)
    34.     print "%d*%d="%(num1,num2)
    35.     print int_result
    36.   37.   38. #将int类型转化为str类型，9-->'09'
    39.   40. def convert_to_str(num):
    41.     if num<10:
    42.         return "0"+str(num)
    43.     else:
    44.         return str(num)
    45.   46.   47. #计算阿拉伯乘法表格左侧开始的各项之和
    48.   49. def summ_left(lst):
    50.     summ = []
    51.     x = [i for i in range(len(lst))]
    52.     y = [j for j in range(len(lst[0]))]
    53.     sx = [i for i in x if i%2==0]
    54.     for i in sx:
    55.         s=0
    56.         j=0
    57.         while i>=0 and j<=y[-1]:
    58.             s = s+ lst[i][j]
    59.             if i%2==1:
    60.                 j = j+1
    61.             else:
    62.                 j = j
    63.             i = i-1
    64.         summ.append(s)
    65.     return summ
    66.   67.   68.   69. #计算阿拉伯乘法表格底部开始的各项之和
    70.   71. def summ_end(lst):
    72.     summ=[]
    73.     y = [j for j in range(len(lst[0]))]
    74.     ex = len(lst)-1
    75.     for m in range(len(y)):
    76.         s = 0
    77.         i=ex
    78.         j=m
    79.         while i>=0 and j<=y[-1]:
    80.             s= s+lst[i][j]
    81.             if i%2==1:
    82.                 j = j+1
    83.             else:
    84.                 j=j
    85.             i = i-1
    86.         summ.append(s)
    87.   88.     return summ
    89.   90. #得到各个元素的个位数，如果是大于10则向下一个进位
    91.   92. def take_digit(lst):
    93.     tmp = 0
    94.     digit_list = []
    95.     for m in range(len(lst)):
    96.         lstm = 0
    97.         lstm = lst[m]+tmp
    98.         if lstm<10:
    99.             tmp = 0
    100.             digit_list.append(str(lstm))
    101.         else:
    102.             tmp = lstm/10
    103.             mm = lstm-tmp*10
    104.             digit_list.append(str(mm))
    105.     return digit_list
    106.   107.   108. if __name__=="__main__":
    109.     arabic_multiplication(469,37)

联系方法

整理人：豆包AI助手

用阿拉伯乘法解决大整数相乘问题

问题

思路说明

解决（Python）

联系方法