Python 实现大整数乘法算法的示例代码

我们平时接触的长乘法,按位相乘,是一种时间复杂度为 O(n ^ 2) 的算法。今天,我们来介绍一种时间复杂度为 O (n ^ log 3) 的大整数乘法(log 表示以 2 为底的对数)。

介绍原理

karatsuba 算法要求乘数与被乘数要满足以下几个条件,第一,乘数与被乘数的位数相同;第二,乘数与被乘数的位数应为  2 次幂,即为 2 ^ 2,  2 ^ 3, 2 ^ 4, 2 ^ n 等数值。

下面我们先来看几个简单的例子,并以此来了解 karatsuba 算法的使用方法。

两位数相乘

我们设被乘数 A = 85,乘数 B = 41。下面来看我们的操作步骤:

将 A, B 一分为二,令 p = A 的前半部分 = 8,q = A 的后半部分 = 5 , r = B 的前半部分 = 4 ,s = B 的后半部分 =  1,n = 2。通过简单的数学运算:

A * B = pq * rs = (p * 10 + q) * (r * 10 + s)  = p * r * 10 ^ 2 + (p * s + q * r ) * 10 + q * s。

令 u = p * r,v =(p - q) * (s - r),w = q * s。所以 A * B =  u * 10 ^ 2 + (u + v + w) * 10 + w。

换成数值求解的过程如下:

A * B = 85 * 41 = (8 * 10 + 5) * ( 4 * 10 + 1) = 8 * 4 * 10 * 10 + (8 * 1 + 5 * 4) * 10 + 5 * 1。

其中 u = 8 * 4 = 32,v = (8 - 5) (1 - 4) = -9,w = 5 * 1 = 5。

所以,A * B = 32 * 100 + (32 - 9 + 5) * 10 + 5 = 3485。与长乘法所得结果一致。

四位数相乘

我们设被乘数 A = 8537,乘数 B = 4123。下面来看我们的操作步骤:

将 A, B 一分为二,令 p = A 的前半部分 = 85,q = A 的后半部分 = 37 , r = B 的前半部分 = 41 ,s = B 的后半部分 =  23,n = 4。

==> 其中,u = 85 * 41, v = (85 - 37) * (23 - 41), w = 37 * 23。

==> A * B = 8537 * 4123 = u * 10 ^ 4 + (u + v + w) * 10 ^ 2 + w =  3485_0000 +34_7200 + 851 = 35198051。

在我们计算 u, v,  w 的过程中又会涉及两位数的乘法,我们继续使用 Karatsuba 算法得出两位数相乘的结果。

N 位数相乘

我们令 n 为 乘数与被乘数的位数,令 p = A 的前半部分,q = A 的后半部分, r = B 的前半部分 ,s = B 的后半部分。

==> 其中, u = p * r,v = (p - q) * (s - r),w = q * s。

所以 A * B =  u * 10 ^ n + (u + v + w) * 10 ^ (n / 2) + w。

而 u, v, w 则是两个 n / 2 位的乘法运算。我们继续调用 Karatsuba 算法计算 u, v, w 的数值。接着,我们在计算 n / 2 乘法的过程中又会遇到 n / 4 位的乘法运算……以此类推,直到我们遇到两个个位数的乘法,我们就直接返回这两个个位数乘法的结果。层层返回,最终得到 N 位数的乘法结果。

时间复杂度

我们平常使用的长乘法,是 O (n ^ 2) 的时间复杂度。比如两个 N 位数相乘,我们需要将每一位按规则相乘,所以需要计算  N * N 次乘法。而使用  Karatsuba 算法每层需要计算三次乘法,两次加法,以及若干次加法,每使用一次 karatsuba 算法,乘法规模就下降一半。

所以,对于两个 n =  2 ^ K 位数乘法运算,我们需要计算 3 ^ k 次乘法运算。而 K = log n(底数为 2), 3 ^ K = 3 ^ log n = 2  ^ (log 3 * log n) = 2 ^ (log n * log 3) = n ^ log 3 (底数为 2)。

代码实现

from math import log2, ceil

def pad(string: str, real_len: int, max_len: int) -> str:
  pad_len: int = max_len - real_len
  return f"{'0' * pad_len}{string}"

def kara(n1: int, n2: int) -> int:
  if n1 < 10 or n2 < 10:
    return n1 * n2
  n1_str: str = str(n1)
  n2_str: str = str(n2)
  n1_len: int = len(n1_str)
  n2_len: int = len(n2_str)
  real_len: int = max(n1_len, n2_len)
  max_len: int = 2 ** ceil(log2(real_len))
  mid_len: int = max_len >> 1
  n1_pad: str = pad(n1_str, n1_len, max_len)
  n2_pad: str = pad(n2_str, n2_len, max_len)
  p: int = int(n1_pad[:mid_len])
  q: int = int(n1_pad[mid_len:])
  r: int = int(n2_pad[:mid_len])
  s: int = int(n2_pad[mid_len:])
  u: int = kara(p, r)
  v: int = kara(q-p, r-s)
  w: int = kara(q, s)
  return u * 10 ** max_len + (u+v+w) * 10 ** mid_len + w

输出结果:

==> kara(123456, 9734) == 123456 * 9734

