Fast Factorial Functions. An example of a PrimeSwing computation: As this example shows an efficient computation of the factorial function reduces to an efficient computation of the swinging factorial n≀.
Some information about these numbers can be found here and here. The prime factorization of the swing numbers is crucial for the implementation of the PrimeSwing algorithm. A concise description of this algorithm is given in this write-up (pdf) and in the SageMath link below (Algo 5). Fast-Factorial-Functions: The Homepage of Factorial Algorithms. Fast inverse square root. The algorithm accepts a 32-bit floating point number as the input and stores a halved value for later use.
Then, treating the bits representing the floating point number as a 32-bit integer, a logical shift right of one bit is performed and the result subtracted from the "magic constant" 0x5f3759df. This is the first approximation of the inverse square root of the input. Treating the bits again as floating point it runs one iteration of Newton's method to return a more precise approximation. This computes an approximation of the inverse square root of a floating point number approximately four times faster than floating point division.
The algorithm was originally attributed to John Carmack, but an investigation showed that the code had deeper roots in both the hardware and software side of computer graphics. Motivation[edit] Surface normals are used extensively in lighting and shading calculations, requiring the calculation of norms for vectors. Is the normalized (unit) vector. . And . . Knuth shuffle. Knuth shuffle You are encouraged to solve this task according to the task description, using any language you may know.
Implement the Knuth shuffle (a.k.a. the Fisher-Yates shuffle) for an integer array (or, if possible, an array of any type). The Knuth shuffle is used to create a random permutation of an array. [edit] ACL2 :set-state-ok t (defun array-swap (name array i j) (let ((ai (aref1 name array i)) (aj (aref1 name array j))) (aset1 name (aset1 name array j ai) i aj))) (defun shuffle-r (name array m state) (if (zp m) (mv array state) (mv-let (i state) (random$ m state) (shuffle-r name (array-swap name array i m) (1- m) state)))) (defun shuffle (name array state) (shuffle-r name array (1- (first (dimensions name array))) state)) [edit] Ada This implementation is a generic shuffle routine, able to shuffle an array of any type. generic type Element_Type is private; type Array_Type is array (Positive range <>) of Element_Type; procedure Generic_Shuffle (List : in out Array_Type); Example: Fisher–Yates shuffle. Fisher–Yates shuffling is similar to randomly picking numbered tickets (combinatorics: distinguishable objects) out of a hat without replacement until there are none left.
Fisher and Yates' original method[edit] The Fisher–Yates shuffle, in its original form, was described in 1938 by Ronald A. Fisher and Frank Yates in their book Statistical tables for biological, agricultural and medical research.[1] Their description of the algorithm used pencil and paper; a table of random numbers provided the randomness. The basic method given for generating a random permutation of the numbers 1 through N goes as follows: Provided that the random numbers picked in step 2 above are truly random and unbiased, so will the resulting permutation be. The modern algorithm[edit] The modern version of the Fisher–Yates shuffle, designed for computer use, was introduced by Richard Durstenfeld in 1964[2] and popularized by Donald E. The "inside-out" algorithm[edit] Examples[edit] Pencil-and-paper method[edit]