Java中一般不太为新人所知的一些技术点

一般比较容易接触的点

Java对象结构

JVM中的Java数据类型

JVM的java方法栈中的数据结构大致的分为两类:

• 内置类型 (一说也叫原子类型)
  • 内置类型指的是java语言规范规定的8个类型,即 boolean, byte, char, short, int, long, float, double
  • 内置类型依据不同的类型在栈帧中占用不同的空间, 他们在堆中存储时按照缩进规则进行padding, 在本地变量表中时, 32位及以下的类型占用一个槽(Variable Slot), double 和 long 占用两个。
• 对象类型 (一说也叫做引用类型, 这里不计较返回地址类型)

指针压缩

Java代码是如何运行的

java代码的执行大概分为两大类三种类型。

• 对于本地代码

  这里说的本地代码指的是JVM通过JNI机制调用的本地代码。

• 对于Java字节码

  对于java字节码需要分两个情形来讨论。

  • 解释执行java字节码
  • 运行JIT代码

类加载和执行过程

装载 -> 链接 -> 初始化

如上过程就是一个类被虚拟机发现并到可用的全部过程, 其中每个步骤执行不同的操作。

类装载过程

类加载器

类加载器是负责加载class到JVM中的组件

在java9之前, 类加载器基本可以分为以下几类:

• 启动类加载器 (bootstrap class loader)

  使用与JVM相同的实现语言编写(Hotspot的话是c++), 它是唯一一个java对象的类加载器, 同时它也是唯一一个不需要其他类加载器加载自身的加载器, 由虚拟机负责加载它。 j9以前负责加载最基础的类库 e.g. JRE的lib目录下的类, 通过虚拟机参数 -Xbootclasspath 指定的类。

• 扩展类加载器(extension class loader)

  它的父加载器是bootstrap加载器, 同时它负责加载那些次一级的重要的类, e.g. JRE的 lib/ext目录下的jar包中的类, java.ext.dirs系统变量指定的类

• 应用类加载器(application class loader)

  它的父加载器是extension加载器, 同时它负责加载应用程序目录下的类和由虚拟机参数 -cp/-classpath 和系统变量 java.class.path指定目录的类的加载。

• 自定义类加载器

  自定义类加载器必须继承java.lang.ClassLoader。由于双亲委派模型,它只能负责加载它的祖先类加载器不能加载的类。

Java 9 引入了模块系统，并且略微更改了上述的类加载器。扩展类加载器被改名为平台类加载器(platform class loader), Java SE 中除了少数几个关键模块(如java.base)是由启动类加载器加载外, 其他模块都是由平台类加载器加载。

双亲委派模型

由于包含但不限于安全角度的考量,java的类加载器不可以随意决定加载类,java的各类加载器职能明确, 他们基本都有自己固定的职责, 例如启动类加载器只负责加载基础的重要的类(不然随意一个类加载器加载一个来源不明的Object类或者String类之类的重要类可就玩完了)。

类加载器基本遵循一个原则, 当收到加载一个类的委托时(这个委托可能是虚拟机发起, 也可能是其他类加载器发起), 需要先去委托自己的父类加载器尝试加载, 如果自己的父类加载器不能加载, 那么则由自己加载, 否则是用父类加载器加载。 这个原则, 就是双亲委派。

定义加载器和初始加载器 (这是俩名词, 不是动词)

类加载的时机

1. JVM采用按需加载类的模式, 类似于脚本语言中的缺页加载, 当JVM需要一个类的结构信息时, 发现它缺少, 才会去尝试加载它。

2. 方法字节码加载, 一些类库的功能可以提供类加载的操作, 例如反射机制, 例如 ClassLoader.load()等。

最初的过程

