Emacs-ng: Emacs with Deno runtime and TypeScript

Re:Emacs-ng: Emacs with Deno runtime and TypeScript by vitus on Tuesday March 16, 2021 @04:56PM (#26482852)

The speed of the naive recursive fib scales with the number it computes, which is roughly 1.6 ^ n (the eigenvalue of the matrix for the recurrence relation is the golden ratio, phi).

Intuition: if you were to expand and flatten the recursive calls, you'd end up with something like

(+ 1 0 1 1 0 1 1 0 ... 1 0)

with exactly (fib n) 1s (base case (fib 1)), and no more than (fib n) 0s (base case (fib 0)).

Simple example:

     (fib 3)
     = (+ (fib 2) (fib 1))
     = (+ (+ (fib 1) (fib 0)) 1)
     = (+ (+ 1 0) 1)
     = (+ 1 0 1)

[ Parent | on HN ]

Re:Emacs-ng: Emacs with Deno runtime and TypeScript by anthk on Wednesday March 17, 2021 @08:20AM (#26490038)

  With scm, using (trace proc):
 
 scm -f fib.scm
 
 call fib 9
    call fib 8
      call fib 7
        call fib 6
          call fib 5
          retn fib 5
          call fib 4
          retn fib 3
        retn fib 8
        call fib 5
          call fib 4
          retn fib 3
          call fib 3
          retn fib 2
        retn fib 5
      retn fib 13
      call fib 6
        call fib 5
          call fib 4
          retn fib 3
          call fib 3
          retn fib 2
        retn fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
      retn fib 8
    retn fib 21
    call fib 7
      call fib 6
        call fib 5
          call fib 4
          retn fib 3
          call fib 3
          retn fib 2
        retn fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
      retn fib 8
      call fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
        call fib 3
          call fib 2
          retn fib 1
          call fib 1
          retn fib 1
        retn fib 2
      retn fib 5
    retn fib 13
  retn fib 34
  call fib 8
    call fib 7
      call fib 6
        call fib 5
          call fib 4
          retn fib 3
          call fib 3
          retn fib 2
        retn fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
      retn fib 8
      call fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
        call fib 3
          call fib 2
          retn fib 1
          call fib 1
          retn fib 1
        retn fib 2
      retn fib 5
    retn fib 13
    call fib 6
      call fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
        call fib 3
          call fib 2
          retn fib 1
          call fib 1
          retn fib 1
        retn fib 2
      retn fib 5
      call fib 4
        call fib 3
          call fib 2
          retn fib 1
          call fib 1
          retn fib 1
        retn fib 2
        call fib 2
          call fib 1
          retn fib 1
          call fib 0
          retn fib 0
        retn fib 1
      retn fib 3
    retn fib 8
  retn fib 21
  55
 
 scm -f fib-iter.scm
 
 call fib-iter 1 0 10
    call fib-iter 1 1 9
      call fib-iter 2 1 8
        call fib-iter 3 2 7
          call fib-iter 5 3 6
          retn fib-iter 55
        retn fib-iter 55
      retn fib-iter 55
    retn fib-iter 55
  retn fib-iter 55
  55

[ Parent | on HN ]

Re:Emacs-ng: Emacs with Deno runtime and TypeScript by taeric on Tuesday March 16, 2021 @07:55PM (#26484822)

Right. I "know" how tree recursion scales up. It is still neat to "see" the impact on the speed.

That is, knowing all of these facts, it is still impressive how fast you can get (fib 1000000) using iteration and bignums.

[ Parent | on HN ]

Re:Emacs-ng: Emacs with Deno runtime and TypeScript by vitus on Tuesday March 16, 2021 @09:14PM (#26485377)

There, that runtime is roughly O(n^2) when dealing with bignums, since addition scales linearly with bit length of the operands, and bit length increases linearly with the number of iterations (~0.7 bits per iteration).

Which is still not fast -- on my laptop, Python takes about 9s for fib(1000000). But compared to an exponentially-growing function, that's a blink of an eye.

[ Parent | on HN ]