|
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.
|
|
|
|
|
|
Why do smoke detector batteries always fail at 2:30 AM?
|
|
|
|
|
Because 4:30 would be more painful.
"If we don't change direction, we'll end up where we're going"
|
|
|
|
|
Well ... it's actually physics, not design.
Battery output varies with temperature, and most houses are coolest between 02:00 and 05:00 (for obvious reasons). As they cool, the battery can't put out as much as it can during the warmer day, and the smoke detector picks this up as an imminent battery failure and starts the "replace me" chirp.
Or in our case it talks to you, which at 02:30 is even more disconcerting as it wakes you up and then shuts up so you hear something and don't know what it was ...
Sent from my Amstrad PC 1640
Never throw anything away, Griff
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
Don't you hate geeky correct answers to rhetorical questions?
|
|
|
|
|
Sometimes.
But ... I really like it when what looks like a random event that apocryphally happend 9 times out of 10 turns out to be a real situation that occurs because of the design of all such devices forces it to.
Battery operated smoke detectors have to monitor the battery because if they didn't they would fail unnoticed and risk lives. But using a temperature sensor in concert with the battery output wouldn't help because if it relied on the temperature change affecting the battery, it would fail by day when it's less likely to be noticed, and not work at night when more domestic fire happen. And (of course) fires alter the temperature).
So it's a serendipitous safety feature, which I love the whole idea of!
Sent from my Amstrad PC 1640
Never throw anything away, Griff
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
AntiTwitter: @DalekDave is now a follower!
|
|
|
|