Boots – shoes – and leggings
Patent
1997-09-25
1999-02-16
Mai, Tan V.
Boots, shoes, and leggings
G06F 102
Patent
active
058727256
DESCRIPTION:
BRIEF SUMMARY
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a method and system for generating a low-discrepancy sequence including a Generalized Nierderreiter Sequence and a Generalized Faure sequence at high speed. This low-discrepancy sequence is a sequence of extremely uniformly distributed points.
2. Description of the Prior Art
With the recent trend of liberalization of interest rates, various financial institutions, such as banks or securities corporations, have come to make the most of a high speed computer for pricing a derivative security and like purposes. The reason for using the high speed computer is because there is a necessity of promptly responding to the demand of customers in spite of great many factors of fluctuation such as various customer-dependent parameters and economic indicators.
As a field of providing a mathematical model for such finances and an algorithm for rationally solving an equation in the mathematical model, a financial engineering is proposed and has recently formed an active study.
Calculations required for the financial engineering, especially for pricing a derivative security include a multiple integral. Generally, for computer-used integral, a technique of equi-partitioning the integral interval into an infinitesimal regions and accumulating the product of a value of function in each subinterval and a width of subinterval is used. In a multiple integral calculation, if a k-fold multiple integral, N.sup.k iterations of calculation for N partitions in one integral interval are necessary. Even for k=5, a calculation time with a practical number N of partitions exceeds the practicable limits for processing with an ordinary computer.
For this reason, a method for calculating a multiple integral, called a Monte Carlo method by use of a certain type of random numbers has so far been proposed. This method comprises the steps of: generating a plenty of k-dimensional coordinates of uniform random numbers within the limits of k-dimensional integral intervals for a multiple integral; successively substituting the generated coordinates in the function to be integrated; and evaluating the probability of the substituted values to satisfy a predetermined condition.
This is expressed with the following formula: ##EQU1##
In this case, to give a set of N points x.sub.i (i=1, . . . , N) is the algorithm itself. For calculating the expected value of prices in pricing a derivative security, an f(x) determined from each stochastic model is used in this formula.
In addition, in this type of problems, an algorithm serving to reduce an error in integral is a "good algorithm". On the other hand, from a consideration with the error kept constant (e.g., 0.001), a "good algorithm" is one in which the target error can be attained by using a set of the fewest possible points (i.e., smaller N). Since the computational time is generally proportional to the number of points in such an algorithm, a "good algorithm" also means a "rapid algorithm".
In the Monte Carlo method in which random points generated by a linear congruence method are used, it is known that the error is almost proportional to an inverse number of the square root of N. Following this and briefly saying, 10.sup.6 points are required for attaining an error of 0.001.
On the other hand, there is also an algorithm with a low-discrepancy sequence used as a set of N points. In this case, it is known that the error is theoretically almost proportional to 1/N. According to this, N=10.sup.3 points are enough for attaining an error of 0.001. Accordingly, using a low-discrepancy sequence enable a 10.sup.3 times faster computation than that of the Monte Carlo.
Some methods for forming a low-discrepancy sequence are proposed, but a sequence called a Faure sequence is regarded as promising for calculating a high-dimensioned multiple integral by those skilled in the art. For further details, refer to the following treatise: P. P. Boyle, New Variance Reduction Methods for Efficient Monte Carlo Simulations, Conference on Advanc
REFERENCES:
patent: 5651123 (1997-07-01), Nakagawa et al.
P.P Boyle, New Variance Reduction Methods for Efficient Monte Carlo Simulations, Conference on Advanced Mathematics on Derivatives, Risk Magazine (Sep., 1994).
P. Bratley, B.L. Fox, and H. Niederreiter, Implementation and Tests of Low-Discrepancy Sequences, ACM Trans. Modeling and Computer Simulation, 2, (Jul., 1992), 195-213.
Ninomiya Syoiti
Tezuka Shu
Gundel Norman L.
International Business Machines - Corporation
Mai Tan V.
Seaman Kenneth A.
LandOfFree
Quasi-random number generation apparatus and method, and multipl does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Quasi-random number generation apparatus and method, and multipl, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quasi-random number generation apparatus and method, and multipl will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2067890