6
18
2016
1

魔法书1.1补充:平方根算法的论证

SICP 1.1 节「程序设计的基本元素」给出了一个计算平方根的算法,原书并没有给出证明,大概是因为不太适合书的主题,我在此写这个证明只是为了补充书上所缺,满足自己的强迫症,如有错误请指出!

证明

数学表达如下:

对于任意实数 [tex]b>0[/tex],数列 [tex]a_n[/tex] 的递推公式是 [tex]a_{n+1}=\frac{a_{n}+b/a_{n}}{2}[/tex],且[tex]a_1=1[/tex],那么当 n 充分大时,[tex]a_n[/tex] 可以无限接近 [tex]\sqrt{b}[/tex]。下面给出证明。

由 [tex]a_{n+1}-a_{n}=\frac{b-a_n^2}{2a_n}[/tex] 可知,当 [tex]a_n<\sqrt{b}[/tex] 时,数列 [tex]a_n[/tex] 是严格递增的;当 [tex]a_n>\sqrt{b}[/tex] 时,数列 [tex]a_n[/tex] 是严格递减的。容易知道,当 b > 1 时,数列 [tex]a_n[/tex] 严格递增且有上界;当 b = 1 时,无疑 [tex]a_n=1[/tex] 恒成立;当 b < 1 时,数列 [tex]a_n[/tex] 严格递减且有下界。因此确信数列 [tex]a_n[/tex] 收敛且存在极限,记作 [tex]a[/tex]。

递推式两边取极限得:[tex]a=\frac{a+\frac{b}{a}}{2}[/tex]

整理即得:[tex]a=\sqrt{b}[/tex]

也就是,当 n 充分大时,[tex]a_n[/tex] 可以无限接近 [tex]\sqrt{b}[/tex]。

注记

我一开始认为 [tex]a_1[/tex] 是可以选取任意正数的,后来计算一番发现,存在特定的组合 [tex]a_1[/tex] 和 [tex]b[/tex],使得数列不收敛。如当 [tex]{a_1}^2=\frac{\sqrt{2}+1}{3}b[/tex] 时,[tex]a_3 = a_1[/tex],此时所有奇数项相等,所有偶数项相等,数列围绕 [tex]\sqrt{b}[/tex] 摆动而不收敛。尽管在计算机上存在浮点数舍入误差,不一定能产生预期的效果,但是只有当[tex]a_1=1[/tex]时才能在数学上严格证明出对于所有正数 [tex]b[/tex] 都一定能求出算数平方根的近似值。

实际上迭代算平方根的方法很多,比如说还可以由 [tex]c^2-1=b-1[/tex] 得到 [tex]c_{n+1}=\frac{b-1}{c_n+1}+1[/tex],可以证明该数列的极限也是 [tex]\sqrt{b}[/tex](选取恰当的 [tex]c_1[/tex])。在此不再赘述。

Category: 编程 | Tags: SICP
10
17
2014
71

(lib)Tcl 现代方法:变量

之前有人问到如何从 C 端访问 Tcl 变量,此处做一总结。庶几不失「现代」之名。有关 Tcl_Obj 的维护者资料击此

于是终于回到了主线。《Tcl 现代方法》本来是作为记录 Tcl 现代用法的系列博文,一开始是介绍 C 库的,但是后来 Tcl 脚本的内容反倒更多,结果现在纯粹谈起来 C 库又会导致歧义,因此在标题前加上 lib 标记,以示内容是 C 库而非 Tcl 脚本。

Category: 编程 | Tags: tcl tcl 现代方法
10
4
2014
4

Tcl 现代方法:你知道几种写类的方法?

本文是从底向上逐步构建其 TclOO 大框架的,如果你更喜欢自顶向上的,可以参考别的教程。

另外,本文只是入门级别,读完本文后再去看文档或者其他教程应该会容易些,毕竟是汉语写的。这里我推荐 Ashok 写的《Tcl Programming for Windows》中的 TclOO 一章。