JVM是按需加载的类, 那么最初的一个类是谁, 如果我们不把引导类加载器(bootstrap class loader)的初始化考虑在内, 那么第一个被加载的类由外部参数指定(就是那个包含 static void main(String[])方法的类, 暂且我们叫他Main类。在Main类的链接和初始化过程中, 可能级联的需要装载更多的类。在Main类初始化完成后, JVM从它的main方法开始执行字节码, 在执行过程中可能再次触发类加载。

数组

数组是一类特殊的类, 它不由类加载器创建(当然, 也就不用编译器生成), 而是有JVM来创建。

数组类的二进制名规则为对于N维数组, 则以N个[作为前缀, 后接元素类型的名称构成名字。

运行时常量池

运行时常量池区别与常量池和字符串常量池 概念

其中, 常量池表是Java类文件结构中的一个区块, 运行时常量池是该结构在类加载后在JVM中维护的一个关联数据结构。每一个类实例在链接后都会有一个自己的运行时常量池。

最容易搞混的是 字符串常量池, 包括很多教材都弄错了, 它是java.lang.String类维护的一个私有的类似于KV结构的常量池, String.intern方法就使用了该结构的数据, 它是使用本地代码来维护的,

它用于在大量重复字符串时优化内存用量(例如某业务中大量使用全国地名, 性别字符串等... 使用intern能节省真的不少内存)。但是intern方法是线程安全的,所以, 在高频代码中我们应该把它的竞争特性考虑在编码中。 (未验证)

这个内容在JVM规范5.1节中介绍

更高级一些的加载约束

JVM规范5.3.4小节

JVM如何调用Java函数

JVM执行java字节码产生函数调用。调用的指令有:

其中, 就调用效率而言

invokestatic > invokespecial > invokevirtual > invokeinterface > invokedynamic

• invokestatic 采用静态绑定, 在方法进行调用点解析一次之后无需再次解析, 每次调用都直接跳转到调用点, 相比于invokespecial因为静态方法无需this指针, 所以并不会将调用者对象压栈。

• invokespecial 采用静态绑定, 类似于invokestatic, 相比后者, 它需要一个this指针, 所以需要对调用的主题进行压栈。 (我本来以为它只能用于对私有或者final方法的调用的, 但是看了虚拟机标准之后发现它可以用于调用protected的方法, 还有一系列的查找规则, 但是我没能实现出这些场景, 还是简单以我以上的认为吧, 八成应该都是正确的。)

• invokevirtual 采用类似于虚表的方式将方法列出, 然后再在调用时根据第一个操作数去查找虚表,在虚表中匹配合适的方法产生调用。这其中比之invokespecial至少多出一个查表的查询操作。 (未经验证的资料指出, jvm会通过记录虚表索引的方式来进行查找优化,使每次调用不必进行搜索,这个有待考证,我想因为泛华的类型去查找最具体的方法,使用最直接的方法应该是不行的,实际测试效率也是这样, 所以对这个说法存疑)

• invokeinterface 采用动态绑定, 类似于invokevitual, (它不需要检查方法的访问权限, 但是可能一个类同时实现多个接口的原因, 它至少每次调用都去查表, 所以我认为它比invokevirtual更慢)。

• invokedynamic 采用程序自定义绑定, 每次这个指令出现的位置都成为一个动态调用点(dynamic call site), 它执行引导代码等一系列过程完成绑定, 然后执行该调用点。对于极少数的情况虚拟机会进行优化, 使之不需要每次执行这个指令都进行绑定, 但是在大多数情况下, 每次调用都需进行引导绑定。它复杂的一笔, 所以效率最低。

  invokedynamic在jvm7首次加入(但是jdk7版本的javac编译器并不能生成含有该指令的字节码)供运行在jvm上的其他基于字节码的动态语言使用, java8中javac首次能生成包含该指令的字节码, 用以实现lanmbda表达式。

就实际工程上来说, 这些调用方式的额外开销几乎可以忽略, 但是应该知道。

JVM是怎么实现invokedynamic的

这个问题单独写了一篇, 这里 指向引用

Java内存模型

java内存模型大概有7条happens-before规则, 不必一一记住,因为都挺简单直观。

这里需要知道的是, 这里的happens-before规则所确定的不是代码执行顺序而是可见性保证。

举个栗子:

1
2

int a = 10;
int b = a;

更深一层的点

即时编译 JIT

编译器类型

• C1编译器
  • j7之前hotspot在-client模式默认使用的编译器, 编译效率快, 但是目标代码执行效率较低。
• C2编译器
  • j7之前hotspot在-server模式默认使用的编译器, 编译效率低, 但是生成的目标代码执行效率高。
• Graal编译器
  • j10采用的实验性质的编译器, 它本身使用java编写, 运行于jvm环境, 自身也可受到jit的优化。相较于C2, 它采用更加激进的优化策略。编译效率未测试,但是编译的目标代码不比C2的编译成果效率低。

分层编译

方法内联

HotSpot虚拟机的intrinsic

逃逸分析

基于逃逸分析做的优化

1. 锁消除

• 如果即时编译器能够证明锁对象不逃逸，那么对该锁对象的加锁、解锁操作没有意义。这是因为其他线程并不能获得该锁对象，因此也不可能对其进行加锁。在这种情况下，即时编译器可以消除对该不逃逸锁对象的加锁、解锁操作。

• 实际上，传统编译器仅需证明锁对象不逃逸出线程，便可以进行锁消除。由于 Java 虚拟机即时编译的限制，上述条件被强化为证明锁对象不逃逸出当前编译的方法。

2. 栈上分配(OSR)

• 由于实现起来需要更改大量假设了“对象只能堆分配”的代码，因此 HotSpot 虚拟机并没有采用栈上分配，而是使用了标量替换这么一项技术。

3. 标量替换

• 所谓的标量，就是仅能存储一个值的变量，比如 Java 代码中的局部变量。与之相反，聚合量则可能同时存储多个值，其中一个典型的例子便是 Java 对象。 标量替换这项优化技术，可以看成将原本对对象的字段的访问，替换为一个个局部变量的访问。这些变量不再要求按照堆对象那样连续分配，甚至可以直接存储在寄存器中不占用内存，对象头则直接消失。

Java Agent与字节码注入

可以不知道的点

即时编译器的中间表达形式

volatile 字段的虚共享

随机数的性质

随机性

顾名思义, 就是生成的随机数数列具有杂乱无章的性质的性质, 即, 无规律性, 生成的序列应该无统计数偏差。

例如:

若生成的序列为 1, 2, 3, 4, 5, 6 .... 这样的与序列相关的, 异或是 1, 2, 3, 1, 2, 3, 1, 2, 3 这样的周期性的, 异或是 6, 1, 6, 2, 6, 6 , 1, 6 这样某一个或者几个特殊元素优于其他元素大概率出现的, 则是不具有随机性的表现。

不可预测性

不可以预测性指的是, 在得知已经生成了的随机序列和随机算法的情况下, 也无法预测接下来随机的结果会是什么的性质。

要满足该性质,那么必然要满足, 从后一个或者多个随机数中, 无法反推出随机数生成器的内部状态的性质。

如果一个随机数生成器能满足不可预测性, 那么它一定是满足随机性的。

不可重现性

不可重现性指的是, 在至少具备了所有相同的初始条件下, 通过生成器两次或者多次生成的随机数数列不相同, 即, 没有办法重现某次输出的随机数列。

仅使用软件无法实现具有不可重现性的随机数生成器。

如果一个随机数生成器能满足不可重现性, 那么它一定是满足不可预测性的。

真随机?

只具备随机性和不可预测性的随机数叫做伪随机数, 具备不可重现性的随机数叫做真随机数。

计算机科学中使用的随机算法

在一般编程语言中, 都会提供两类随机, 例如Java提供了java.util.Random, 但是它并不能用于密码和安全相关的用途, Java另外提供了 java.security.SecureRandom 类用于实现这个用途。

安全相关的用途应该使用安全的随机算法, 不可以直接使用普通的随机

重要的连续分布

各分布简介

均匀分布

均匀分布的定义

如果连续随机变量X的概率密度函数为：

\[ p(x)= \begin{cases} \frac{1}{b-a}, &a < x < b\\ 0, & 其它 \end{cases} \]

则称X服从区间(a,b)上的均匀分布，记作 \(X\sim U(a,b)\) ，其累积分布函数为：

\[ F(x)=\begin{cases} 0,&x < a\\ \frac{x-a}{b-a},&a\le x \le b\\ 1,&x > b \end{cases} \]

期望和方差分别为：

\[ E(X)=\frac{a+b}{2},\quad Var(X)=\frac{(b-a)^2}{12} \]

正态分布

二项分布原是一个离散分布模型。 但是, 当伯努利实验次数较多的时候, 二项分布的计算较为困难(没有计算机的时候), 所以, 就有了逼近二项分布, 在当n比较大的时候用于逼近二项分布。

逼近二项分布的定义

X服从于二项分布

\[ X \sim b(n, p) \]

那么它的期望和方差为

\[ \begin{split} \mu & = np \\ \sigma^2 & = np(1-p) \end{split} \]

则可以使用以下公式逼近二项分布

\[ p(x)=\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{(x-\mu)^2}{2\sigma^2}},\quad -\infty < x < +\infty \]

这个逼近的分布方式, 就是 正态分布 (normal distribution), 也叫做 高斯分布 (Gaussian distribution)

其累积分布函数为:

\[ F(x)=\frac{1}{\sigma\sqrt{2\pi}}\int_{-\infty}^{x}e^{-\frac{(t-\mu)^2}{2\sigma^2}}\mathrm{d}t \]

正态分布的重要性质

线性

若有随机变量X符合正态分布

\[ X\sim N(\mu, \sigma^2) \]

那么则有

\[ aX+b \sim N(a\mu + b, a^2\sigma^2) \]

这条重要的性质可以使得任意的正态分布转换为标准正态分布。

即:

若有

\[ \text{若有} X \sim N(\mu, \sigma^2) \]

则有

\[ \ Z = \frac{X-\mu}{\sigma} \sim N(0, 1) \]

上α分位点

如果有 \(Z\sim N(0,1)\) ，如果 \(z_\alpha\) 满足：

\[ P(Z > z_\alpha) = \alpha,\quad 0 < \alpha < 1 \]

那么称点 \(z_\alpha\) 为标准正态分布的 上α分位点。

六西格玛

对于随机变量 \(X\sim N(\mu, \sigma^2)\)

不论 \(\mu , \sigma\) 的取值是什么, 其中, 关于 \(\mu\) 对称的面积都是确定的

\[ \begin{split} P(\mu-\sigma\le X\le \mu+\sigma)\approx 68.26\% \\ P(\mu-3\sigma\le X\le \mu+3\sigma)\approx 99.72\% \end{split} \]

指数分布

指数分布的定义

若随机变量X的概率密度函数为：

\[ p(x)=\begin{cases} \lambda e^{-\lambda x}, & x \ge 0\\ 0,& x < 0 \end{cases} \]

其中 \(\lambda > 0\) ，称X服从指数分布，也可以记为：

\[ X \sim Exp(\lambda) \]

累积分布函数为：

\[ F(x)=\begin{cases} 1-e^{-\lambda x}, & x \ge 0\\ 0,& x < 0 \end{cases} \]

指数分布 \(X\sim Exp(\lambda)\) 的期望和方差为：

\[ E(X)=\frac{1}{\lambda},\quad Var(X)=\frac{1}{\lambda^2} \]

指数分布的性质

无记忆性

ARTS-10

Algorithm

引言

做了太多的二叉, 本来想着尽量做一些从数学上的高效求解的题目, 但是我的博客数学公式渲染有问题,我还没能搞定, 所以这次来个DP问题。

Description

70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2

Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps

Example 2:

Input: 3
Output: 3

Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step

大意

有一个n层的楼梯, 每次你可以迈一层或者两层, 问, 爬到楼梯顶部一共有多少种走法。

思路

典型的动规问题。虽然也有其他一些不同的解法, 例如穷举, 但是效率太低,并不合适。

这里具体不再展开, 本篇解法会在Share当中分享。

Code

代码可以更加精简, 基本4~5行就能够完成, 但是我为了尽量通过代码能体现思路, 按照思路的进行续来编码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int climbStairs(int n) {
        if (n==1)
          return 1;
        if (n==2)
          return 2;
      
        int stair_1 = 2;    // pre stair ways
        int stair_2 = 1;    // the second pre stair ways
        int stair = 3;
        while (stair++ <= n) {
          int old = stair_2;
          stair_2 = stair_1;
          stair_1 = stair_2 + old;
        }
        return stair_1;
    }
};

