How do you store an arbitrarily large integer value in memory?

by

Think about storing a numbers as sequences of decimal digits using a struct like this:

struct num {
    int ndigits;
    char d[MAXDIGITS];
};

For example, the number 123456 could be initialized as

struct num n = { 6, { 6, 5, 4, 3, 2, 1 } };

The reversed digit order turns out to be important for easy calculation. In particular, the place value of n.d[i] is n.d[i] * 10^i.

Now, a few questions:

  • How would you add one to a num?
  • How would you add an arbitrary single digit to a num?
  • How would you add two nums together?
  • How would you multiply a num by two?
  • How would you multiply a num by a single digit?
  • How would you multiply a num by 10?
  • How would you multiply two nums together? HINT: Do some pencil and paper multiplications and see how they work.

If you work through this sequence of questions, you should be able to write a function for each step, and re-use those functions to answer the later questions, and end up with a very simple and unoptimized long (well, up to MAXDIGIT digits) integer package for addition and multiplication of positive numbers.

Other questions:

  • How do you generalize num to represent negative numbers as well as positive?
  • How do you divide one num by another (ignoring remainders)? This is trickier than multiplication, but again, start by doing a few pencil and paper long divisions and think carefully about what you do.

More Related Contents:

  1. How to convert an int to string in C?
  2. Where in memory are my variables stored in C?
  3. Dividing 1/n always returns 0.0 [duplicate]
  4. How to allocate aligned memory only using the standard library?
  5. When you exit a C application, is the malloc-ed memory automatically freed?
  6. Check if input is integer type in C
  7. Is unsigned integer subtraction defined behavior?
  8. Catch and compute overflow during multiplication of two large integers
  9. How do I check if an integer is even or odd? [closed]
  10. How to dynamically allocate memory space for a string and get that string from user?
  11. What do numbers using 0x notation mean?
  12. SIMD signed with unsigned multiplication for 64-bit * 64-bit to 128-bit
  13. Print an int in binary representation using C
  14. Should I free char* initialized using string-literals?
  15. Why do we define INT_MIN as -INT_MAX – 1? [duplicate]
  16. How can I create a dynamically sized array of structs?
  17. Alloca implementation
  18. Is it good practice to free a NULL pointer in C? [duplicate]
  19. How do I free memory in C?
  20. Integer conversions(narrowing, widening), undefined behaviour
  21. Why does “memset(arr, -1, sizeof(arr)/sizeof(int))” not clear an integer array to -1?
  22. Force free() to return malloc memory back to OS
  23. C: pointer to array of pointers to structures (allocation/deallocation issues)
  24. malloc for struct and pointer in C
  25. How can I convert an int to a string in C?
  26. Is there any reason not to use fixed width integer types (e.g. uint8_t)?
  27. C usual arithmetic conversions
  28. memory allocation in Stack and Heap
  29. /proc/[pid]/pagemaps and /proc/[pid]/maps | linux
  30. Performance: memset

Leave a Comment