c# 4.0 - Calculating fibonacci -


i sent nice non-recursive function computing fibonacci sequence.

alt text

so coded bit of c# , able verify numbers 1474 correct.

the problem comes in when attempting calculate 1475 , above. c# math skills aren't task of figuring out different way. so, have better way of expressing particular math function in c#? other traditional way of doing recursive function?

incidentally, started use biginteger return type. problem comes in when trying raise (1+math.sqrt(5) /2) 1475th power. don't see data type need (nor mechanism matter) come other infinity.

here's starting point.

private double fibsequence(int32 input) {     double part1 = (1 / math.sqrt(5));     double part2 = math.pow(((1 + math.sqrt(5)) / 2), input);     double part3 = math.pow(((1 - math.sqrt(5)) / 2), input);      return (part1 * part2) - (part1 * part3); }

and, no, it's not homework. "simple" problem slow day.

i don't think c# has data type enough floating precision , range handle naïvely.

if want go down path, can notice conjugate \phi=\phi^{-1}=\phi-1=\frac{-1+\sqrt 5}{2} less one, -\frac{(-\phi)^n}{\sqrt 5} same rounding nearest integer, can simplify solution finding \left\lfloor\frac{\phi^n}{\sqrt 5}+\frac12\right\rfloor. use binomial expansion have calculate \left\lfloor a+b\sqrt 5\right\rfloor, appropriate a , b (which rational , can computed biginteger). if still go double this, still won't further 1475, should able figure out how part exact integer math ☺

\frac{\phi^n}{\sqrt 5}=\frac{(1+\sqrt 5)^n}{2^n\sqrt 5}=\frac{\sum_{k=0}^n{n\choose k}\sqrt 5^k}{2^n\sqrt 5}
=\left(\sum_{k=0}^{\left\lfloor\frac{n-1}2\right\rfloor}\frac{{n\choose 2k+1}5^k}{2^n}\right)+\left(\sum_{k=0}^{\left\lfloor\frac n2\right\rfloor}\frac{{n\choose 2k}5^{k-1}}{2^n}\right)\sqrt 5

there's neat method computing fibonacci numbers, using matrix exponentiation:

\left(\begin{matrix}1&1\1&0\end{matrix}\right)^n=\left(\begin{matrix}f_n&f_{n-1}\f_{n-1}&f_{n-2}\end{matrix}\right)

this can done in o(log n) if you're clever.

i ended implementing these in haskell. fib1 matrix exponentiation , fib2 exact integer translation of closed-form formula, described above. respective runtimes this, measured criterion when compiled ghc 7.0.3:
matrix exponentiation runtime closed-form runtime 

import control.arrow import data.list import data.ratio  newtype matrix2 = matrix2 (a, a, a, a) deriving (show, eq) instance (num a) => num (matrix2 a)     matrix2 (a, b, c, d) * matrix2 (e, f, g, h) =         matrix2 (a*e+b*g, a*f+b*h, c*e+d*g, c*f+d*h)     frominteger x = let y = frominteger x in matrix2 (y, 0, 0, y) fib1 n = let matrix2 (_, x, _, _) = matrix2 (1, 1, 1, 0) ^ n in x  binom n =     scanl (\a (b, c)-> a*b `div` c) 1 $     takewhile ((/=) 0 . fst) $ iterate (pred *** succ) (n, 1) evens (x:_:xs) = x : evens xs evens xs = xs odds (_:x:xs) = x : odds xs odds _ = [] iterate' f x = x : (iterate' f $! f x) powers b = iterate' (b *) 1 esqrt e n = x     (_, x):_ = dropwhile ((<=) e . abs . uncurry (-)) $ zip trials (tail trials)     trials = iterate (\x -> (x + n / x) / 2) n fib' n = (a, b)     d = 2 ^ n     = sum (zipwith (*) (odds $ binom n) (powers 5)) % d     b = sum (zipwith (*) (evens $ binom n) (powers 5)) % d fib2 n = numerator r `div` denominator r     (a, b) = fib' n     l = lcm (denominator a) (denominator a)     r = + esqrt (1 % max 3 l) (b * b / 5) + 1 % 2

Comments

Post a Comment

Popular posts from this blog

asp.net - repeatedly call AddImageUrl(url) to assemble pdf document -

i'm using abcpdf , i'm curious if can recursively call addimageurl() function assemble pdf document compile multiple urls? something like: int pagecount = 0; int theid = thedoc.addimageurl("http://stackoverflow.com/search?q=abcpdf+footer+page+x+out+of+", true, 0, true); //assemble document while (thedoc.chainable(theid)) { thedoc.page = thedoc.addpage(); theid = thedoc.addimagetochain(theid); } pagecount = thedoc.pagecount; console.writeline("1 document page count:" + pagecount); //flatten document (int = 1; <= pagecount; i++) { thedoc.pagenumber = i; thedoc.flatten(); } //now try again theid = thedoc.addimageurl("http://stackoverflow.com/questions/1980890/pdf-report-generation", true, 0, true); //assemble document while (thedoc.chainable(theid)) { thedoc.page = thedoc.addpage(); theid = thedoc.addimagetoc...
Read more

java - Android recognize cell phone with keyboard or not? -

in android app, want detect user's device if device has keyboard(like motorola milestone) , show corresponding user interface. guys know how that? ! regards justicepenny http://developer.android.com/reference/android/content/res/configuration.html public int keyboard the kind of keyboard attached device. 1 of: keyboard_nokeys, keyboard_qwerty, keyboard_12key. that's it!
Read more

iphone - How would you achieve a LED Scrolling effect? -

how achieve led scrolling effect example below? led sign - led ticker emulator iphone , ipad http://img.skitch.com/20101201-rsfh4p1bajb1wp94k466pdpiuj.preview.jpg sometimes remunerates comment in other posts :) have put code you, should implement font '8pin matrix' realistic feeling. uilabel *label; - (void)viewdidload { [super viewdidload]; label = [[uilabel alloc]initwithframe:cgrectmake(10, 50, 300, 20)]; label.font = [uifont fontwithname:@"courier-bold" size:16.0]; label.backgroundcolor = [uicolor blackcolor]; label.textcolor = [uicolor greencolor]; label.linebreakmode = uilinebreakmodecharacterwrap; // otherwise "…" label.text = @"this led text scrolled "; // blanks space between [self.view addsubview:label]; [nstimer scheduledtimerwithtimeinterval:0.12f target:self selector:@selector(scrolllabel) use...
Read more