Operation with long_numbers

OK, I couldn't find anything about this topic, so it's either that i'm not looking where I should, or i'm not looking for what i should. If there is such a topic on this forum, then the search tool sux :D.

Long doesn't stand for the numeric type LONG <aka 0-2^16-1>, but really long <aka many digits> numbers, which wouldn't fit in any numeric type. So these numbers are stored as arrays (1 dim: e.g. 1024 is stored in num: num[1]=1, num[2]=0, num[3]=2, num[4]=4).

My question is: does anyone have any idea about mathematical algorithms to use with such numbers?? (where to find info about that, or even already made)

Addition is easy: just add array elements and watch out for carry...
What about multiplication, or even more complex operations??

PS: yep, search tool not that reliable... found something on the 9th page of results...

[ Redirected thread ]

Hi draqula,

If you want to study the algorithms, see Knuth's The Art of Computer Programming, Seminumerical Algorithms.

If you want an implementation, I prefer Crypto++. An implementation of Knuth can be found here.

For a tutorial on using the CryptoPP::Integer, see A Big Integer Package for Use in Visual Basic Written in Visual C++. The article is a COM wrapper, but the mathematical operations are the same.

Jeff

Well, the thing is i have this project for school, implementing a calculator (something like WIN calc) that operates with long|large|big numbers (which is the right name??), and this has to be done using Visual C++ 6 (Visual Studio...), without VB, and without MFC...
The thing is i know almost NOTHING about such algorithms (dealing with big numbers)...
Not to mention i haven't been programming for quite some time, and not to mention i haven't done any Visual programming... :(

BTW: What is Crypto++?

In this case I guess "pencil-and-paper" algorithms would be enough.

What do you mean by that??

Does it mean I should implement the reasoning one does when he computes on paper?? Isn't it a bit difficult? Aren't there any algorithms??

There is not much of reasoning with calculation on paper, just algorithms. Apart from that, division may be implemented using bisection, that is to divide x=a/b you search a solution to equation x*b-a=0, keeping track of lower and upper bounds [x1, x2] on x and shifting bounds to either [(x1+x2)/2, x2] or [x1, (x1+x2)/2]. To implement this you'll only need division by 2, which is quite straightforward.

Yeah, well, ok, that sounds easy...
The thing is i'm not working with numbers... I mean that these numbers are stored as vectors/strings (i.e. 3415 - v[1]=3, v[2]=4, v[3]=1, v[4]=5, a.s.o)
THIS is where i got stuck...
How do I divide [3 4 1 5] by [1 2 5]?
This example is perhaps a fortunate one, 'cause you can transform the strings into the corresponding int/long/double. What if you have a really LONG number (10 digits at least)? What if you have 2 long numbers? That kind of algorithms I'm talkin' about...