Counting powers of 3 within a given range in C

Question

I have to write a program that takes in two positive integers, start and end, where (1 < start < end). Then the program would look within this range [start, end] and count the number of powers of 3.

So, for example, if start is 2 and end is 10, the output would be 2. (as 3 and 9 are powers of 3).

Below is my code:

#include <stdio.h>
#include <math.h>

int main(void) {

    int start, end, i, count = 0;

    printf("Enter start and end: ");
    scanf("%d %d", &start, &end);

    for (i = start; i <= end; i++) {
        if ((log(i) / log(3)) == floor((log(i) / log(3)))) {
            printf("%d\n", i);
            count++;
        }
    }
    printf("Answer = %d\n", count);

    return 0;
}

But, when I tried to run one of the test cases [3, 1000], the output is 5, when it should be 6.

3
9
27
81
729
Answer = 5

The number 243 is missing. Is there something wrong with my code?

Answer 1

The problem is you are using exact comparison of floating point numbers. Specifically, here:

if ((log(i)/log(3)) == floor((log(i)/log(3))))

Since log() and floor() return double, you're comparing without any tolerance two values which cannot be compared that way.

How should I do floating point comparison?

Answer 2

Your immediate problem has to do with the imprecision of floating point numbers, something that is generally well documented on the net, including various methods useful in fixing that problem.

However, I'm not actually going to bother referring you to them because the use of floating point is totally unnecessary here. There's a much more efficient way of doing this that involves only integers.

Rather than going through numbers in your range looking for powers of three using floating point operations, you would be better off going through powers of three (using just integer multiplication) looking for numbers in your range.

In pseudo-code, that would go something like:

powerOfThree = 1
while powerOfThree <= endRange:
    if powerOfThree >= startRange:
        print powerOfThree
    powerOfThree = powerOfThree * 3

You could even make it more efficient by selecting a more suitable starting value for powerOfThree but, since there are only 40-odd powers of three in a 64 bit number, that's probably a waste of time.

When converting from pseudo-code to the more concrete C, you unfortunately come across the limitations of the datatypes in that language, specifically the fact that multiplication may result in overflow.

There are various ways you can avoid this this such as detecting that it's about to happen and exiting the loop early.

Given below is the function that you need, one which handles this issue, along with some test code which can be used for validating it.

#include <stdio.h>
#include <limits.h>

// I hate typing :-)

typedef unsigned long ULONG;
typedef unsigned int UINT;

static UINT countPowersOfThreeBetween (ULONG low, ULONG high) {
    // Catch invalid params, just exit with zero.

    if (low > high) return 0;

    // Go through all powers of three.

    ULONG powerOfThree = 1;
    UINT count = 0;
    do {
        // If within your range, count it.

        if ((powerOfThree >= low) && (powerOfThree <= high)) {
            count++;
            // printf ("DEBUG: got %lu\n", powerOfThree);
        }

        // Early exit if about to overflow.

        if (ULONG_MAX / powerOfThree < 3) break;

        // Advance to next power and continue if within range.

        powerOfThree *= 3;

    } while (powerOfThree <= high);

    // Notify caller of count.

    return count;
}

// Test function to make test suite easier.

static void testRange (ULONG low, ULONG high) {
    UINT count = countPowersOfThreeBetween (low, high);
    printf ("In range %lu..%lu, found %u occurrences\n", low, high, count);
}

// Test suite, add whatever you need.

int main (void) {
    testRange (1000, 10);
    testRange (0, 0);
    testRange (9, 9);
    testRange (3, 1000);
    testRange (0, ULONG_MAX);
    testRange (ULONG_MAX, ULONG_MAX);
    return 0;
}

As you will see from the output, this gives the correct counts for various ranges:

In range 1000..10, found 0 occurrences
In range 0..0, found 0 occurrences
In range 9..9, found 1 occurrences
In range 3..1000, found 6 occurrences
In range 0..18446744073709551615, found 41 occurrences
In range 18446744073709551615..18446744073709551615, found 0 occurrences

And, if you uncomment the printf line in countPowersOfThreeBetween(), you'll also see the actual values detected.

Answer 3

Before choosing floating point types in the future, I strongly recommend you read this article entitled "What every computer scientist should know about floating-point arithmetic", by David Goldberg. It explains your problem(s) nicely, much better than I could have.

You don't actually need floating point (or negative integer) types here, so they should be avoided. Form your powers by multiplication, rather than addition:

#include <assert.h>
#include <limits.h>
#include <stdio.h>

int main(void){
    unsigned int start, end, i, count = 0;

    printf("Enter start and end: ");
    int x = scanf("%u %u", &start, &end);
    assert(x == 2);            // XXX: INSERT PROPER ERROR HANDLING!

    // find the first power greater than or equal to start
    for (i = 1; i < start && UINT_MAX / 3 >= i; i *= 3);

    // ... then count each one less than or equal to end
    while (i <= end && UINT_MAX / 3 >= i) {
        printf("%u\n", i);
        i *= 3;
        count++;
    }

    printf("Answer = %u\n", count);
}

Answer 4

Your problem is round-off error while float calculating in computer, the result of log(243)/log(3) is not exactly log3(243), where computer store approximate value of it. eg, in my 32bit computer, it is 4.99999999999999911182.

However, you have two ways to solve it,

1. use integer calculation instead of float.

2. simple mathematical transformation. number of powers of 3 in [start, end] is equivalent to floor(log3(end)-log3(start))+1, wrote in c is

   printf("answer:%d\n", (int)((log(1000)-log(3))/log(3))+1);

complete code:

#include <stdio.h>
#include <math.h>

int pow3(int n) {
    int ret = 1;
    while(n--) {
        ret *= 3;
    }
    return ret;
}

int main() {
    int a, start, end, answer;
    scanf("%d%d", &start, &end);
    a = (int)(log(start+0.5)/log(3));
    //printf("%d,%d,%d\n", a, pow3(a), start);
    if(start == end) answer = (start == pow3(a));
    else answer = (int)((log(end+0.5)-log(start))/log(3))+1;
    printf("answer = %d\n", answer);

}

Result:

Input[0]: 2 10
Output[0]: 2
Input[1]: 1 3
Output[1]: 2
Input[2]: 3 1000
Output[2]:6

Answer 5

Your program fails because of floating point precision issues.

Use integer arithmetics instead:

#include <limits.h>
#include <stdio.h>

int main(void) {
    unsigned int start, end, i, count;

    printf("Enter start and end: ");
    if (scanf("%u %u", &start, &end) == 2) {
        for (i = 1, count = 0; i <= end && i <= UINT_MAX / 3; i *= 3) {
            if (i >= start) {
                printf("%u\n", i);
                count++;
            }
        }
        printf("Answer = %u\n", count);
    }
    return 0;
}

A direct solution with floating point arithmetics is possible too:

#include <math.h>
#include <stdio.h>

int main(void) {
    unsigned int start, end, count = 0;

    printf("Enter start and end: ");
    if (scanf("%u %u", &start, &end) == 2) {
        if (end > 0 && end >= start) {
            int start3 = (start <= 1) ? 0 : (int)(log(start - 0.5) / log(3));
            int end3 = (int)(log(end + 0.5) / log(3));
            count = end3 - start3;
        }
        printf("Answer = %u\n", count);
    }
    return 0;
}