Lines Matching +full:3 +full:- +full:n

7 This `bc` uses brute force addition, which is linear (`O(n)`) in the number of
12 This `bc` uses brute force subtraction, which is linear (`O(n)`) in the number
22 this `bc`, is superlinear but subpolynomial (bounded by `O(n^log_2(3))`).
25 polynomial (`O(n^2)`), but since Karatsuba requires both more intermediate
31 ***WARNING: The Karatsuba script requires Python 3.***
36 (`O(n^2)`), but unlike Karatsuba, any division "divide and conquer" algorithm
53 complexity of `O(n^(2*log_2(3)))` (best case) and `O(n^3)` (worst case).
57 This `bc` implements [Exponentiation by Squaring][3], which (via Karatsuba) has
58 a complexity of `O((n*log(n))^log_2(3))` which is favorable to the
59 `O((n*log(n))^2)` without Karatsuba.
64 Newton-Raphson Method, or the [Babylonian Method][5]) to perform the square root
67 Its complexity is `O(log(n)*n^2)` as it requires one division per iteration, and
75 x - x^3/3! + x^5/5! - x^7/7! + ...
84 to calculate `cos(x)`. It has a complexity of `O(n^3)`.
99 1 + x + x^2/2! + x^3/3! + ...
110 It has a complexity of `O(n^3)`.
121 a + a^3/3 + a^5/5 + ...
124 (where `a` is equal to `(x - 1)/(x + 1)`) to calculate `ln(x)` when `x` is small
133 It has a complexity of `O(n^3)`.
144 x - x^3/3 + x^5/5 - x^7/7 + ...
150 atan(x) = atan(c) + atan((x - c)/(1 + x * c))
153 to reduce `x` to small enough. It has a complexity of `O(n^3)`.
164 x^n/(2^n * n!) * (1 - x^2 * 2 * 1! * (n + 1)) + x^4/(2^4 * 2! * (n + 1) * (n + 2)) - ...
172 j(-n,x) = (-1)^n * j(n,x)
175 to calculate the bessel when `x < 0`, It has a complexity of `O(n^3)`.
183 This `dc` uses the [Memory-efficient method][8] to compute modular
184 exponentiation. The complexity is `O(e*n^2)`, which may initially seem
185 inefficient, but `n` is kept small by maintaining small numbers. In practice, it
188 ### Non-Integer Exponentiation (`bc` Math Library 2 Only)
194 It has a complexity of `O(n^3)` because both `e()` and `l()` do.
216 if it was an integer). We also save the number in `z`; being non-zero is a flag
221 relationship `l(x) == -l(1/x)`; we negated the exponent, which is equivalent to
252 calculate `e((y - a) * l(x))`, where `a` is the integer portion of `y`. It's
253 easy to see that `y - a` will be just the fractional portion of `y` (the
271 It has a complexity of `O(n)` because of add.
279 It has a complexity of `O(n)` because of add.
283 This is implemented in the function `f(n)`.
287 It has a complexity of `O(n^3)` because of linear amount of `O(n^2)`
292 This is implemented in the function `perm(n,k)`.
294 The algorithm is to use the formula `n!/(n-k)!`.
296 It has a complexity of `O(n^3)` because of the division and factorials.
300 This is implemented in the function `comb(n,r)`.
302 The algorithm is to use the formula `n!/r!*(n-r)!`.
304 It has a complexity of `O(n^3)` because of the division and factorials.
314 It has a complexity of `O(n^3)` because of the division and `l()`.
330 This is implemented in the function `root(x,n)`.
333 `10^ceil(length(x)/n)`.
335 Like square root, its complexity is `O(log(n)*n^2)` as it requires one division
342 This is a convenience wrapper around `root(x,3)`.
350 It has a complexity of `O(n^4)` because it has a linear number of divisions.
361 It has a complexity of `O(n^4)` because of `gcd()`.
369 It has a complexity of `O(n^3)` because of arctangent.
377 It has a complexity of `O(n^3)` because of sine, cosine, and division.
385 It has a complexity of `O(n^3)` because of arctangent.
389 [3]: https://en.wikipedia.org/wiki/Exponentiation_by_squaring
394 [8]: https://en.wikipedia.org/wiki/Modular_exponentiation#Memory-efficient_method
395 [9]: https://en.wikipedia.org/wiki/Root-finding_algorithms#Newton's_method_(and_similar_derivative-…