Hexadecimals

[thomaselder84]

Hey guys and gals

I'm writing a program for class that gets a hexadecimal of any length from the user. The hexadecimal is to be stored on a linked list. So an input of say 4F3A6 would be 4->F->3->A->6

After the number is stored, the user can then either add or multiply another hexadecimal to the original number.

My first idea was to convert the two hexadecimals to decimals and then either add or multiply them. After that I would convert the sum or product back to hexadecimal. Converting it back seems very problematic though. Range checks of the value would need to be done to determine the number of hexadecimals digits to use, and then calculate them. This might work if I had an upper bound, but I don't. So, theoretically there could be an infinite number of hexadecimal digits.

If anyone has any experience with this type of problem and could recommend a good approach, I would really appreciate it.

Thanks.

[Duthomhas]

You are being asked to write a basic bignum.

There is no need to convert to decimal. (So don't do that. It is distracting you from the real problems you should be solving.)

Remember, the radix of a number is for humans to read. Hexadecimal numbers have 16 digits: 0..9,A..F. So if you have D+2, the answer is F. likewise, F+1 is 10 (just like 9+1 in decimal is 10).

First write yourself a function to add two hex numbers together. You'll have to do it just like in gradeschool. Add corresponding columns, left to right, and remember to carry.

After that you can write your multiplication function. Use a loop to add the first number to itself the second number number of times.

If you wish, there are more efficient algorithms to multiply bignums, but they aren't entirely simple or obvious. Katsuraba's is a good one. I am partial to Malenkov's. For a simple homework, though, the simple loop should be fine.

Hope this helps.

[ultifinitus]

Working with individual hexadecimal pods (each of the items in your linked list) just like you would if you were to work the problem out on paper would be one way to do it, a bit tedius perhaps, but doing things that way would actually make your project useful (and perhaps a bit inefficient) If you're unsure about how you would do that on paper, just consider the hexidecimal individual units are just like decimal units but they "wrap around" at 15 instead of 9.

In other words, adding is easy

1 ... f ... +
3 ... 3 ... 
________
5 ... 2


f+3= 12 (f is the last digit in hexidecimal, so it goes f, 10, 11, 12) , carry the 1

1 + 3 + 1 (carried) = 5

The end result:
1f + 33 = 52

so working from right to left in your linked list, you can add just like you did back in primary school. The result would be another linked list.

Multiplication is even more fun :)

I believe in you! Good luck!