Thread: Help with an algorithm

I'm currently writing a small application that is supposed to calculate the digital root of any given number (Within certain bounds obviously).

At the moment i'm trying to get the logic right:
The number i will be using is inputted by the user from the command-line, i'll then simply loop through argv and add up all the numbers, but this is as far as i got. After i got the sum of all the digits, i need to allocate an array big enough to hold the result (With one digit in each int, so i can work with them one digit at a time). This means, i have to figure out the maximum possible value of the sum of the inputted numbers, this in itself is not hard (Size of argv * 9, since 9 is the highest single digit number), but then i need to figure out how many digits this new number has, and allocate the appropriate amount of memory.

So far i've been doing this:
Say the user inputs a number with 12 digits on the cmd line, i know that no matter what was inputted, the resulting number after adding them all, can't be bigger than 12*9, so i just allocated an array of [12*9], but this isn't what i really wan't, this is actually way more space than i need, and i just realized this.
In this example i won't need more than 3 int's, because the resulting number is 108, but how would i go about figuring this out in C? How can i do that mathematically?

Oh, and another small question, how can i check if the user inputted only numbers, or decided to put some letters in there for whatever reason? Is there a function similar to isalpha() that will do this, e.g. isnumber()?

Oh, and another small question, how can i check if the user inputted only numbers, or decided to put some letters in there for whatever reason? Is there a function similar to isalpha() that will do this, e.g. isnumber()?

#
Yes, isdigit() should do it. I think its in <ctype>.

Originally Posted by mike_g

#
Yes, isdigit() should do it. I think its in <ctype>.

Argh, how obvious, i've been googling all over for isnumber(), and all i was getting was some "char.isnumber" for C# and vb.NET...

Thanks alot.

Oddly enough I forgot it was isdigit too and was playing with isnum for ages. Luckily intellisense was my friend though

Originally Posted by dwks

When INT_MAX is 2^31 (2,147,483,648), which it is on most modern computers (with 32-bit integers), the maximum number of digits for a number would be 10, not 9. On older machines with 16-bit numbers, INT_MAX would be 2^15 (32,768), which is 5 digits.

[edit=2] For 64-bit integers, which you probably won't get with an int but might with a long, the maximum value would be 2^63 = 9223372036854775808L
(9,223,372,036,854,775,808) -- 19 digits; see below. [/edit]

INT_MAX is a real constant, declared in <limits.h> (or <climits> for C++). You could could the number of digits in that value if you wanted to be really portable.

I've seen software that uses 19 for INT_DIGITS:

Code:

#define INT_DIGITS 19		/* enough for 64-bit integer */

This is the C++ programming forum. So are you using C or C++? Because in C I might mention realloc(), but in C++ . . .

First of all, i'm doing this in C++, the C was just a typo.

And yes, i'm aware that integers have a very limited size, but the thing is, i'm not using an integer to save the user input, i'm using an array of integers, and then saving one digit in each int. So if the user inputs '1289' for example, i would allocate an array of 4 ints, the first one with 1 in it, second with 2, and so on...

This makes it much easier to do operations on each digit one at a time, so i can do the adding up when i need to calculate the digital root. It also means that the number can be much larger than if i was using an integer to hold the number, so i'm not limited to a 10 digit number (or 19 with a long).

And i am aware of how to allocate the memory, the problem is how MUCH do i need...

Well, if you're actually calculating the digital root of a number, you'll need exactly one digit per number, no matter how big it is. Right?

Yes, the point is to reach one single number, but that's not really where i'm having problems. To get to that single number, i need to add all the numbers up more than once (Depending on how big the input number is ofcourse), and after the first round of addition, i need to determine how much memory i need to save the result (One int for each number), so i can keep adding numbers untill my number is < 10...

Yes, isdigit(), from <ctype.h> (or, in C++, <cctype>), just like isalpha(). However, it only works on one character, so to apply it to a string you have to apply it to each letter in the string.

[edit] @mike_g: It's <cctype> or <ctype.h>. <ctype> doesn't exist. [/edit]

That's strange, i'm using MingW and even when compiling with "-Wall -ansi -pedantic", i won't get a single warning for including <ctype>..?

Originally Posted by matsp

