Abstract | ||
---|---|---|
The main contribution of this paper is to present an implementation that performs the exhaustive search to verify the Collatz conjecture using a GPU. Consider the following operation on an arbitrary positive number: if the number is even, divide it by two, and if the number is odd, triple it and add one. The Collatz conjecture asserts that, starting from any positive number m, repeated iteration of the operations eventually produces the value 1. We have implemented it on NVIDIA GeForce GTX TITAN and evaluated the performance. The experimental results show that, our GPU implementation can verify 5.01x10(11) 64-bit numbers per second, while the CPU implementation on Intel Xeon X7460 can verify 1.80 x 10(9) 64-bit numbers per second. Thus, our implementation on the GPU attains a speed-up factor of 278 over the single CPU implementation. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1007/978-3-319-11197-1_37 | ALGORITHMS AND ARCHITECTURES FOR PARALLEL PROCESSING, ICA3PP 2014, PT I |
Keywords | Field | DocType |
Collatz conjecture,GPGPU,Parallel processing,Exhaustive verification | Central processing unit,Monad (category theory),Brute-force search,Computer science,Parallel processing,Parallel computing,General-purpose computing on graphics processing units,Xeon,Collatz conjecture | Conference |
Volume | ISSN | Citations |
8630 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 11 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Takumi Honda | 1 | 4 | 3.22 |
Yasuaki Ito | 2 | 511 | 60.47 |
Koji Nakano | 3 | 1165 | 118.13 |