python里大整数相乘相关技巧指南

问题

大整数相乘

思路说明

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

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

例如：

>>> 2899887676637907866*1788778992788348277389943

5187258157415700236034169791337062588991638L

注意：前面的“无限精度”是有引号的。事实上也是有限制的，对于32位的机器，其上限是：2^32-1。真的足够大了。

为什么Python能够做到呢？请有兴趣刨根问底的去看Python的有关源码。本文不赘述。

在其它语言中，通常用“分治法”解决大整数相乘问题。

但是，这里提供一个非常有意思的计算两个整数相乘的方法，算是做为大整数相乘的演示。

两个整数相乘：阿拉伯乘法。关于这个乘法的详细描述，请看：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，转化为list类型的[1,2,3]，每个元素都是int类型
  num_lst2 = [int(i) for i in str(num2)]

  #两个list中整数两两相乘
  int_martix = [[i*j for i in num_lst1] for j in num_lst2]

  #将上述元素为数字的list转化为元素类型是str，主要是将9-->'09'
  str_martix = [map(convert_to_str,int_martix[i]) for i in range(len(int_martix))]

  #将上述各个list中的两位数字分开：['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)]

  #计算阿拉伯乘法表的左侧开始各项和
  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)
  print int_result

#将int类型转化为str类型，9-->'09'

def convert_to_str(num):
  if num<10:
    return "0"+str(num)
  else:
    return str(num)

#计算阿拉伯乘法表格左侧开始的各项之和

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

#得到各个元素的个位数，如果是大于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)
赞 (0)

