Adding two gigantic numbers [C++]

sigmend

[H]ard|Gawd
Joined
Aug 6, 2003
Messages
1,303
I have two text files, they all have 0.[alot of numbers]. I need to add these two numbers.
I don't have a good idea how to do this. I can think of a way to do it really inefficiently, but it won't do. I was thinking that I could load the files into an array, every 4 or so numbers would be a entry, then start at the end of both arrays and add, carrying the needed stuff, which I think would be within my ability to do.
The real problem is that each file has well over 1 billion digits, and loading 1.8 gigabytes into memory really isn't an option on anything but my dev box. Maybe I could load bits of it in at a time, but I don't know how to do this. Start at the end of the file then read backwards 10k digits or something. But again, I don't have a clue how to do this.
What would be a sane way (if any) of doing this?!?

Also, I don't want to use GMP or other maths libraries besides math.h. I'm doing this as a programming exercise.

fake edit: Rereading my post I see that it could come off as asking for help with homework, which I am not. I'm doing this for Physics club at my HS, not for a grade. The larger goal behind all of this is to be able to calculate Pi to an arbitrary digit.
I'm using the formula at http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibpi.html under the section "Gregory's series and Pi".
I've already written the devision operation (Its where I get the huge text files), but I am having trouble with the addition part
 

mikeblas

[H]ard|DCer of the Month - May 2006
Joined
Jun 26, 2004
Messages
12,776
sigmend said:
The real problem is that each file has well over 1 billion digits, and loading 1.8 gigabytes into memory really isn't an option on anything but my dev box. Maybe I could load bits of it in at a time, but I don't know how to do this. Start at the end of the file then read backwards 10k digits or something. But again, I don't have a clue how to do this.
What would be a sane way (if any) of doing this?!?

The files are just text, then?

0.2468...
0.1369...

and so on, right? Are they the same length? Just two files? A stream of digits, no line breaks?

The big problem is that you naturally want to start adding from the right hand side. You'll read the file backward, essentially, then just add the digits one by one, handling the carry.

If you knew there were only 100 digits to add, and you had them in two arrays, you'd know how to handle the problem, right? The only thing for handling 200 digits by doing 100 digits twice is that the second time through the carry might not be initially zero.

Maybe you can approach it by breaking it down into the functions you'll need:

read the next (previous, really) block of 100 digits
add a block of 1000 digits
write the result of an addition block

You'll also have to reverse the digits in the result.

Do you want code, or do these hints help?
 

ekliptikz

Limp Gawd
Joined
Jul 29, 2002
Messages
259
train a team of monkeys to read numbers and use an abacus


computers are overrated
 

Fryguy8

[H]ard|Gawd
Joined
Sep 26, 2001
Messages
1,707
I wrote a Giant Number implementation for a school project last year. The code is somewhat half-assed, but would give you plenty of basis for doing what you want.

IM me xxfryguy on aim if you want it.
 
Top