Result

Success Details

Runtime: 4 ms, faster than 87.64% of C++ online submissions for Climbing Stairs.

Memory Usage: 8.2 MB, less than 78.25% of C++ online submissions for Climbing Stairs.

Review

Tips

RSA 非对称加密算法原理

欧拉函数

在数论中，对正整数n，欧拉函数 \(\varphi(n)\) 是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。 欧拉函数

RSA 算法的核心: 欧拉定理

. > 在数论中，欧拉定理（也称费马-欧拉定理或欧拉 \(\varphi\) 函数定理）是一个关于同余的性质。欧拉定理表明，若 n,a为正整数，且 n,a 互素（即 \(\gcd(a,n)=1\) ），则

\[\begin{equation}a^{\phi{\left(n\right)}} \equiv 1 \pmod n \end{equation}\]

欧拉定理

费马小定理: 欧拉定理的特例

费马定理的表达式 :

\[ a^{\phi{\left(n\right)}} \equiv 1 \pmod n \]

在特殊情况下, 当n为质数时, \(\varphi(n)=n-1\), 此时, 欧拉定理的表述即为:

\[ a^{n-1} \equiv 1\pmod n \]

这个公式就是费马小定理。

模反元素

如果两个正整数 a 和 n 互质, 那么一定存在一个整数 b 满足:

