How to calculate Fibonacci sequence for large numbers

Firstly, here’s a basic implementation of Fibonacci using recursion:

    using Numbers = std::vector<unsigned long long>;
    Numbers cache( 5000, 0 );
    
    unsigned long long fibonacciRecursiveImpl( size_t n, Numbers& cache )
    {
        if ( n == 0 ) return 0ULL;
        if ( n == 1 ) return 1ULL;
        
        if ( cache[n] != 0 ) return cache[n];
        
        auto num = fibonacciRecursiveImpl( n-1, cache ) + fibonacciRecursiveImpl( n-2, cache );
        cache[n] = num;
        return num;
    }
    
    unsigned long long fibonacciRecursive( size_t n )
    {
        return fibonacciRecursiveImpl( n, cache );
    }

This works fine for small numbers (e.g. up to 20). I was interested to know where it would fail first, data overflow (due to the size of the numbers involved) or stack overflow (due to the recursive approach)? I implemented this on a MacBook using Apple LLVM 7.0 and the C++14 flag, but no other special switches set. It turns out that the overflow problems kick in for n > 93, but there was no sign of stack overflows, even up for n ~ 2000.

Even if there was a stack overflow, you could still use recursion, but change to a tail recursive solution (many C++ compilers will eliminate tail calls, essentially turning this into an iterative solution):

    // Implement recursive approach with possibility for "Tail call elimination",
    // avoids any concerns about stack overflow
    unsigned long long fibonacciTailRecursiveImpl( size_t n, unsigned long long prevprev, unsigned long long prev )
    {
        if ( n == 0 ) return prevprev;
        if ( n == 1 ) return prev;
        
        return fibonacciTailRecursiveImpl( n-1, prev, prevprev + prev );
    }
    
    unsigned long long fibonacciTailRecursive( size_t n )
    {
        return fibonacciTailRecursiveImpl( n, 0, 1 );
    }

So how to avoid the data overflow for Fibonacci over n = 93? At that point, you need to introduce a large number type with its own internal representation of large integers and suitable operator+ implementation. I used one such, BigNum, for this HackerRank challenge. The implementation stores the large integer as a string, with each character taking values in the range [0,100]. This reduces the number of digit-by-digit additions by a factor of 10 compared to a straight decimal representation.

I replaced unsigned long long with BigNum in the recursive solution above and verified that it returns the correct answers for n ~ 2000, with no stack overflows. Here, I’ll show it in an iterative solution (if you don’t want to keep a cache around, this is highly memory efficient, because you only need to store the previous two values):

    BigNum fibonacciBigNumIterativeImpl( size_t n )
    {
        BigNum prevprev(0);
        BigNum prev(1);
        
        if ( n == 0 ) return prevprev;
        if ( n == 1 ) return prev;
        
        BigNum num(0);
        for ( size_t i = 2; i <= n; ++i )
        {
            num = prevprev + prev;
            prevprev = prev;
            prev = num;
        }
        return num;
    }
    
    std::string fibonacciBigNumIterative( size_t n )
    {
        auto result = fibonacciBigNumIterativeImpl( n );
        return result.toString();
    }

Leave a comment

Filed under C++, C++ Code, Programming

How to approximate Pi using C++11 random number generators

The other day I learnt a method to approximate Pi if you have a random number generator for the range [0,1]. Consider a unit circle centred on (0,0) in 2D coordinates. Then one quarter of the area of the circle lies in the quadrant formed by x and y in range [0,1]. The area of the quarter circle is Pi * R^2/4, and here, R = 1 (it’s a unit circle). So we can generate a bunch of random 2D points, calculate the ratio between those that fall inside the circle and those in the outer unit square, then multiply by 4 to approximate Pi.
approximatepi
That sounds like a neat test case for the C++11 random number generators, so I thought I’d try it out. It turns out to work pretty well, if you’re prepared to use a sufficiently large number of random values.

    double approxPi( size_t points )
    {
        std::random_device rand_device;
        
        // mersenne_twister_engine is a random number engine 
        // based on Mersenne Twister algorithm.
        std::mt19937 generator( rand_device() );
        
        // We want random values uniformly distributed in [0,1]
        std::uniform_real_distribution<> unif_zero_one(0, 1);
        
        size_t points_inside{0};
        
        for (int i = 0; i < points; ++i )
        {
            auto x = unif_zero_one( generator );
            auto y = unif_zero_one( generator );
            double d = std::sqrt( x*x + y*y );
            
            if ( d <= 1.0 )
                ++points_inside;
        }
                
        return 4.0 * (static_cast<double>(points_inside) / static_cast<double>(points));
    }
}

