-2
#include <stdio.h>

long equation(long x){
  return x*x+x;
}

long BinarySearch(long arr[],long start,long end,long k){

  if(start==0 && end==0){
    return 0;
  }
  else if((end-start)<=5){
    for(int i=start;i<=end;i++){
      if(arr[i]<=k && arr[i+1]>k){
        return i;
      }
    }
  }
  else{
    long mid=(start+end)/2;
    if(arr[mid]==k){
      return mid;
    }
    else if(arr[mid]>k){
      return BinarySearch(arr,start,mid-1,k);
    }
    else{
      return BinarySearch(arr,mid+1,end,k);
    }
  }

}

int main() {

  long a;
  scanf("%ld",&a);
  long roots[a];
  for(long i=0;i<a;i++){
    roots[i]=equation(i);
  }

  printf("%ld",BinarySearch(roots,0,a-1,a));

  return 0;
}

For small numbers (under 100000000), this code works, but over 100000000, this code has runtime error. I set every variables as a long int... I used c++ tutor, it said that the step at long equation has a problem. Invalid write of size 8... Why?

황지원
  • 1
  • Since it needs to be said: `long roots[a];` is a variable length array and is not allowed by the C++ standard (although some compilers do support it). And in general, your code does not use any C++ feature whatsoever. You would not have the problem you are describing if you used `std::vector roots(a);` instead. – Max Langhof Feb 05 '19 at 12:24
  • Not directly related to your problem, but using a recursive algorithm is really the wrong approach here. – Jabberwocky Feb 05 '19 at 12:32
  • 1
    [VLA](https://en.wikipedia.org/wiki/Variable-length_array "Variable-length array")s are not standard C++ – YSC Feb 05 '19 at 12:34
  • `long equation(long x){ return x*x+x; }` will exhibit signed integer overflow (hence undefined behavior) for large enough number (and certainly for 100000000). – YSC Feb 05 '19 at 12:35
  • You don't say what your environment is, but debugging tools should really be a reflex. With gcc or clang, `-fsanitize=address -g` gives you a nice message that there is a stack overflow on line 38. – Marc Glisse Feb 05 '19 at 13:07

1 Answers1

0

long roots[a];

It's variable length array. Which is not a part of C++ standard. (But GNU compliers do support it. And it's a part of C99 and C11-optional). Not knowing how it implemented. But whatever it is, it cannot contain so many long ints.

lets do a mathematical problem. Assume 1MB = 10**6 Bytes, a long int's size is 4 Bytes, then 100000000 longs takes 400MB memory. I don't think it can be stored in a stack which is typically 4MB.

And you said that you' ve used long int. But in most compliers, there's no difference between int and long(though it may be unrelated to this question).

And big enough data range makes you call the recursion function too many times, which may leads to stack overflow.

con ko
  • 1,368
  • 5
  • 18
  • At most, there will be `1+log2(N)` recursive calls where `N` is the size of the range to search. But definitely, `long roots[a]` for really huge `a`s will break something. – YSC Feb 05 '19 at 12:51
  • @YSC Yes, I do think even a array in DSS or heap cannot contain so many elements. – con ko Feb 05 '19 at 12:56
  • 1
    400M of memory is not much using the heap, current computers have gigabytes of memory, it is only a problem because the stack is more limited (typically less than 10M unless you ask for more explicitly). – Marc Glisse Feb 05 '19 at 13:09
  • @MarcGlisse I don't really know how does vla be stored, and a heap are typically 1GB, for I' ve never apply to such a big memory, even in algorithm competitions. I've got it, thanks :) – con ko Feb 05 '19 at 13:15
  • I'd appreciate a hint to cstdint header for the `[u]intN_t` data types. Number of recursions is not *necessarily* a problem, as is, the function would qualify for [tail call optimisation](https://stackoverflow.com/questions/310974/what-is-tail-call-optimization)... – Aconcagua Feb 06 '19 at 08:59