除去协程,面向对象编程也是现代编程语言不可或缺的一部分。Tcl 在 8.6 之前都没有内建支持面向对象编程,但这不意味着 Tcl 没法 OO——恰恰相反,Tcl 有一大堆 OO 库,我随口就能叫出几个出名的:[incr Tcl]、XOTcl、Snit。这些库各有千秋,有的模仿 C++,有的是原型继承,还有的是模仿 Common Lisp Object System,千姿百态。可能和大家所想不同,这样的「大好」局势并未给 Tcl 带来许多好处:依然有人批评 Tcl 没有 OO 支持;有的人虽然知道有,但批评选择太多让用户无所适从,或者为自己所爱的库口诛笔伐;有的人虽然不在乎别人怎么选择,但很苦恼其他扩展包依赖了自己根本不需要的 OO 库……在这种情况下,Tcl Core Team 站了出来,提出了 TIP 257,由 Donal K. Fellows 主要实现。这套面向对象机制起名叫做 TclOO,并随 Tcl 本身提供。TclOO 的设计十分灵活,可以以此为基础重新制作 [incr Tcl] 等库,让大家其乐融融地生活在一起。

思考一下,开源系统的桌面环境是不是也是这样呢?

Category: 编程 | Tags: tcl tcl 现代方法 tcloo
10
2
2014
4

Tcl 现代方法:协程(coroutine)

协程已经是现代语言的必备要素了。Tcl 的协程仿效的是 Lua,在 8.6 版本中引入。(感谢 NRE 引擎!)

 

Category: 编程 | Tags: tcl coroutine tcl 现代方法
9
30
2014
0

Tcl 现代方法:TclHttpd 入门

TclHttpd 是 Tcl 界人尽皆知的有名软件,功能强大,易于使用。在其原作者不再维护之后,Cliff 和 Sean 于最近接手维护,使之支持最新的 8.6。

Category: 编程 | Tags: tcl tcl 现代方法 tclhttpd
9
21
2014
0

Tcl 现代方法:tailcall

Tailcall 是 Tcl 8.6 引入的新功能。功能如其名,本来是用来实现尾调用的。

Category: 编程 | Tags: tcl tcl 现代方法
9
21
2014
1

Tcl 现代方法:eval 方法大全

#include <tcl.h>

/**
 * puts [set a [expr {20 * 30}]
 */
void EvalString(Tcl_Interp *interp) {
    Tcl_Obj *result;
    char script[] = "set a [expr {20 * 30}]";
    
    if (Tcl_Eval(interp, script) != TCL_OK) {
        fprintf(stderr, "Error was: %s\n", Tcl_GetStringResult(interp));
        return;
    }
    result = Tcl_GetObjResult(interp);
    printf("%s\n", Tcl_GetStringFromObj(result, NULL));
}

/**
 * puts [set a [expr {30 * 30}]]
 */
void EvalStringObj(Tcl_Interp *interp) {
    Tcl_Obj *script;
    Tcl_Obj *result;
    
    script = Tcl_NewStringObj("set a [expr {30 * 30}]", -1);
    Tcl_IncrRefCount(script);
    Tcl_EvalObjEx(interp, script, 0);
    result = Tcl_GetObjResult(interp);
    printf("%s\n", Tcl_GetStringFromObj(result, NULL));
}

/**
 * puts {hello world}
 */
void EvalListObj(Tcl_Interp *interp) {
    Tcl_Obj *cmd;
    cmd = Tcl_NewObj();
    Tcl_ListObjAppendElement(interp, cmd, Tcl_NewStringObj("puts", -1));
    Tcl_ListObjAppendElement(interp, cmd, Tcl_NewStringObj("hello world", -1));
    Tcl_IncrRefCount(cmd);
    Tcl_EvalObjEx(interp, cmd, 0);
    Tcl_DecrRefCount(cmd);
}

/**
 * puts [set a 32]
 */
