python里大整數(shù)相乘相關(guān)技巧指南
問題
大整數(shù)相乘
思路說明
對于大整數(shù)計算,一般都要用某種方法轉(zhuǎn)化,否則會溢出。但是python無此擔憂了。
Python支持“無限精度”的整數(shù),一般情況下不用考慮整數(shù)溢出的問題,而且Python Int類型與任意精度的Long整數(shù)類可以無縫轉(zhuǎn)換,超過Int 范圍的情況都將轉(zhuǎn)換成Long類型。
例如:
>>> 2899887676637907866*1788778992788348277389943 5187258157415700236034169791337062588991638L
注意:前面的“無限精度”是有引號的。事實上也是有限制的,對于32位的機器,其上限是:2^32-1。真的足夠大了。
為什么Python能夠做到呢?請有興趣刨根問底的去看Python的有關(guān)源碼。本文不贅述。
在其它語言中,通常用“分治法”解決大整數(shù)相乘問題。
但是,這里提供一個非常有意思的計算兩個整數(shù)相乘的方法,算是做為大整數(shù)相乘的演示。
兩個整數(shù)相乘:阿拉伯乘法。關(guān)于這個乘法的詳細描述,請看:http://ualr.edu/lasmoller/medievalmult.html
解決(Python)
#!/usr/bin/env python #coding:utf-8 #阿拉伯乘法 def arabic_multiplication(num1,num2): num_lst1 = [int(i) for i in str(num1)] #將int類型的123,轉(zhuǎn)化為list類型的[1,2,3],每個元素都是int類型 num_lst2 = [int(i) for i in str(num2)] #兩個list中整數(shù)兩兩相乘 int_martix = [[i*j for i in num_lst1] for j in num_lst2] #將上述元素為數(shù)字的list轉(zhuǎn)化為元素類型是str,主要是將9-->'09' str_martix = [map(convert_to_str,int_martix[i]) for i in range(len(int_martix))] #將上述各個list中的兩位數(shù)字分開:['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)] #計算阿拉伯乘法表的左側(cè)開始各項和 sum_left = summ_left(martix) #計算阿拉伯乘法表的底部開始各項和 sum_end = summ_end(martix) #將上述兩個結(jié)果合并后翻轉(zhuǎn) sum_left.extend(sum_end) sum_left.reverse() #取得各個和的個位的數(shù)字(如果進位則加上) result = take_digit(sum_left) #翻轉(zhuǎn)結(jié)果并合并為一個結(jié)果字符串數(shù)值 result.reverse() int_result = "".join(result) print "%d*%d="%(num1,num2) print int_result #將int類型轉(zhuǎn)化為str類型,9-->'09' def convert_to_str(num): if num<10: return "0"+str(num) else: return str(num) #計算阿拉伯乘法表格左側(cè)開始的各項之和 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 #得到各個元素的個位數(shù),如果是大于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)
- Python 判斷是否為質(zhì)數(shù)或素數(shù)的實例
- 使用Python判斷質(zhì)數(shù)(素數(shù))的簡單方法講解
- python實現(xiàn)挑選出來100以內(nèi)的質(zhì)數(shù)
- Python實現(xiàn)利用最大公約數(shù)求三個正整數(shù)的最小公倍數(shù)示例
- python 判斷是否為正小數(shù)和正整數(shù)的實例
- Python編程判斷一個正整數(shù)是否為素數(shù)的方法
- python里對list中的整數(shù)求平均并排序
- Python兩個整數(shù)相除得到浮點數(shù)值的方法
- Python基于二分查找實現(xiàn)求整數(shù)平方根的方法
- Python實現(xiàn)將一個正整數(shù)分解質(zhì)因數(shù)的方法分析
相關(guān)文章
Django 響應數(shù)據(jù)response的返回源碼詳解
這篇文章主要介紹了Django 響應數(shù)據(jù)response的返回源碼詳解,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-08-08巧用python和libnmapd,提取Nmap掃描結(jié)果
本文將會講述一系列如何使用一行代碼解析 nmap 掃描結(jié)果,其中會在 Python 環(huán)境中使用到 libnmap 里的 NmapParser 庫,這個庫可以很容易的幫助我們解析 nmap 的掃描結(jié)果2016-08-08