以滾動式進位演算法計算大數乘法

作者：

 以滾動式進位計算大數乘法

計算 (n位被乘數) X (m位乘數)，以傳統方式計算乘法，我們通常需要 n X m 次乘法及 2n(m-1) 次加法，更甚者，運算過程中是乘法與加法混合在一起，而這也是手算不易及造成錯誤的根源，若將計算思路稍微改變一下，不僅可減少計算時間，也能提高計算結果的正確性，這也是本文提出滾動式進位演算法(Rolling Carry Algorithm)的初衷。

我們知道乘法可以改成加法計算，以 3 X 2 = 6 來說，一般人會直覺的就是把 3 加 2 次或 2 加 3 次，但若是 33 X 22 或 333 X 222 抑或是更大的數字呢！那原本簡單的思維大概無法處理了，誰也無法忍受把 333 加 222 次罷。

雖說方法不好，但並不代表觀念錯誤，只需稍微改變一下思路，仍是大有可為的，滾動式進位演算法就是藉著改變計算方法，得到不僅手算及以電腦運算皆較佳的乘法計算方式，接著我們就來說說滾動式進位演算法的觀念，

首先，我們將被乘數當作一個完整的數字，並建立一個被乘數基數表，如下表，


接著，從被乘數基數表找到乘數相對應值，並循乘數的 LSD 至 MSD 逐次與前一進位相加，相加後保留個位數與前一運算以文字相加，其餘皆是次一進位，完成所有乘數運算即得到運算之積。

範例  12170126 X 258 = ?


大數乘法程式流程圖範例



大數乘法 Python 程式範例





















留言

張貼留言

這個網誌中的熱門文章

大整數的因數分解

作者：
# # 測試由 BARD 提供的因數分解的 Python 程式 # # 8976543213214567897654321987123456789111 = # 60337 * # 148773442716982413737082088720411303 # def sieve_of_eratosthenes(n):   """   使用Eratosthenes篩選法找出1到n之間的所有素數。   Args:     n:  要找的素數上限。   Returns:     一個包含1到n之間所有素數的列表。   """   primes = []   is_prime = [True] * (n + 1)   is_prime[0] = False   is_prime[1] = False   for i in range(2, n + 1):     if is_prime[i]:       primes.append(i)       for j in range(i * 2, n + 1, i):         is_prime[j] = False   return primes def factorize(n):   """   使用二次篩選法找出n的所有質因數。   Args:     n:  要分解的整數。   Returns:     一個包含n的所有質因數的列表。   """   factors = []   for prime in primes:     while n % prime == 0:       factors.append(prime)       n //= prime   if n > 1:     factors...
Read more »

The product of two odd numbers.

作者：
兩奇數之積 ( The product of two odd numbers) 熟悉環境中...... 數之分類 自然數若以4之餘數分類可表示為 4n+1、4n+2、4n+3 及 4n 四類， 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 ---------------- 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 ---------------- 41 42 43 44 45 46 47 48 49 50 51 52 由上述分類可知奇數必為 4n+1 及 4n+3 兩類，且可進一步將其歸納為  20n+1、20n+5、20n+9、20n+13 、 20n+17 及   20n+3、20n+7、20n+11、20n+15、20n+19 八個小類， 後續將更進一步討論每個小類的細分類。 設兩奇數之積為 N= P*Q 一坪院魚菜坊網誌
Read more »

LaTex_Texmaker 學習之路

作者：
圖片
這是將原本由 Microsoft Word 完成的作業，改以 LaTex_Texmaker 完成的 PDF 檔 。 目前中文目錄的編號仍在努力中，LaTex_Texmaker 寫法放在圖片之後。 LaTex_Texmaker \documentclass [a4paper,12pt]{article} % 使用中文 \usepackage { xeCJK } %\setCJKmainfont{SimSun} % 新宋体 SimSun、NSimSun %\setCJKmainfont{標楷體} \setCJKmainfont { 細明體 } %\setCJKmainfont{新細明體} %\setCJKmainfont{微軟正黑體} % 日期格式 \usepackage [ nodayofweek ]{ datetime } \newdateformat { mydate }{ \THEYEAR {} \twodigit { \THEMONTH } \twodigit { \THEDAY }} % 設定邊界、段距及列距 \usepackage [margin= 2cm ]{geometry} \usepackage { setspace } %\doublespacing % 2.0 倍列距 \onehalfspacing % 1.5 倍列距 \setlength { \parskip }{ 6pt } % 字體大小擴充功能 \usepackage { moresize } % 使用圖片 \usepackage {graphicx} % 清單擴充功能 \usepackage {enumerate} % 參考文獻 需另建立一個 .bib 檔 \usepackage [ notocbib ]{ apacite } % 目錄中不出現 reference %%%%%% 文章起始 %%%%%% \begin {document} %%% 封面 \begin {titlepage} \begin {center} \vspace* {0. 5cm } \huge 數位家庭程式設計入門作業04 \vspace { 1cm } \HUGE \textbf { 名稱：黑洞數 } ...
Read more »