{"id":367,"date":"2017-05-17T11:48:48","date_gmt":"2017-05-17T11:48:48","guid":{"rendered":"http:\/\/perfectionatic.org\/?p=367"},"modified":"2017-06-12T14:41:36","modified_gmt":"2017-06-12T14:41:36","slug":"exploring-fibonacci-fractions-with-julia","status":"publish","type":"post","link":"https:\/\/perfectionatic.org\/?p=367","title":{"rendered":"Exploring Fibonacci Fractions with Julia"},"content":{"rendered":"

Recently, I came across a fascinating blog and video from Mind your Decisions<\/a>. It is about how a fraction
\n\\(\\frac{1}{999,999,999,999,999,999,999,998,,999,999,999,999,999,999,999,999}\\)
\nwould show the Fibonacci numbers in order when looking at its decimal output.<\/p>\n

On a spreadsheet and most standard programming languages, such output can not be attained due to the limited precision for floating point numbers. If you try this on R or Python, you will get an output of 1e-48<\/code>.
\nWolfram alpha<\/a>,however,allows arbitrary precision.<\/p>\n

In Julia by default we get a little better that R and Python<\/p>\n

\njulia> 1\/999999999999999999999998999999999999999999999999\n1.000000000000000000000001000000000000000000000002000000000000000000000003000002e-48\n\njulia> typeof(ans)\nBigFloat\n<\/pre>\n
We observe here that we are getting the first few Fibonacci numbers \\(1, 1, 2, 3\\). We need more precision to get more numbers. Julia has arbitrary precision arithmetic<\/a> baked into the language.  We can crank up the precision of the BigFloat<\/code> type on demand. Of course, the higher the precision, the slower the computation and the greater the memory we use. We do that by setprecision<\/code>.<\/p>\n
julia> setprecision(BigFloat,10000)\n10000\n<\/pre>\n
Reevaluating, we get<\/p>\n
julia> 1\/999999999999999999999998999999999999999999999999\n1.00000000000000000000000100000000000000000000000200000000000000000000000300000000000000000000000500000000000000000000000800000000000000000000001300000000000000000000002100000000000000000000003400000000000000000000005500000000000000000000008900000000000000000000014400000000000000000000023300000000000000000000037700000000000000000000061000000000000000000000098700000000000000000000159700000000000000000000258400000000000000000000418100000000000000000000676500000000000000000001094600000000000000000001771100000000000000000002865700000000000000000004636800000000000000000007502500000000000000000012139300000000000000000019641800000000000000000031781100000000000000000051422900000000000000000083204000000000000000000134626900000000000000000217830900000000000000000352457800000000000000000570288700000000000000000922746500000000000000001493035200000000000000002415781700000000000000003908816900000000000000006324598600000000000000010233415500000000000000016558014100000000000000026791429600000000000000043349443700000000000000070140873300000000000000113490317000000000000000183631190300000000000000297121507300000000000000480752697600000000000000777874204900000000000001258626902500000000000002036501107400000000000003295128009900000000000005331629117300000000000008626757127200000000000013958386244500000000000022585143371700000000000036543529616200000000000059128672987900000000000095672202604100000000000154800875592000000000000250473078196100000000000405273953788100000000000655747031984200000000001061020985772300000000001716768017756500000000002777789003528800000000004494557021285300000000007272346024814100000000011766903046099400000000019039249070913500000000030806152117012900000000049845401187926400000000080651553304939300000000130496954492865700000000211148507797805000000000341645462290670700000000552793970088475700000000894439432379146400000001447233402467622100000002341672834846768500000003788906237314390600000006130579072161159100000009919485309475549700000016050064381636708800000025969549691112258500000042019614072748967300000067989163763861225800000110008777836610193100000177997941600471418900000288006719437081612000000466004661037553030900000754011380474634642900001220016041512187673800001974027421986822316700003194043463499009990500005168070885485832307200008362114348984842297700013530185234470674604900021892299583455516902600035422484817926191507500057314784401381708410100092737269219307899917600150052053620689608327700242789322839997508245300392841376460687116573000635630699300684624818301028472075761371741391301664102775062056366209602692574850823428107600904356677625885484473810507049252476708912581411411405930102594397055221918455182579303309636633329861112681897706691855248316295261201016328488578177407943098723020343826493703204299739348832404671111147398462369176231164814351698201718008635835925499096664087184867000739850794865805193502836665349891529892378369837405200686395697571872674070550577925589950242511475751264321287522115185546301842246877472357697022053e-48\n<\/pre>\n
That is looking much better. However it we be nice if we could extract the Fibonacci numbers that are buried in that long decimal. Using the approach in the original blog. We define a function<\/p>\n
\ny(x)=one(x)-x-x^2\n<\/pre>\n
and calculate the decimal<\/p>\n
\na=1\/y(big\"1e-24\")\n<\/pre>\n
Here we use the non-standard string literal big\"...\"<\/code> to insure proper interpretation of our input. Using BigFloat(1e-24))<\/code> would first construct at floating point with limited precision and then do the conversion. The initial loss of precision will not be recovered in the conversion, and hence the use of big<\/code>. Now we extract our Fibonacci numbers by this function<\/p>\n
\nfunction extract_fib(a)\n   x=string(a)\n   l=2\n   fi=BigInt[]\n   push!(fi,1)\n   for i=1:div(length(x)-24,24)\n        j=parse(BigInt,x[l+1+(i-1)*24:l+i*24])\n        push!(fi,j)\n   end\n   fi\nend\n<\/pre>\n
Here we first convert our very long decimal number of a string and they we exploit the fact the Fibonacci numbers occur in blocks that 24 digits in length. We get out output in an array of BigInt<\/code>. We want to compare the output with exact<\/em> Fibonacci numbers, we just do a quick and non-recursive implementation.<\/p>\n
\nfunction fib(n)\n    f=Vector{typeof(n)}(n+1)\n    f[1]=f[2]=1;\n    for i=3:n+1\n       f[i]=f[i-1]+f[i-2]\n    end\n    f\nend\n<\/pre>\n
Now we compare…<\/p>\n
\nfib_exact=fib(200);\nfib_frac=extract_fib(a);\nfor i in eachindex(fib_frac)\n     println(fib_exact[i], \" \", fib_exact[i]-fib_frac[i])\nend\n<\/pre>\n
We get a long sequence, we just focused here on when the discrepancy happens.<\/p>\n
\n...\n184551825793033096366333 0\n298611126818977066918552 0\n483162952612010163284885 0\n781774079430987230203437 -1\n1264937032042997393488322 999999999999999999999998\n2046711111473984623691759 1999999999999999999999997\n...\n<\/pre>\n
The output shows that just before<\/em> the extracted Fibonacci number exceeds 24 digits, a discrepancy occurs. I am not quite sure why, but this was a fun exploration. Julia allows me to do mathematical explorations that would take one or even two orders of magnitude of effort to do in any other language.<\/p>\n","protected":false},"excerpt":{"rendered":"
Recently, I came across a fascinating blog and video from Mind your Decisions. It is about how a fraction \\(\\frac{1}{999,999,999,999,999,999,999,998,,999,999,999,999,999,999,999,999}\\) would show the Fibonacci numbers in order when looking at its decimal output. On a spreadsheet and most standard programming languages, such output can not be attained due to the limited precision for floating point […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[74,73,62],"tags":[92],"class_list":["post-367","post","type-post","status-publish","format-standard","hentry","category-julia","category-julialang","category-math","tag-julia"],"_links":{"self":[{"href":"https:\/\/perfectionatic.org\/index.php?rest_route=\/wp\/v2\/posts\/367","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/perfectionatic.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/perfectionatic.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/perfectionatic.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/perfectionatic.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=367"}],"version-history":[{"count":35,"href":"https:\/\/perfectionatic.org\/index.php?rest_route=\/wp\/v2\/posts\/367\/revisions"}],"predecessor-version":[{"id":412,"href":"https:\/\/perfectionatic.org\/index.php?rest_route=\/wp\/v2\/posts\/367\/revisions\/412"}],"wp:attachment":[{"href":"https:\/\/perfectionatic.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=367"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/perfectionatic.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=367"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/perfectionatic.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=367"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}