==> kara(1234233456756, 32459734) == 1234233456756 * 32459734

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Python中实现最小二乘法思路及实现代码

    之所以说"使用"而不是"实现",是因为python的相关类库已经帮我们实现了具体算法,而我们只要学会使用就可以了.随着对技术的逐渐掌握及积累,当类库中的算法已经无法满足自身需求的时候,我们也可以尝试通过自己的方式实现各种算法. 言归正传,什么是"最小二乘法"呢? 定义:最小二乘法(又称最小平方法)是一种数学优化技术,它通过最小化误差的平方和寻找数据的最佳函数匹配. 作用:利用最小二乘法可以简便地求得未知的数据,并使得这些求得的数据与实际数据之间误

  • 学习python之编写简单乘法口诀表实现代码

    实现代码一. #!/usr/bin/python x,y=9,9 lst=[(x,y,str(y)+'X'+str(x)+'='+str(x*y)) for x in range(1,y+1) for y in range(1,x+1)] for item in lst: print item[2], if(item[0]==item[1]): print '\n' 实现代码二. for i in range(1,10): for j in range(1,i+1): print str(i*j

  • Python最小二乘法矩阵

    最小二乘法矩阵 #! /usr/bin/env python # -*- coding: utf-8 -*- import numpy as np def calc_left_k_mat(k): """ 获得左侧k矩阵 :param k: :return: """ k_mat = [] for i in range(k + 1): now_line = [] for j in range(k + 1): now_line.append(j + i

  • Python实现矩阵加法和乘法的方法分析

    本文实例讲述了Python实现矩阵加法和乘法的方法.分享给大家供大家参考,具体如下: 本来以为python的矩阵用list表示出来应该很简单可以搞..其实发现有大学问. 这里贴出我写的特别不pythonic的矩阵加法,作为反例. def add(a, b): rows = len(a[0]) cols = len(a) c = [] for i in range(rows): temp = [] for j in range(cols): temp.append(a[i][j] + b[i][j

  • python中数组和矩阵乘法及使用总结(推荐)

    Matrix是Array的一个小的分支,包含于Array.所以matrix 拥有array的所有特性. 但在数组乘和矩阵乘时,两者各有不同,如果a和b是两个matrices,那么a*b,就是矩阵积 如果a,b是数组的话,则a*b是数组的运算 1.对数组的操作 >>> import numpy as np >>> a=np.array([[1,2,3],[4,5,6],[7,8,9]]) >>> a array([[1, 2, 3], [4, 5, 6]

  • Python中列表与元组的乘法操作示例

    本文实例讲述了Python中列表与元组的乘法操作.分享给大家供大家参考,具体如下: 直接上code吧,还可以这么玩儿 列表乘法: li=[1,] li=li*3 print(li) out: [1, 1, 1] 元组乘法: >>> t=(1,2) >>> t*3 (1, 2, 1, 2, 1, 2) 但字典,集合不能这么玩 例如: >>> dict1={'k1':1,'k2':2} >>> dict1*2 #报错 Traceback

  • python实现矩阵乘法的方法

    本文实例讲述了python实现矩阵乘法的方法.分享给大家供大家参考.具体实现方法如下: def matrixMul(A, B): res = [[0] * len(B[0]) for i in range(len(A))] for i in range(len(A)): for j in range(len(B[0])): for k in range(len(B)): res[i][j] += A[i][k] * B[k][j] return res def matrixMul2(A, B):

  • python九九乘法表的实例

    python2.7 for i in range(1,10): for j in range(1,i+1): print j,'x',i,'=',j*i,'\t', print '\n' print '\nDone' python3.7 i = 1 while i<=9: j = 1 while j<=i: print ("%d*%d=%-2d "%(j,i,j*i),end="") j+=1 print("") i+=1 以上这篇p

  • Python基于最小二乘法实现曲线拟合示例

    本文实例讲述了Python基于最小二乘法实现曲线拟合.分享给大家供大家参考,具体如下: 这里不手动实现最小二乘,调用scipy库中实现好的相关优化函数. 考虑如下的含有4个参数的函数式: 构造数据 import numpy as np from scipy import optimize import matplotlib.pyplot as plt def logistic4(x, A, B, C, D): return (A-D)/(1+(x/C)**B)+D def residuals(p

  • Python用for循环实现九九乘法表

    下面通过一段代码给大家介绍python 使用for 循环实现九九乘法表,具体代码如下所示: #for 循环实现99乘法表 for i in range (1,10): for j in range (1,i+1): print("{}*{} = {:<4}".format(i,j,i*j),end = " ") print("") print('第1种'+"-"*96) for i in range (9,0,-1):

  • Python中的几种矩阵乘法(小结)

    一.  np.dot() 1.同线性代数中矩阵乘法的定义.np.dot(A, B)表示: 对二维矩阵,计算真正意义上的矩阵乘积. 对于一维矩阵,计算两者的内积. 2.代码 [code] import numpy as np # 2-D array: 2 x 3 two_dim_matrix_one = np.array([[1, 2, 3], [4, 5, 6]]) # 2-D array: 3 x 2 two_dim_matrix_two = np.array([[1, 2], [3, 4],

  • python实现最小二乘法线性拟合

    本文python代码实现的是最小二乘法线性拟合,并且包含自己造的轮子与别人造的轮子的结果比较. 问题:对直线附近的带有噪声的数据进行线性拟合,最终求出w,b的估计值. 最小二乘法基本思想是使得样本方差最小. 代码中self_func()函数为自定义拟合函数,skl_func()为调用scikit-learn中线性模块的函数. import numpy as np import matplotlib.pyplot as plt from sklearn.linear_model import Li

随机推荐