What is causing error in first function which seemingly looks similar to second function?

user_15996609 0
Viewed 49

Below functions are giving different results. What's the supposed difference between them that is causing different outputs. e.g n=30 and k=417219134 are giving output 0 and 1 respectively.

Function 1(Wrong):

int kthGrammar(int n, int k) {
if (n==1){
    return 0;
}
int parent_node = kthGrammar(n-1, ceil(float(k)/2));
int isKodd = k%2;
if (isKodd){
    return parent_node;}
else{
    return parent_node==0?1:0;}
}

Function 2(Right):

int kthGrammar(int n, int k){
if (n==1){
    return 0;
}
int isKodd = k%2;
if (isKodd){
    return kthGrammar(n-1, (k+1)/2);}
else{
    return (kthGrammar(n-1, k/2)==0?1:0);}
}
c++11 syntax
1 Answers

The int 417219134 can't be perfectly represented by a float.

float  f = 417219134;
double d = 417219134;

std::cout << std::fixed
          << f << '\n'   // 417219136.000000
          << d << '\n';  // 417219134.000000

This explains why ceil(float(k)/2) returns a number that is +1 off from the expected when k = 417219134.

I'd convert to double in the function instead:

int parent_node = kthGrammar(n-1, ceil(k / 2.));
user_75822470
Related