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...
[918 byte] By [
draqula] at [2007-11-19 15:47:38]
# 2 Re: Operation with long_numbers
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.dev-archive.com/Cpp/Cpp/algorithms/math/article.php/c10609). The article is a COM wrapper, but the mathematical operations are the same.
Jeff
# 3 Re: Operation with long_numbers
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++?
# 7 Re: Operation with long_numbers
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.
# 8 Re: Operation with long_numbers
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...
