Adding very large integers in 8 Bit BASIC
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
to
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$="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"
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