TY - JOUR

T1 - The p-sized partitioning algorithm for fast computation of factorials of numbers

AU - Ugur, Ahmet

AU - Thompson, Henry

PY - 2006/10

Y1 - 2006/10

N2 - Computing products of large numbers has always been a challenging task in the field of computing. One such example would be the factorial function. Several methods have been implemented to compute this function including naive product, recursive product, Boiten split, and prime factorization, and linear difference. The method presented here is unique in the sense that it exploits finite order differences to reduce the number of multiplications necessary to compute the factorial. The differences generated are regrouped into a new sequence of numbers, which have at most half as many elements of the original sequence. When the terms of this new sequence are multiplied together, the factorial value is obtained. The cardinality of the new sequence can further be reduced by partitioning. The sequence is computed by using several difference tables that assist in establishing the pattern that determines the sequence. An analysis of the algorithm is presented. The analysis shows that the execution time can be reduced significantly by the algorithm presented.

AB - Computing products of large numbers has always been a challenging task in the field of computing. One such example would be the factorial function. Several methods have been implemented to compute this function including naive product, recursive product, Boiten split, and prime factorization, and linear difference. The method presented here is unique in the sense that it exploits finite order differences to reduce the number of multiplications necessary to compute the factorial. The differences generated are regrouped into a new sequence of numbers, which have at most half as many elements of the original sequence. When the terms of this new sequence are multiplied together, the factorial value is obtained. The cardinality of the new sequence can further be reduced by partitioning. The sequence is computed by using several difference tables that assist in establishing the pattern that determines the sequence. An analysis of the algorithm is presented. The analysis shows that the execution time can be reduced significantly by the algorithm presented.

KW - Fast factorial computation

KW - Partitioning

UR - http://www.scopus.com/inward/record.url?scp=33748928659&partnerID=8YFLogxK

U2 - 10.1007/s11227-006-7285-5

DO - 10.1007/s11227-006-7285-5

M3 - Article

AN - SCOPUS:33748928659

SN - 0920-8542

VL - 38

SP - 73

EP - 82

JO - Journal of Supercomputing

JF - Journal of Supercomputing

IS - 1

ER -