Can't increase range of numbers in a program in C++

Question

Here is the question:

Comparing two numbers written in index form like 2^11 and 3^7 is not difficult, as any calculator would confirm that 2^11=2048<3^7=2187.

However, confirming that 632382^518061>519432^525806 would be much more difficult, as both numbers contain over three million digits.

You are given N base exponent pairs, each forming a large number you have to find the Kth smallest number of them. K is 1−indexed.

Input Format First line containts an integer N, number of base exponent pairs. Followed by N lines each have two space separated integers B and E, representing base and exponent. Last line contains an integer K, where K<=N Constraints 1≤N≤105 1≤K≤N 1≤B≤109 1≤E≤109 No two numbers are equal.

Here is my code:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int N,i = 0,k,j=0,x,m;
    long long int *arr,*arr2,*arr3;
    cin >> N;
    arr = (long long int *)malloc(sizeof(long long int)*2*N);
    arr2 = (long long int *)calloc(N,sizeof(long long int));
    arr3 = (long long int *)calloc(N,sizeof(long long int));
    x = 2*N;
    while(x>0)
    {
        cin >> arr[i];
        i++;
        x--;
    }
    cin >> k;
    for(i=0;i<2*N;i+=2)
    {
        arr2[j] = pow(arr[i],arr[i+1]);
        j++;
    }
    arr3 = arr2;
    sort(arr2,arr2+N);
    for(i=0;i<N;i++)
    {
        if(arr3[i] == arr2[k-1])
        {
            m = i;
            break;
        }
    }
    cout << arr[2*m] << " " << arr[2*m + 1];
    return 0;
}

The program works for small numbers only, can't make it work for large numbers. what to do?

How are you defining "large" and "small" numbers? (And how specifically is it failing) — Lilith Daemon, Aug 11 '15 at 12:44
The statement `arr3 = arr2;` doesn't copy the array, it merely makes both pointers point to the same memory (and leaks what `arr3` used to point to). The `sort(arr2,arr2+N);` is useless because the array is all zeroes. Is this your actual code? I don't see how it does anything useful. — Blastfurnace, Aug 11 '15 at 12:57
when i am giving two numbers like 21 and 23. The value of 21^23 getting stored in arr2 is wrong. But when I use like 5 7 the value of 5^7 is getting stored properly — mayview, Aug 11 '15 at 13:14
@Blastfurnace the statements you mentioned is working correctly, I checked. — mayview, Aug 11 '15 at 13:17
@mayview You are not putting any values to arr2 and arr3 so I don't know what you're talking about. — Sopel, Aug 11 '15 at 13:18

score 4 · Answer 1 · edited May 23 '17 at 12:06

4

Maybe you are generating an overflow on the big numbers. You could consider using a multiprecision arithmetic library such as https://gmplib.org/. I haven't used this library myself.

Have a look at this post How to detect integer overflow? on how to detect integer overflow.

edited May 23 '17 at 12:06

Community

1
1

answered Aug 11 '15 at 12:47

fbastian

111
4

Taher Rahgooy · Answer 2 · 2015-08-11T13:37:48.143

From your choosing of long long int type I guess you calculated the a^b of the numbers in order to sort them, which leads to very big numbers and may lead to overflow.
Note that in order to sort the numbers there is no need for this calculation, for knowing if a^b > d^c it is sufficient to check log(a^b) > log(c^d) and therefore b*log(a) > d*log(c).

And it's better to use a struct or class to create a data structure for this big numbers.

This is the code for it:

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
struct BigNumber{
    int base;
    int exponent;
};
int Compare(BigNumber x, BigNumber y);
void Sort(BigNumber* arr, int N);
int main() {
    int N,i = 0,k;
    BigNumber *numbers;
    cout<<"\nEnter N:";
    cin >> N;
    numbers = (BigNumber *)calloc(N,sizeof(BigNumber));
    for(i=0; i<N; i++)
    {
        cout<<"\nEnter base and exponent for number "<<i<<":";
        cin >> numbers[i].base>>numbers[i].exponent;
    }
    cout<<"\nEnter K:";
    cin >> k;
    Sort(numbers,N);
    cout << "Kth number is :" << numbers[k].base << "^" << numbers[k].exponent;
    return 0;
}
void Sort(BigNumber* arr, int N){
    for(int i=0; i< N; i++ ){
        for(int j=0; j< N; j++){
            if(Compare(arr[i], arr[j])<0){
                BigNumber temp = arr[j];
                arr[j] = arr[i];
                arr[i] = arr[j];
            }
        }
    }
}
int Compare(BigNumber x, BigNumber y){
    double X = x.exponent * log10(x.base);
    double Y = y.exponent * log10(x.base);
    return X == Y? 0: X > Y ? 1: -1;
}

score 0 · Answer 3 · answered Aug 11 '15 at 14:22

I changed the code a little. Only problem I was having was I was calculating the exponent rather than comparing log of exponent.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int N,i = 0,k,j=0,x,m;
    int *arr;
    double *arr2,*arr3;
    cin >> N;
    arr = (int *)malloc(sizeof(int)*2*N);
    arr2 = (double *)calloc(N,sizeof(double));
    arr3 = (double *)calloc(N,sizeof(double));
    x = 2*N;
    while(x>0)
    {
        cin >> arr[i];
        i++;
        x--;
    }
    cin >> k;
    for(i=0;i<2*N;i+=2)
    {
        arr2[j] = arr[i+1]*log10(arr[i]);
        j++;
    }

    for (i = 0; i < N; i++) {
      arr3[i] = arr2[i];
   }
    sort(arr2,arr2+N);
    for(i=0;i<N;i++)
    {
        if(arr3[i] == arr2[k-1])
        {
            m = i;
            break;
        }
    }

    cout << arr[2*m] << " " << arr[2*m + 1];
    return 0;
}

Can't increase range of numbers in a program in C++

3 Answers3