Archive for August, 2007

An unbounded Sieve of Eratosthenes

August 30, 2007

This small program is a simplified implementation of an approach described in an old post by Alex Martelli on it.comp.lang.c++. There he demonstrated a use of streams, which are a metaphor for possibly infinite sequences whose elements are retrieved one at a time.

For each prime number we store in a vector a pair consisting of the prime itself and a multiple, initialized to the prime number again. We compare each candidate with each multiple; if the multiple is smaller we increment it by the corresponding prime. Then if the candidate is equal to the multiple we discard it as it’s obviously a multiple of the current prime, otherwise we move on to the next prime; when there isn’t any prime left we have found another one and we append it to the vector.

Thus this program performs the same operations as the traditional algorithm, but through a form of diagonalization it removes the original’s need for an upper bound. Rather neat, isn’t it? Here’s the code:

#include <cmath>
#include <iostream>
#include <limits>
#include <ostream>
#include <utility>
#include <vector>

typedef long long number;
typedef std::pair<number, number> prime;
typedef std::vector<prime> prime_vector;

int main() {
    prime_vector primes;
    number candidate = 2;
    for ( ; ; ) {
        prime_vector::iterator i = primes.begin();
        for ( ; i != primes.end(); ++i ) {
            while ( candidate > i->second )
                i->second += i->first;
            if ( candidate == i->second )
                break;
        }
        if ( i == primes.end() ) {
            std::cout << candidate << 'n';
            primes.push_back(prime(candidate, candidate));
        }
        ++candidate;
    }
}

As you probably noticed I’m using long long to represent my primes, so there’s an obvious hard limit at std::numeric_limits<long long>::max() (yes, I’m aware that long long isn’t in the standard yet); by using an arbitrary precision integer implementation the only limit is in the underlying hardware.In case you’re wondering why I used std::vector for an ever growing data structure, read what Alex Stepanov and Bjarne Stroustrup have to say about it. I didn’t make any benchmark, but for such small elements that are only appended at the back std::vector is likely to perform better than any other container. What I did notice is that vector reallocations don’t appear to cause any perceptible slowdown in the output flow.

Advertisements

Young Americans – David Bowie (1975)

August 22, 2007

In Young Americans David Bowie is caught in between Ziggy Stardust and his Berlin period, which would peak with the “Heroes” album. Here instead is a rather commercial album, heavily influenced by Gamble & Huff‘s “Philly Sound“, which was then evolving soul into disco.

To be honest there’s more to Young Americans than disco, from echoes of early Roxy Music (I wonder who influenced whom?) to John Lennon, who is present as performer and co-author of “Fame“, the album’s most notable and successful song. Lennon is also paid homage to by the inclusion of a rather anonymous cover of the Beatles‘ “Across the Universe“.

All in all not a bad record, but certainly not one of Bowie’s best. Even among his forays into dance music I find Let’s Dance to be a better achievement.

bcbboost & Boost 1.34.1

August 17, 2007

By the way, bcbboost‘s current release, 1.34.0-5.9.0-0.1 , works also with the latest Boost release, 1.34.1 ; if you have installed C++ Builder 2007 Update 2 you need to apply the fix described in this post.

English Settlement – XTC (1982)

August 17, 2007

XTC‘s uncommonly original style can be at the same time an asset and a liability. While it makes the band’s work immediately recognizable, it may make it difficult to identify original elements in an album such as English Settlement. This is not to say that it’s too uniform; influences range from reggae to a probably unintentional reminiscence of Adam & the Ants in a song or two.

However just about every one of the album’s songs carries some of the XTC hallmarks, be it in a melodic passage or in some arrangement detail, and English Settlement will immediately sound familiar to anybody who is acquainted with other XTC records.

I find it hard to identify any of English Settlement‘s songs as my favourite; in my opinion they are not as distinct and powerful as, for instance, those from Black Sea. On the other hand I have to admit that “Senses Working Overtime“, the album’s most successful single, stuck to my mind and I keep finding myself humming it.

XTC is definitely a band worth exploring, but this is not the album I would start with, better alternatives being Black Sea and Skylarking. Still, if you already know and like XTC, you won’t be disappointed by this album.

bcbboost & CB2007 Update2

August 14, 2007

If you’re using bcbboost with C++Builder 2007 and you intend to install Update 2 you need to edit boost\config\compiler\borland.hpp and change all occurencies of 0x590 into 0x591 .

I’m investigating other changes that may be required and hope to come out with a new version in a short time.

Many thanks to Andrew Bond for the heads up.