0

I have a project to compute 64 bit unsigned integer addition, multiplication and subtraction using only 32 bit signed/unsigned integers in c. The 64 bit unsigned integer is newly defined like this :

typedef struct {
unsigned integer hi;
unsigned integer lo;
} Integer64;

so 64 bit integer is just a struct that stores the upper 32 bit in high and the lower 32 bit in low.

Now I get these two Integer64 and I have to produce the multiplication and subtraction in Integer64 type as well. In multiplication and subtraction function, I am only allowed to use Integer64 type, unsigned int type, and only integer arithmetic and logical operations.

I solved how to write addition function, but I have no clue how to do multiplication and subtraction. Can you guys help?

jimhark
  • 4,938
  • 2
  • 27
  • 28
outofthewoods
  • 11
  • 1
  • Have you tried using strings for storing large integers and then multiplying them? – Gaurav Sep 22 '18 at 13:20
  • unfortunately I am not allowed to use string types either – outofthewoods Sep 22 '18 at 13:22
  • 1
    How do you multiply two-digit decimal numbers by each other when you have only memorized a multiplication table for one-digit numbers? Everybody is taught a way of doing that in elementary school. The same method that works in base 10 works in base 65536 or base 4294967296. – Eric Postpischil Sep 22 '18 at 13:31
  • only in this case you need to find a way to store and manage the overflow.that is the problem – outofthewoods Sep 22 '18 at 13:44
  • 3
    Use base 65536. – Eric Postpischil Sep 22 '18 at 15:21
  • This https://stackoverflow.com/questions/1815367/catch-and-compute-overflow-during-multiplication-of-two-large-integers deals with multiplication of 64 bit integers with 128 bit result, but he solution is the same, just different data types. – Clifford Sep 22 '18 at 18:13
  • 1
    Type/variable names can't start with a number. Maybe call it `struct u64`. Don't use `uint64_t`; that's already defined by ISO C as being a 64-bit integer type which is only defined by implementations that support it. (But typically defined as either `unsigned long long` or `unsigned long`). – Peter Cordes Sep 22 '18 at 23:01
  • 1
    You can't do this efficiently on most architectures. Most have widening multiplication of 32b x 32b => 64b, but the only way to express that in C is `a.lo * (unsigned long long)b.lo`, or with an intrinsic / built-in. With portable C and no type wider than 32-bit, you'll have to build an extended-precision 64-bit multiply out of 16x16 => 32b chunks, like Eric said. That probably won't optimize, so you never want to do this in practice. – Peter Cordes Sep 22 '18 at 23:13
  • 1
    It might be useful to look at how real compilers do 64x64 => 64b on a 32-bit architecture like MIPS or i386, using 1 widening multiply and 2 `lo*hi` https://godbolt.org/z/T_UzGk. Of course this doesn't end up needing an add-with-carry (which is easy in asm but hard in C). – Peter Cordes Sep 22 '18 at 23:14
  • 1
    If you're doing this with only pure ISO C, then the [tag:cpu-architecture] tag doesn't apply. Normally this is done in asm, because like I said it generally sucks in C, especially trying to do add-with-carry when there's a carry-in and a carry-out. – Peter Cordes Sep 23 '18 at 09:13

0 Answers0