How do you store an arbitrarily large integer value in memory?
Solution 1
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
numby two? - How would you multiply a
numby a single digit? - How would you multiply a
numby 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
numto represent negative numbers as well as positive? - How do you divide one
numby 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.
Solution 2
Possible solutions:
1) Define custom integer type that is large enough to hold that value. 128-bit integer is large enough to hold 98474737475747374739399.
2) Use any available bignum library.
Solution 3
I won't give you the code, but I can make a couple of suggestions for approaches to take:
- Try storing the value as a character string and converting to perform calculations
- Try breaking the value up into multiple integers representing a portion of the value
- Look up existing libraries that may take care of this for you
Good luck
Solution 4
Robert Lafore - Object-Oriented Programming in C++, 4th Edition :
// verylong.cpp
// implements very long integer type
#include "verylong.h" //header file for verylong
//--------------------------------------------------------------
void verylong::putvl() const //display verylong
{
char temp[SZ];
strcpy(temp,vlstr); //make copy
cout << strrev(temp); //reverse the copy
} //and display it
//--------------------------------------------------------------
void verylong::getvl() //get verylong from user
{
cin >> vlstr; //get string from user
vlen = strlen(vlstr); //find its length
strrev(vlstr); //reverse it
}
//--------------------------------------------------------------
verylong verylong::operator + (const verylong v) //add verylongs
{
char temp[SZ];
int j;
//find longest number
int maxlen = (vlen > v.vlen) ? vlen : v.vlen;
int carry = 0; //set to 1 if sum >= 10
for(j = 0; j<maxlen; j++) //for each position
{
int d1 = (j > vlen-1) ? 0 : vlstr[j]-'0'; //get digit
int d2 = (j > v.vlen-1) ? 0 : v.vlstr[j]-'0'; //get digit
int digitsum = d1 + d2 + carry; //add digits
if( digitsum >= 10 ) //if there's a carry,
{ digitsum -= 10; carry=1; } //decrease sum by 10,
else //set carry to 1
carry = 0; //otherwise carry is 0
temp[j] = digitsum+'0'; //insert char in string
}
if(carry==1) //if carry at end,
temp[j++] = '1'; //last digit is 1
temp[j] = '\0'; //terminate string
return verylong(temp); //return temp verylong
}
//--------------------------------------------------------------
verylong verylong::operator * (const verylong v) //multiply
{ //verylongs
verylong pprod; //product of one digit
verylong tempsum; //running total
for(int j=0; j<v.vlen; j++) //for each digit in arg
{
int digit = v.vlstr[j]-'0'; //get the digit
pprod = multdigit(digit); //multiply this by digit
for(int k=0; k<j; k++) //multiply result by
pprod = mult10(pprod); // power of 10
tempsum = tempsum + pprod; //add product to total
}
return tempsum; //return total of prods
}
//--------------------------------------------------------------
verylong verylong::mult10(const verylong v) const //multiply
{ //arg by 10
char temp[SZ];
for(int j=v.vlen-1; j>=0; j--) //move digits one
temp[j+1] = v.vlstr[j]; // position higher
temp[0] = '0'; //put zero on low end
temp[v.vlen+1] = '\0'; //terminate string
return verylong(temp); //return result
}
//--------------------------------------------------------------
verylong verylong::multdigit(const int d2) const
{ //multiply this verylong
char temp[SZ]; //by digit in argument
int j, carry = 0;
for(j = 0; j<vlen; j++) //for each position
{ // in this verylong
int d1 = vlstr[j]-'0'; //get digit from this
int digitprod = d1 * d2; //multiply by that digit
digitprod += carry; //add old carry
if( digitprod >= 10 ) //if there's a new carry,
{
carry = digitprod/10; //carry is high digit
digitprod -= carry*10; //result is low digit
}
else
carry = 0; //otherwise carry is 0
temp[j] = digitprod+'0'; //insert char in string
}
if(carry != 0) //if carry at end,
temp[j++] = carry+'0'; //it's last digit
temp[j] = '\0'; //terminate string
return verylong(temp); //return verylong
}
Verylong class header
// verylong.h
// class specifier for very long integer type
#include <iostream>
#include <string.h> //for strlen(), etc.
#include <stdlib.h> //for ltoa()
using namespace std;
const int SZ = 1000;
//maximum digits in verylongs
class verylong
{
private:
char vlstr[SZ]; //verylong number, as a string
int vlen; //length of verylong string
verylong multdigit(const int) const; //prototypes for
verylong mult10(const verylong) const; //private functions
public:
verylong() : vlen(0) //no-arg constructor
{ vlstr[0]='\0'; }
verylong(const char s[SZ]) //one-arg constructor
{ strcpy(vlstr, s); vlen=strlen(s); } //for string
verylong(const unsigned long n) //one-arg constructor
{ //for long int
ltoa(n, vlstr, 10); //convert to string
strrev(vlstr); //reverse it
vlen=strlen(vlstr); //find length
}
void putvl() const; //display verylong
void getvl(); //get verylong from user
verylong operator + (const verylong); //add verylongs
verylong operator * (const verylong); //multiply verylongs
};
Solution 5
This is a common question in introductory computer science classes at university. The primary areas of focus are a) understanding how (integer) numbers are stored as binary digits, and b) the basics of data structures, where if a programming language does not provide the desired data structure itself, you can use meta or collection structures, such as struct in C, class in C++, or record in Pascal.
So how is a smaller integer stored in a computer? In C, you have data types char, short, int, long that can all be used to store integers of various sizes. (I'll ignore long long for this discussion.) Let's say for sake of generality that on a given 32-bit platform the sizes are 8-bit, 16-bit, 32-bit, and 64-bit respectively. Consider the values that can be represented (to simplify considered unsigned).
Now, how could you store a larger integer, that cannot be stored in an unsigned 64-bit long? Make your own large integer data type, comprised of multiple smaller (but standard) integers such that they represent larger values.
I think this should point you in the right direction, and enable you to write your own answer to your homework or exam question.
Admin
Updated on June 08, 2020Comments
-
Admin almost 4 years
I have to store an integer value that is larger than the maximum value for the long datatype. How would I store and manipulate this value in memory?
Please illustrate it through an example, if possible.
-
PP. about 14 yearsParticularly if this is for an exam, I would recommend you think about how you performed math in primary school. You know, add, carry the 1, subtract, take away 10, etc. If you can't do these operations on a character string, you failed primary school, and consequently failed computer science at university.
-
Bill Forster about 14 yearsSorry, but until you fix this it is a candidate for the most confusing answer ever.
-
Paolo Di Pietro about 14 yearsThanks for pointing that out, I should always re-read. However the question is rather confusing too.
-
Kos over 13 yearsA good description. And after that: Use base-256 instead of base-10 on that array. :)
-
phuclv almost 10 years@Kos using base 2^32 (or 2^64 if on 64-bit systems) is much better -
Dale Hagglund almost 10 years@LưuVĩnhPhúc, working with the base 2^32 (or base 2^64) can be awkward in C, because there's no efficient way to detect the carry bit being set after adding two "digits". In raw assembler, this check would be easy, of course, or with in-line assembler in your C program. However, I suspect it's a bit beyond where the OP would be comfortable, at least at this point in time.
-
phuclv almost 10 years@DaleHagglund It's not much that difficult. There are lots of arbitrary precision library written in C. For unsigned addition it's a simple comparison, you can find numerous examples of that on this site. For signed addition it's a bit more tricky but can still achived within 1 line using bitwise operations. If you need speed, that's another matter.
-
phuclv almost 10 yearshowever, in 2's complement you can use the same procedure for both signed and unsigned addition/subtraction so it's actually very easy. You can find the solutions here stackoverflow.com/questions/22126073/multiword-addition-in-c
-
phuclv over 7 yearssome examples to get carry flag efficiently in C stackoverflow.com/q/10959725/995714 stackoverflow.com/q/6659414/995714
-
phuclv over 7 yearsStoring decimal digits like this may be enough for an exam but in real computations it'll be inefficient. Bigint libraries use digits in base 2^64 (or base 2^32 in a 32-bit computer) instead
-
rene almost 5 yearsFrom the question I have to store an integer value that is larger than the maximum value for the long datatype ... your answer at best wins a single bit.