相关推荐

  • Python基于二分查找实现求整数平方根的方法

    本文实例讲述了Python基于二分查找实现求整数平方根的方法.分享给大家供大家参考,具体如下: x=int(raw_input('please input a int:')) if x<0: retrun -1 low=0 high=x ans=(low+high)/2.0 sign=ans while ans**2 !=x: if ans**2>x: high=ans else: low=ans ans=(low+high)/2.0 if sign==ans: break print ans

  • Python编程判断一个正整数是否为素数的方法

    Python编程判断一个正整数是否为素数的方法

    本文实例讲述了Python编程判断一个正整数是否为素数的方法.分享给大家供大家参考,具体如下: import string import math #判断是否素数的函数 def isPrime(n): if(n<2): return False; elif(n==2): return True; elif(n>2): for d in range(2,int(math.ceil(math.sqrt(n))+1)): if(n%d==0): return False; return True;

  • Python两个整数相除得到浮点数值的方法

    在python中进行两个整数相除的时候,在默认情况下都是只能够得到整数的值,而在需要进行对除所得的结果进行精确地求值时,想在运算后即得到浮点值,那么如何进行处理呢? 1.修改被除数的值为带小数点的形式即可得到浮点值,这种方法在被除数事先知道的情况下才可以采用有效,而这种情况意味着被除数的值是写死的.固定的,在绝大多数的情况下是不可行的: 2.在进行除法运算前导入一个实除法的模块,即可在两个整数进行相除的时候得到浮点的结果; 复制代码 代码如下: from __future__ import di

  • Python解惑之整数比较详解

    前言 在 Python 中一切都是对象,毫无例外整数也是对象,对象之间比较是否相等可以用==,也可以用is. ==和is操作的区别是: is比较的是两个对象的id值是否相等,也就是比较俩对象是否为同一个实例对象,是否指向同一个内存地址. ==比较的是两个对象的内容是否相等,默认会调用对象的__eq__()方法. 清楚is和==的区别之后,对此也许你有可能会遇到下面的这些困惑,于是就有了这样一篇文章,试图把Python中一些隐晦的东西趴出来,希望对你有一定的帮助. 我们先来看两段代码: 片段一:

  • python将ip地址转换成整数的方法

    本文实例讲述了python将ip地址转换成整数的方法.分享给大家供大家参考.具体分析如下: 有时候我们用数据库存储ip地址时可以将ip地址转换成整数存储,整数占用空间小,索引也会比较方便,下面的python代码自定义了一个ip转换成整数的函数,非常简单,代码同时还提供了整数转换成ip地址的方法. import socket, struct def ip2long(ip): """ Convert an IP string to long """

  • python里对list中的整数求平均并排序

    问题 定义一个int型的一维数组,包含40个元素,用来存储每个学员的成绩,循环产生40个0~100之间的随机整数, (1)将它们存储到一维数组中,然后统计成绩低于平均分的学员的人数,并输出出来. (2)将这40个成绩按照从高到低的顺序输出出来. 解决(python) #! /usr/bin python #coding:utf-8 from __future__ import division #实现精确的除法,例如4/3=1.333333 import random def make_scor

  • python里大整数相乘相关技巧指南

    问题 大整数相乘 思路说明 对于大整数计算,一般都要用某种方法转化,否则会溢出.但是python无此担忧了. Python支持"无限精度"的整数,一般情况下不用考虑整数溢出的问题,而且Python Int类型与任意精度的Long整数类可以无缝转换,超过Int 范围的情况都将转换成Long类型. 例如: >>> 2899887676637907866*1788778992788348277389943 5187258157415700236034169791337062

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

    我们平时接触的长乘法,按位相乘,是一种时间复杂度为 O(n ^ 2) 的算法.今天,我们来介绍一种时间复杂度为 O (n ^ log 3) 的大整数乘法(log 表示以 2 为底的对数). 介绍原理 karatsuba 算法要求乘数与被乘数要满足以下几个条件,第一,乘数与被乘数的位数相同:第二,乘数与被乘数的位数应为  2 次幂,即为 2 ^ 2,  2 ^ 3, 2 ^ 4, 2 ^ n 等数值. 下面我们先来看几个简单的例子,并以此来了解 karatsuba 算法的使用方法. 两位数相乘 我

  • python使用pandas处理大数据节省内存技巧（推荐）

    一般来说,用pandas处理小于100兆的数据,性能不是问题.当用pandas来处理100兆至几个G的数据时,将会比较耗时,同时会导致程序因内存不足而运行失败. 当然,像Spark这类的工具能够胜任处理100G至几个T的大数据集,但要想充分发挥这些工具的优势,通常需要比较贵的硬件设备.而且,这些工具不像pandas那样具有丰富的进行高质量数据清洗.探索和分析的特性.对于中等规模的数据,我们的愿望是尽量让pandas继续发挥其优势,而不是换用其他工具. 本文我们讨论pandas的内存使用,展示怎样

  • 对Python中小整数对象池和大整数对象池的使用详解

    1. 小整数对象池 整数在程序中的使用非常广泛,Python为了优化速度,使用了小整数对象池, 避免为整数频繁申请和销毁内存空间. Python 对小整数的定义是 [-5, 256] 这些整数对象是提前建立好的,不会被垃圾回收.在一个 Python 的程序中,无论这个整数处于LEGB中的哪个位置, 所有位于这个范围内的整数使用的都是同一个对象.同理,单个字母也是这样的. In [1]: a=-5 In [2]: b=-5 In [3]: a is b Out[3]: True In [4]: a

  • Python 实现两个列表里元素对应相乘的方法

    方法一: 结合zip函数,使用map函数: List1 = [1,2,3,4] List2 = [5,6,7,8] List3 = map(lambda (a,b):a*b,zip(List1,List2)) print List3 方法二: 把列表转化为数组,使用np.multiply函数 List = [1,2,3] List2 = [5,6,7] List3 = np.multiply(np.array(List1),np.array(List2)) print List3.tolist(

  • Python如何处理大数据？3个技巧效率提升攻略（推荐）

    如果你有个5.6 G 大小的文件,想把文件内容读出来做一些处理然后存到另外的文件去,你会使用什么进行处理呢?不用在线等,给几个错误示范:有人用multiprocessing 处理,但是效率非常低.于是,有人用python处理大文件还是会存在效率上的问题.因为效率只是和预期的时间有关,不会报错,报错代表程序本身出现问题了~ 所以,为什么用python处理大文件总有效率问题? 如果工作需要,立刻处理一个大文件,你需要注意两点: 01.大型文件的读取效率 面对100w行的大型数据,经过测试各种文件读取

  • 写好Python代码的几条重要技巧

    写好Python代码的几条重要技巧

    程序设计的好与坏,早在我们青葱岁月时就接触过了,只是那是并不知道这竟如此重要.能够立即改善程序设计.写出"好"代码的知识有以下几点: •面向对象五个基本原则: •常见的三种架构: •绘图: •起一个好名字: •优化嵌套的 if else 代码: 当然,其他技术知识的丰富程度也决定了程序设计的好坏.例如通过引入消息队列解决双端性能差异问题.通过增加缓存层提高查询效率等.下面我们一起来看看,上面列出的知识点包含哪些内容,这些内容对代码和程序设计的改善有何帮助. 面向对象五个基本原则 本书作

  • Python容器使用的5个技巧和2个误区总结

    Python容器使用的5个技巧和2个误区 "容器"这两个字很少被 Python 技术文章提起.一看到"容器",大家想到的多是那头蓝色小鲸鱼:Docker,但这篇文章和它没有任何关系.本文里的容器,是 Python 中的一个抽象概念,是对专门用来装其他对象的数据类型的统称. 在 Python 中,有四类最常见的内建容器类型: 列表(list). 元组(tuple). 字典(dict). 集合(set).通过单独或是组合使用它们,可以高效的完成很多事情. Python

  • TensorFlow2.1.0安装过程中setuptools、wrapt等相关错误指南

    笔者remove TensorFlow总共四次. reinstall anaconda 三次. 安装技巧可以根据这个博主的文章进行安装. https://www.jb51.net/article/184309.htm 我就是用这个教程安装的 因为直接用 pip install安装太慢了 所以在官网CUDA 和cuDNN+清华镜像的TensorFlow来安装比较快. 总结我的几个问题. 一.安装错误 · (1) tensorboard 1.14.0 has requirement setuptoo

  • python简单实现整数反转的画解算法

    python简单实现整数反转的画解算法

    题目描述 给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果. 如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ,就返回 0. 假设环境不允许存储 64 位整数(有符号或无符号). 示例 1: 输入:x = 123 输出:321 示例 2: 输入:x = -123 输出:-321 示例 3: 输入:x = 120 输出:21 示例 4: 输入:x = 0 输出:0 问题分析 首先我们想一下,怎么去反转一个整数? 用栈? 或者把整数变成字符串

随机推荐