|
As an aside there is a method for calculating a fibonacci number without calculating all of the previous numbers in the sequence.
If you are interested it was a method proposed by Dijkstra - scroll down to the middle of (search for 'Can we find a quicker method using only integers?' )
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section1.3
|
|
|
|
|
That's very interesting. Thanks for sharing. Very cool math.
|
|
|
|
|
It would be interesting to see your C# examples side-by-side against the same problems solved in F#
"There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult." - C.A.R. Hoare
Home | LinkedIn | Google+ | Twitter
|
|
|
|
|
F# ( glazes over ) does anyone here use it for a living ?
We can’t stop here, this is bat country - Hunter S Thompson RIP
|
|
|
|
|
Dominic Burford wrote: It would be interesting to see your C# examples side-by-side against the same problems solved in F#
Great idea. Maybe someone with knowledge will chime in.
|
|
|
|
|
OK but why make the input to fib a decimal? This way we can do some party tricks such as calling fib(16.646211646837820914214151535M) (just a hair over 2019) but it's unusual.
|
|
|
|
|
harold aptroot wrote: OK but why make the input to fib a decimal?
Oh, yeah. That was just so I could do very large Fib calcs.
It's 16 bytes so you can get a really large value.
You can calculate Fib(132) = 1725375039079340637797070384
That's a big Fib, but no lie! 
And, yes, I probably should've done some protective coding and truncated any value after a decimal but this was just for my learning.
|
|
|
|
|
OH I like big fibs and I cannot lie, here's a nice trick if you don't mind some BigInteger hackery,
Take some nice prime p such that p ≡ 3 mod 4 (this congruence is not strictly required but makes the next part easier). For example p = 45427892858481394071686190649738831656137145778469793250959984709250004157335359
Then calculate the square root of 5 = BigInteger.ModPow(5, (p + 1) / 4, p) (this simple formula works before p was chosen with p ≡ 3 mod 4).
Calculate a couple of fancy constants,
BigInteger half = BigInteger.ModPow(2, p - 2, p);
BigInteger phi = (1 + sqrt5) * half % p;
BigInteger psi = (1 + p - sqrt5) * half % p;
BigInteger invsqrt5 = BigInteger.ModPow(sqrt5, p - 2, p);
And then you can use the modular arithmetic version of Binet's Formula,
BigInteger fib(int n)
{
return (BigInteger.ModPow(phi, n, p) - BigInteger.ModPow(psi, n, p) + p) * invsqrt5 % p;
}
Good for n up to around 380 or so, you can use a bigger prime if you want to go higher.
This is more or less a joke of course, if you wanted efficient fibonacci calculations you could also use the optimized version (less redundancy) of matrix powering.
|
|
|
|
|
Very cool. Thanks for sharing.
|
|
|
|
|
Has anyone heard of SmartXML or used it?
|
|
|
|
|
XML ain't smart.
It's the idiot inbred grandchild of PostScript.
I wanna be a eunuchs developer! Pass me a bread knife!
|
|
|
|
|
You and Marc are a tag team terror.  The math behind it looked interesting.
|
|
|
|
|
And here I thought Javascript was evil.
Latest Article - A 4-Stack rPI Cluster with WiFi-Ethernet Bridging
Learning to code with python is like learning to swim with those little arm floaties. It gives you undeserved confidence and will eventually drown you. - DangerBunny
Artificial intelligence is the only remedy for natural stupidity. - CDP1802
|
|
|
|
|
You and Mark are a tag team terror. The math behind it looked interesting.
|
|
|
|
|
See, now if you'd used PostScript, you could have single-sourced that statement, making allowance for the fact that Marc doesn't know how to spell his name properly.
With XML? Not in a million man-hours.
I wanna be a eunuchs developer! Pass me a bread knife!
|
|
|
|
|
Mark_Wallace wrote: Marc doesn't know how to spell his name properly
It's spelled Klifton, right?
|
|
|
|
|
Bassam Abdul-Baki wrote: It's spelled Klifton, right?
I like that. Has a Klingon undertone to it. 
Latest Article - A 4-Stack rPI Cluster with WiFi-Ethernet Bridging
Learning to code with python is like learning to swim with those little arm floaties. It gives you undeserved confidence and will eventually drown you. - DangerBunny
Artificial intelligence is the only remedy for natural stupidity. - CDP1802
|
|
|
|
|
WTF.
What do you get when you cross a joke with a rhetorical question?
The metaphorical solid rear-end expulsions have impacted the metaphorical motorized bladed rotating air movement mechanism.
Do questions with multiple question marks annoy you???
|
|
|
|
|
What in the universe is someone calculating where they need 100,000,000 digits?
|
|
|
|
|
I suspect that you clicked the wrong comment in the wrong discussion when you wrote your followup.
Nevertheless, I would like to comment on your question:
In my student days (long ago), a fellow student in theoretical physics was working on an analytical model of what happens when two waves collide. He did some numerical simulations, but his results displayed discontinuieties which he traced down to limited precision (72 bits double precision on a Univac mainframe). We wrote him a library for arbitrary precision floating point calculations (they weren't readily available on the Internet in those days), and he set out with 200 decimal digits of precision. This reduced the problems significantly, but not entirely.
Here comes the important stuff: As a student of theoretical physics, math is not hampered by issues like "limited precision". Our fellow student refused to relate to such mundane things. After two others have failed to make him understand that when adding the elements of a series expansion, it does matter if you add them from the one end or from the other one, I came in as the third one and finally made him accept (I wouldn't say "willingly"...) that adding "from the small end" could make an essential difference. It actually turned out that by adding from the small end, he never needed the exended precision library at all.
Numerical methods, error propagation and stuff like that are certainly not subjects taught to theoretical physicists or anyone else who simply use a computer as a tool to procuce some results. If the users think in math terms, like this student, you need all the precision that can be provided to make computer math behave as closely to real math as possible.
In mathematical theory, you may of course encounter people who really explore extremes of the concepts of numbers. They may even care for integers of 100,000,000 digits - not because they need the precision, but they really handle numbers of that range. The numbers are certainly not needed for any industrial or financial application, only for the number theory. Say, if a mathmatician is studying the possibility of there being a largest possible prime number, he might very well end up in those number ranges.
(Disclaimer: For all I know, it may have been proven that there is no such largest possible prime number. I am not a mathmatician; I simply made it up as a possible example.)
|
|
|
|
|
After a failed build on our Windows build server with Visual Studio 2017, it turned out that the C: drive had run out of space. Freeing up space in the usual way with "Disk Cleanup" did not help much. Only after inspection of directories my eye fell on C:\ProgramData\Package Cache which was over 9 Gb in size !
After Googling a bit I found this helpful link: Move C:\ProgramData\Package Cache\ to D:\ – Knowledgebase[^]
Following the instructions I could move the data to the D: drive and created a "filesystem junction" to point to the new location.
Everything seemed to work fine after that, but beware that problems can occur when updating or repairing with the Visual Studio installer 
|
|
|
|
|
All of the cached updates and packages of ms stuff can be safely archived to remote locations.
Just copy them back when you have to do maintenance.
I wanna be a eunuchs developer! Pass me a bread knife!
|
|
|
|
|
Great, yet another folder in which MS dumps random files of dubious value. I have 3GB in there right now.
I wish all folders of that nature could be consolidated under a common root.
|
|
|
|
|
That would go against MS's multiple points of failure motto. And better brittle than well-designed.
|
|
|
|
|
Good thing cynicism doesn't kill.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
