文档章节

函数平方pow(x,n)的求法

smart_w
 smart_w
发布于 2016/01/28 15:19
字数 450
阅读 340
收藏 0

考虑到n个x相乘式子的对称关系,可以对上述方法进行改进,从而得到一种时间复杂度为O(logn)的方法,递归关系可以表示为pow(x,n) = pow(x,n/2)*pow(x,n-n/2)

func pow(x float64, n int) float64 {
	if n == 0 {
		return 1.0
	}
	if n < 0 {
		return 1.0 / pow(x, -n)
	}

	half := pow(x, n>>1) //example: n = 3 3/2 = 1

	if n%2 == 0 {
		return half * half
	} else {
		return half * half * x
	}

}

除了上述方法,这里还提到了一种十分巧妙并且快速的方法,原文描述如下:

Consider the binary representation of n. For example, if it is "10001011", then x^n = x^(1+2+8+128) = x^1 * x^2 * x^8 * x^128. Thus, we don't want to loop n times to calculate x^n. To speed up, we loop through each bit, if the i-th bit is 1, then we add x^(1 << i) to the result. Since (1 << i) is a power of 2, x^(1<<(i+1)) = square(x^(1<<i)). The loop executes for a maximum of log(n) times.

func my_pow(x float64, n int) float64 {
	if n == 0 {
		return 1.0
	}
	if n < 0 {
		return 1.0 / my_pow(x, -n)
	}
	var result float64 = 1.0
	for ; n > 0; n = n >> 1 {
		if n&1 != 0 {
			result *= x
		}
		x = x * x
	}
	return result
}

完整代码 :

package main

import (
	"fmt"
)

func pow(x float64, n int) float64 {
	if n == 0 {
		return 1.0
	}
	if n < 0 {
		return 1.0 / pow(x, -n)
	}
	half := pow(x, n>>1) //example: n = 3 3/2 = 1
	if n%2 == 0 {
		return half * half
	} else {
		return half * half * x
	}
}

func my_pow(x float64, n int) float64 {
	if n == 0 {
		return 1.0
	}
	if n < 0 {
		return 1.0 / my_pow(x, -n)
	}
	var result float64 = 1.0
	for ; n > 0; n = n >> 1 {
		if n&1 != 0 {
			result *= x
		}
		x = x * x
	}
	return result
}

func main() {
	fmt.Printf("pow result %v \n", my_pow(6.0, 2))
}

 

本文转载自:http://blog.csdn.net/fengbingyang/article/details/12236121

共有 人打赏支持
smart_w
粉丝 32
博文 74
码字总数 23007
作品 0
武汉
程序员
私信 提问
数论基础 扩展欧几里得 线性筛 逆元 欧拉函数 Lucas定理

扩展欧几里得 欧几里得算法,又叫辗转相除法,用于求两个数的最大公约数(gcd)。 由此可以得到最小公倍数 (先除防止溢出)。 扩展欧几里得,是用于解出方程 的一组解的。比如方程 ,可以解...

myjs999
2017/10/25
0
0
WC模拟:function(杜教筛)

题意: 求: 题解: 杜教筛。。 设 打表(我太弱了只会打表)发现: 根据杜教筛的复杂度分析,如果能够在 内处理出这个函数的值,那么就可以在 的时间内处理出这个前缀和。 以下推导的一些证明...

qq_35649707
01/10
0
0
【模式识别】学习笔记(2)>>>【判别函数】

判别函数在模式识别系统的主要作用就是判别各个模式所属的类别。 如下直线描述的判别函数即将模式分为两类。 获取判别函数: 1-先确定判别函数形式,线性还是非线性、直线曲线折线等; 2-确定...

Parser7
2015/03/02
0
0
BZOJ3028:食物(OGF)

传送门 题意: 给一堆东西和选的限制,求把背包装满的方案数。。 题解: 对于每种组合我们只关心每种食物的个数,故可以每一个组成对象构造一般性生成函数。 显然答案为所有食物的笛卡尔积,...

qq_35649707
2017/12/22
0
0
超级pow(a^b,b由数组表示)Super Pow

问题: Your task is to calculate a^b mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array. Example1: a = 2b = [3]Res......

叶枫啦啦
2017/12/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

docker搞个wordpress

1.先把wordpress的镜像下载下来 docker pull wordpress 2.下载mysql docker pull mysql:lastest 3.启动mysql docker run --name blog -e root -d mysql:5.7 docker run --name some-mysql -e......

无极之岚
10分钟前
0
0
【宇润日常疯测-005】PHP 中的 clone 和 new 性能比较

clone和new本不应该放在一起比较,它们的作用是不同的。但可能有一些场景下,可以用clone也可以用new,那么这时候我们选哪个呢? 我编写了两个测试,第一个是声明一个空类,第二个是带构造方...

宇润
10分钟前
0
1
点击按钮弹出类似IOS 底部 dialog

implementation 'com.baoyz.actionsheet:library:1.1.7' 然后设置按钮点击监听,,调用下列代码即可 ActionSheet.createBuilder(this, getSupportFragmentManager()) ......

lanyu96
13分钟前
1
0
专访阿里云专有云马劲,一个理性的理想主义者

“我的故事都是和团队技术相关的,自己还真没有什么引人入胜的故事。”当马劲被问到能不能多分享些个人经历故事时他笑着说,我们就干脆怀着好奇聊了聊他和阿里云专有云一路走来的故事。 马劲...

阿里云官方博客
45分钟前
1
0
java环形缓冲区

import java.util.ArrayList;import java.util.List;/** * * 环形缓冲区<br/> * 一. 写数据:<br/> * 1. push: 当数据已写满时返回false,否则可以正常写入返回true<br/>......

whoisliang
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部