\[ ab \equiv 1\pmod n \]

即, (ab - 1)能被n整除。 b就叫做a的模反元素。 显然的, 模反元素并不唯一, 对于模反元素b, 对于所有的正整数 $m=b+kn$也为a的模反元素。

模反元素必然存在

对费马定理进行变形:

\[ a^{\phi\left({n}\right)}\equiv a\times a^{\phi\left(n\right)-1}\equiv 1 \pmod n \]

在此变形中, \(a^{\phi\left(n\right)-1}\) 即为a的模反元素。

RSA 基本概念

我们约定:

• RSA加密秘钥为E, 它是一个大整数。
• RSA解密秘钥为D, 它是一个大整数。
• RSA加密和解密需要用的模数N, 它是一个大整数。

RSA 加密过程

\[ 密文 = 明文^E mod N \]

RSA 加密过程就是这么简单, 它对明文做一个E次幂运算, 然后对N取模。 在这个过程中, E和N的组合就是公钥。

RSA 解密过程

对应的, RSA的解密过程也非常简单:

\[ 明文 = 密文^D mod N \]

RSA 的加密和解密过程完全一致, 只是它们换了一个秘钥, 进行了完全一样的运算。 在这个过程中, D和N的组合就是私钥。

非对称秘钥对的生成

在基本概念中, 约定了几个量, E, D, N 在这里,我么继续沿用, 额外的,在生成密钥对的过程中, 引入一个新的量L, 它只用于生成密钥对, 但是最终结果中我们并不体现它。

