Adding big numbers

teammatt3 posted this at 02:45 — 22nd January 2009.

Joined: Sep 2003

How would you add two huge natural numbers as strings? Like "9999999999999999999999999" + "1"?

I wrote an algo to do it in PHP, and it takes about 70 seconds to add 1 to a number with 207,360 digits. I use the algo I was taught in elementary school (add each column, and carry a 1 if necessary). Can you think of something better?

This isn't for anything important. I was curious about how computers perform addition on massive numbers.

decibel.places posted this at 05:32 — 22nd January 2009.

He has: 1,494 posts

Joined: Jun 2008

well, I am not familiar with the flips and flops of the digital circuits, if that is what you mean...

couldn't you typecast the strings as integers?

In JavaScript you would just eval(string1 + string2)

I think in PHP you can add "0" to convert a numerical string into an integer as in

$string1 = "9999999999999999999999999";
$string2 = "1"; 
$int1 = 0+$string1;
$int2 = 0+$string2;
$total = $int1 + $int2;

for $total I get 1.0E+25

there are some more methods to type strings as integers here such as int($string)

teammatt3 posted this at 06:20 — 22nd January 2009.

He has: 2,102 posts

Joined: Sep 2003

I'm talking about huge numbers that are outside the bounds of normal numbers in programming languages.

I just looked at GMP functions in PHP and the addition of a number with 207,360 digits and a 1 only took a second. Anyone know how they do it?

I suppose I could look at their source...