c# - Fibonacci's recurrence relation loss of precision on big digits -

-

i'm trying use binet's formula solve fibonacci's nth number o(1) time complexity.

class application {     static void main(string[] c)     {         console.writeline($"fib(15) : expected 610 got : {fibonacci(15)}");         console.writeline($"fib(20) : expected 6765 got : {fibonacci(20)}");         console.writeline($"fib(100) : expected 354224848179261915075 got : {fibonacci(100)}");          console.readkey();     }      private static biginteger fibonacci(int n)     {         double sqrt5 = math.sqrt(5d);         return new biginteger((1/sqrt5)*math.pow((1 + sqrt5)/2, n) - (1/sqrt5)*math.pow((1 - sqrt5)/2, n));     }        }

the following example works charm first 2 tests, fails quite huge amount third test (result 354224848179263111168 vs. 354224848179261915075.

i guess might problem math.pow((1+sqrt5)/2,n) part of formula, tried using formula using decimal, double, float , biginteger itself, , result never one.

is there way around problem or should accept can't using math.pow?

edit tried using biginteger.pow, use 1+sqrt5 needs biginteger too, makes code @ end because of castings : 

double sqrt5 = math.sqrt(5d); return new biginteger(1/sqrt5)*biginteger.pow(new biginteger(1 + sqrt5/2), n) - new biginteger(1 / sqrt5) * biginteger.pow(new biginteger((1 - sqrt5)/2), n);

and values returned zeroes.

using double have 15 , half digits of accuracy. can not expect more, output of integer conversion input.

that why binets formula not o(1) o(m(n)) n bit computations, using f[n] smaller 2^n m(n) cost of multiplication measure cost of exponentiation , logarithm.


Comments

Post a Comment

Popular posts from this blog

javascript - Chart.js (Radar Chart) different scaleLineColor for each scaleLine -

-
Image
i try , create radar chart using chart.js has various colours each scaleline, or coloured between scalelines. wondering if possible? from: to: i have working graph, though there doesn't seem method change individual scale lines. kind regards leigh you can extend radar chart type this, so chart.types.radar.extend({ name: "radaralt", initialize: function (data) { chart.types.radar.prototype.initialize.apply(this, arguments); var originalscaledraw = this.scale.draw; var ctx = this.chart.ctx; this.scale.draw = function () { var linewidth = this.linewidth; // bypasses line drawing in originalscaledraw this.linewidth = linewidth; originalscaledraw.apply(this, arguments); ctx.linewidth = this.linewidth; var scale = this; // draw chart.helpers.each(scale.ylabels, function (label, index) { // color of ...
Read more

apache - Error with PHP mail(): Multiple or malformed newlines found in additional_header -

-
suddenly have started receiving above error without changes having been made script. host 1and1 (i know...) the script still works fine on different server, , suspicion there must have been server config change has lead this, although hosts plead ignorance. there's no information on above error @ in google can find - have ideas? server running apache if helps. had similar problem. came out of blue. no php code changed. what changed: php upgraded 5.5.25-1 5.5.26. a security risk in php mail() function has been fixed , newlines in additional_headers allowed no more. because newlines mean: starts email message (and surely don't want inject newlines through headers followed evil message). what have worked fine, e.g. having newlines after headers or passing whole message additional_headers , function no more. solution : sanitize headers. no multiple newlines in additional_headers argument. these count "multiple or malformed newlines":...
Read more

java - Android – MapFragment overlay button shadow, just like MyLocation button -

-
Image
i'm struggling add shadow custom overlay button on google map. goal make custom button google's mylocation button. here's how app looks now: layout.xml <relativelayout xmlns:android="http://schemas.android.com/apk/res/android" xmlns:tools="http://schemas.android.com/tools" xmlns:map="http://schemas.android.com/apk/res-auto" android:layout_height="match_parent" android:layout_width="match_parent" style="@style/apptheme"> <fragment android:layout_width="match_parent" android:layout_height="match_parent" android:id="@+id/map" tools:context=".mapsactivity" android:name="com.google.android.gms.maps.supportmapfragment" android:layout_alignparentend="true" android:layout_alignparentstart="true" android:layout_alignparentbottom="true" ...
Read more