void testApproximatePi()
{
    SHOULD_BE_APPROX( 3.14159, 0.3, approxPi( 100 ) );
    SHOULD_BE_APPROX( 3.14159, 0.1, approxPi( 1000 ) );
    SHOULD_BE_APPROX( 3.14159, 0.01, approxPi( 100000 ) );
    SHOULD_BE_APPROX( 3.14159, 0.001, approxPi( 10000000 ) );
    
    std::cout << "\n";
}

A typical run gives reasonable approximations once you get over 100,000 points:
screen-shot-2016-09-16-at-13-30-26

Leave a comment

Filed under C++, C++ Code, Programming

How to learn Python

Having learnt enough Swift to write a neat watch face app for Apple Watch this summer, I thought I’d turn my attention to learning some Python.

Firstly, I wanted a way to edit Python commands in a decent editor and run them. It appears that Xcode doesn’t support this out of the box, but this handy StackOverflow question gives the details on how to set it up.

Secondly, I wanted a series of challenges/tutorials to walk through the basic syntax of Python. HackerRank.com is very good for this sort of thing and has a decent set of exercises to work through.

My first bug was very revealing about the differences between Python and strongly-typed languages like F# and C++:

N = int(raw_input().strip())
if (n > 10):
    print( "big" )
elif ( N < 0 ):
    print( "negative" )
else:
    print( "normal" )

The Python Interpreter doesn’t give an error because of the typo “n > 10” instead of “N > 10” – it just carries on regardless!

Finally, Python Software Foundation seems like a good reference site with lots of examples.

2 Comments

Filed under Programming, Python

Solving large puzzles on HackerRank

I’ve solved quite a few puzzles on HackerRank, HackerRankbut this one had me stumped. The actual algorithm didn’t seem too hard, although there is a bit of a trick to it. The problem I had was extending the solution afterwards to handle large numbers. Usually, it’s enough to use ‘long long’ throughout, but it still wasn’t passing all the test cases.

In the end, I narrowed down the problem to the following code:

  long long maximiseScore( int N )
  {
    std::vector<long long> health( N, 0 );
    for ( size_t i = 0; i < N; ++i ) std::cin >> health[i];
    long long sum = std::accumulate( health.begin(), health.end(), 0 );
    // ...
  }

In case you didn’t spot it, the bug is that std::accumulate has inferred the type of the init parameter from 0 (zero), which is an int. So the sum is calculated as an int, then assigned into our long long variable. The solution is to cast the init to a long long (either using ‘LL’ or static_cast).

    long long sum = std::accumulate( health.begin(), health.end(), 0LL );

Leave a comment

Filed under C++, C++ Code, Programming

Video: Writing good C++14 with Guideline Support Library (GSL), Bjarne Stroustrup

ISOCpp.org re-advertised the Channel9 videos from last year’s CppCon, so I thought I’d watch a couple. I started with Writing Good C++14. The slides are available here.

Stroustrup’s aim is to provide guidelines for writing simpler, cleaner C++ – then use this to spread the word of how Modern C++ can be so much better than archaic C++ idioms that have been superseded by new techniques.

But how to do it, because coding guidelines are frequently ignored or wrong. Telling what not to do is not enough – you need to do more than prohibit use of certain language features. Instead, build a set of what you should do – comprehensive, browsable, teachable guidelines.

High-level rules: philosophical approach to coding. And low-level rules: more specific, tangible rules that can be checked using tools (at least in the future) – each rule must have a rationale and an example as well as alternatives/exceptions/enforcement. And Guideline Support Library (GSL) for useful abstractions over messy/dangerous features – e.g. not_null, owner, array_view.

Result could be: productivity doubled (like a great programmer working on a modern codebase); less debugging by eliminating whole classes of errors – resource leaks, dangling pointers.

For example, dealing with range checking:

// Before
void f( int* p, int n ) // this is Stroustrup's least favourite interface!
{
    p[7] = 9;
    for ( int i = 0; i < n; ++i ) p[i] = 7;
}

// Guideline - better
void f( array_view<int> a)
{
    a[7] = 9; // checkable against a.size() e.g. in debug mode
    for (int x : a ) a = 7;
}

Example – dealing with null pointers:

// Before
void f( char* p )
{
    if ( p == nullptr ) // is it necessary to check every time?
    {
    }
}

// Guideline - better
void f( not_null<char*> p )
{
    // no longer needs to check, not_null<> cannot hold nullptr.
}

This looks pretty interesting – there’s a VS2015 plugin to run the GSL tools too. This featured in the follow-up presentation by Herb Sutter:
Screen Shot 2016-08-19 at 16.52.11

Leave a comment

Filed under C++, Programming, Video

How to draw text onto an image in Apple Watch App

