What is your magnum opus?

I created a Scheme LISP compiler that assembles to machine code in x86 format. What have you guys done that many people use today?

>>40
It can do fib 100000000 in less than 2 seconds if your machine has enough RAM.

>>41
proof or GTFO.

>>40
do your own damn project euler questions!

>>42
You are not welcome here.

>>42
It should be trivial to implement it in O(1) using memoization, however this would mean high RAM usage. And one can use a hybrid approach which requires very little RAM(constant), where only the last 2 values of fibs are stored and passed recursively(tail-recursive, so can be implemented as iteration too). The hybrid approach has one disadvantage to the memoization version, as the first should be able to instantly return a previously calculated fibs, while the hybrid one actually recalculates fibs each time.

P.S.: I'm not >>41

O(1)

Your use of this term intrigues me. Have we forgotten amortization, /prog/?

One could use that formula to calculate fib n, though it technically isn't "O(1)"

>>46
It's O(1) with probability of 1.

Fibs discussion is the height of /prog/ achievements. Continue.

O(1) fibonacci is only possible for fixed-size integers. and it's slow as fuck unless that size is extremely small (much smaller than you'd need for fib 100000000). so it's actually completely useless.

My attempt at the hybrid version:


(*let fibs n =
  let rec fibq fkm1 fkm2 k n =
    if (n<2) then (if (n=0) then 0 else 1)
    else if (n=k) then (fkm1+fkm2)
         else fibq (fkm1+fkm2) fkm1 (k+1) n
  in fibq 1 0 2 n*)

(*#load "nums.cma";;*)

open Big_int;;

let fibs_big n =
  let rec fibq fkm1 fkm2 k n =
    if (n<2) then (if (n=0) then big_int_of_int(0) else big_int_of_int(1))
    else if (n=k) then (add_big_int fkm1 fkm2)
         else fibq (add_big_int fkm1 fkm2) fkm1 (k+1) n
  in fibq (big_int_of_int(1)) (big_int_of_int(0)) 2 n;;

let f10_8 = string_of_big_int (fibs_big 1000000);;

print_endline f10_8;
flush stdout

It actually runs in a reasonable amount of time, but something like 10**10 is very slow due to the amount of memory needed to represents the bignums as >>50 stated

>>51
You spelled let* wrong.  (Didn't read past that.)

>>52
It's not LISP code, but O'Caml code. The code compiles and runs fine. IHBT

let f10_8 = string_of_big_int (fibs_big 1000000);;
that's only 10⁶, idiot.

>>53
It also works in F# if you use option strict