Preemptive defense to control a possible overflow

[Carnotter]

This is an exercise, so I'm seeking no help, but understanding.
One of my exercises to deliver after the vacation:

We have n tour buses. They make a round of x minutes. Determine after how much time will all the buses come back at the station.

If bad translated, this is an example with 3 buses.
Bus 1 makes a round in 10 minutes, the second in 15 minutes and the third in 20 minutes. In 60 minutes, they all will back at station. I'm just calculating lcm(a,b,c).

I already have a solution but as you know, I face the problem of overflow, both overflows: datatype and stack.

int b_lcm; //lcm to find
int b_product = 1; //assume all are prime numbers
int b_max = buses[0]; //largest tour

int i;
for (i = 0; i < nbuses; i++) {
    b_product*=buses[i];
    if (buses[i] > b_max) b_max = buses[i];
}




while (b_max < b_product) {
    int tmp = 0;
    i = 0;
    while (i < nbuses) {
        if (b_max % buses[i] == 0) {
            tmp++;
            i++;
            if (tmp == nbuses) {
                b_lcm = b_tmp; // save the lcm as answer
                b_tmp = b_product;
            }
        } else {
            b_tmp++; 
            tmp = 0;
            i = 0;
            continue;
        }
    }


}

I understand the problem of VLAs (explained very well by Prelude in thread About the function rand(), post 26), so the n should be determined.

A solution expected is to use int with some buses and approx. 1 hour per bus, but (for myself) I would like to expand it, and make it more powerful with or without using datatypes with big ranges like long long whatever, like converting minutes to hours and hours to day and so on.

So, what is the best way to control datatype overflow , and how to know if memory stack ok?

Is it a good programming habit to use larger datatype temporarily to check if a result is? Declare unsigned int to check if int is ok, for example?

Thank you in advance

[GReaper]

Isn't this a classic problem of the Least Common Multiple? Wikipedia provides some decent solutions to the problem.

EDIT: Nevermind, I just noticed that your problem was elsewhere.

[whiteflags]

I'm not immediately sure why you are afraid of stack overflow, but if you don't have enough stack memory, then you have to use heap memory instead (i.e. malloc()). Neither should you really have to worry about overflow in your integers, unless you want to make a program that does this for billions of buses and very, very long trips. Your current solution measures the trip in minutes: even if that stays the same, one year in minutes is only about 525600, which is well within the limits of long int.

[Carnotter]

I was in kind of hurry, I didn't translate the code well. That example won't work but I can't edit it now. I post it here here hoping one of our moderators will delete it and put it in previous post.

whiteflags,
Thanks for your reply, but why billion buses and very long tours? Suppose we take 5 buses. They make tours in 71, 73, 79, 83, 89 minutes.The result will easy exceed the boundaries of an int since the lcm is 3024658859 or 2100457 days and 54 hours.

I would like to understand the strategies or programming habits in such as situations.

Solution without using LCM(LCM(x,y),z) .. and so on.

#include <stdio.h>
#include <stdlib.h>


int main(int argc, char *argv[])
{
	int nbuses = argc - 1; // number of buses
	int buses[nbuses]; // list of buses
	int lcm = 0; //lcm to find
	int product = 1; //assume all are prime numbers
	int max = 1; //largest tour




	int i = 0;
	while (i < nbuses) {
		int num;
		if ((sscanf(argv[i+1], "%d", &num) == 1)) {
			buses[i] = num;
			i++;
		} else {
			fprintf(stderr, "Not a number.\n");
			exit(EXIT_FAILURE); 
		}
	}


	for (i = 0; i < nbuses; i++) {
		product*=buses[i];
		if (buses[i] > max) {
			max = buses[i];
		}
	}


	while (max < product) {
		int tmp = 0;
		i = 0;
		while (i < nbuses) {
			if (max % buses[i] == 0) {
				tmp++;
				i++;
				if (tmp == nbuses) {
					lcm = max;
					max = product;
				}
			} else {
				max++;
				tmp = 0;
				i = 0;
				continue;
			}
		}
	}


	printf("LCM is: %d.", lcm);


	return 0;
}

[whiteflags]

whiteflags,
Thanks for your reply, but why billion buses and very long tours? Suppose we take 5 buses. They make tours in 71, 73, 79, 83, 89 minutes.The result will easy exceed the boundaries of an int since the lcm is 3024658859 or 2100457 days and 54 hours.

You're quite right - I forgot about prime numbers, which would force the LCM to be quite high. Then again, most real-life trips really aren't planned to be some prime minutes long.

Fundamentally, you will need more space the bigger the number is, unless you find a way to make the numbers smaller (e.g. if the trips are all long enough, is it sufficient to compute the LCM in terms of hours etc.?) You get some very silly answers the longer the trips become anyway - so it might be good to round to a realistic number instead. Because:

the lcm is 3024658859 or 2100457 days and 54 hours.

I cannot resist the temptation to tell you that you could just use a 64-bit integer instead, like uint64_t in C99 with #include <stdint.h>

But, realistically, isn't this the same as saying a bus will always be out of the station? They aren't together in less than a year, so maybe I don't really get it.

Anyway...

To handle very large numbers you basically have to throw a library at the problem, like GMP. This is a library that treats an integers bits like a dynamic array and will grow as you need more and more bits. If you don't want to do that, you have to be clever. It can take math skills to pull off. You can create your own math algorithms and store the digits of large integers in a string or something. For example, it can be sufficient for toy programs to implement a multiply-and-carry or add-and-carry algorithm digit by digit. Just like you did in school!

If you're patient, you can learn binary multiplication and do roughly what GMP does for this problem...

You don't beat integer overflow, you plan to avoid it. That's real advice.

[GReaper]

If you're patient, you can learn binary multiplication and do roughly what GMP does for this problem...

Alas, if you'd want to print/show the number to the user, you'd need much more than just multiplication... I've been through this torture XD

[Carnotter]

Sorry, 2100457 days and 12 hours and 59 minutes

Whiteflags,
I think, this exercise is on how to work with arrays to solve some problems with it, that's all. But while I was making it (with reading input instead of using *argv[] of course as we didn't yet receive a lesson on pointers) alongside improving my project, the question of controlling the overflow came up in my mind. I know there are some common answers like you don't beat division by zero but you just avoid it, and that kind of stuff. I's OK, but is it what experienced programmers and engineers actually do, or are there any other, better, more efficient ways in "avoiding"?

The GMP is great for research programs. Not what I need (to understand) at the moment.