Suppose you want to label an item in your WatchKit App. If you’re able to put a label widget onto the storyboard next to the item, that’s fine – but if you’re using Core Graphics to construct an overlay image, chances are you’ll need to draw the text onto the image too. My ultimate aim was to be able to draw the date on my Watch Face App.

It took some digging to find out how to do this. The obvious candidate was CoreGraphics.CGContextShowTextAtPoint, but that’s deprecated from WatchKit 2.0 onwards. Its replacement is the CoreText library, but “import CoreText” doesn’t find it.

CGContextShowTextAtPoint

Searching on StackOverflow met with little success, possibly because people’s solutions might work for iPhone Apps but don’t satisfy the restricted API available for WatchKit Apps. However, I found this gem which did work on the Apple Watch.

As a worked example, let’s take the Treasure Map App from an earlier post. It’s natural for a treasure map to indicate what’s buried at the cross. I’ve changed the method signature from the one on StackOverflow so that you specify the centre of the text block.

    func drawText( context : CGContext?, text : NSString, centreX : CGFloat, centreY : CGFloat )
    {
        let attributes = [
            NSFontAttributeName : UIFont.systemFontOfSize( 20 ),
            NSForegroundColorAttributeName : UIColor.blackColor()
        ]
        
        let textSize = text.sizeWithAttributes( attributes )
        
        text.drawInRect(
            CGRectMake( centreX - textSize.width / 2.0,
                        centreY - textSize.height / 2.0,
                        textSize.width,
                        textSize.height ),
            withAttributes : attributes )
    }    

Calling this from drawCross() in the Treasure Map App results in a neat label underneath the cross:

        drawText( context, text: "Gold", centreX: 100, centreY: 210 )

Screen Shot 2016-08-05 at 08.00.08

Using the same method, I updated my Watch Face App to draw the day and date onto this watch face:

Screen Shot 2016-08-07 at 21.28.23

See also: How to write a Watch Face App for Apple Watch and How to draw on top of an image in Apple WatchKit

Leave a comment

Filed under Programming, Swift

How to write a Watch Face App for Apple Watch

Having owned an Apple Watch for over a year, I’ve grown a little bored with the available watch faces. So I was very impressed with the new, special edition Hermes watch face. This is quite different to any of the other faces on the Apple Watch. Unfortunately, it’s only available to new purchasers who buy the brand new Hermes Apple Watch – starting at £1000.
HermesFace2

Having written my first Watch App recently, I thought I’d have a go at writing a Watch Face App. Apple WatchKit doesn’t officially support writing watch faces, so this would have to be an ordinary App that happens to display the time. There are plenty of custom faces you can use as wall-paper to create an attractive digital watch, but I wanted the analogue look.

The approach I took was:

  • Start with an image e.g. from the custom faces library
  • Look up how to get the current time in the WatchKit API
  • Find out how to draw graphics on top of an image
  • Work out the maths to draw the hands in the right place
  • Work out how to render proper watch hands

I already blogged about how to get the current time and how to draw graphics on top of an image. So if you followed along, you can replace your Treasure Map image with a watch face image and use the createContext(), drawLine() and applyContextToImage() methods to draw the hour and minute hands. In fact, by making the colour a parameter of drawLine(), you’ve got the method to draw the second hand too.

As for the maths to draw the hands in the right place, it’s trigonometry. Both sin and cos are available in WatchKit, so convert the hours/minutes into radians and calculate the end coordinate of your watch hand, treating the length of the hand as the hypotenuse of a right-angled triangle.

That leaves the trick of how to draw a proper watch hand given only the drawLine() and drawCircle() methods. This is the method I used:

WatchHand

In order to draw the white circle outline with solid black inner-circle, I used this method:

    func drawCircle( context : CGContext?, radius : CGFloat, centreX : CGFloat, centreY : CGFloat, colour : CGColor )
    {
        let diameter = radius * 2.0
        let rect = CGRect( x: centreX - radius, y : centreY - radius, width : diameter, height : diameter )
        
        CGContextSetFillColorWithColor( context, UIColor.blackColor().CGColor )
        CGContextFillEllipseInRect( context, rect )
        
        CGContextSetLineWidth( context, 2.0 )
        CGContextSetStrokeColorWithColor( context, colour )
        CGContextStrokeEllipseInRect( context, rect )
    }

There are a couple of limitations:

That said, I’m really happy with the results:

Watch Face App

This is actually one Watch App – I changed the Image to a Button so that I could iterate through different watch faces by tapping the watch. If you do this, call button.setBackgroundImage on the button instead of image.setImage.

See also: How to draw text onto an image and How to draw on top of an image.

2 Comments

Filed under Programming, Swift