Fibs in your favourite language

fibs = 1 : zipWith (+) fibs (tail fibs)

>>32
Run it more than 3 times.
(time (nth fibs 10000))
"Elapsed time: 1.708 msecs"
54438373113565281338734260993750380135389184554695967026247715841208582865622349017083051547938960541173822675978026317384359584751116241439174702642959169925586334117906063048089793531476108466259072759367899150677960088306597966641965824937721800381441158841042480997984696487375337180028163763317781927941101369262750979509800713596718023814710669912644214775254478587674568963808002962265133111359929762726679441400101575800043510777465935805362502461707918059226414679005690752321895868142367849593880756423483754386342639635970733756260098962462668746112041739819404875062443709868654315626847186195620146126642232711815040367018825205314845875817193533529827837800351902529239517836689467661917953884712441028463935449484614450778762529520961887597272889220768537396475869543159172434537193611263743926337313005896167248051737986306368115003088396749587102619524631352447499505204198305187168321623283859794627245919771454628218399695789223798912199431775469705216131081096559950638297261253848242007897109054754028438149611930465061866170122983288964352733750792786069444761853525144421077928045979904561298129423809156055033032338919609162236698759922782923191896688017718575555520994653320128446502371153715141749290913104897203455577507196645425232862022019506091483585223882711016708433051169942115775151255510251655931888164048344129557038825477521111577395780115868397072602565614824956460538700280331311861485399805397031555727529693399586079850381581446276433858828529535803424850845426446471681531001533180479567436396815653326152509571127480411928196022148849148284389124178520174507305538928717857923509417743383331506898239354421988805429332440371194867215543576548565499134519271098919802665184564927827827212957649240235507595558205647569365394873317659000206373126570643509709482649710038733517477713403319028105575667931789470024118803094604034362953471997461392274791549730356412633074230824051999996101549784667340458326852960388301120765629245998136251652347093963049734046445106365304163630823669242257761468288461791843224793434406079917883360676846711185597501

>>31
No, it was Joe Stoy from Kaldewaij 1990 (Footnote 41.)

>>41
try calculating 10000 different fibs.
#include <stdio.h>
#include <gmp.h>

int main(void){
 mpz_t n;
 mpz_init(n);
 for(unsigned long i = 0; i < 10000; ++i){
  mpz_fib_ui(n, i);
  printf("fib(%lu) == ", i);
  mpz_out_str(stdout, 10, n);
  putchar('\n');
 }
 return 0;
}
hotaru@olorin$ gcc -std=c99 -O2 -s -lgmp test.c                           < ~ >
hotaru@olorin$ time ./a.out>/dev/null                                     < ~ >
./a.out > /dev/null  2,68s user 0,03s system 97% cpu 2,787 total

>>29
that MIT-SCHEME is super fast!!
1 ]=> (fib 10000)
;Value: 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

1 ]=>
End of input stream reached.
Happy Happy Joy Joy.

real    0m0.070s
user    0m0.041s
sys     0m0.023s

Guys, if you really want a good benchmark, may I suggest the Ackermann function?

>>45
Beautiful wiki page.
http://en.wikipedia.org/wiki/Ackermann_function

Free SUSSMAN HAT to the first person to implement "Fibonacciruna" inFjölnir.

>>45
My... my... my Haskell is not up to the problem.

>>45
like this?
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <gmp.h>

void ack(mpz_t rop, unsigned long m, unsigned long n){
 if(m < 0 || n < 0){
  mpz_set_ui(rop, 0);
  return;
 }
 switch(m){
  case 0:
   mpz_set_ui(rop, n);
   mpz_add_ui(rop, rop, 1);
   break;
  case 1:
   mpz_set_ui(rop, n);
   mpz_add_ui(rop, rop, 2);
   break;
  case 2:
   mpz_set_ui(rop, n);
   mpz_mul_ui(rop, rop, 2);
   mpz_add_ui(rop, rop, 3);
   break;
  case 3:
   if(n <= ULONG_MAX - 3){
    mpz_set_ui(rop, 1);
    mpz_mul_2exp(rop, rop, n + 3);
    mpz_sub_ui(rop, rop, 3);
    break;
   }
  default:
   switch(n){
    case 0:
     ack(rop, m - 1, 1);
     break;
    default:
     ack(rop, m, n - 1);
     mpz_fits_ulong_p(rop) ?
      ack(rop, m - 1, mpz_get_ui(rop)) :
      mpz_set_ui(rop, 0);
   }
 }
}

int main(int argc, char **argv){
 mpz_t res;
 if(argc < 2){
  printf("Usage: %s m n\n", argv[0]);
  return EXIT_FAILURE;
 }
 mpz_init(res);
 ack(res, strtoul(argv[1], NULL, 0), strtoul(argv[2], NULL, 0));
 mpz_out_str(stdout, 10, res);
 mpz_clear(res);
 putchar('\n');
 return 0;
}

./a.out 3 1000000  1,24s user 0,01s system 97% cpu 1,284 total

>>48
here's a nice functional implementation of the Ackermann function for you, it shouldn't be too hard to translate into your toy language:
USING: kernel math arrays sequences ;
: ackermann ( m n -- r )
 over zero? [
  1+ nip
 ] [
  over 1 = [
   2 + nip
  ] [
   over 2 = [
    1 shift 3 + nip
   ] [
    over 3 = [
     3 + 1 swap shift 3 - nip
    ] [
     1+ swap 1- <array> 1 [ swap ackermann ] reduce
    ] if
   ] if
  ] if
 ] if
;

>>50
Good lord, that's a mess. Surely it can be done cleaner. Surely.

