The Fast Linear Algorithm
N dimensional ball
Probabilities and Performances :

The Fast Linear Algorithm is the fastest of all algorithms proposed. Indeed we can show generally that another algorithm cannot be faster (see article).
  • Figure: The probability P(x) and the test function f(x)
    FLA=Fast Linear Algorithm
 
 
 
  • Figure: comparison of the time of simulation for various algorithms as function of N, the dimension of the space
    • FLA=Fast Linear Algorithm
    • Ba  =Banerjia method (Comm. Stat. Simulations 22(1993)1205
    • Mar =Marsaglia method (Annal of Math. Stat. 43(1972)645
    • G   =using Gaussian random numbers.
    • UnifS = angles, sinNS-2(theta) ... are chosen from a sinus distribution and the rejection method
    • Unifa = angles, sinNS-2(theta) ... are chosen from a uniform distribution and the rejection method
  • Figure: comparison of the rate of simulation for various algorithms
    • FLA=Fast Linear Algorithm
    • Ba  =Banerjia method (Comm. Stat. Simulations 22(1993)1205
    • Mar =Marsaglia method (Annal of Math. Stat. 43(1972)645
    • G   =using Gaussian random numbers.
    • UnifS = angles, sinNS-2(theta) ... are chosen from a sinus distribution and the rejection method
    • Unifa = angles, sinNS-2(theta) ... are chosen from a uniform distribution and the rejection method