Like Tree2Likes
  • 1 Post By Nominal Animal
  • 1 Post By iMalc

Parsing an Integer with modulus and division

This is a discussion on Parsing an Integer with modulus and division within the C Programming forums, part of the General Programming Boards category; I'm looking to be able to parse the individual digits from a large integer using modulus and division such as ...

  1. #1
    Registered User
    Join Date
    Oct 2012
    Posts
    2

    Parsing an Integer with modulus and division

    I'm looking to be able to parse the individual digits from a large integer using modulus and division such as in the code below (which was an answer to the same question on another thread.

    Example:
    Input: 123456789

    9
    8
    7
    6
    5
    4
    3
    2
    1

    Code:
    #include <stdio.h>
    
     
    
    int main(void)
    {
      int a = 12345;
     
      do
      {
        printf("%d\n", a % 10);
      }
      while (a /= 10);
     
      return 0;
    }
    This code works fine for when you have integers less than 10 digits. But say i was trying to parse a 20 digit int, it gives odd results.

    Example:
    Input: 123456789123456789
    Output:
    -5
    -1
    -3
    0
    -3
    -6
    -5
    -9
    -3
    -1

    I'm trying to do this as a way to parse a 20 digit int of 1's and 0's into an array so i can compare individual values.

    Also im new to the forum, sorry if my the code is posted incorrectly

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Welcome to the forum, HoldenR.

    Are you sure the INT is 20 digits long? Usually you'd use sprintf() to take your number into a string array, but I don't know of any int's that are 20 digits long.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,300
    How do you think you are getting a 20-digit into into your system?
    It certainly isn't possible with the above code.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,831
    32-bit integers can hold 9 decimal digits. 64-bit integers can hold 18 decimal digits or 19 if it's unsigned. By decimal digits I mean digits that range from 0 to 9.
    So you might want to look into type 'long long'.

  5. #5
    Registered User
    Join Date
    Oct 2012
    Posts
    2
    My point was that the above code would not work, i do understand that. And sorry about the misunderstanding, I am new to programming. It does not specifically need to be stored as an INT. I was using integer in the context of 'number' not the data type. I don't need to see specific code from anybody, i just am trying to understand the logic behind storing a very large number and then getting the digits into an array and how to go about it. Would it be best to go about storing the number as a string? I have not learned long long.

  6. #6
    Registered User
    Join Date
    Oct 2011
    Posts
    838
    Look at my example code in this post. The small_mul_add() multiplies a multi-limb natural number with a 32-bit value and adds a 32-bit value to the result, returning any overflow (new highest limb, if nonzero). The string_to_natural() reads a decimal number string, using small_mul_add() to multiply the parsed value by ten and adding the new digit. It grows the binary decimal dynamically, then saves the pointer to the limbs, and the number of limbs, at the supplied locations.

    A big natural number has to be divided into bit groups, "limbs". I used 32-bit limbs, since then I could use the standard 32-bit and 64-bit unsigned integer types from stdint.h to handle the math easily. If you are familiar with long multiplication by hand, the algorithms are very similar. Instead of individual digits, we just work with 32-bit "digits" (limbs!).

    The binary representation has the least significant limb first. That way you can for example add two numbers together by adding the first limbs, then the second limbs, and so on, simply carrying any overflow to the next limb. Similarly, the other algebraic functions are easier to implement if limbs are listed least significant limb first.

    If you have any questions, I'd be happy to elaborate. Just be specific, please.
    HoldenR likes this.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,300
    Quote Originally Posted by HoldenR View Post
    i just am trying to understand the logic behind storing a very large number and then getting the digits into an array and how to go about it. Would it be best to go about storing the number as a string? I have not learned long long.
    If the input comes from the user, then as you probably already realise, it can just go straight into a string and never has to go through an integer.
    Otherwise, there are various libraries out there to deal with large or even arbitrarily large integers. I've actually written three such libraries myself, in C++.
    One of mine stores the number itself as a string internally, so for that one converting to string is trivial. For the other two, its pretty much like you have it with the modulus and disivion to get each digit.
    So yes, you are going about it the right way. The only issues are that
    1. You should use an unsigned type because the algorithm only works when the number is positivie, and
    2. You'd need to use a type that allows you to store larger numbers.
    HoldenR likes this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Modulus Division?
    By Shamshir in forum C Programming
    Replies: 5
    Last Post: 03-09-2011, 08:03 AM
  2. BigInt division and modulus
    By User Name: in forum C++ Programming
    Replies: 4
    Last Post: 09-11-2010, 03:54 PM
  3. Replies: 5
    Last Post: 10-14-2009, 05:47 AM
  4. Modulus division
    By WatchTower in forum C Programming
    Replies: 4
    Last Post: 07-20-2009, 11:26 PM
  5. overloading the division operator with Integer Class
    By silk.odyssey in forum C++ Programming
    Replies: 3
    Last Post: 05-17-2004, 06:59 PM

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