6 ms·

There may be a faster or cleverer way to do it but here's a basic tail recursive fibonacci: (defun nth-fibonacci (n &optional (a 0) (b 1)) (if (= n 0

There may be a faster or cleverer way to do it but here's a basic tail recursive fibonacci: (defun nth-fibonacci (n &optional (a 0) (b 1)) (if (= n 0) a (nth-fibonacci (- n 1) b (+ a b))))

Jtsummers 5y ago
Yep, that's how you'd do it. So long as your CL implementation supports tail call optimization, that will be on par with the same algorithm using loop or another looping construct.
gibsonf1 5y ago
WEB> (time (nth-fibonacci 9999)) Evaluation took: 0.005 seconds of real time 0.004520 seconds of total run time (0.000168 user, 0.004352 system) 100.00% CPU 13,120,881 processor cycles 4,716,256 bytes consed 20793608237133498072112648988642836825087036094015903119682945866528501423455686648927456034305226515591757343297190158010624794267250973176133810179902738038231789748346235556483191431591924532394420028067810320408724414693462849062668387083308048250920654493340878733226377580847446324873797603734794648258113858631550404081017260381202919943892370942852601647398213554479081823593715429566945149312993664846779090437799284773675379284270660175134664833266377698642012106891355791141872776934080803504956794094648292880566056364718187662668970758537383352677420835574155945658542003634765324541006121012446785689171494803262408602693091211601973938229446636049901531963286159699077880427720289235539329671877182915643419079186525118678856821600897520171070499437657067342400871083908811800976259727431820539554256869460815355918458253398234382360435762759823179896116748424269545924633204614137992850814352018738480923581553988990897151469406131695614497783720743461373756218685106856826090696339815490921253714537241866911604250597353747823733268178182198509240226955826416016690084749816072843582488613184829905383150180047844353751554201573833105521980998123833253261228689824051777846588461079790807828367132384798451794011076569057522158680378961532160858387223882974380483931929541222100800313580688585002598879566463221427820448492565073106595808837401648996423563386109782045634122467872921845606409174360635618216883812562321664442822952537577492715365321134204530686742435454505103269768144370118494906390254934942358904031509877369722437053383165360388595116980245927935225901537634925654872380877183008301074569444002426436414756905094535072804764684492105680024739914490555904391369218696387092918189246157103450387050229300603241611410707453960080170928277951834763216705242485820801423866526633816082921442883095463259080471819329201710147828025221385656340207489796317663278872207607791034431700112753558813478888727503825389066823098683355695718137867882982111710796422706778536913192342733364556727928018953989153106047379741280794091639429908796650294603536651238230626 WEB>
- Jtsummers 5y ago
  You may want to put extra spaces in front of those lines, and also manually break up that massive number.
weavie 5y ago
SBCL doesn't optimize tail calls by default. If I recall you have to set the optimization level prior to compiling the function using `(declaim (optimize xxx))` - where xxx is something I've forgotten. Perhaps someone can come along and point out what xxx should be?
- gibsonf1 5y ago
  Oh thats interesting!, we don't use that but use tail recursion extensively https://0branch.com/notes/tco-cl.html#sec-2-2 https://0branch.com/notes/tco-cl.html#sec-2-2
- Jtsummers 5y ago
  ; disassembly for NTH-FIBONACCI ; Size: 94 bytes. Origin: #x2264E531 ; NTH-FIBONACCI ; 31: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer ; 35: 488945F8 MOV [RBP-8], RAX ; 39: 488B55F0 MOV RDX, [RBP-16] ; 3D: 31FF XOR EDI, EDI ; 3F: E8AC343BFF CALL #x21A019F0 ; GENERIC-= ; 44: 750A JNE L0 ; 46: 488B55E8 MOV RDX, [RBP-24] ; 4A: 488BE5 MOV RSP, RBP ; 4D: F8 CLC ; 4E: 5D POP RBP ; 4F: C3 RET ; 50: L0: 488B55F0 MOV RDX, [RBP-16] ; 54: BF02000000 MOV EDI, 2 ; 59: E8C2323BFF CALL #x21A01820 ; GENERIC-- ; 5E: 488BC2 MOV RAX, RDX ; 61: 488945D8 MOV [RBP-40], RAX ; 65: 488B55E8 MOV RDX, [RBP-24] ; 69: 488B7DE0 MOV RDI, [RBP-32] ; 6D: E84E323BFF CALL #x21A017C0 ; GENERIC-+ ; 72: 488BF2 MOV RSI, RDX ; 75: 488B45D8 MOV RAX, [RBP-40] ; 79: 488BD0 MOV RDX, RAX ; 7C: 488B7DE0 MOV RDI, [RBP-32] ; 80: B906000000 MOV ECX, 6 ; 85: FF7508 PUSH QWORD PTR [RBP+8] ; 88: E99507DBFD JMP #x203FED22 ; #<FDEFN NTH-FIBONACCI> ; 8D: CC10 INT3 16 ; Invalid argument count trap Looks like it's doing tail call optimization to me, this is without doing anything special with declaim. Note that where it returns to the top is with JMP not CALL. http://www.sbcl.org/manual/index.html#Debug-Tail-Recursion http://www.sbcl.org/manual/index.html#Debug-Tail-Recursion