1. 求N

准备两个大质数p, q。(p和q要最够大)

\(N=p \times q\)

2. 求L

L是 p-1 和 q-1 的最小公倍数。

\(L=lcm(p-1. q-1)\)

实际上, 理论公式上, L应为ϕ(n), 这样后面的一系列推倒便是欧拉定理的应用了, 但是在实际中,它可以化简为更小的最小公倍数L, 这里,我们使用了实际中的化简方案

3. 求E

E是一个比1大, 比L小的数字,且E和L要互质, 即 E和L的最大公约数为1, 表达为数学语言为。

\[1 < E < L\\ \gcd(E, L) = 1\]

计算E的过程我们采用随机穷举的模式, 使用伪随机数生成器, 随机生成一个1和L之间的数字, 判断是否满足它与L互质, 如果不满足, 则重复生成并判断下一个随机数。

至此, RSA的公钥部分E,N我们已经得到了, 公钥: (E, N)。

我们加入E和L互质的这个条件,是为了满足我们需要的解密参数D一定存在

4. 求D

\(1 < D < L\)

\(E \times D\ mod\ L = 1\)

按照上述的限制条件, 计算出D, 至此, 私钥部分也计算完成, 私钥为(D, N)。

Share

算法-动态规划 Dynamic Programming--从菜鸟到老鸟

End

ARTS-9

Algorithm

Description

69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2

Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

大意

实现一个开平方的函数, 它输入一个整数x, 输出一个整数y 满足 \(y^2<=x\) 且 \((y+1)^2>x\)

思路