>>51
It kind of makes sense, I do not know the coding style but it is a stack language; this is Factor?

>>50
sure, if you want it to be slow as fuck.
fib(n - 1) + fib(n - 2) is the cleanest way to define fib(n), but it's pretty stupid to do it that way.

>>52
It is Factor. He should have used cond to fix those ifs though. This isn't C.

IN: ackermann
USING: kernel math arrays sequences combinators ;

: ackermann ( m n -- r )
{
 { [ over 0 = ] [ nip 1 + ] }
 { [ dup 0 = pick 0 > and ] [ drop 1 - 1 ackermann ] }
 { [ dup 0 > pick 0 > and ] [ dupd 1 - ackermann swap 1 - swap ackermann ] }
} cond ;

>>52,54
switch > cond
also, it's a little cleaner if you reverse the arguments.
USING: kernel math arrays sequences combinators.lib memoize ;
MEMO: ackermann ( n m -- r ) {
  { [ 0 = ] [ drop 1+ ] }
  { [ 1 = ] [ drop 2 + ] }
  { [ 2 = ] [ drop 2 * 3 + ] }
  { [ 3 = ] [ drop 3 + 2^ 3 - ] }
  { [ 3 > ] [ [ 1+ ] [ 1- ] bi* <array> 1 [ ackermann ] reduce ] }
 } switch ;

{ [ dup 0 = pick 0 > and ] [ drop 1 - 1 ackermann ] }
{ [ dup 0 > pick 0 > and ] [ dupd 1 - ackermann swap 1 - swap ackermann ] }
you fail at factor.

>>37
primes = 2:3:5:[n | n <- [7,9..], all (\p -> (mod n p) /= 0) (takeWhile (\p -> let hpf = ceiling (sqrt (fromIntegral n)) in p <= hpf) primes)]
Improvements to the above are welcome.¹


References
[1]. http://forums.xkcd.com/viewtopic.php?f=40&p=1172786#p1241663

>>58
Simon Peyote-Joints is spinning in his grave. He never did like one liners.

>>58
Ugly!

primes = 2:3:[x | x <- [5,7..], all ((0 /=) . mod x) $ (takeWhile ((x >=) . (^2))) primes]

Though I'm currently using this one:
primes = 2 : 3 : [x | x <- primeWheel, isPrime x] where
    primeWheel = [6*k+r | k <- [1..], r <- [-1,1]]
isPrime x = null [i | i <- takeWhile ((<= x) . (^2)) primes, x `mod` i == 0]

>>59
haskell is one-liners.

module Ackermann where
ackermann 0 n = n+1
ackermann 1 n = n+2
ackermann 2 n = 2*n+3
ackermann 3 n = 2^(n+3)-3
ackermann m n = foldr ackermann 1 [(m-1) | i <- [0..n]]

FIBONACCI IS A MURDERER.

Now, time for something a bit wild. Hold onto your hats, fellow Haskellers.

hexanacci :: Int -> Int
hexanacci 0 = 1
hexanacci 1 = 1
hexanacci 2 = 2
hexanacci 3 = 4
hexanacci 4 = 8
hexanacci 5 = 16
hexanacci n = h n-1 + h n-2 + h n-3 + h n-4 + h n-5
  where h = hexanacci


fibs 0 = 1
fibs 1 = 1
fibs 2 = 2
fibs 3 = 3
fibs 4 = 5
fibs 5 = 8
fibs _ = error "You can't do that!"

>>57
: ackermann ( m n -- r )
{
    { [ over 0 = ] [ nip 1 + ] }
    { [ 2dup [ 0 > ] [ 0 = ] bi* and ] [ drop 1 - 1 ackermann ] }
    { [ 2dup [ 0 > ] both? ] [ dupd 1 - ackermann [ 1 - ] dip ackermann ] }
} cond ;

Better, Fagtorman?

>>65
look at how many shuffle words you have in your code. using shuffle words in factor is like using global variables in c.

What are shuffle words?

>>67
they are the words in teh dictionary that are in the wrong order.

>>67
Words whose purposes are to rearrange the top of the stack.

>>66
Six, and you didn't answer the question. So what would you do, without switching to a different definition of the function?

Since factor is a stack based language does that mean there is no need for TCO or anything?

>>70
Total Cost of Ownership?

>>71
Tail Call Optimization!

[strong]Tit-Covering Orgasm[/strong]

>>69
use switch instead of cond. this will cut the number of shuffle words in half and make your code a lot clearer. then look at refactoring the branch with the two recursive calls.
dupd [ 1- ] [ ] [ 1- ] tri* ackermann ackermann

>>74
How am I supposed to use switch in this situation, when I need to examine two variables? And why are you suggesting I change my last branch from a version with one shuffle word to a version with the exact same shuffle word?

pooooooooooopoooooooooooooopoooooooo

How am I supposed to use switch in this situation, when I need to examine two variables?
ok, since you're too stupid to figure this out, i'll do it for you:
: ackermann ( m n -- r )
{
    { [ drop 0 = ] [ nip 1+ ] }
    { [ [ 0 > ] [ 0 = ] bi* and ] [ drop 1- 1 ackermann ] }
    { [ [ 0 > ] both? ] [ [ [ 1- ] keep ] dip 1- ackermann ackermann ] }
} switch ;

And why are you suggesting I change my last branch from a version with one shuffle word to a version with the exact same shuffle word?
i wasn't suggesting you change it to that version, i was simply pointing you in the right direction.

Shuffle words are the new Monads

>>77
Never mind, I was thinking of case. Switch must have been added since I last updated. You can see why I was confused.

Goddamnit I hate it when my troll threads turn into something serious.