Javascript must be enabled for the correct page display

Calculating the 8th Dedekind Number

Zijlstra, A.T. (2013) Calculating the 8th Dedekind Number. Bachelor's Thesis, Computing Science.

[img]
Preview
Text
ThesisDedekind-ArjenZijlstra.pdf - Published Version

Download (557kB) | Preview
[img] Text
AkkoordRenardeldeLavalette3.pdf - Other
Restricted to Registered users only

Download (32kB)

Abstract

Dedekind Numbers (dn | n = 0, 1, 2, . . . ) are a rapidly growing sequence of integers: 2, 3, 6, 20, 168, 7 581, 7 828 354, 2 414 682 040 998, 56 130 437 228 687 557 907 788. dn counts the number of monotone subsets of a power set on n elements. A subset is monotone when there are no elements in the power set, that contain an element of the subset, and are not an element of the subset themself. d8 is the biggest computed Dedekind number so far. It was first computed in 1991 by Doug Wiedemann. This took him 200 hours on a Cray-2. In this thesis, Wiedemanns strategy is explained, implemented in C/C++ and parallelised using the Message Passing Interface. The goal is to gather knowledge about the theory and to check the calculation. Another intention in this thesis is to speedup the calculation as much as possible. The first goal is accomplished and the result of dn is exactly the same as Wiedemanns result. The shortest time to calculate d8 is about 30 minutes. Other results are discussed in this thesis. Furthermore, some things are said about scaling this calculation to d9.

Item Type: Thesis (Bachelor's Thesis)
Degree programme: Computing Science
Thesis type: Bachelor's Thesis
Language: English
Date Deposited: 15 Feb 2018 07:53
Last Modified: 15 Feb 2018 07:53
URI: https://fse.studenttheses.ub.rug.nl/id/eprint/11075

Actions (login required)

View Item View Item