gonium.net » projecteuler

Code Kata: Project Euler #7, Finding Primes

md — Mon, 08 Sep 2008 08:08:52 +0000

I resumed my code katas – this time, I’m using Erlang to solve the problem:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10001st prime number?

It seems to be clever to have a prime number generator for Project Euler anyway. My implementation is based on the Sieve of Erathosthenes and uses the Prime Number Theorem for an estimate on the size of the sieve. The code is pretty easy:

[viewcode]src=pe7.erl [/viewcode]

HTML code generated by vim-color-improved v.0.4.0.Download this code: pe7.erl

In the erathosthenes function, a list comprehension is used to purge all multiplies of the current Index value. My first attempt didn’t include the Index variable – I simply decreased the boundary. The disadvantage of this method is that it keeps the list of primes bigger over the runtime: Instead of removing the multiples of 2 at the very beginning, they get removed as the last multiples. The size of PurgedNumbers stays bigger, which leads to a runtime of 6.7 seconds. When I use the Index variable, the multiples of 2 get removed first which avoids copying them all the way. The runtime decreases to 1.2 seconds (on my Mac Mini).

Since all variables in Erlang are bound only once, I don’t know how to optimize this further. In C, I would use a bit array to further reduce the memory footprint. But: the Erlang code is much easier to read and write. I think Erlang is just not made for low memory bandwidth requirements :-)

The picture above is an representation of the Ulam spiral, CCed on flickr by no_typographic_man.

Code Kata: Project Euler #4, Finding Palindromes

md — Sat, 19 Apr 2008 17:57:51 +0000

This weekend, I solved problem 4 of Project Euler:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99. Find the largest palindrome made from the product of two 3-digit numbers.

