menu

Month: June 2018

Posted on by Arnon Erba in How-To Guides

The Fibonacci sequence (or series) is a classic example of a problem that can be solved by using recursion. As such, it’s often used to teach the concept of recursion in introductory programming courses. In this post, I’m going to explain how to write a simple recursive Fibonacci sequence calculator in C++ and how to optimize it so that it is capable of computing large Fibonacci numbers more efficiently.

Some Background: What is Recursion?

If you’re already familiar with the concept of recursion, you’re welcome to skip to the next section, where I’ll jump right into the code. Otherwise, you may want to review this section before continuing.

An Informal Definition

Put most simply, a recursive problem is one that is defined in terms of itself. In computer science, recursive procedures (functions) are used to break these kinds of problems down into simpler, easier-to-solve versions of themselves. Recursive functions, like the problems they solve, are also defined in terms of themselves.

Recursion in Code

In practice, this means a recursively defined function must call itself when it runs. To prevent an infinite loop, a correctly written recursive function will stop calling itself once it reaches a base case, which is a problem it can solve without having to call itself again. This is the idea behind recursion: A complex problem is eventually reduced to an easy-to-solve base case with a known solution. Recursive functions achieve this goal by re-using the same logic with different parameters every time the function is recursively called.

Recursion and the Fibonacci Sequence

With this in mind, it’s easy to see why the Fibonacci sequence is a good example of recursion. In the Fibonacci sequence, each number is recursively defined as the sum of the two previous numbers. For example, to find the fifth Fibonacci number, you first have to find the third and fourth numbers. However, you can’t find the fourth number without finding the second and third numbers, and so on. In fact, the whole sequence is constructed from the first two numbers, 0 and 1, which are the base cases. Some recursive problems only have one base case, but the Fibonacci sequence has two.

The Simple Function (And Why It’s So Slow)

All of this can be expressed more clearly with code:

 1 int fibonacci(int n) {
 2     if (n == 0) {
 3         return 0;
 4     } else if (n == 1) {
 5         return 1;
 6     } else {
 7         return fibonacci(n-1) + fibonacci(n-2);
 8     }
 9 }

This basic fibonacci function takes a single integer n as a parameter. This integer is the index value of the desired Fibonacci number. The first two if statements (lines 2 and 4) are simple: If the 0th Fibonacci number is requested, return 0. If the 1st Fibonacci number is requested, return 1.

However, if anything beyond the 1st Fibonacci number is requested, the function jumps to the statement in the last else block (line 7):

return fibonacci(n-1) + fibonacci(n-2);

In this case, the function will first compute the previous two values of the sequence, and then add them together and return the answer. This is because the value of fibonacci(2) depends on the values of fibonacci(1) and fibonacci(0), and so on.

This quickly becomes complex. Calling fibonacci(5) results in calls to fibonacci(4) and fibonacci(3). However, calling fibonacci(4) results in a second call to fibonacci(3), since we need to know the value of the 3rd number in the sequence before we can find the value of the 4th. Likewise, both calls to fibonacci(3) will result in duplicate calls to fibonacci(2) (and eventually fibonacci(1) and fibonacci(0)).

Re-computing values we’ve already calculated is a big performance drain, and it only gets worse as we go farther into the sequence. Wouldn’t it be great if we could store the value of fibonacci(3) somewhere so we didn’t have to re-compute it later?

The Optimized Function

 1 unsigned long fibonacci(unsigned long n) {
 2         static std::vector<unsigned long> fibovector = {0, 1};
 3         unsigned long temp;
 4         if (n < fibovector.size()) {
 5                 return fibovector[n]; 
 6         } else {
 7                 temp = fibonacci(n-1) + fibonacci(n-2);
 8                 fibovector.push_back(temp);
 9                 return temp;
10         } 
11 }               

In this optimized version of the fibonacci function, I’ve added a vector (called fibovector) that caches the computed values. I’ve also changed the base case: The function no longer checks to see if the requested value is 0 or 1 but instead checks to see if the value is cached in the vector (line 4). If the requested value is already stored in the vector, the function uses the cached value and skips having to re-compute it. If it’s not already cached, the function recursively computes it (line 7) and then adds it to the vector for later use.

