I have developed a set of "Oversized integer full precision fast algorithm" hugecalc, can quickly calculate the super-integer, minus, multiplication, division (commercial / Yu), multiplication, and rapid calculation of large numbers Fibonacci number, (double) step-by-step, arrangement, combination, etc., can complete the maximum number of conventions of large integer arrays, the least common multiple, etc. Accumulate. Since the public online, it has been widely received by netizens. There are often netizens to contact, I want to exchange some algorithms. The most involved the most about "step" algorithms, part of the school student, maybe their graduation design? :) Here, I will put the core part of the algorithm module, but some key points, sorted out for your reference.
Squaining, it is the product of a set of number columns, the efficiency is high, and one, it is depends on the high-precision multiplier algorithm, and two is the optimization of the algorithm for the characteristic algorithm.
The former is a well-known technology. Although different algorithms can be efficient, they can be obtained by learning, and even the "brought-in-law" of Lu Xun;
The latter, there are many development space. Here I will introduce a method that is completely original, welcome everyone to discuss, if it can play the effect of "throwing bricks", it is truly a purpose.
When I develop "step" class algorithm, I always follow the following principles:
Participate in the two numbers of high-precision multiplication algorithms, the size should be as similar as possible; the multiplication is converted to the multiplication as much as possible; the square will be called as much as possible;
The words are turned forward, and the following is calculated at a precise calculation 1000! Take the algorithm:
Remember F1 (N) = n * (n-1) * ... * 1;
F2 (n) = n * (n-2) * ... * (2 or 1);
POW2 (R) = 2 ^ R;
Have F1 (2K 1) = F2 (2K 1) * F2 (2K)
= POW2 (K) * F2 (2K 1) * F1 (K),
F1 (2K) = POW2 (K) * F2 (2K-1) * F1 (K),
And POW2 (U) * POW2 (V) = POW2 (U V),
∴ 1000! =
F1 (1000)
= POW2 (500) * F2 (999) *
F1 (500)
= POW2 (750) * F2 (999) * F2 (499) *
F1 (250)
= POW2 (875) * F2 (999) * F2 (499) * F2 (249) *
F1 (125)
= POW2 (937) * F2 (999) * F2 (499) * F2 (249) * F2 (125) *
F1 (62)
= POW2 (968) * F2 (999) * F2 (499) * F2 (249) * F2 (125) * F2 (61) *
F1 (31)
= POW2 (983) * F2 (999) * F2 (499) * F2 (249) * F2 (125) * F2 (61) * F2 (31) *
F1 (15)
= ...
If you predict some small interactions (such as here "
F1 (15) "), then terminate decomposition in advance, otherwise until the last one of the right is"
F1 (1) "; then we
The integer power of the step-by-step transition into 2, and some consecutive numbers (or multiplication by a small integer);
Refined: F2 (E, F) = E * (E-2) * ... * (f 2), here is still "F2", it is "function overload" good :), then F2 (e) = f2 (e, -1) = f2 (e, f) * f2 (f, -1) (e, f is an odd number, 0 ≤ F ≤ E)
∴ F2 (999) = F2 (999, 499) * F2 (499, 249) * F2 (249, 125) * F2 (125, 61) * F2 (61, 31) * F2 (31),
F2 (499) = ____________f2 (499, 249) * F2 (249, 125) * F2 (125, 61) * F2 (61, 31) * F2 (31),
F2 (249) = _______________________f2 (249, 125) * F2 (125, 61) * F2 (61, 31) * F2 (31),
F2 (125) = ___________________________________f2 (125, 61) * f2 (61, 31) * F2 (31),
F2 (61) = _____________________________________________f2 (61, 31) * F2 (31),
F2 (31) = _____________________________________________f2 (31),
∴ f1 (1000) =
F1 (15) * POW2 (983) * F2 (999, 499) /
* [F2 (499, 249) ^ 2] * [F2 (249, 125) ^ 3] /
* [F2 (61, 31) ^ 4] * [f2 (31) ^ 5]
In this way, we
Transform steps into the multiplication.
The above formula is actually a form of a * B ^ 2 * c ^ 3 * D ^ 4 * e ^ 5; we will convert the index to binary, you can get the following formula:
A * b ^ 2 * c ^ 3 * D ^ 4 * e ^ 5 = (a * c * e) * [(b * c) ^ 2] * [(d * e) ^ 4]
=
((((E * D) ^ 2) * (C * b)) ^ 2 * (E * C * a),
I.e.
Conversion to a highly efficient square algorithm.
Finally, I will provide you again.
Make sure that "small integer is more tired of overflow" skills, this is my homemade, I believe that there will be a role in everyone:
"Reverse" should be used. For example, it should be in the order of 999 * 997 * ..., and an array can be set in advance, and if the maximum value of the current start array is not more than a certain value, how many numbers do not take It will overflow; the "geometric average ≤ arithmetic average" Theorem can be derived "K natural number is not more than a certain value, the sufficient condition is that it is not more than a critical value," we only need prior Calculate their correspondence and save it.
The above algorithm is
HUGECALC VER 1.2.0.1 Algorithm key points, its efficiency is slightly higher than the senior algorithm of Liangbch (Baby) 3.0.
In the latest
In HugeCalc Ver2.1.0.1, it is a more thorough decomposition method, and the skill is not as strong as strong (but there is a high-efficiency diameter screening method), but many of the idea is still continuing.
Remarks:
Factorial.exever2.1.0.1Cleron (TM) 466MHz64MB RAM, WIN98SECPENTIUM (R) 4 1.70GHz256MB RAM, WinXPRESULT 10,000! 0.069S 0.031S2.8462 ... x 10 ^ 35,659 20,000! 0.236s 0.109s1.8192 ... x 10 ^ 77, 337 40,000! 0.795s 0.390s2.0916 ... x 10 ^ 166, 713 80,000! 2.661S 1.328S3.0977 ... x 10 ^ 357, 506100,000! 4.177s 1.969s2.8242 ... x 10 ^ 456, 573200,000! 13.663s 6.438s1.4202 ... x 10 ^ 973, 350400,000! 43.818s20.828s2.5344 ... x 10 ^ 2,067,109800,000! 139.337s66.921s5.6846 .. . x 10 ^ 4,375,039 author: Guo Xianqiang; release date: 2004-06-15; the first draft of this article appeared in the famous "9CBS - technology community - to develop data structures and algorithms thematic issues"; Download: super fast full precision integer calculator / Algorithm Copyright, not authorized by the original author, it is strictly forbidden!
