Thread: Can someone try to explain what my professor is talking about...

  1. #1
    Registered User
    Join Date
    Nov 2012
    Posts
    5

    Can someone try to explain what my professor is talking about...

    Hi friends!

    I have a problem set which we have to read in large integers from a file and multiply them, but the numbers can't be int because they are too big so we have to read them in character by character and create a convert function and multiply function.

    Anyways, he writes here:

    Each integer is represented as an array of digits, where the least significant digit is storedin index 0, and the last index stores a non-zero number. (The only exception to this is 0,
    which is stored in an array of size 1 that has a single element storing 0.) For instance, the
    value 1234567890 would be stored as:

    index 0- 0
    index 1- 9
    index 2- 8
    index 3- 7
    index 4- 6
    index 5- 5
    index 6- 4
    index 7- 3
    index 8- 2
    index 9- 1

    Note: Although this seems counter-intuitive, it makes the code slightly easier, because in
    all standard mathematical operations, we start with the least significant digit. It also
    makes sense that the digit at the place 10i is stored in index i.

    Can someone explain what he means here?
    Also, I hate to ask but can someone explain to me what steps it takes to do this problem, I attached the problem if you are interested. The professor didn't teach the way to solve a problem like this. Please note, I am not looking for the answer, just someone with more experience to explain to me.Thanks
    Attached Images Attached Images
    Last edited by Simon Pacheco; 01-21-2013 at 09:32 PM.

  2. #2
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Copied from PDF by hand; might have mistakes.
    Which part do you not understand?

    I suggest writing the print function first.
    Second, I would do the convert_integer function.
    Third, I would write the suggested addition function.
    Fourth, I would write the multiply function.
    Last, I would do the full program reading the data file.

    Edit: The solution to this problem would be more elegant with the use of dynamic memory via the malloc and related functions.
    I would write it using dynamic memory; but, you might not yet have learned that.

    Tim S.

    Code:
    struct integer {
        int* digits;
        int size;
    }
    
    struct integer* convert_integer(char* stringInt);
    
    void print(struct integer *p);
    
    struct integer* multiply(struct integer *p, struct integer *q);
    The code I used to test the print function I wrote.
    Code:
    #include <stdio.h>
    
    struct integer {
        int* digits;
        int size;
    };
    
    void print(struct integer *p);
    
    int main()
    {
        struct integer testValue;
        int testDigits[] = {0,9,8,7,6,5,4,3,2,1};
        testValue.digits = testDigits;
        testValue.size = sizeof(testDigits)/sizeof(testDigits[0]);
    
        printf("testValue.size:= %d\n", testValue.size);
    
        print(&testValue);
    
        return 0;
    }
    Last edited by stahta01; 01-21-2013 at 10:14 PM.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  3. #3
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907
    I did something similar to solve a projecteuler question a few months ago.

    The best place to start is to get a pen and paper and start multiplying 2 numbers together - I assume that you remember multiplication.

    Think of the carry as a variable and the answer as a third array.

    Once you do a few different numbers by hand, the algorithm is very quick to work out
    Fact - Beethoven wrote his first symphony in C

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    The description of the problem is perfectly clear. I wouldn't know what to do differently than copy and paste the same description back to you. You just store the numbers as reversed strings, and then do the maths on those strings yourself with a couple of nested loops. It's no different to how you do it on paper. Just make a start and post the code for more help.

    I have already written code that solves this exact problem in C++, except I didn't store the strings reversed because I found it to have negligible performance benefit in my case. (std::strings have a constant time length() function.)
    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"

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I did it almost exactly as Click_here described above. I used three int arrays:
    Code:
      car[]
    x num[] 
    =========
      ans[]
    and followed exactly the same method as multiplying by hand. For the last bit of speed, you'd want a faster bit hack, but this is fast enough.

    I didn't reverse any numbers. Working from the larger index to the smallest one seemed quite natural.

    The technique of starting your program modeled after how you do something on paper, is a good place to start, imo. So many times you'll start with that, and think "wait! This would be a more efficient way ...".

  6. #6
    Registered User
    Join Date
    Nov 2012
    Posts
    5
    Code:
    int main()
    {
        // File pointer and file opening code. Test to see if the file is able to read is also included.
        FILE *ifp = fopen("bigint.txt", "r");
        if (!ifp)
        {
            printf("The file is unable to open!\n");
            return -1;
        }
    
    
        int num_operations, i;
    
    
        fscanf(ifp, "%d", &num_operations);
    
    
        for (i=0; i < num_operations; i++)
        {
    
    
            char *stringInt = malloc(sizeof(char));
    
    
            int k;
            char fullString[SIZE], temp1[SIZE], temp2[SIZE];
    
    
            for (k=0; k != '\0'; k++)
            {
                stringInt[i] = malloc(sizeof(char));
                fscanf(ifp, "%s", fullString[SIZE]);
            }
    
    
    
    
            int j = 0;
            fscanf(ifp, "%s", fullString[j]);
    
    
            while (fullString[j] != ' ')
            {
                fullString[j] = temp1[j];
                j++;
            }
    
    
            while (fullString[j] != '\0')
            {
                fullString[j] = temp2[j];
                j++;
            }
    
    
    
    
    
    
        // Assigns the line 1 of the text file to num_operations. TESTED AND WORKS!
        //fscanf(ifp, "%d", &num_operations);
    
    
        }
    
    
        // Close the file.
        fclose(ifp);
    
    
        return 0;
    
    
    }
    This is what I have so far.

    The test case is:
    Code:
    3
    4 5
    27 10
    1111111111111111111 4
    In my main function, I am reading the
    Code:
    3
    into num_operations and then trying to move to the second line and store
    Code:
    4 5
    into one array, I don't think I am doing this right though. After doing that, I want to store them into individual arrays using the two while loops. Is this the right approach to solve the conversion of integers to individual characters?

    I truly feel so lost with this problem it is very discouraging. My plan is to read in the single character array, pass it into a function that will then split it into two character arrays, and then converting them into integers. After that I have to follow through with the multiplication.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Why work with chars, at all? Read the digits in as ints, put them into int arrays, and multiply and add any carry to the correct column. There's no need for a char "middle man".

  8. #8
    Registered User
    Join Date
    Nov 2012
    Posts
    5
    I see what you are saying, however we have no choice but to convert them into characters.

  9. #9
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    I would give you advice; but, I have no idea where to start.
    Your code has only slight resemblance to the problem.

    I would do a bottom-up design; but, you look like you are trying a top-down design.
    If you understand the big picture better than the details top-down design is a good choice.

    I use bottom-up design most often because I often have no grasp of the big picture; till after I solve small details.

    Both ways work; but, you seem to be writing code I can not easily follow how it relates to the problem.

    Top-down and bottom-up design - Wikipedia, the free encyclopedia

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  10. #10
    Registered User
    Join Date
    Nov 2012
    Posts
    5
    I never really learned this strategy. In top down approach always seemed natural because for example how am I going to test the numbers the prof gave us and match the exact output without the problem working. I am a noob programmer and this project is very difficult for me. I don't understand why we are using all these pointers and structs. I am a cs major and I am feeling very discouraged right now. I should try the bottom up approach but I don't know what to test for if the problem itself isn't solved. I suck at this but it's the only thing I picture studying

  11. #11
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    I am having trouble sleeping so I did a little work on this.

    Here's the code I am testing with.

    I have decided after getting the addition function to work to not use it. But, it was useful as a re-learning experience. I tend to get a little confused around this time of being up for about 20 hours.

    Tim S.

    Code:
    struct integer* addition(struct integer *p, struct integer *q);
    
    void print(struct integer *p);
    struct integer* convert_integer(char* stringInt);
    struct integer* multiply(struct integer *p, struct integer *q);
    
    int main()
    {
        struct integer testValue;
        int testDigits[] = {0,9,8,7,6,5,4,3,2,1};
        testValue.digits = testDigits;
        testValue.size = sizeof(testDigits)/sizeof(testDigits[0]);
    
        printf("testValue.size:= %d\n", testValue.size);
    
        print(&testValue);
    
        print(convert_integer("12345678910"));
    
        print(addition(convert_integer("0"), convert_integer("0")));
    
        print(addition(convert_integer("3"), convert_integer("6")));
    
        print(addition(convert_integer("5"), convert_integer("6")));
    
        print(addition(convert_integer("9999"), convert_integer("1")));
    
        return 0;
    }
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  12. #12
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    My test results and test code.

    Code:
    testValue.size:= 10
    1234567890
    12345678910
    0
    0
    99
    9000000000
    99999999910
    Error: NULL pointer passed to print function
    10000000000
    0
    999990000
    1000000
    999998000001
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    struct integer {
        int* digits;
        int size;
    };
    
    /* Make all the digits 9 or less by carrying the value to next higher digit */
    /* WARNING returns NULL pointer if size is too small */
    struct integer* normalize_digits(struct integer *p);
    /* Reduce the size by how many leading digits are zero; min size is 1 */
    struct integer* normalize_size(struct integer *p);
    
    void print(struct integer *p);
    struct integer* convert_integer(char* stringInt);
    struct integer* multiply(struct integer *p, struct integer *q);
    
    int main()
    {
        struct integer testValue3;
        int testDigits3[] = {10,9,9,9,9,9,9,9,9,9};
        testValue3.digits = testDigits3;
        testValue3.size = sizeof(testDigits3)/sizeof(testDigits3[0]);
    
        struct integer testValue2;
        int testDigits2[] = {10,9,9,9,9,9,9,9,9,8};
        testValue2.digits = testDigits2;
        testValue2.size = sizeof(testDigits2)/sizeof(testDigits2[0]);
    
        struct integer testValue;
        int testDigits[] = {0,9,8,7,6,5,4,3,2,1};
        testValue.digits = testDigits;
        testValue.size = sizeof(testDigits)/sizeof(testDigits[0]);
    
        printf("testValue.size:= %d\n", testValue.size);
    
        print(&testValue);
    
        print(convert_integer("12345678910"));
    
    #if 1 /* change 1 to 0 to disable this code section */
        print(normalize_size(convert_integer("0000000"))); /* 0 */
        print(normalize_size(convert_integer("0")));       /* 0 */
        print(normalize_size(convert_integer("99")));      /* 99 */
    
        print(normalize_digits(&testValue2));              /* 9000000000   */
        print(&testValue3);                                /* 99999999910  */
        print(normalize_digits(&testValue3));              /* NULL POINTER */
        print(&testValue3);                                /* 10000000000  */
    #endif
    
        print(multiply(convert_integer("1000"), convert_integer("0"))); /* 0 */
    
        print(multiply(convert_integer("99999"), convert_integer("10000"))); /* 999990000 */
    
        print(multiply(convert_integer("1000"), convert_integer("1000"))); /* 1000000 */
    
        print(multiply(convert_integer("999999"), convert_integer("999999"))); /* 999998000001 */
    
        return 0;
    }
    No plans to work on this anymore; the major thinking for me is solving the lower level functions. The read and process of the data file holds no interest. Nothing for me to learn doing it. And if I did it, I might be temped to post it; that much help is against the idea of this site.

    Edit: Both my normalize_ functions returns the pointer passed to it; except in errors where NULL pointer is returned.
    This allows easier testing.

    Tim S.
    Last edited by stahta01; 01-22-2013 at 04:53 AM.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  13. #13
    Registered User
    Join Date
    Nov 2012
    Posts
    5
    Quote Originally Posted by Adak View Post
    I did it almost exactly as Click_here described above. I used three int arrays:
    Code:
      car[]
    x num[] 
    =========
      ans[]
    Can you explain what carry does please? Thanks for all of your guys help so far.

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by Simon Pacheco View Post
    Can you explain what carry does please? Thanks for all of your guys help so far.
    First, I should explain that there is no need to use int's in this algorithm - it works just as well with chars. It's just my opinion that it's easier to do this with ints - but it's certainly NOT a requirement.

    The carry array holds the amount that falls into the next column up, when you add or multiply:

    7 x 7 = 49, so
    Code:
    char carry[3]= {0};
    char num1[3]=7;
    char num2[3]=7;
    char answr[3]={0};
    Multiplying 7 x 7, answr[] immediately gets the 9 in one slot of the answr[] array (hi or low index position depends on your logic, but either way it gets ONE index in the answr[] array.

    But the 40 part of the answer won't fit into a digit less than 10, so the zero is dropped, (essentially dividing by 10 since the next column in our base 10 requires it), and then moves from the carry[] array, down to the answr[] array.

    It's clear that you're over-thinking this problem. Think of the number line, and emphasize the COLUMNS (one's, tens, hundreds, thousands, etc.) in our base 10 number system.

    Each operation is done FOR THAT COLUMN on a digit less of 9 or less. Everything else must be carried (or borrowed for subtraction), to or from an adjacent column's digit.

    It's been a long time since I did this, but I don't believe you need to work with integers, at all. Chars are enough, and they can be added, multiplied, subtracted, etc. They're basically just small int's (but when you display them, they show their offset value - you don't want that offset value - so subtract '0' from them, straight away, and you should be good to go.

    char chr = 0; means chr equals 48 decimal. That is it's offset. You want it to be a REAL 0, so

    Code:
    chr -= '0';  // chr = chr-'0'
    does the trick. That's true for all chars, btw.

    chr = '1'; char chr assigned the value of '1' (49). Change is:

    Code:
    chr -= '0'; //chr=chr-'0'. Now chr equals a REAL 1, not 49.

  15. #15
    Registered User
    Join Date
    Nov 2011
    Location
    Saratoga, California, USA
    Posts
    334
    Quote Originally Posted by Simon Pacheco View Post
    I see what you are saying, however we have no choice but to convert them into characters.
    au contraire...

    "You must use the following struct:"
    Code:
    struct integer {
          int* digits;
          int   size;
    }
    "Here are the prototypes of the functions you must write:"
    Code:
    struct integer* convert_integer( char* stringInt );
    ...
    void print( struct integer *p );
    ...
    struct integer* multiply( struct integer *p, struct integer *q );
    Pretty clear you're expected to convert the character string to a dynamic array of int-s.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ professor requiring 3 files for headers?
    By JonathanS in forum C++ Programming
    Replies: 4
    Last Post: 09-06-2012, 01:15 PM
  2. sadistic calculus professor
    By sean in forum A Brief History of Cprogramming.com
    Replies: 9
    Last Post: 09-13-2008, 10:03 AM
  3. I'm meeting with a college professor (computer science). Questions...... ->
    By SG57 in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 12-07-2006, 06:55 PM
  4. frustrating professor
    By vwy in forum C Programming
    Replies: 10
    Last Post: 02-07-2006, 09:55 PM
  5. Ask Professor Giraffenstein! (Contains some NSFW material)
    By Glirk Dient in forum A Brief History of Cprogramming.com
    Replies: 14
    Last Post: 08-20-2005, 10:23 PM