Lines Matching +full:integer +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
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).
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)`.
110 It has a complexity of `O(n^3)`.
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)) - ...
167 to calculate the bessel function (integer order only).
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.
206 Next, check if the exponent is actually an integer, and if it is, use the
215 (and the integer version of the exponent, which we calculated earlier to check
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
240 Then we have the most clever trick: we add the length of that integer power (and
242 is calculated to at least as many digits as should be in the integer *plus* any
248 integer portion of the power again.
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
256 But then we *multiply* it into the integer portion of the power. Why? Because
260 So we multiply it into the integer portion of the power.
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
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.
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-…