Operation with long_numbers

[draqula]

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...

[ovidiucucu]

[ Redirected thread ]

[jeffrey@toad.net]

Hi draqula,

If you want to study the algorithms, see Knuth's The Art of Computer Programming, Seminumerical Algorithms (http://www-cs-faculty.stanford.edu/~knuth/taocp.html).

If you want an implementation, I prefer Crypto++ (http://www.cryptopp.com/). An implementation of Knuth can be found here (http://www.di-mgt.com.au/bigdigits.html).

For a tutorial on using the CryptoPP::Integer, see A Big Integer Package for Use in Visual Basic Written in Visual C++ (http://http://www.codeguru.com/Cpp/Cpp/algorithms/math/article.php/c10609). The article is a COM wrapper, but the mathematical operations are the same.

Jeff

[draqula]

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++?

[RoboTact]

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

[draqula]

What do you mean by that??

[draqula]

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??

[RoboTact]

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.

[draqula]

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...