๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Parallel Algorithms for Counting and Randomly Generating Integer Partitions

โœ Scribed by Laura A. Sanchis; Matthew B. Squire

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
228 KB
Volume
34
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

โœฆ Synopsis

This paper presents parallel algorithms for determining the number of partitions of a given integer N, where the partitions may be subject to restrictions, such as being composed of distinct parts, of a given number of parts, and/or of parts belonging to a specified set. We present a series of adaptive algorithms suitable for varying numbers of processors. The fastest of these algorithms computes the number of partitions of n with largest part equal to k, for 1 ี… k ี… n ี… N, in time O(log 2 (N )) using O(N 2 /log N ) processors. Parallel logarithmic time algorithms that generate partitions uniformly at random, using these quantities, are also presented.

๐Ÿ“œ SIMILAR VOLUMES

A generic approach to parallelizing and
A generic approach to parallelizing and developing control algorithms for heterogeneous architectures
โœ M. J. Baxter; M. O. Tokhi; P. J. Fleming ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 249 KB ๐Ÿ‘ 2 views

System developers have found that exploiting parallel architectures for control systems is challenging and often the resulting implementations do not provide the expected performance advantages over traditional uniprocessor solutions. This paper presents a generic method and a suite of design tools