Is there a more elegant syntax for these boolean expressions?

Question

I was just writing an improved linear version of a recursive Fibonacci algorithm, and realized that my boolean expressions look really bad and unreadable. Is there a cleaner way to do what I'm trying to do?

int fibonacci(int num) {

    if (num <= 1)
        return num;

    // starts looking ugly here

    int a = intExists(num-1);
    int b = intExists(num-2);

    bool aAndB = (a != -1 && b != -1);
    bool justA = (a != -1 && b == -1);
    bool justB = (a == -1 && b != -1);

    int number = 0;

    if (aAndB)
        number = (a + b);
    else if (justA)
        number = (a + fibonacci(num - 2));
    else if (justB)
        number = (fibonacci(num-1) + b);
    else
        number = (fibonacci(num - 1) + fibonacci(num - 2));

    map.push_back(Pair(num, number));

    return number;
}

Thanks

Answer 1

You could rewrite it to use conditional branching, like this:

int fibonacci(int num) {

    if (num <= 1)
        return num;

    int a = intExists(num-1);
    int b = intExists(num-2);

    const bool isA = (a != -1);   // change in the definition
    const bool isB = (b != -1);   // change in the definition

    int number = 0;

    if (isA && isB)
        number = (a + b);
    else if (isA)   // conditional branching
        number = (a + fibonacci(num - 2));
    else if (isB)   // conditional branching
        number = (fibonacci(num-1) + b);
    else
        number = (fibonacci(num - 1) + fibonacci(num - 2));

    map.push_back(Pair(num, number));

    return number;
}

Answer 2

A slightly drastic rewrite is to let an external function handle the lookup table.
That way you don't need to care about more than one value at a time.

This one uses map so I didn't have to write so much in order to test it, but it should be easy enough to adapt:

std::map<int, int> table;

int fibonacci(int num);

int value(int num)
{
    int result = table[num];
    if (!result)
    {
        result = fibonacci(num);
        table[num] = result;
    }
    return result;
}

int fibonacci(int num) 
{
    if (num <= 2)
        return 1;
    return value(num - 1) + value(num - 2);
}

Answer 3

Changing intExists to return boolean values, you can do a switch-case statements like that:

bool a = intExists(num-1);
bool b = intExists(num-2); 

switch ((a << 1) + b) {
default: // none exists
case 1: // only b exist
case 2: // only a exist
case 3: // both exists
}

The rationale is to transform those booleans in a binary number

Answer 4

I'm assuming that intExists(n) looks up map and if finds n in there, returns fibonacci(n) else it returns -1. Then you could do this:

int fibonacci(int num) {

    if (num <= 1)
        return num;

    int a = intExists(num-1);
    int b = intExists(num-2);

    if (a == -1) // if a wasn't found, then compute it
        a = fibonacci(num-1);

    if (b == -1) // if b wasn't found, then compute it
        b = fibonacci(num-2);

    int number = a + b;
    map.push_back(std::make_pair(num, number));

    return number;
}

Bonus:

Here is another completely different implementation of fibonnacci() based on Binet's formula:

#include <cmath>

int fibonacci(int n) {
    static const double e1 =  1.6180339887498948482045868343656;  // = (1 + sqrt(5)) / 2
    static const double e2 = -0.61803398874989484820458683436564; // = (1 - sqrt(5)) / 2
    static const double c =   0.44721359549995793928183473374626; // = 1 / sqrt(5);
    double f = c * (std::pow(e1, n) - std::pow(e2, n));
    return static_cast<int>(f + 0.5);
}

int main() {
    for (int n = 1; n < 15; ++n)
        std::cout << fibonacci(n) << ' ';
}

It outputs:

1 1 2 3 5 8 13 21 34 55 89 144 233 377

Answer 5

int a = intExists(num-1);
int b = intExists(num-2);

bool aAndB = (a != -1 && b != -1);
bool justA = (a != -1 && b == -1);
bool justB = (a == -1 && b != -1);

Quick look into the approach you took. Under what circumstances can justB be true? (Hint: never)

That should help you simplify your approach, although there are better approaches than memoization.

Answer 6

Plain C++ code is clean enough:

bool a = intExists(num-1);
bool b = intExists(num-2);

if (a && b) {
  //
} else if (a) {
  //
} else if (b) {
  //
} else {
  //
}

Answer 7

If you're talking about:

bool aAndB = (a != -1 && b != -1);

then I would say, "no."

This code looks perfectly expressive to me. aAndB is initialized at the moment it comes in to being, and the conditions are very clear. This might look a bit odd when you're first starting out in C++, but before you know it it will be second nature and other constructs will seem silly.

One thing I would suggest is to make aAndB const if you don't intend to change it:

const bool aAndB = (a != -1 && b != -1);

This is even more expressive.

It also might give the compiler an additional opportunity to optimize your code.

Remember -- write code for humans to understand. Not for computers to understand.

Answer 8

Why don't you make a and b as bools and assign those as true if a == -1 and false otherwise. Then, the expressions will become easier to handle.

Answer 9

Could do a switch statement to clean up the if else statements a little. Other than that just add comments