There may be a faster or cleverer way to do it but here's a basic tail recursive fibonacci: (defun nth-fibonacci (n &optional (a 0) (b 1)) (if (= n 0) a (nth-fibonacci (- n 1) b (+ a b))))

Jtsummers 5y ago

Yep, that's how you'd do it. So long as your CL implementation supports tail call optimization, that will be on par with the same algorithm using loop or another looping construct.

gibsonf1 5y ago

WEB> (time (nth-fibonacci 9999)) Evaluation took: 0.005 seconds of real time 0.004520 seconds of total run time (0.000168 user, 0.004352 system) 100.00% CPU 13,120,881 processor cycles 4,716,256 bytes consed 20793608237133498072112648988642836825087036094015903119682945866528501423455686648927456034305226515591757343297190158010624794267250973176133810179902738038231789748346235556483191431591924532394420028067810320408724414693462849062668387083308048250920654493340878733226377580847446324873797603734794648258113858631550404081017260381202919943892370942852601647398213554479081823593715429566945149312993664846779090437799284773675379284270660175134664833266377698642012106891355791141872776934080803504956794094648292880566056364718187662668970758537383352677420835574155945658542003634765324541006121012446785689171494803262408602693091211601973938229446636049901531963286159699077880427720289235539329671877182915643419079186525118678856821600897520171070499437657067342400871083908811800976259727431820539554256869460815355918458253398234382360435762759823179896116748424269545924633204614137992850814352018738480923581553988990897151469406131695614497783720743461373756218685106856826090696339815490921253714537241866911604250597353747823733268178182198509240226955826416016690084749816072843582488613184829905383150180047844353751554201573833105521980998123833253261228689824051777846588461079790807828367132384798451794011076569057522158680378961532160858387223882974380483931929541222100800313580688585002598879566463221427820448492565073106595808837401648996423563386109782045634122467872921845606409174360635618216883812562321664442822952537577492715365321134204530686742435454505103269768144370118494906390254934942358904031509877369722437053383165360388595116980245927935225901537634925654872380877183008301074569444002426436414756905094535072804764684492105680024739914490555904391369218696387092918189246157103450387050229300603241611410707453960080170928277951834763216705242485820801423866526633816082921442883095463259080471819329201710147828025221385656340207489796317663278872207607791034431700112753558813478888727503825389066823098683355695718137867882982111710796422706778536913192342733364556727928018953989153106047379741280794091639429908796650294603536651238230626 WEB>

Jtsummers 5y ago
You may want to put extra spaces in front of those lines, and also manually break up that massive number.

weavie 5y ago

SBCL doesn't optimize tail calls by default. If I recall you have to set the optimization level prior to compiling the function using `(declaim (optimize xxx))` - where xxx is something I've forgotten. Perhaps someone can come along and point out what xxx should be?

gibsonf1 5y ago
Oh thats interesting!, we don't use that but use tail recursion extensively https://0branch.com/notes/tco-cl.html#sec-2-2 https://0branch.com/notes/tco-cl.html#sec-2-2
Jtsummers 5y ago
; disassembly for NTH-FIBONACCI ; Size: 94 bytes. Origin: #x2264E531 ; NTH-FIBONACCI ; 31: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer ; 35: 488945F8 MOV [RBP-8], RAX ; 39: 488B55F0 MOV RDX, [RBP-16] ; 3D: 31FF XOR EDI, EDI ; 3F: E8AC343BFF CALL #x21A019F0 ; GENERIC-= ; 44: 750A JNE L0 ; 46: 488B55E8 MOV RDX, [RBP-24] ; 4A: 488BE5 MOV RSP, RBP ; 4D: F8 CLC ; 4E: 5D POP RBP ; 4F: C3 RET ; 50: L0: 488B55F0 MOV RDX, [RBP-16] ; 54: BF02000000 MOV EDI, 2 ; 59: E8C2323BFF CALL #x21A01820 ; GENERIC-- ; 5E: 488BC2 MOV RAX, RDX ; 61: 488945D8 MOV [RBP-40], RAX ; 65: 488B55E8 MOV RDX, [RBP-24] ; 69: 488B7DE0 MOV RDI, [RBP-32] ; 6D: E84E323BFF CALL #x21A017C0 ; GENERIC-+ ; 72: 488BF2 MOV RSI, RDX ; 75: 488B45D8 MOV RAX, [RBP-40] ; 79: 488BD0 MOV RDX, RAX ; 7C: 488B7DE0 MOV RDI, [RBP-32] ; 80: B906000000 MOV ECX, 6 ; 85: FF7508 PUSH QWORD PTR [RBP+8] ; 88: E99507DBFD JMP #x203FED22 ; #<FDEFN NTH-FIBONACCI> ; 8D: CC10 INT3 16 ; Invalid argument count trap Looks like it's doing tail call optimization to me, this is without doing anything special with declaim. Note that where it returns to the top is with JMP not CALL. http://www.sbcl.org/manual/index.html#Debug-Tail-Recursion http://www.sbcl.org/manual/index.html#Debug-Tail-Recursion