14,392,749 members

# Welcome to the Lounge

For discussing anything related to a software developer's life but is not for programming questions. Got a programming question?

The Lounge is rated Safe For Work. If you're about to post something inappropriate for a shared office environment, then don't post it. No ads, no abuse, and no programming questions. Trolling, (political, climate, religious or whatever) will result in your account being removed.

 Re: Classic computer science problems Fueled By Caffeine25-Apr-19 22:16 Fueled By Caffeine 25-Apr-19 22:16
 Re: Classic computer science problems Dominic Burford25-Apr-19 23:01 Dominic Burford 25-Apr-19 23:01
 Re: Classic computer science problems pkfox26-Apr-19 1:32 pkfox 26-Apr-19 1:32
 Re: Classic computer science problems harold aptroot26-Apr-19 5:34 harold aptroot 26-Apr-19 5:34
 Re: Classic computer science problems harold aptroot26-Apr-19 7:09 harold aptroot 26-Apr-19 7:09
 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.
 SmartXML Bassam Abdul-Baki25-Apr-19 9:05 Bassam Abdul-Baki 25-Apr-19 9:05
 Re: SmartXML Mark_Wallace25-Apr-19 9:07 Mark_Wallace 25-Apr-19 9:07
 Re: SmartXML Bassam Abdul-Baki25-Apr-19 10:13 Bassam Abdul-Baki 25-Apr-19 10:13
 Re: SmartXML Marc Clifton25-Apr-19 9:54 Marc Clifton 25-Apr-19 9:54
 Re: SmartXML Bassam Abdul-Baki25-Apr-19 10:13 Bassam Abdul-Baki 25-Apr-19 10:13
 Re: SmartXML Mark_Wallace25-Apr-19 10:55 Mark_Wallace 25-Apr-19 10:55
 Re: SmartXML Bassam Abdul-Baki25-Apr-19 13:19 Bassam Abdul-Baki 25-Apr-19 13:19
 Re: SmartXML Marc Clifton26-Apr-19 3:08 Marc Clifton 26-Apr-19 3:08
 Re: SmartXML Brisingr Aerowing25-Apr-19 12:45 Brisingr Aerowing 25-Apr-19 12:45
 Re: SmartXML MarkTJohnson26-Apr-19 4:01 MarkTJohnson 26-Apr-19 4:01
 Re: SmartXML Member 798912226-Apr-19 8:33 Member 7989122 26-Apr-19 8:33
 Space, the final frontier RickZeeland25-Apr-19 7:49 RickZeeland 25-Apr-19 7:49
 Re: Space, the final frontier Mark_Wallace25-Apr-19 9:05 Mark_Wallace 25-Apr-19 9:05
 Re: Space, the final frontier dandy7225-Apr-19 10:22 dandy72 25-Apr-19 10:22
 Re: Space, the final frontier David O'Neil25-Apr-19 16:23 David O'Neil 25-Apr-19 16:23
 Re: Space, the final frontier dandy7226-Apr-19 11:03 dandy72 26-Apr-19 11:03
 Last Visit: 15-Dec-19 21:17     Last Update: 15-Dec-19 21:17 Refresh « Prev1...1129113011311132113311341135113611371138 Next »