let fibs = (1I, 1I) |> Seq.unfold (fun (a,b) -> Some (a, (b,a+b)))
What it does:
The bigint tuple (1I, 1I) is piped into the Seq.unfold function. Seq.unfold takes a function and a seed (the 2-tuple in this case.) The function you pass in should take in as an argument the same type as the seed, so it's the tuple (a,b) as above.
The function returns a 2-tuple option value. An option value is simple None or an actual value. Returning None at any stage will termiante the sequence.
The first value in the returned tuple is the value you want to yield in the sequence. The second value in the tuple is the new accumulator, to be passed into the function on the next iteration of the sequence. In our case, it will be the next iteration of fibonacci, (b, a+b).
F# sequences, obviously, are lazy evaluated. To access the nth value of the sequence, simply use
let nthfib = fibs |> Seq.nth n
>>10
I've been really getting into F# lately, especially since Microsoft have decided to include it as an official .NET language in the next Visual Studio iteration.
(define (fib n)
(define (iter a b p q count)
(cond ((= count 0) b)
((even? count)
(iter a
b
(+ (* p p) (* q q))
(+ (* 2 p q) (* q q))
(/ count 2)))
(else (iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))
(iter 1 0 0 1 n))
>>32
Run it more than 3 times.
(time (nth fibs 10000))
"Elapsed time: 1.708 msecs"
54438373113565281338734260993750380135389184554695967026247715841208582865622349017083051547938960541173822675978026317384359584751116241439174702642959169925586334117906063048089793531476108466259072759367899150677960088306597966641965824937721800381441158841042480997984696487375337180028163763317781927941101369262750979509800713596718023814710669912644214775254478587674568963808002962265133111359929762726679441400101575800043510777465935805362502461707918059226414679005690752321895868142367849593880756423483754386342639635970733756260098962462668746112041739819404875062443709868654315626847186195620146126642232711815040367018825205314845875817193533529827837800351902529239517836689467661917953884712441028463935449484614450778762529520961887597272889220768537396475869543159172434537193611263743926337313005896167248051737986306368115003088396749587102619524631352447499505204198305187168321623283859794627245919771454628218399695789223798912199431775469705216131081096559950638297261253848242007897109054754028438149611930465061866170122983288964352733750792786069444761853525144421077928045979904561298129423809156055033032338919609162236698759922782923191896688017718575555520994653320128446502371153715141749290913104897203455577507196645425232862022019506091483585223882711016708433051169942115775151255510251655931888164048344129557038825477521111577395780115868397072602565614824956460538700280331311861485399805397031555727529693399586079850381581446276433858828529535803424850845426446471681531001533180479567436396815653326152509571127480411928196022148849148284389124178520174507305538928717857923509417743383331506898239354421988805429332440371194867215543576548565499134519271098919802665184564927827827212957649240235507595558205647569365394873317659000206373126570643509709482649710038733517477713403319028105575667931789470024118803094604034362953471997461392274791549730356412633074230824051999996101549784667340458326852960388301120765629245998136251652347093963049734046445106365304163630823669242257761468288461791843224793434406079917883360676846711185597501
Name:
Anonymous2008-12-21 1:01
>>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
Name:
Anonymous2008-12-21 1:12
>>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
Name:
Anonymous2008-12-21 1:19
Guys, if you really want a good benchmark, may I suggest the Ackermann function?
./a.out 3 1000000 1,24s user 0,01s system 97% cpu 1,284 total
Name:
Anonymous2008-12-21 2:36
>>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
;
Name:
Anonymous2008-12-21 3:26
>>50
Good lord, that's a mess. Surely it can be done cleaner. Surely.
Name:
Anonymous2008-12-21 3:31
>>51
It kind of makes sense, I do not know the coding style but it is a stack language; this is Factor?
Name:
Anonymous2008-12-21 3:56
>>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.
Name:
Anonymous2008-12-21 4:06
>>52
It is Factor. He should have used cond to fix those ifs though. This isn't C.
Name:
Anonymous2008-12-21 4:22
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 ;
Name:
Anonymous2008-12-21 6:36
>>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 ;
Name:
Anonymous2008-12-21 6:53
{ [ 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.
Name:
Anonymous2008-12-21 11:39
>>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.1
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]
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]]
Name:
Anonymous2008-12-21 15:39
FIBONACCI IS A MURDERER.
Name:
Anonymous2008-12-21 15:58
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
>>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
Name:
Anonymous2008-12-21 20:45
>>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?
Name:
Anonymous2008-12-21 20:54
pooooooooooopoooooooooooooopoooooooo
Name:
Anonymous2008-12-21 22:54
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.
Name:
Anonymous2008-12-21 22:56
Shuffle words are the new Monads
Name:
Anonymous2008-12-22 3:38
>>77
Never mind, I was thinking of case. Switch must have been added since I last updated. You can see why I was confused.
Name:
Anonymous2008-12-22 5:41
Goddamnit I hate it when my troll threads turn into something serious.
>>82
Í þessu forriti eru notaðar þrjár einingar. Fyrsta einingin inniheldur ste ð aðalstef sem er stef það sem
framkvæmt er þegar forritið er keyrt. Næsta eining inniheldur ste ð f, og á þá einingu er beitt ítrunarað-
gerðinni til þess að tengja endurkvæmar tilvísanir í f. Inn utningsaðgerðinni er síðan beitt til að tengja ste ð
f við tilvísunina í aðalste nu. Út úr þeirri aðgerð fáum við einingu sem inniheldur aðalstef, og vísar í ste n
lesa , skrifa, +, - og <=. Mynd 4.1 lýsir tengingum þessum.
Þessi nýja eining vísar nú ekki lengur í "+"og -"heldur í "(+)"og "(-)". Einingin "GRUNNUR" inniheldur stef með þessum nöfnum, og eru það sömu stef og "+"og -". Þar eð aðeins einingarnar GRUNNUR og KJARNI innihalda "(+)"og "(-)"og ekki er mögulegt að uppnefna "(+)"og "(-)"er tryggt að stef þessi tengjast grunnstefjunum eða kjarnastefjunum, sem reyndar eru þau sömu.
Einingin FELAGRUN er reyndar ekkert annað en uppnefning á öllum grunnstefjum sem gefur þeim nöfn með svigum, þ.e.a.s.: "FELAGRUN" =
{
! -> (!)
% -> (%)
.
.
.
vhliðra -> (vhliðra)
vistfang -> (vistfang)
} ;
Slíka einingu er ekki hægt að skrifa í Fjölni þar eð svigar eru ekki ley legir í nöfnum. Svipað gildir um eininguna FELAKJAR.
Redirecting it to sysnull doesn't help much, you're still doing a syscall and a lot of unrelated shit still happens.
Name:
Anonymous2008-12-22 15:00
>>95
yet it still manages to take less time to run than your shitty code.
Name:
Anonymous2008-12-22 15:03
NEVER FORGET THE HEROES THAT GAVE THEIR TIME AND THEIR LIVES TO DIE FOR [b]THE GREATER CAUSE OF MAKING THE PLEASURE OF BEING CUMMED INSIDE[b] A GOOGLE MEME. YOUR SACRIFICE WILL NOT BE FORGOTTEN.
NVR FGT
Name:
Anonymous2008-12-22 15:04
>>96
I never posted any code in this thread, neither I am lisp supporter.
I just wanted to point out that your(his) benchmark was dumb.
Name:
Anonymous2008-12-22 15:11
>>98
the benchmark shows that the c code hardly takes practically no time at all to do the actual calculation, while the lisp code is slow as fuck. it served it's purpose.
Name:
Anonymous2008-12-22 15:58
>>94 That code gives correct results for me.
Bullshit. Unless you want to show me where you got a 1000-bit FPU.
>>99
it shows that the c code doesn't fucking work.
Name:
Anonymous2008-12-22 16:19
>>98 neither I am lisp supporter. And why the hell not‽‽
Name:
Anonymous2008-12-22 19:00
>>98
Incinerate this man immediately. Burn him, burn his Java books, and let him have his anus haxed by an endless procession of Haskell monads.
Name:
Anonymous2008-12-22 22:29
I use an ENTERPRISE-GRADE optimizing fibonacci compiler
Name:
Anonymous2008-12-23 5:22
module Ackermann where
hyper 1 a b = a + b
hyper 2 a b = a * b
hyper n a 0 = 1
hyper 0 _ b = b + 1
hyper n a b = foldr1 (hyper(n-1)) [a|i<-[1..b]]
ackermann m n = (hyper m 2 (n+3))-3
Name:
Anonymous2008-12-23 5:38
Bullshit. Unless you want to show me where you got a 1000-bit FPU.
'correct' ≢ 'exact'
there are practical uses for fibonacci numbers where the precision of a long double is good enough.
also, fib(999) doesn't require anywhere near 1000 bits: Prelude> let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Prelude> logBase 2 (fromIntegral (fibs!!999))
692.3867076695431
//JavaScript 1.7
function fibs2(x){a=0;b=1;while(x>0){[a,b]=[b,a+b];x--}return a}
Name:
Anonymous2008-12-25 15:22
>>113
Optimized: x20 speed
function fibs3(x){var a=0;var b=1;while(x>0){[a,b]=[b,a+b];x--}return a}
Name:
Anonymous2008-12-25 15:25
Fibs is an infinite series beginning with the elements zero and one,
and pursuing such that each additional element is the sum of the two
elements directly preceding it.
Name:
Anonymous2008-12-25 21:43
>>115 So you think you're being literal?
I implemented fibs by actually breeding rabbits.
Name:
Anonymous2008-12-26 6:19
//Object-oriented fibs
function fibs5(x){var t=this;t.a=0;t.b=1;while(x>0){[t.a,t.b]=[t.b,t.a+t.b];x--}return t.a}
Name:
Anonymous2008-12-26 8:02
"fibs" < main
{
main ->
stef(;)
staðvær i,a,b
a := 0
b := 1
skrifastreng(;"0 1")
stofn
fyrir(i := 0; i < 98; i := i + 1) lykkja
b := a + b,
a := b - a,
skrifastreng(;" "),
skrifa(;b)
lykkjulok,
stofnlok
skrifastreng(;"\n"),
}
*
"GRUNNUR"
;