文档章节

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

smart_w
 smart_w
发布于 2016/01/28 15:19
字数 450
阅读 295
收藏 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
粉丝 31
博文 74
码字总数 23007
作品 0
武汉
程序员
数论基础 扩展欧几里得 线性筛 逆元 欧拉函数 Lucas定理

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

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

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

qq_35649707
01/10
0
0
GIS坐标转换及其编程实现

最近,在做这个坐标转换的东西,涉及到大地测量学等很深奥的东西,在这里我就不讲解那些难懂的理论了,在此,我将会把代码贴出来和大家分享,其实要编写出这个代码,还真得把大地测量相关的知...

长平狐
2013/12/25
287
0
【模式识别】学习笔记(2)>>>【判别函数】

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

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

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

qq_35649707
2017/12/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

讲述下 :LVM逻辑卷管理遇到的问题

LVM学习逻辑卷管理创建逻辑卷遇到的问题 1 实验环境 系统 内核 发行版本 CentOS 2.6.32-754.2.1.el6.x86_64 CentOS release 6.10 (Final) 由于是最小化安装没有xfs命令,yum安装如下包支持此...

linuxprobe16
39分钟前
0
0
day95-20180922-英语流利阅读-待学习

Hey Jude 半个世纪传唱不衰的背后故事 毛西 2018-09-22 1.今日导读 2004 年,The Beatles 被《滚石》杂志选为“历史上最伟大的 50 位流行音乐家的第一位”。这四名来自英国利物浦的男孩不仅对...

飞鱼说编程
46分钟前
1
0
OSChina 周六乱弹 —— 放假前期焦虑症晚期

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @andonny :分享Matteo的单曲《Panama》: 《Panama》- Matteo 手机党少年们想听歌,请使劲儿戳(这里) @新垣吉衣OSC :我发现只要去有小朋友...

小小编辑
今天
163
9
wait()被notify()后,接着执行wait()后面的语句

wait()被notify()后,接着执行wait()后面的语句

noteman
今天
1
0
Ubuntu集群-使用MAAS开始裸机安装

Ubuntu使用MAAS装机的七个步骤。 1、Setup your hardware You need one small server for MAAS and at least one server which can be managed with a BMC. It is recommended to have the M......

openthings
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部