Help with an algorithm

This is a discussion on Help with an algorithm within the C++ Programming forums, part of the General Programming Boards category; I'm currently writing a small application that is supposed to calculate the digital root of any given number (Within certain ...

  1. #1
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964

    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()?

  2. #2
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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>.

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    Size of argv * 9, since 9 is the highest single digit number
    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 */
    how would i go about figuring this out in C?
    This is the C++ programming forum. So are you using C or C++? Because in C I might mention realloc(), but in C++ . . .

    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?
    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?

    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(), 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]
    Last edited by dwks; 09-19-2007 at 03:03 PM.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #4
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Quote Originally Posted by mike_g View Post
    #
    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.

  5. #5
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,262
    Oddly enough I forgot it was isdigit too and was playing with isnum for ages. Luckily intellisense was my friend though

  6. #6
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Quote Originally Posted by dwks View Post
    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>..?

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Quote Originally Posted by matsp View Post
    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?

  9. #9
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    Since you're using C++, why not use std::strings or std::vectors? Then you don't have to worry about how much memory you're allocating.

    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?

    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...
    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 MingW and even when compiling with "-Wall -ansi -pedantic", i won't get a single warning for including <ctype>..?
    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

    [edit]
    Allocating really small chunks of memory may be bad
    Why?
    Umm, matsp just showed you why. Because unless the amount of memory that you allocate is a multiple of the chunks of the size of the memory that malloc() (or whatever) returns, you're probably going to be wasting a little bit of memory each time you allocate something. Probably not, depending on what memory manager your runtime is using, but it's certainly a possibility.

    Not to mention that requesting and freeing memory can be quite an expensive operation. So expensive, in fact, that many systems use a layer under malloc() which requests memory from the system in large chunks, and gives you small chunks of that chunk when you request memory with malloc(). Again, it all depends on what system you're using.

    But just in general -- it's better to get a large chunk than a number of smaller chunks that add up to the same amount. Why do you think calloc() exists?

    Actually, there might be one case where it would be better to get smaller chunks. When your memory is highly fragmented, the memory manager might be able to find three 1MB chunks but not one 3MB chunk of memory. [/edit]

    [edit=2]
    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?
    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]
    Last edited by dwks; 09-19-2007 at 03:53 PM.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  10. #10
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    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?

  11. #11
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    Divide by 10 until the result is 0. Count how many divisions it took.

  12. #12
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    Why not just use 9*digits? 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;
    }
    [edit] Or see Daved's post for the same thing but more concisely.

    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.....
    From your original post, I thought you were stating that a number could only have 9 digits. I misread it.

    Well, i'm only on gcc 3.4.2 here, but still, i should be getting an error right?
    I don't know why you're not. Probably so many people thought "well, I included <ctype> and there was no error, so it must be okay, right?" that the developers of GCC decided to put it in, and by now they've come to their senses. [/edit]
    Last edited by dwks; 09-19-2007 at 04:11 PM.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  13. #13
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Quote Originally Posted by dwks View Post
    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

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Neo1 View Post
    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?
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  15. #15
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Quote Originally Posted by matsp View Post
    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...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21