I designed a routine that checks whether a given number is a palindrome. This routine is then used inside two loops iterating from 999 downto 0. The first hit is the largest palindrome. The core functionality is here: bool Problem4::isPalindrome(long number) { bool retval = false; std::vector digits; while (number > 0) { long lastdigit = number % 10; digits.push_back(lastdigit); number = number / 10; } reverse(digits.begin(), digits.end()); std::vector::iterator front = digits.begin(); std::vector::iterator back = –digits.end(); retval = false; while (! (front >= back)) { if ((*front) == (*back)) { retval = true; // move iterators to the next digits front++; back–; } else { // cannot be a palindrome, back out retval = false; break; } } return retval; } This implementation reverses the vector. By using the front and back operators in the other direction, this could be left out. But it serves its purpose for now. You can get the full sourcecode from the download page. Please note that the code in the tarball calculates *all* palindromes smaller than 1000000. The picture was CCed on flickr by TisseurDeToile -[mangerait bien un petit chat]-.

Code Kata: Project Euler #3 + CMake distributions

md — Sun, 13 Apr 2008 17:26:31 +0000

This weekend, I tackled the Project Euler problem #3:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

Pretty straightforward: Just test and recurse. The core of the implementation is here: std::set Problem3::_findFactor(ull number, ull startFactor ) { std::set retval; for( ull factor = startFactor; factor < = number; factor += 1) { if (number % factor == 0) { retval.insert(factor); std::set recursive = _findFactor(number / factor, factor); retval.insert(recursive.begin(), recursive.end()); break; } } return retval; } Please note that "ull" is a typedef for unsigned long long. For increasing integers, I test whether it is a factor of the given number. If yes, add it to the set of result values and descent one level into the recursion. In addition, I extended my CMake infrastructure: You can now roll distributions based on CPack. In my oppinion you should start having a distribution target as early as possible within your development cycle. This way, you're always ready to ship/deploy your software, i.e. for beta testers. Ship early, ship often... And of course automatically. When I type "make release", CMake builds the software in release mode ("-O3") and rolls several distributions. This is the output: Run CPack packaging tool... CPack: Create package using PackageMaker CPack: Install projects CPack: - Run preinstall target for: PROBLEM3 CPack: - Install project: PROBLEM3 CPack: Compress package Building in backwards compatible mode Preverifying PROBLEM3 Preverifying PROBLEM3 Checking bundle identifiers Checking package configuration Checking contents Loading contents Checking for ZeroLink Building PROBLEM3 Building PROBLEM3 Creating shell Copying scripts Writing description Writing bundle versions Copying resources Creating Requirements Creating permission hierarchy Creating Bill-of-Materials file Archiving files Creating Info.plist CPack: Finalize package CPack: Package /Users/gonium/Projects/project-euler/trunk/problem3/build/PROBLEM3-0.2.0-Darwin.dmg generated. CPack: Create package using STGZ CPack: Install projects CPack: - Run preinstall target for: PROBLEM3 CPack: - Install project: PROBLEM3 CPack: Compress package CPack: Finalize package CPack: Package /Users/gonium/Projects/project-euler/trunk/problem3/build/PROBLEM3-0.2.0-Darwin.sh generated. CPack: Create package using TGZ CPack: Install projects CPack: - Run preinstall target for: PROBLEM3 CPack: - Install project: PROBLEM3 CPack: Compress package CPack: Finalize package CPack: Package /Users/gonium/Projects/project-euler/trunk/problem3/build/PROBLEM3-0.2.0-Darwin.tar.gz generated. As you can see, a DMG image, a self-extracting shell installer and a tar.gz are built. The DMG contains all metadata for a nice MacOS installer - for Windows, a NSIS-based installer would have been created. CPack reuses the dependency information from my CMakeLists.txt files, so I don't have to maintain another place and avoid duplication. You simply add CPack to your toplevel CMakeLists.txt: # add some files to the installation target INSTALL(FILES README.txt COPYRIGHT.txt DESTINATION share/PROBLEM3/doc) # CPACK packaging INCLUDE(InstallRequiredSystemLibraries) SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY "Project Euler Problem 3") SET(CPACK_PACKAGE_VENDOR "Mathias Dalheimer") SET(CPACK_PACKAGE_DESCRIPTION_FILE "${CMAKE_CURRENT_SOURCE_DIR}/README.txt") SET(CPACK_RESOURCE_FILE_LICENSE"${CMAKE_CURRENT_SOURCE_DIR}/COPYRIGHT.txt") SET(CPACK_PACKAGE_VERSION_MAJOR ${V_MAJOR}) SET(CPACK_PACKAGE_VERSION_MINOR ${V_MINOR}) SET(CPACK_PACKAGE_VERSION_PATCH ${V_PATCH}) SET(CPACK_PACKAGE_INSTALL_DIRECTORY "CMake ${CMake_VERSION_MAJOR}.${CMake_VERSION_MINOR}") SET(CPACK_PACKAGE_EXECUTABLES "pe-problem3" "Solves Project Euler problem 3") INCLUDE(CPack) I choose to add the resulting binary in a subsequent CMakeLists.txt where the binary is compiled: INSTALL(PROGRAMS ${PROBLEM3_BINARY_DIR}/src/pe-problem3 DESTINATION bin) Pretty easy and maintainable :-) You can get the source package from the download page. Picture taken by 8#X and CCed on flickr.

Code Kata: Project Euler #2 with CMake

md — Sun, 06 Apr 2008 10:41:35 +0000

Recently, I started to use the autotools for building a project. But I am really unhappy with it – although a lot of special cases can be handled by the toolchain, it is extremely complex to use and prone to user errors. Auto-Hell, I guess… So, this code kata is dedicated to the alternative CMake package. I have written a simple C++ program to solve problem #2 of Project Euler. The autotools toolchain attempts to solve two problems:

Configuration: On the compile system, where do libraries etc live?
Build: How is the software built?

The configuration step is the famous “./configure” everyone comes across when installing software on unix systems. The autotools employ a mix of SH, Commandline-Magic, M4 and fairy dust to handle this. It generates Makefiles so that one can use make to build the software. Additional make targets such as make dist or make install help during deployment of the software. The problem lies in the complexity of the toolchain: in the mixture of tools that build upon other tools, M4 macros and shell scripts, it is extremely difficult to find errors. If your buildsystem is as complex as the software you’re developing, something is wrong. In addition, the autotools are not really portable to other systems such as windows, at least not straightforward. For these reasons the KDE project moved away from the autotools. They evaluated many different buildsystems and choose CMake. I played a little bit with it and I am quite happy. Of course, one needs to asses such a system in a bigger scenario in order to judge it, but at a first glance it really does the trick. There are plenty of articles around – to get you started I suggest Tanner Lovelace’s introduction. In addition, the following resources are helpful:

Mal ausspannen (German, Linux-Magazin 02/2007)
Cross-Platform Software Development Using CMake (Linux Magazine)
The KDE subversion provides also a nice collection of CMake scripts which might give you some ideas.
The CMake manpage, highly readable reference.

But now, on to building the software. My project directory has the following structure:


.
|-- CMakeLists.txt
|-- Makefile
|-- Modules/
|   `-- FindLog4Cxx.cmake
|-- common/
|   |-- CMakeLists.txt
|   |-- common.h
|   `-- config.h.in
|-- problem2/
|   |-- CMakeLists.txt
|   |-- problem2.cpp
|   `-- problem2.hpp
|-- src/
|   |-- CMakeLists.txt
|   `-- main.cpp
`-- timer/
    |-- CMakeLists.txt
    |-- clock.cpp
    `-- clock.hpp

In order to keep things interesting I moved the code for solving the Project Euler task to the problem2 library. There’s a common library that defines project-wide settings. In timer, there’s a little routine for measuring execution times. The main routine lives in the src directory. The CMakeList.txt files define the tasks to be done by CMake – this can be seen as the equivalent to the Makefile.am files. But you can define much more stuff in there. Here’s the top-level CMakeList.txt file: # Define project name and version numbers. project (PROBLEM2) set(V_MAJOR 0) set(V_MINOR 1) set(V_PATCH 1) # add a path where some libraries might be stored set(CMAKE_INCLUDE_PATH ${CMAKE_INCLUDE_PATH} /opt/local/include) set(CMAKE_LIBRARY_PATH ${CMAKE_LIBRARY_PATH} /opt/local/lib) # look for the external log4cxx library set(LOG4CXX_FIND_REQUIRED true) include(modules/FindLog4Cxx.cmake) OPTION(ENABLE_LOGGING “Build the project with logging enabled” ON) if(ENABLE_LOGGING) message(STATUS “Building with logging enabled.”) endif(ENABLE_LOGGING) # Make sure all subdirectories include correctly include_directories(${CMAKE_CURRENT_BINARY_DIR}) # process the subdirectories in the right order. add_subdirectory (common) add_subdirectory (problem2) add_subdirectory (timer) add_subdirectory (src) I wanted to create a template which can be used as a staring point for later projects. I tend to use the Apache Log4CXX library for producing log messages. In order to discover the include and library directories, I created a CMake module – the equivalent of an Autotools M4 macro. CMake comes with lots of example modules for detecting libraries. But it is also easy to write your own modules. In contrast to the Autotools, all modules are specified in CMake’s own language. Typically, you want to be able to deactivate all logging during the build process, e.g. prior to shipping the release version. You can define Options which can be set with various GUI tools. On Unix platforms, a curses-based GUI allows you to select your options. In this example, the ENABLE_LOGGING variable gets processed by the CMakeList.txt in the common directory: set(lib_src config.h common.h) # create autotools-like config.h file from template. config.h will be # generated in the build directory – add a global include so that we can # find the config.h. In addition, copy the header-only common.h file to # the build tree. configure_file(config.h.in ${CMAKE_CURRENT_BINARY_DIR}/config.h) configure_file(common.h ${CMAKE_CURRENT_BINARY_DIR}/common.h COPYONLY) This generates a config.h file and copies it to the right location in the build directory. The config.h.in file defines some variables that will be replaced based on the values determined by CMake during the build step. Altogether, I like CMake. It is as powerful as the Autotools but without the quirks of the latter. You can download the example from the download page. There are other tools in the CMake package, namely CTest for testing software – but I’ll save this for another sunday ;-) Finally, the Project Euler task is to solve the following problem:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … Find the sum of all the even-valued terms in the sequence which do not exceed four million.

The code to solve this problem is pretty easy: unsigned long long sum, tmp = 1; current = 2; previous = 1; while (current < _max) { if (current % 2 == 0) sum += current; tmp=current; current = current + previous; previous = tmp; } The heaven or hell picture was CC'ed by karmablue.

Code Kata: Project Euler #1

md — Sun, 30 Mar 2008 18:13:39 +0000

Following the example of doing code katas, I spend my sunday morning thinking about integer performance in C++. Project Euler provides a nice collection of mathematical problems. As it turns out, some of my assumptions on C++ were totally wrong :-) The problem to solve is the following:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

Quite easy. A straightforward, naive implementation uses the modulo operator to filter the integers up to the maximum: unsigned long method1(const unsigned long max) { unsigned long sum=0; for (unsigned long i=0; i torrent; for (unsigned long i=0; i::iterator it; for (it=torrent.begin(); it != torrent.end(); it++) { sum += (*it); } return sum; } Turns out this code is way slower than the first method: 0.34318700 seconds, more than two orders of magnitudes. Thinking of it, it is easy to see why: while the first method can completely run within the CPU, the second code suffers from accessing the main memory. I didn’t assess the overhead imposed by the std::set (no working gprof around). As it turns out, the C++ modulo operator uses the assembler div operation – so the compiler can optimize the code, keep all variables in registers, and use a fast operation. However, the above code is not quite nice as it allows integer overflows for the sum variable. The GNU MP Bignum Library (GMP) provides big integers. Method 3 uses them for the sum variable: mpz_class method3(const unsigned long max) { mpz_class sum(0); for (unsigned long i=0; i Project Euler – Problem 1 Method 1: 1404932684 -> 0.00952700 s. Method 2: 1404932684 -> 0.34736500 s. Method 3: 1404932684 -> 0.01851300 s. Method 4: 1404932684 -> 0.57744300 s. Method 5: 1404932684 -> 0.00094000 s. Creating comparison of methods 4 and 5 100 2318(0.00006400) 2318(0.00001400) 10000 23331668(0.00579500) 23331668(0.00043900) 1000000 233333166668(0.57718100) 233333166668(0.05124100) 100000000 2333333316666668(57.69583200) 2333333316666668(5.84172500) You can download the code from the download page.