问题

大整数相乘

思路说明

对于大整数计算,一般都要用某种方法转化,否则会溢出。但是python无此担忧了。

Python支持“无限精度”的整数,一般情况下不用考虑整数溢出的问题,而且Python Int类型与任意精度的Long整数类可以无缝转换,超过Int 范围的情况都将转换成Long类型。

例如:

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

联系方法