proofdopa.blogg.se

1. #CALCULATOR FOR LARGE VALUES FULL#
2. #CALCULATOR FOR LARGE VALUES CODE#

Splitting in this way requires two BigInt squares as before, but only a single BigInt addition. This overhead can be eliminated almost entirely by splitting on L n and L n+1 instead:

Aside from the two BigInt squares, splitting on F n and F n+1 also has an overhead of three BigInt additions and two small constant multiplications per split. Since originally posting, I've improved upon the previous result slightly as well. As expected, the run-time is measurably faster than the above implementation for very large n, but is somewhat slower for small values ( n > 1) Iterating in this way will require two BigInt squares per split, rather than a BigInt square and a BigInt multiplication as above. The author suggestions an iteration, splitting on F n and L n, using the following identities: def fibonacci(n):Ī greybeard points out, the above result has already been improved upon by Takahashi (2000) 2, by noting that BigInt squaring is generally (and specifically for the Schönhage-Strassen algorithm) less computationally expensive than BigInt multiplication. Note: the original source has been modified (improved) slightly to allow a fair comparison.

#CALCULATOR FOR LARGE VALUES CODE#

This is about 20% faster than the code provided by Project Nayuki ( test script). Proceeding in this way requires only two BigInt-to-BigInt multiplications per split, and only one for the final result. Further identities used in the implementation below can either be found or derived from the identities listed for Lucas Sequences: There's a few more-or-less equivalent ways to proceed recursively, but the most logical seems to be on F n and L n.

This identity can be further generalized as: One of the most elegant Fibonacci identities is related to the Lucas Numbers: We can still do slightly better than this, though. Note that this requires only 3 BigInt-to-BigInt multiplications per split, rather than 8 as matrix exponentiation would. Given F k and F k+1, we can calculate these: As a developer at Project Nayuki has noticed, matrix exponentiation carries with it redundant calculations, which can be removed. However, matrix exponentiation isn't necessarily the best way to go about it. Using Karatsuba Multiplication, for example, the overall run-time complexity would be O(n log 23) ≈ O(n 1.585).

#CALCULATOR FOR LARGE VALUES FULL#

The calculation would go on forever, so we have to stop somewhere.Ĭontact us with any suggestions for improvements or enhancements to this full precision calculator.I agree with Wayne Rooney's answer that the optimal solution will complete in O(log n) steps, however the overall run-time complexity will depend upon the complexity of the multiplication algorithm used. The same thing happens with functions like square root, sine, cosine, etc. Most calculations are done to full precision.īut some decimals go on forever (such as 1/3 = 0.33333.), so we stop after 200 decimals. To estimate how long it should take on your device.Īlso if you want to calculate high powers, for example, 2^1000, it may be quicker to calculate 2^100, then take that result and raise that For example if 200! is taking a long time, then try 100!, then 120! etc In some cases it may be better to approach things more gently. It is up to you whether to continue to run the script or not.