void Eval(Tcl_Interp *interp) {
    int i;
    Tcl_Obj *scriptArr[3];
    Tcl_Obj *resultObj;
    int result;
    
    scriptArr[0] = Tcl_NewStringObj("set", 3);
    scriptArr[1] = Tcl_NewStringObj("a", 1);
    scriptArr[2] = Tcl_NewIntObj(32);
    for (i = 0; i < 3; ++i) {
        Tcl_IncrRefCount(scriptArr[i]);
    }
    Tcl_EvalObjv(interp, 3, scriptArr, 0);
    for (i = 0; i < 3; ++i) {
        Tcl_DecrRefCount(scriptArr[i]);
    }
    resultObj = Tcl_GetObjResult(interp);
    Tcl_IncrRefCount(resultObj);
    Tcl_GetIntFromObj(interp, resultObj, &result);
    Tcl_DecrRefCount(resultObj);
    printf("%d\n", result);
}

int main(int argc, char *argv[]) {
    Tcl_Interp *interp;
    
    interp = Tcl_CreateInterp();
    EvalString(interp);
    EvalStringObj(interp);
    EvalListObj(interp);
    Eval(interp);
    Tcl_DeleteInterp(interp);
    return 0;
}
Category: 编程 | Tags: tcl tcl 现代方法
8
28
2014
1

Tcl 实现伪闭包

proc lambda {vars args body} {
    set exvars [lmap var $vars {
        upvar $var localvar
        list $var $localvar
    }]
    lappend args {*}$exvars
    list apply [list $args $body]
}

简单地用 apply 实现一个“伪闭包”。其中 {*} 需要 Tcl 8.5,[lmap] 需要 8.6。

所谓“伪”是因为这个函数没法真正地持有变量引用,只能复制一下。有点像是缩水版的 C++ 闭包frown。虽说只是复制,但还是十分好用,因为 Tcl 在核心层面的“复制”使用的是引用计数,而且若原函数退出,也不会影响到匿名函数里面的变量,毕竟 Tcl 是没有垃圾收集的,这样做凑合能算不错吧。

有个比较遗憾的限制是,因为我比较懒,用“可选参数”实现了变量复制,所以如果参数列表有 args 且使用了外部变量,就会退化到普通的变量(正如 lambda 自身的 args)。

这个函数基本用法是这样的:

set x 100
{*}[lambda x {a b} {
    puts "x = $x\na=$a\nb=$b"
}] 10 20

自然,你也可以给 lambda 返回的“闭包”一个名字:

set x 100
set closure [lambda x {a b} {
    puts "x = $x\na=$a\nb=$b"
}]
{*}$closure 10 20

实际上,这玩意在 Tk 上最好用:

proc foo {} {
    set msg "使用 lambda 辅助函数十分方便吧!"
    ttk::button .b -text 点我 -command [lambda msg {} {
        tk_messageBox -message $msg
    }]
    pack .b
}
foo

一般情况下,Tk 直接这样写是不行的,因为 -command 是在全局命名空间里执行的:

proc foo {} {
    set msg "这是不行的!"
    ttk::button .b -text 点我 -command {
        tk_messageBox -message $msg
    }
    pack .b
}
foo

会报错找不到 msg 变量。

如果你比较熟悉 Tcl,可能想问为什么不用 subst,像下面这样:

proc foo {} {
    set msg "hello tcl!"
    ttk::button .b -text 点我 -command [subst -nocommands {
        tk_messageBox -message $msg
    }]
    pack .b
}
foo

我开始也以为可以,但遗憾的是,不行。因为 Tk 使用 eval 处理 command,在上面的例子中,eval 会把原来好好的命令曲解成这样:

tk_messageBox -message hello tcl!
# 也就是
tk_messageBox -message {*}"hello tcl!"

这是因为 eval 使用了 concat,而 concat 会把列表展开一层,正如 {*} 一样:

concat {{1 2} 3} 4
# → {1 2} 3 4

eval 的“展开”特性在少数情况下有用,大部分情况下 {*} 就可以替代 eval,在此不赘述。

Category: 编程 | Tags: tcl

Powered by Chito | Hosted at is-Programmer | Theme: Aeros 2.0 by TheBuckmaker.com