CODEWITHSUNDEEP
c++integerabstract-data-type
user2271933
user2271933

Reputation: 491

ADT Integer class questions

I am pretty new to programming and I have to do an Abstract Data Type (ADT) for integer numbers.

I've browsed the web for some tips, examples, tutorials but i couldn't find anything usefull, so i hope i will get here some answers. I thinked a lot about how should i format the ADT that stores my integer and I'm thinking of something like this:

int lenght; // stores the length of the number(an limit since this numbers goes to infinite)
int[] digits; // stores the digits of my number, with the dimension equal to length

Now, I'm confused about how should i tackle the sign representation.Is it ok to hold the sign into an char something like: char sign?

But then comes the question what to do when I have to add and multiply two integers, what about the cases when i have overflows on this operations.

So , if some of you have some ideas about how should I represent the number(the format) and how should I do the multiply and add i would be very great full. I don't need any code, I i the learning stage just some ideas. Thank you.

Upvotes: 0

Views: 372

Answers (2)

user1196549
user1196549

Reputation:

The first design decision you have to make is the choice of a basis.

You seem to lean towards plain decimal. Could be unpacked (one full byte per digit, numerical or ASCII representation), or packed digits pairs (Decimal Coded Binary, twice four bits in a byte).

Other schemes are more convenient for faster operations: basis being a power of 2 or a power of 10, fitting in a byte, a short, an int...

Powers of 10 have the benefit that conversion to and from base 10 can be done word by word.

Addition is an easy matter: add the words in pairs and handle the carries. Same for subtraction, with borrows.

Multiplies are a whole different story if you care about efficiency. The method of written computation taught at school can be used, but it requires length1 x length2 operations. For long numbers, more efficient methods are preferred (http://en.wikipedia.org/wiki/Multiplication_algorithm#Karatsuba_multiplication). They are also more complex.

Upvotes: 1

Robert Mason
Robert Mason

Reputation: 4039

One good way to do this is to store the sign as a bool (e.g. bool is_neg;). That way it's completely clear what that data means (vice with a char, where it's not entirely clear.

You might want to store each digit in an unsigned short (or if you want to be precise about sign, uint16_t). Then, when you do a multiply of two digits, you can just multiply them as unsigned ints (uint32_t), and then the low 16 bits are your result and the overflow is in the high 16 bits. You can then add this to the result array fairly easily. You know that the multiplication of a n-bit number by a k-bit number is at most n + k bits long, so you can preallocate your array to that size and then worry about removing extra zeros later.

Hope this helps, and let me know if you want more tips.

Upvotes: 2

Related Questions