文档章节

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

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

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

myjs999 ⋅ 2017/10/25 ⋅ 0

WC模拟:function(杜教筛)

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

qq_35649707 ⋅ 01/10 ⋅ 0

GIS坐标转换及其编程实现

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

长平狐 ⋅ 2013/12/25 ⋅ 0

【模式识别】学习笔记(2)>>>【判别函数】

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

Parser7 ⋅ 2015/03/02 ⋅ 0

python基础学习中发现的一些小知识

1.abs()函数 >>> abs(-1)1>>> abs(1+2j)2.23606797749979 abs函数常用返回绝对值,而复数使用abs则返回(a+bj)中a与b平方和再取平方根,如上所示 2.pow()与math.pow()函数 >>> pow(1,2)1>>> p......

chuang_py ⋅ 2015/05/16 ⋅ 0

LeetCode:Pow(x, n) - 求指定数字x的整数次幂

1、题目名称 Pow(x, n)(求指定数字x的整数次幂) 2、题目地址 https://leetcode.com/problems/powx-n/ 3、题目内容 英文:Implement pow(x, n) 中文:给定底数x和指数n,求x的n次幂 4、解题...

北风其凉 ⋅ 2015/08/08 ⋅ 0

BZOJ3028:食物(OGF)

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

qq_35649707 ⋅ 2017/12/22 ⋅ 0

hnust - 最小平方数

先科普一下如何判断一个数是否是完全平方数: 直接求这个数n的平方根,看他的平方根结果是否有小数,有小数就是非平方数。 方法一:使用浮点函数sqrt。 方法二:使用等差数列求和性质。 我们...

deaidai ⋅ 2017/06/01 ⋅ 0

Eran/BezierMathUtils

#BezierMathUtils 介绍 BezierMathUtils是用来提供计算贝塞尔曲线时候需要用到的数学公式。 比如存在如下需求: 有两点坐标A和B,希望某一个物品从A点移动到B点. 移动方式希望采用贝塞尔曲线...

Eran ⋅ 2015/02/18 ⋅ 0

Python 寻找相近的用户

今天看了一篇文章写的挺好的,所以自己总结一下,发出来大家一起学习一下 欧几里德距离(百度来的哦):欧几里得度量(euclidean metric)(也称欧式距离)是一个通常采用的距离定义,指在m...

yark志 ⋅ 2015/12/03 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JPA入门,配置文件的设置

<?xml version="1.0" encoding="UTF-8"?> <persistence xmlns="http://java.sun.com/xml/ns/persistence" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http......

码农屌丝 ⋅ 22分钟前 ⋅ 0

Java基础——面向对象和构造器

声明:本栏目所使用的素材都是凯哥学堂VIP学员所写,学员有权匿名,对文章有最终解释权;凯哥学堂旨在促进VIP学员互相学习的基础上公开笔记。 静态成员介绍 为什么要有静态成员?静态成员用来...

凯哥学堂 ⋅ 24分钟前 ⋅ 0

vmware中Centos 7 linux的LVM磁盘扩容

系统是RHEL7(centos7差不多一样) 关闭系统,在vmware、设置、硬盘、扩展、输入数字大于当前系统内存、点击扩展。 开机再查看磁盘信息 fdisk -l 注意:可以看出sda磁盘增加了,但是根目录还...

gugudu ⋅ 34分钟前 ⋅ 0

JAVA线程sleep和wait方法区别

昨天面试,突然被问到sleep 和 wait的区别,一下子有点蒙,在这里记一下,以示警戒。 首先说sleep,sleep就是正在执行的线程主动让出cpu,cpu去执行其他线程,在sleep指定的时间过去后,cpu...

徐玉强 ⋅ 36分钟前 ⋅ 0

vuex学习--模块

随着项目复杂性增加,共享状态也越来越多。需要对转态操作进行分组,分组后在进行分组编写。学习一下module:状态管理器的模块组操作。 首先是声明: const moduleA={ state,mutations,g...

大美琴 ⋅ 39分钟前 ⋅ 0

Selenium 简单入门

安装 pip install selenium 驱动下载 https://chromedriver.storage.googleapis.com/index.html 下载最新的驱动,放入path中,可以放入Python的scripts目录下,也可以放入Chrome安装目录,并...

阿豪boy ⋅ 40分钟前 ⋅ 0

292. Nim Game - LeetCode

Question 292. Nim Game Solution 思路:试着列举一下,就能发现一个n只要不是4的倍数,就能赢。 n 是否能赢1 true2 true3 true4 false 不论删除几,对方都能一把赢5 t...

yysue ⋅ 今天 ⋅ 0

6.5 zip压缩工具 6.6 tar打包 6.7 打包并压缩

zip压缩工具 zip命令可以压缩目录和文件,-r 压缩目录。 zip使用方法 zip 1.txt.zip 1.txt //压缩文件 zip -r 123.zip 123/ //压缩目录 unzip 1.txt.zip //解压 unzip 123.zip -d /root/456...

Linux_老吴 ⋅ 今天 ⋅ 0

react-loadable使用跳坑

官方给react-loadable的定义是: A higher order component for loading components with dynamic imports. 动态路由示例 withLoadable.js import React from 'react'import Loadable fro......

pengqinmm ⋅ 今天 ⋅ 0

记录工作中遇到的坑

1、ios safari浏览器向下滚动会触发window resize事件

端木遗风 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部