生成黄金比例 (Phi) 的 n 位数字
0/5 (0投票)
用 Scheme 编写的高度优化的程序，可以准确生成黄金比例的数字
项目目标
此项目的目标是实现并评估一种算法，该算法采用 Scheme 中无限流的概念，以便精确地评估无限数字序列的第 n 位。
我们特别计划评估的序列是黄金比例，即斐波那契数列 F n+1 与 Fn 的比值在 n 趋于无穷大时的极限。
重要的是，我们的解决方案不应近似此值。
我们还计划通过使用更精确的数学方法来确定黄金比例的值，从而比较我们解决方案的正确性，利用该序列的固有属性，即黄金比例的极限，当项数趋于无穷大时，可以用以下公式表示：
Golden Ratio Value = (1 + sqrt{5} )/2
引言
黄金比例，一种在数学中自然出现的数字，是该学科中最令人着迷的数字之一，并且由于它在自然界中的出现，在向日葵、锥花和松果的种子角度几何中观察到它，以及许多其他地方。 它也被大量用于建筑中，并且现在有一些证据表明，从希腊人开始，该比例以某种形式或另一种形式被用于大多数后来的建筑作品中。
当然，有很多方法可以计算这个比例（顺便说一句，它是一个无理数），因此它由无限级数的收敛或涉及无理数的公式表示。 然而，该比率是实数，不包括虚部。
以下是评估此比率的几种方法。
实现
我们专注于两种方法来解决生成代表黄金比例的无限流的问题。
第一种方法涉及计算第 (N+1)th 斐波那契数与第 Nth 斐波那契数的比率。
第二种方法涉及计算比率 (1 + v5 )/2。 这种方法的重点是计算 5 的平方根，我们用无限流来表示。 Scheme 允许通过使用关键字 delay 来延迟表达式的求值，然后通过使用关键字 force 来求值表达式。
a) Cons-Stream
流本质上由一个已经评估的值作为流中的第一个值组成，以及如果强制流返回另一个值时将返回另一个值的承诺。
上面发生了两件事
- 它将 cons-stream 作为新的语法规则添加到环境中，以便以后再次使用（作为语法）
- 它设置了 cons-stream 的定义，以暗示一对对象，其中第一个对象表示可以立即检索到的有形值，而第二个对象是承诺如果流当然要求这样做，则返回另一个值。（这本质上是关键字 delay 的含义）。
a) 斐波那契近似法
;Infinite Fibonacci Stream
(define fibs
(cons-stream 0 (cons-stream 1 (add (tail fibs) fibs))))
(define goldenRatioStream
(lambda (n)
(/ (getn fibs (+ n 1)) (getn fibs n))))
b) 平方根近似法
我们用来计算 5 的平方根的算法是公元前 1700 年左右巴比伦人熟知的除法和平均算法，巴比伦人。
以下是从 www.mathpath.org 提取的该算法。 初步猜测是任意的，但必须是非零的，虽然下面给出的例子设置 A = 2，为了简单起见，我设置 A = 1。
关注点
我实现了一个自定义的除法算法，该算法生成一个无限除法循环，用于除两个不可整除的数字，可以在许多不同的应用程序中重用。 对于一个可以精确地将一个数学数字打印到无限长度以达到任何精度的程序来说，该代码非常简单。
;Custom Scheme Fraction to Decimal Conversion
(define gr_fib_exact
(lambda (n precision)
(divide (getn fibs (+ n 1)) (getn fibs n) precision )))
结论
最后，我们看一下我们的数据，该数据描述了黄金比例的增加项的评估，随着序列的增加，更多的位数锁定到某些位置，并且随着序列中项数的增加，它们的值不会改变。
进一步检查，我们注意到，如果索引 i 处的数字 d（例如）（从小数点从左到右 i 位）在黄金比例的两个项中连续出现多次（随着 n 的增加），那么它会锁定在该位置，并且序列的增加项不会更改索引 i 处的值 d。
通过参考附录 C，我们从理论上证明了，如果与该值关联的 N（由公式给出）大于用于评估黄金比例的 n 值，则给定的 d（其中 d 指的是小数点后的 i 位）对于黄金比例在该索引处（小数点后的 i 位）的正确值是完全准确的。
n = 5/2(d + 1)
代码列表
Call.SCM
;This calls the EXACT fibonacci function n Times from (1 to n) with a Precision of 300
(loop gr_fib_exact 10 300)
;This calls the EXACT square root algorithm function n Times from (1 to n)
with a Precision of 10
;This function is much slower and a n value > 15 took more than 1 minute
on my 2 GB RAM machine
(loop gr_square_inexact4 10 10)
Golden.SCM
;Evaluate Golden Ratio using Different Methods
(require (lib "trace.ss"))
;Loads Relevant Stream Functions
(require "stream.scm")
;Square Root Functions
(define (average x y ) (/ (+ x y) 2))
(define (sqrt-improve guess x)
(average guess (/ x guess)))
;Note the 1.0 (this is inexact since Decimals are forced in the recursion)
(define (sqrt1 x)
(define guesses (cons-stream 1.0 (applyproc (lambda (guess)
(sqrt-improve guess x)) guesses))
)
guesses
)
;Note that this is Exact ( since only Fractions are used in Recursion)
(define (sqrt2 x)
(define guesses (cons-stream 1 (applyproc (lambda (guess)
(sqrt-improve guess x)) guesses))
)
guesses
)
;Four Ways of Using Recursion varying by Exact |
Inexact Recursion and Exact | Inexact Calling towards the End
(define gr_square_inexact1
(lambda (n)
( exact->inexact (/ (+ 1 (getn (sqrt1 5) n)) 2))))
(define gr_square_inexact2
(lambda (n)
( / (+ 1 (getn (sqrt2 5) n)) 2)))
(define gr_square_inexact3
(lambda (n)
( exact->inexact (/ (+ 1 (getn (sqrt2 5) n)) 2))))
(define gr_square_inexact4
(lambda (n precision)
(
letrec((x (/ (+ 1 (getn (sqrt2 5) n)) 2)))
(divide (numerator x) (denominator x) precision))))
;Infinite Fibonacci Stream
(define fibs
(cons-stream 0 (cons-stream 1 (add (tail fibs) fibs))))
(define goldenRatioStream
(lambda (n)
(/ (getn fibs (+ n 1)) (getn fibs n))))
;Native Scheme Fraction to Decimal Conversion
(define gr_fib_inexact
(lambda (n)
( exact->inexact (/ (getn fibs (+ n 1)) (getn fibs n)) )))
;Custom Scheme Fraction to Decimal Conversion
(define gr_fib_exact
(lambda (n precision)
(divide (getn fibs (+ n 1)) (getn fibs n) precision )))
(define ge2
(lambda (n)
( exact->inexact (/ (+ 1 (getn (sqrt 5) n)) 2) )))
(define ge2
(lambda (n)
(let ((x (/ (+ 1 (getn (sqrt 5) n)) 2)))
(divide (numerator x) (denominator x) n)
)))
(define ratio
(lambda(term precision)
(display 'Golden_Ratio_using_Fibonacci_at_N= )
(display term)
(display " ")
(display 'Precision=)
(display precision)
(display " ")
(display 'is )
(display " ")
(newline)
(display (ge1 term precision))
(newline)
(display 'Golden_Ratio_using_Square_Root_Method )
(display " ")
(display 'Precision=)
(display precision)
(display " ")
(display 'is )
(display " ")
(newline)
(display (list (ge2 term ) )
)))
(define integers
(lambda(n)
(cons-stream n (integers (+ n 1)))))
;Evaluates a Function from 1 to N, spaced by a NewLine
(define (loop proc n precision)
(call-with-current-continuation
(lambda (stop)
(define (inner-loop proc i)
(cond ((> i n) (stop 'done))
(else
(display (proc i precision))
(newline)
(inner-loop proc (+ i 1))
)))
(inner-loop proc 1))))
List.SCM ;Scheme 中惰性求值的教程
(delay (+ 5 6))
;Returns; #<struct:promise>
;(force (delay ( + 5 6)))
;11
;Call Promise
(let
(
(delayed (delay (+ 5 6)) )
)
(force delayed)
)
;Returns 11
;These are the Header Files, sort of the Core Functions that Are Used Later on.
(define-syntax cons-stream
(syntax-rules ()
((cons-stream x y)
(cons x (delay y)))))
;Just the First element of the Stream
(define head
(lambda(stream)
(car stream)))
;Forces Evaluation of the Cdr of the Stream
(define tail
(lambda(stream)
(force(cdr stream))))
;Adds two Streams (in Reality it only adds the First Element of Both Streams,
but Promises to add the Rest of the Stream later, by delaying it)
(define add
(lambda (s1 s2)
(cons-stream (+ (head s1) (head s2) ) (add (tail s1) (tail s2)))))
;Gets the First N Characters of any Stream, by recursively
Forcing evaluation of the Stream one at a time.
(define get
(lambda(stream n)
(cond
((= n 0) '())
(else (cons (head stream) (get (tail stream) (- n 1)))))))
;Gets the Nth Character of any Stream, by discarding all characters
until it reaches the Nth character. N here serves as a counter.
(define getn
(lambda(stream n)
(cond
((= n 0) (head stream))
(else (getn (tail stream) (- n 1))))))
;Define a List of Infinite Ones
(define ones (cons-stream 1 ones))
;Gets Integers from n Onwards (Example 1)
(define integers
(lambda(n)
(cons-stream n (integers (+ n 1)))))
;Prime Nos (Example 2)
(define (divisible? x y) (= (remainder x y) 0))
(define sieve
(lambda(stream)
(cons-stream (head stream) (sieve (filter (lambda(x)
(not (divisible? x (head stream)))) (tail stream))))))
(define filter
(lambda(p lst)
(cond
((null? lst) '())
((p (head lst)) (cons-stream (head lst) (filter p (tail lst))))
(else (filter p (tail lst))))))
(define primes (sieve (integers 2))) ;;Prime Seed Value of 2
(get primes 5)
;(2 3 5 7 11)
;Fibonacci Series (Example 3)
(define fibs
(cons-stream 0 (cons-stream 1 (add (tail fibs) fibs))))
(define golden
(lambda (n)
(/ (getn fibs (+ n 1)) (getn fibs n))))
历史
- 2010 年 3 月 3 日：首次发布