python里大整数相乘相关技巧指南
问题
大整数相乘
思路说明
对于大整数计算，一般都要用某种方法转化，否则会溢出。但是python无此担忧了。
Python支持“无限精度”的整数，一般情况下不用考虑整数溢出的问题，而且PythonInt类型与任意精度的Long整数类可以无缝转换，超过Int范围的情况都将转换成Long类型。
例如：
>>>2899887676637907866*1788778992788348277389943 5187258157415700236034169791337062588991638L
注意：前面的“无限精度”是有引号的。事实上也是有限制的，对于32位的机器，其上限是：2^32-1。真的足够大了。
为什么Python能够做到呢？请有兴趣刨根问底的去看Python的有关源码。本文不赘述。
在其它语言中，通常用“分治法”解决大整数相乘问题。
但是，这里提供一个非常有意思的计算两个整数相乘的方法，算是做为大整数相乘的演示。
两个整数相乘：阿拉伯乘法。关于这个乘法的详细描述，请看：http://ualr.edu/lasmoller/medievalmult.html
解决（Python）
#!/usr/bin/envpython #coding:utf-8 #阿拉伯乘法 defarabic_multiplication(num1,num2): num_lst1=[int(i)foriinstr(num1)]#将int类型的123，转化为list类型的[1,2,3]，每个元素都是int类型 num_lst2=[int(i)foriinstr(num2)] #两个list中整数两两相乘 int_martix=[[i*jforiinnum_lst1]forjinnum_lst2] #将上述元素为数字的list转化为元素类型是str，主要是将9-->'09' str_martix=[map(convert_to_str,int_martix[i])foriinrange(len(int_martix))] #将上述各个list中的两位数字分开：['01','29','03']-->[0,2,0],[1,9,3] martix=[[int(str_martix[i][j][z])forjinrange(len(str_martix[i]))]foriinrange(len(str_martix))forzinrange(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) printint_result #将int类型转化为str类型，9-->'09' defconvert_to_str(num): ifnum<10: return"0"+str(num) else: returnstr(num) #计算阿拉伯乘法表格左侧开始的各项之和 defsumm_left(lst): summ=[] x=[iforiinrange(len(lst))] y=[jforjinrange(len(lst[0]))] sx=[iforiinxifi%2==0] foriinsx: s=0 j=0 whilei>=0andj<=y[-1]: s=s+lst[i][j] ifi%2==1: j=j+1 else: j=j i=i-1 summ.append(s) returnsumm #计算阿拉伯乘法表格底部开始的各项之和 defsumm_end(lst): summ=[] y=[jforjinrange(len(lst[0]))] ex=len(lst)-1 forminrange(len(y)): s=0 i=ex j=m whilei>=0andj<=y[-1]: s=s+lst[i][j] ifi%2==1: j=j+1 else: j=j i=i-1 summ.append(s) returnsumm #得到各个元素的个位数，如果是大于10则向下一个进位 deftake_digit(lst): tmp=0 digit_list=[] forminrange(len(lst)): lstm=0 lstm=lst[m]+tmp iflstm<10: tmp=0 digit_list.append(str(lstm)) else: tmp=lstm/10 mm=lstm-tmp*10 digit_list.append(str(mm)) returndigit_list if__name__=="__main__": arabic_multiplication(469,37)