文档章节

俄罗斯农民乘法的Python实现

圣洁之子
 圣洁之子
发布于 2014/09/21 15:06
字数 259
阅读 49
收藏 0

《计算机程序的构造和解析》第31页提到一种有时被称作“俄罗斯农民的方法”的乘法运算,是基于加、加倍和折半的算法。译言上有详细解释(http://article.yeeyan.org/view/57492/28201)。

下面的代码是基于Python的实现, 在 timeit.Timer().timeit(1) 中测试了25位数字的乘法,耗时176 us (微秒)。

# coding:utf-8
# in Python 2.7.5
import timeit
def russian(x,y):
	L = []
	s = 0
	while y > 0:
		L.append( (x,y) )
		x *= 2
		y /= 2
		
	#print x,y
	for x,y in L:
		#print x, y
		if y % 2:
			s += x
	return s
	
def russian2(x,y):
	L = []
	s = 0
	while y > 0:
		L.append( (x,y) )
		x <<=1
		y >>=1
		
	#print x,y
	for x,y in L:
		#print x, y
		if y % 2:
			s += x
	return s
	
def russian3(n,m):
    L = {}
    s = 0
    while m > 0:
        L[m] = n
        #m /= 2
        #n *= 2
        m >>= 1
        n <<= 1
    for key in L:
        #print key,
        if key%2 ==1:
            s += L[key]
         
    return s

def test():
	return russian3(3206542342234343411233123,2534542342234343411233123)
	#return  (3206542342234343411233123 * 2534542342234343411233123)
'''
if __name__ == '__main__':
	import timeit
	print timeit.timeit('test()', setup="from __main__ import test")
'''
#print test()

#begin=time.time()
t1=timeit.Timer("test()","from __main__ import test")
print t1.timeit(1)
#end=time.time()
#print (end-begin)



本文转载自:http://www.oschina.net/code/snippet_2242563_38820

圣洁之子
粉丝 10
博文 402
码字总数 124050
作品 0
深圳
后端工程师
私信 提问
任意精度整数计算的实现 (Python 1.5 源码)

在学习 Python 源码中, 我们遇到了 longobject, 它表示任意精度的整数. 要注意的是这里 long 不是 C/Java 等语言中 long 的语义, 一般它们的 long 型是 32-bits (或有 64-bits long long). ...

刘军兴
2016/01/04
267
0
MobileNet原理+手写python代码实现MobileNet

MobileNet是针对移动端优化的卷积,所以当需要压缩模型时,可以考虑使用MobileNet替换卷积。下面我们开始学习MobileNet原理,并且先通过Tensorflow函数接口实现MobileNet,再手写python代码实...

huachao1001
2018/06/30
0
0
Python 3.5 新特性预览

Python 3.5b1 已经发布,Python 3.5 正式版已经不远啦!Python 3.5 相比 Python 3.4 详细改进请看 Misc/NEWS。 Python 3.5 发布计划: 3.5.0 alpha 1: February 8, 2015 3.5.0 alpha 2: Mar......

oschina
2015/07/09
19.9K
31
Python 3.5.1/3.4.4.rc1/2.7.11 发布

Python 3.5.1 发布,Python 3.5 系列主要新特性: PEP 441, 改进 Python zip 应用支持 PEP 448, 额外的开箱概括 PEP 461, 为字节和字节数组对象提供 "%-formatting" PEP 465, 新矩阵乘法操作...

oschina
2015/12/07
6.5K
13
一行 Python 代码能实现什么丧心病狂的功能?

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 https://blog.csdn.net/xufive/article/details/96475103 手头有 109 张头部 CT 的断层扫描图...

天元浪子
07/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

查看线上日志常用命令

cat 命令(文本输出命令) 通常查找出错误日志 cat error.log | grep 'nick' , 这时候我们要输出当前这个日志的前后几行: 显示file文件里匹配nick那行以及上下5行 cat error.log | grep -C ...

xiaolyuh
22分钟前
3
0
六、Java设计模式之工厂方法

工厂方法定义: 定义一个创建对象的接口,但让实现这个接口的类来决定实例化哪个类,工厂方法让类的实例化推迟到子类中进行 类型:创建型 工厂方法-使用场景: 创建对象需要大量重复的代码 ...

东风破2019
29分钟前
3
0
win服务器管理遇到的一系列问题记录

有些小伙伴在使用iis7远程桌面管理工具的时候总是会遇到一系列的问题,下面就是为大家介绍一下服务器日常管理过程中出现的问题及我的解决办法和心得。希望能帮到大家。   拒绝服务器重新启...

1717197346
36分钟前
4
0
flutter 剪切板 复制粘贴

复制粘贴功能 import 'package:flutter/services.dart'; Clipboard.setData(ClipboardData(text:_text));Clipboard.getData;...

zdglf
38分钟前
3
0
如何保证消息的可靠性传输?或者说,如何处理消息丢失的问题?

面试题 如何保证消息的可靠性传输?或者说,如何处理消息丢失的问题? 面试官心理分析 这个是肯定的,用 MQ 有个基本原则,就是数据不能多一条,也不能少一条,不能多,就是前面说的重复消费...

米兜
39分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部