Adding very large integers in 8 Bit BASIC

By Michael Doornbos

July 15, 2022 - 3 minutes read - 541 words

As we’ve discussed, large integer math is a pretty interesting problem, even for modern computers.

What if we wanted to add very, very, very large integers without using scientific notation, but this time let’s do it extra slowly. Extra slow… this seems like a job for BASIC!!

Strings

We’re going to need to use strings. On the Commodore BASICs of the 80s, strings have a max length of 255, so the largest sum we’ll be able to represent is:

9999999999999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999

That’s… a large number.

Yes, there are interesting ways to use string pointers to make much longer strings in BASIC, but for now, let’s stick to the built-in defaults. It’s already too long for Wolfram Alpha.

Let’s Code

Setup

We’re going to add:

98587518550502192097031006776933719884110139086568645137100350710251433881496023001109113974270671309633787404745541339750716077156740262234504640022600388928075977475692052478192953980072903492891166507195010182212748470877114763949693664888859937748596

53790661810213889520858337790205023839288911641850081520399857719579236428169601022227319557417217405084175344187287691086727370333531536625602807708733181965023743645615205252509637602700890294693520507609495844797945233313654250365590355765575121179501

It should be fun…

Padding

While not strictly necessary, we should pad the number with the least number of digits with leading zeros to remove any ambiguity if they are not the same length.

3000 rem pad strings
3105 if la=lb then return
3110 if la<lb then 3150
3120 p=la-lb:lb=la  
3130 for pa=1 to p
3140 sb$="0"+sb$
3145 next:return
3150 p=lb-la
3160 for pa=1 to p
3170 sa$="0"+sa$
3190 next:return

This gets skipped in line 3105 in our example since they are the same length, but it keeps the program flexible for all numbers this way.

Mod 10

We’ve talked about modulus before. Without using a built-in or defining a function (also a perfectly valid method for this) a mod b is:

r=a-int(a/b)*b

Easy enough. So we’re going to mod 10 and set a carry if the sum is > 9. Then we add the carry to the next addition.

2000 rem mod 10 
2020 a=val(mid$(sa$,i,1))+val(mid$(sb$,i,1)):b=10
2030 a=a+c:c=0:ifa>9thenc=1
2040 r=a-int(a/b)*b
2050 a$=mid$(str$(r),2)+a$ 
2999 return

Line length

The primary machine we’re testing, the Commodore PET 8032, has a max line length of 80 characters. We’ll need to break our 255 digits into 4 lines:

20 sa$="9858751855050219209703100677693371988411013908656864513710035071025143"
25 sa$=sa$+"388149602300110911397427067130963378740474554133975071607715674026"
30 sa$=sa$+"223450464002260038892807597747569205247819295398007290349289116650"
35 sa$=sa$+"7195010182212748470877114763949693664888859937748596"
40 sb$="5379066181021388952085833779020502383928891164185008152039985771957923"
45 sb$=sb$+"642816960102222731955741721740508417534418728769108672737033353153"
50 sb$=sb$+"662560280770873318196502374364561520525250963760270089029469352050"
55 sb$=sb$+"7609495844797945233313654250365590355765575121179501"

Add

And we just start on the right like you would if you were adding these on paper. Add the two digits and carry the 1 when necessary. Easy peasy.

How’d we do?

Commodore PET

Commodore 128

VIC-20

As expected, the fastest

Bigger?

Our method is simple and will keep working as long as you keep feeding inputs into it. Two methods I can think of to do larger than 255 digits:

use an array
Feed DATA statements from somewhere. A sequence file?

Whole listing

10 rem add two very large integers on commodore pet 
20 sa$="98587518550502192097031006776933719884110139086568645137100350
71025143"
25 sa$=sa$+"3881496023001109113974270671309633787404745541339750716077
15674026"
30 sa$=sa$+"2234504640022600388928075977475692052478192953980072903492
89116650"
35 sa$=sa$+"7195010182212748470877114763949693664888859937748596"
40 sb$="53790661810213889520858337790205023839288911641850081520399857
71957923"
45 sb$=sb$+"6428169601022227319557417217405084175344187287691086727370
33353153"
50 sb$=sb$+"6625602807708733181965023743645615205252509637602700890294
69352050"
55 sb$=sb$+"7609495844797945233313654250365590355765575121179501"
100 rem *****************************************
110 la=len(sa$):lb=len(sb$):c=0 : rem carry bit
120 gosub 3000
130 print sa$:print"+":printsb$
140 print "--------------------"
150 fori=lbto1step-1:gosub2000:next:print
160 if c=1 then a$="1"+a$ :rem last carry
170 print a$
180 end 
200 rem *****************************************
2000 rem mod 10 
2020 a=val(mid$(sa$,i,1))+val(mid$(sb$,i,1)):b=10
2030 a=a+c:c=0:ifa>9thenc=1
2040 r=a-int(a/b)*b
2050 a$=mid$(str$(r),2)+a$ 
2999 return 
3000 rem pad strings
3105 if la=lb then return
3110 if la<lb then 3150
3120 p=la-lb:lb=la  
3130 for pa=1 to p
3140 sb$="0"+sb$
3145 next:return
3150 p=lb-la
3160 for pa=1 to p
3170 sa$="0"+sa$
3190 next:return