|
Binary Splitting
In mathematics, binary splitting is a technique for speeding up numerical evaluation of many types of series with rational terms. In particular, it can be used to evaluate hypergeometric series at rational points. Method Given a series :S(a,b) = \sum_^b \frac where ''pn'' and ''qn'' are integers, the goal of binary splitting is to compute integers ''P''(''a'', ''b'') and ''Q''(''a'', ''b'') such that :S(a,b) = \frac{Q(a,b)}. The splitting consists of setting ''m'' = ''a'' + ''b'')/2and recursively computing ''P''(''a'', ''b'') and ''Q''(''a'', ''b'') from ''P''(''a'', ''m''), ''P''(''m'', ''b''), ''Q''(''a'', ''m''), and ''Q''(''m'', ''b''). When ''a'' and ''b'' are sufficiently close, ''P''(''a'', ''b'') and ''Q''(''a'', ''b'') can be computed directly from ''pa...pb'' and ''qa...qb''. Comparison with other methods Binary splitting requires more memory than direct term-by-term summation, but is asymptotically faster since the sizes of all occurring subproducts are re ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics with the major subdisciplines of number theory, algebra, geometry, and analysis, respectively. There is no general consensus among mathematicians about a common definition for their academic discipline. Most mathematical activity involves the discovery of properties of abstract objects and the use of pure reason to prove them. These objects consist of either abstractions from nature orin modern mathematicsentities that are stipulated to have certain properties, called axioms. A ''proof'' consists of a succession of applications of deductive rules to already established results. These results include previously proved theorems, axioms, andin case of abstraction from naturesome basic properties that are considered true starting points of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Series (mathematics)
In mathematics, a series is, roughly speaking, a description of the operation of adding infinitely many quantities, one after the other, to a given starting quantity. The study of series is a major part of calculus and its generalization, mathematical analysis. Series are used in most areas of mathematics, even for studying finite structures (such as in combinatorics) through generating functions. In addition to their ubiquity in mathematics, infinite series are also widely used in other quantitative disciplines such as physics, computer science, statistics and finance. For a long time, the idea that such a potentially infinite summation could produce a finite result was considered paradoxical. This paradox was resolved using the concept of a limit during the 17th century. Zeno's paradox of Achilles and the tortoise illustrates this counterintuitive property of infinite sums: Achilles runs after a tortoise, but when he reaches the position of the tortoise at the beginning of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Toom–Cook Multiplication
Toom–Cook, sometimes known as Toom-3, named after Andrei Toom, who introduced the new algorithm with its low complexity, and Stephen Cook, who cleaned the description of it, is a multiplication algorithm for large integers. Given two large integers, ''a'' and ''b'', Toom–Cook splits up ''a'' and ''b'' into ''k'' smaller parts each of length ''l'', and performs operations on the parts. As ''k'' grows, one may combine many of the multiplication sub-operations, thus reducing the overall computational complexity of the algorithm. The multiplication sub-operations can then be computed recursively using Toom–Cook multiplication again, and so on. Although the terms "Toom-3" and "Toom–Cook" are sometimes incorrectly used interchangeably, Toom-3 is only a single instance of the Toom–Cook algorithm, where ''k'' = 3. Toom-3 reduces 9 multiplications to 5, and runs in Θ(''n''log(5)/log(3)) ≈ Θ(''n''1.46). In general, Toom-''k'' runs in , where , ''ne'' is the time spent on sub-mul ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Schönhage–Strassen Algorithm
The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers. It was developed by Arnold Schönhage and Volker Strassen in 1971.A. Schönhage and V. Strassen,Schnelle Multiplikation großer Zahlen, ''Computing'' 7 (1971), pp. 281–292. The run-time bit complexity is, in big O notation, O(n \cdot \log n \cdot \log \log n) for two ''n''-digit numbers. The algorithm uses recursive fast Fourier transforms in rings with 2''n''+1 elements, a specific type of number theoretic transform. The Schönhage–Strassen algorithm was the asymptotically fastest multiplication method known from 1971 until 2007, when a new method, Fürer's algorithm, was announced with lower asymptotic complexity, and is used in the Basic Polynomial Algebra Subprograms (BPAS) open source library. The algorithm does not adapt for polynomials over finite fields though. The current best multiplication algorithm in terms of asymptotic complexity is by David Harvey and Jor ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Parallelization
Parallel computing is a type of computation in which many calculations or processes are carried out simultaneously. Large problems can often be divided into smaller ones, which can then be solved at the same time. There are several different forms of parallel computing: bit-level, instruction-level, data, and task parallelism. Parallelism has long been employed in high-performance computing, but has gained broader interest due to the physical constraints preventing frequency scaling.S.V. Adve ''et al.'' (November 2008)"Parallel Computing Research at Illinois: The UPCRC Agenda" (PDF). Parallel@Illinois, University of Illinois at Urbana-Champaign. "The main techniques for these performance benefits—increased clock frequency and smarter but increasingly complex architectures—are now hitting the so-called power wall. The computer industry has accepted that future performance increases must largely come from increasing the number of processors (or cores) on a die, rather than m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Checkpointing
Checkpointing is a technique that provides fault tolerance for computing systems. It basically consists of saving a snapshot of the application's state, so that applications can restart from that point in case of failure. This is particularly important for long running applications that are executed in failure-prone computing systems. Checkpointing in distributed systems In the distributed computing environment, checkpointing is a technique that helps tolerate failures that otherwise would force long-running application to restart from the beginning. The most basic way to implement checkpointing, is to stop the application, copy all the required data from the memory to reliable storage (e.g., parallel file system) and then continue with the execution. In case of failure, when the application restarts, it does not need to start from scratch. Rather, it will read the latest state ("the checkpoint") from the stable storage and execute from that. While there is ongoing debate on wh ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Divide And Conquer Algorithm
In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. The divide-and-conquer technique is the basis of efficient algorithms for many problems, such as sorting (e.g., quicksort, merge sort), multiplying large numbers (e.g., the Karatsuba algorithm), finding the closest pair of points, syntactic analysis (e.g., top-down parsers), and computing the discrete Fourier transform (FFT). Designing efficient divide-and-conquer algorithms can be difficult. As in mathematical induction, it is often necessary to generalize the problem to make it amenable to a recursive solution. The correctness of a divide-and-conquer algorithm is usually proved by mathematical induction, and its computational cost is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Class Library For Numbers
Class Library for Numbers (CLN) is a free library for arbitrary precision arithmetic. It operates on signed integers, rational numbers, floating point numbers, complex numbers, modular numbers, and univariate polynomials. Its implementation programming language is C++. Details CLN uses object oriented techniques and operator overloading to achieve a natural algebraic syntax: The sum ''x'' of two variables ''a'' and ''b'' is written as ''x'' = ''a'' + ''b'', as opposed to the function sum(&''x'', ''a'', ''b''). CLN uses class inheritance to model the natural subsets of the available number types: E.g. the integer class is a subtype of the rational class, just as the integer numbers are a subset of the rational numbers. The complex numbers and all its subtypes behave exactly like the types of numbers known to the Common Lisp language, giving CLN another meaning: it becomes an abbreviation of ''Common Lisp Numbers''. Due to this, CLN can be and is used ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
