32 0 0 0 IR Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator
- 著者
- Matsumoto Makoto Nishimura Takuji
- 出版者
- ACM
- 雑誌
- ACM Transactions on Modeling and Computer Simulation (ISSN:10493301)
- 巻号頁・発行日
- vol.8, no.1, pp.3-30, 1998-01
- 被引用文献数
- 131 3927
A new algorithm called Mersenne Twister (MT) is proposed for generating uniform pseudorandom numbers. For a particular choice of parameters, the algorithm provides a super astronomical period of 219937 - 1 and 623-dimensional equidistribution up to 32-bit accuracy, while using a working area of only 624 words. This is a new variant of the previously proposed generators, TGFSR, modified so as to admit a Mersenne-prime period. The characteristic polynomial has many terms. The distribution up to v bits accuracy for 1 ≤ v ≤ 32 is also shown to be good. An algorithm is also given that checks the primitivity of the characteristic polynomial of MT with computational complexity O(p2) where p is the degree of the polynomial. We implemented this generator in portable C-code. It passed several stringent statistical tests, including diehard. Its speed is comparable to other modern generators. Its merits are due to the efficient algorithms that are unique to polynomial calculations over the two-element field.
- 著者
- Unno Hiroshi Terauchi Tachio Kobayashi Naoki
- 出版者
- ACM
- 雑誌
- Proceeding POPL '13 Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages
- 巻号頁・発行日
- pp.75-86, 2013-01
- 被引用文献数
- 30
We present an automated approach to relatively completely verifying safety (i.e., reachability) property of higher-order functional programs. Our contribution is two-fold. First, we extend the refinement type system framework employed in the recent work on (incomplete) automated higher-order verification by drawing on the classical work on relatively complete "Hoare logic like" program logic for higher-order procedural languages. Then, by adopting the recently proposed techniques for solving constraints over quantified first-order logic formulas, we develop an automated type inference method for the type system, thereby realizing an automated relatively complete verification of higher-order programs.
- 著者
- Tachibana Tatsuhiro Murata Yoshihiro Shibata Naoki Yasumoto Keiichi Ito Minoru
- 出版者
- ACM
- 巻号頁・発行日
- pp.236, 2006
- 被引用文献数
- 7
Genetic algorithms (GAs) are useful since they can find near optimal solutions for combinatorial optimization problems quickly. Although there are many mobile/home applications of GAs such as navigation systems, QoS routing and video encoding systems, it was difficult to apply GAs to those applications due to low computational power of mobile/home appliances. In this paper, we propose a technique to flexibly implement genetic algorithms for various problems on FPGAs. For the purpose, we propose a basic architecture which consists of several modules for GA operations to compose a GA pipeline, and a parallel architecture consisting of multiple concurrent pipelines. The proposed architectures are simple enough to be implemented on FPGAs, applicable to various problems, and easy to estimate the size of the resulting circuit. We also propose a model for predicting the size of resulting circuit from given parameters consisting of the problem size, the number of concurrent pipelines and the number of candidate solutions for GA. Based on the proposed method, we have implemented a tool to facilitate GA circuit design and development. This tool allows designers to find appropriate parameter values so that the resulting circuit can be accommodated in the target FPGA device, and to automatically obtain RTL VHDL description. Through experiments using Knapsack Problem and TSP, we show that the FPGA circuits synthesized based on the proposed method run much faster and consume much lower power than software implementation on a PC and that our model can predict the size of the resulting circuit accurately enough.
1 0 0 0 OA Geostatistical Motion Interpolation
- 著者
- 向井 智彦 栗山 繁
- 出版者
- ACM
- 雑誌
- Proceedings of ACM SIGGRAPH 2005 (ACM Transactions on Graphics Vol.24 Issue 3, July 2005)
- 巻号頁・発行日
- vol.24, no.3, pp.1062-1070, 2005-07
- 被引用文献数
- 111
A common motion interpolation technique for realistic human animationis to blend similar motion samples with weighting functionswhose parameters are embedded in an abstract space. Existingmethods, however, are insensitive to statistical properties, suchas correlations between motions. In addition, they lack the capabilityto quantitatively evaluate the reliability of synthesized motions.This paper proposes a method that treats motion interpolationsas statistical predictions of missing data in an arbitrarily definableparametric space. A practical technique of geostatistics, calleduniversal kriging, is then introduced for statistically estimating thecorrelations between the dissimilarity of motions and the distancein the parametric space. Our method statistically optimizes interpolationkernels for given parameters at each frame, using a posedistance metric to efficiently analyze the correlation. Motions areaccurately predicted for the spatial constraints represented in theparametric space, and they therefore have few undesirable artifacts,if any. This property alleviates the problem of spatial inconsistencies,such as foot-sliding, that are associated with many existingmethods. Moreover, numerical estimates for the reliability of predictionsenable motions to be adaptively sampled. Since the interpolationkernels are computed with a linear system in real-time,motions can be interactively edited using various spatial controls.