The Vector

There’s a few important points worth noting regarding the vector. The vector is declared with the static keyword so that its contents can persist between function calls. To get the program started, the vector is “preloaded” with the first two values in the Fibonacci sequence, 0 and 1. These are the initial base cases for the function.

Because the vector gets populated in order, there’s an easy way to check if the desired value is already cached or not. Since the index values of the numbers in the vector correspond to the actual index values of the numbers in the Fibonacci sequence, you can simply compare the desired index value with the size of the vector. If the requested index value is less than the size of the vector (line 4), the function has already cached that value. It’s important to keep in mind that this works because the largest index value in a vector is always one less than the total number of elements it contains (the size) since index values start at 0.

Why unsigned long?

Fibonacci numbers get very large very quickly, and due to the nature of how computers store numerical data it’s easy to overflow your chosen data type before getting very far. There’s a section about integer overflow at the end of this article about email servers, but the bottom line is that the 46th number in the Fibonacci sequence is the largest Fibonacci number that can be stored in a 32-bit integer. With unsigned long as the data type, we’re able to store up to the 93rd Fibonacci number before overflowing that data type as well. To keep the function simple, I’ve opted to use native C++ data types instead of writing or importing a custom “big integer” class that would allow for the storage of even larger Fibonacci numbers.

Checking Your Work

To test if your program is working correctly, you can compare its output to the list of the first 2000 Fibonacci numbers published by the On-Line Encyclopedia of Integer Sequences (OEIS).

Then, try timing each program and comparing how long they both take to reach the 46th Fibonacci number. The results might surprise you.

Posted on by Arnon Erba in News

Messages in iCloud, Apple’s hotly anticipated cloud-syncing feature for the Messages app, has arrived on macOS a few days after debuting on iPhone and iPad in iOS 11.4. Messages in iCloud is an aptly named new iCloud feature that allows iMessages and regular SMS messages to live in iCloud rather than be stored locally per-device.

On iPhone, Messages in iCloud is available in iCloud Settings as another small toggle switch and requires two-factor authentication to be active before it can be enabled. Enabling Messages in iCloud can free up space on your device, streamline the process of deleting messages across all your Apple devices, and make it easy to sync your text message history to a new iPhone, iPad, or Mac. However, you may need to upgrade your iCloud storage plan if you like to keep a large amount of old messages and attachments, since iCloud’s 5 GB free tier may not be sufficient for heavy users.

The macOS High Sierra 10.13.5 update brings these new features to the Mac as well as the usual round of security updates. However, rather than being located in the iCloud section of System Preferences, the setting for Messages for iCloud on Mac is located in the Messages app settings pane. Refer to Apple’s official support page for instructions on enabling Messages in iCloud for both Mac and iPhone.

Posted on by Arnon Erba in News

Rufus, the lightweight and portable program for creating bootable USB drives on Windows, has reached version 3.0. Rufus, primarily developed by Pete Batard of Akeo Consulting, remains one of the easiest and most powerful ways to create bootable USB drives on Windows. Its simple user interface is easy to navigate, and Rufus is able to create bootable USB drives from a wide variety of Windows and Linux ISO files. It supports MBR and GPT partitioning and can even be used to create bootable DOS disks.

Released on May 29th, the version 3.0 of Rufus brings a new user interface and many other changes (pulled directly from the changelog):

  • UI redesign to follow the flow of user operations (with thanks to Fahad Al-Riyami for the concept)
  • Drop Windows XP and Windows Vista platform support
  • Switch all downloads to SSL and use https://rufus.ie as the new base URL
  • Add ARM64 support for UEFI:NTFS
  • Fix delays when querying floppy drives during device enumeration
  • Improve support of efi.img files on Linux ISOs
  • Improve support for non-ISO9660 compliant openSUSE Leap ISOs
  • Improve translation support and remove manual positioning
  • Internal fixes and improvements

You can grab a copy of Rufus at its new website, https://rufus.ie/. Rufus can be run directly from the downloaded .exe file — no installation is necessary.