Why is it that people are overly worried about allocating EXACTLY the right amount of memory for things like numbers? If you are reading huge text files (e.g the entire Linux source tree) into separate strings for each line and lines can vary from 0 to 500 chars, I can understand that allocating 500 chars * hundreds of thousands of lines might be a bit excessive, but for simple problems like this, it shouldn't really matter - the command-line is very unlikely to contain more than a few hundred numbers at the most, so allocating (say) 19 chars for each shouldn't be too excessive.

If you want to save memory, try allocating a big lump of memory and split that up yourself. Allocating really small chunks of memory may be bad - the following

Code:

	char *pold = 0;
	for(int i = 0; i < 10; i++) {
		char *p = new char[16];
		cout << "p = " << hex << (int) p << " diff " << dec << p - pold << endl;
		pold = p;
	}

gives this (first line ommited, as it's pretty meaningless):

Code:

p = 2f0ae0 diff 64
p = 2f0b20 diff 64
p = 2f0b60 diff 64
p = 2f0ba0 diff 64
p = 2f0be0 diff 64
p = 2f0c20 diff 64
p = 2f0c60 diff 64
p = 2f0ca0 diff 64
p = 2f0ce0 diff 64

So each allocation of 10 bytes actually uses 64 bytes. This is with Microsofts Visual Studio .Net (2003).

--
Mats

Well, i'm just doing this for learning purposes, so just allocating 19 ints and calling it a day wouldn't really benefit all that much, i'm not going to use this program for anything, i just wan't to get better at programming logic. What i'm basically asking is how to calculate the number of digits that will be left after doing a digit sum on the input from the command-line?

Allocating really small chunks of memory may be bad

Why?

But wait, you're confusing me. If you want to convert the strings to numbers and then do the calculations, then you don't need to allocate any memory -- you just need to use an int. (This is assuming that the sum fits into an int.) If you're not using ints, because perhaps the values won't fit, then you're probably doing all of the calculations in strings, so why are you limiting the digits in the numbers to 9 or whatever?

How could one digit ever be more than 9? I don't know about you, but i'm using the decimal number system here, that is, base 10.....

Why not modify the values you already have? The sum of all of the digits of a number will always be less than the number itself. At most you'll need an amount of memory equal to the number of digits in your largest number.


That's strange, I'm using Debian GNU/Linux and even when compiling without any warnings at all, I get an error message when including <ctype>.

Code:

ctype.cpp:1:17: error: ctype: No such file or directory

Since I think we can assume that my compiler[1] is standards-compliant on this count, <ctype> obviously doesn't exist on all standards-compliant systems. Don't use it. Use <cctype> or <ctype.h>.

[1] gcc (GCC) 4.1.2

Well, i'm only on gcc 3.4.2 here, but still, i should be getting an error right? Whatever, ill just use cctype then...

[edit=2]
Well, of course, it depends. If the number is 11111, then the sum will be 5, which is one digit. But if the number is 99999, then the sum will be 5*9 = 45, which is two digits. You can't really tell.

But one thing you can do is assume that the number is all 9's and calculate the space required for that. Just a thought.

I think I'll stop editing this post now. [/edit]

Bingo That is basically what i have been trying to do, and that is what i need help with. I can't know for sure if the digit sum of the inputted number will be 2 or 3 or 40000 digits long, so i need some way of calculating how many digits the digit sum of any given number will be, how would i go about this?

Divide by 10 until the result is 0. Count how many divisions it took.

Originally Posted by dwks

Why not just use 9*digits?

Quote from my original post:
"Say the user inputs a number with 12 digits on the cmd line, i know that no matter what was inputted, the resulting number after adding them all, can't be bigger than 12*9"

If that's, say, 45, then you need space for 2 digits. You can count the number of digits in a number like 45 with something like

Code:

int count_digits(int num) {
    int digits = 0;

    do {
        num /= 10;
        digits ++;
    } while(num);

    return digits;
}

Thanks alot, this is what is was looking for Guess i should try to be more clear in what i wan't to do next time, otherwise you guys will just start talking about memory management and how malloc() works on certain systems, etc

Originally Posted by matsp

So your number in argv[n] could be 40000 digits long, or the sum of the digits can be 40000 digits long? That's quite a number. But the sum of that is still only a 32-bit integer, as 9 * 40000 is less than 2^30 by a large margin (about 2^19 is enough to do 9*40000). So calculate the sum of the digits, then figure out how long that number is (per dwks suggestion of how to find the number of digits in an integer).

--
Mats

Yes, precisely Thanks alot...