开平方的普遍简单做法一般有两种, 一个是二分法逼近, 一个是牛顿迭代开平方法。因为之前已经做过了太多的二分法了, 所以决定这次使用牛顿开平方法。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x==0:
            return 0
        if x==1:
            return 1

        y = x/2.0
        while abs(x-y**2) > 0.5:
            y=((y*1.0)+(1.0*x)/y)/2.0000
        return int(y)

Result

Review

Learning Python: From Zero to Hero

引言

之前medium老是给我推送javascript的文, 我越是看, 它越是推, 然而,我几乎从不写js, 这次我自己主动去看python文, 让它学习下, 以后换个口味给我推。

内容

Learning Python: From Zero to Hero

“high-level programming language, and its core design philosophy is all
about code readability and a syntax which allows programmers to express
concepts in a few lines of code.”

“高级编程语言，其核心设计理念是代码可读性和一个允许程序员用稍几行代码表达概念的语法。”

变量

1
2
3

one = 1

print(one)

数组

1
2
3
4
5
6

array = [1, 2, 3]

array[1] = 5

for v in array:
    print(v)

字典

1
2
3
4
5
6

dictionary = { "one" : 1, "two" : 2, "three" : 3}
dictionary["four"] = 4

for k, v in dictionary.items():
    print(k)
    pirnt(v)

循环

1
2

while Condition:
    doSomething()

1
2

for key in dictionary:
    doSomething(dictionary[key])

1
2

for k, v in dictionary.items():
    doSomething(k, v)

类和对象

类是对象的模板, 对象是程序使用类复刻的产物。

类中定义构造方法为 init, 它第一个参数为代表当前对象的self 类可以有对公属性和非对公属性, 对公属性普通命名, 以下划线开头的名字为非对公属性, 除了本类定义的方法外不可以访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Model:
    def __init__(self, attr1, attr2):
        self.attr1 = attr1
        self._attr2 = attr2
    
    def getAttr1():
        return self.attr1
        
    def getAttr2():
        return self._attr2

object = Model('a', 'b')
print(object.getAttr1())
print(object.getAttr2())

本篇出错

有趣的是, 在本篇评论上有个网友指出了作者在文中的一处错误

作者原文:

For a Python class, we can initialize a public instance variable within our constructor method or just inside the class.

网友评论:

That is not true!

Variables declared at class level are not instance variables, they are class attributes. Class attributes are defined outside of all the methods, usually they are placed at the top, right below the class header.

意思大意为, 作者说对于python类, 我们可以在构造函数或者类内部直接初始化一个对公变量。 网友说作者错了, 应该为, 在构造函数中初始化的是对象变量, 而类中进行声明的则为类变量。

Tips

牛顿迭代

牛顿法使用迭代来求解一个方程, 其原理大致如下:

对于一个函数 \(f(x)\) ,它的泰勒级数展开式是这样的,

\[ f(x)=f(x_0)+f'(x_0)(x-x_0)+\frac{1}{2}f''(x_0)(x-x_0)^2+...+\frac{1}{n!}f^n(x0)(x-x_0)^n \]

牛顿法使用泰勒级数前两项来代替这个函数，即用ϕ(x)代替f(x):

\[ \phi(x)=f(x_0)+f'(x_0)(x-x_0) \]

令 \(\phi\left(x\right)=0\) , 则 \(x = x_0 - \frac{f(x_0)}{f'(x_0)}\)

所以,牛顿迭代式为 \(f(x_{n+1})=x_n - \frac{f(x_n)}{f'(x_n)}\)

牛顿迭代法开平方

开平方即为求解 \(f(x)=x^2-n\) 在 \(f(x)=0\) 时的解。

代入牛顿迭代式

\[ x_{n+1} = \frac{x_n^2-n} {2x_n} \\ = \frac{x_n}{2} - \frac{n}{2x_n} \\ = \frac{1}{2}\left(x_n-\frac{n}{x_n} \right) \]

牛顿迭代开平方在代码中的写法

1
2
3
4
5
6
7
8
9
10
11

const EPS = 0.0001
func sqrt(x double) {
    reuslt := x
iteration:
    last := x
    result = (result - (x-result))/2.0
    if abs(last-result)>EPS {
        goto iteration
    }
    return result
}

Share

[直观详解]泰勒级数

End