Dealing with large numbers in computing has been an attractive problem area for a long time. Using an average calculator might lead you to believe that it's too tricky for most applications.
But it's not that difficult. And to prove it, we're going to implement this calculation on machines with 8 Bit registers (I mean, cmon, on this site, you can't even pretend to be shocked).
Big numbers with the wheat and chessboard problem
A classic math exercise is called the wheat and chessboard problem.
If a chessboard were to have wheat placed upon each square such that one grain were placed on the first square, two on the second, four on the third, and so on (doubling the number of grains on each subsequent square), how many grains of wheat would be on the chessboard at the finish?
We can do this with simple addition. As a review, the largest 32-bit integer is 232 or 4,294,967,296. After that many digits calculators, and even languages, default to scientific notation. Something like:
Let's visualize what we're going to build in assembly in an easy to read language:
grains_sum = UInt64(0) grains = UInt64(1) wheat_mass = 65 # assume 65 mg per "grain" for square in range(1, 64) grains_sum += grains println("square $(square) grains $(grains) total $(grains_sum)") grains *= 2 end total_mass_kg = UInt128(fld(grains_sum * wheat_mass,1000)) println("$(total_mass_kg) kg")%
Pretty easy. Loop 64 times, add the number of grains to the previous and double the current for the next loop.
You might think this would be difficult on an 8 Bit processor, but it's not. To add two 8-bit numbers together, we simply add with carry the low byte and then do it over and over for the next 7 bytes. The carry bit moves on down with our addition. Easy peasy.
Fortunately, the problem we've chosen to tackle here is a multiply by two, which any computer going back to the 1960s can do pretty easily. Binary multiply and divide are just shifting left (multiply by 2) and shifting right (divide by two). Jim Butterfield's fantastic "Machine Language for the Commodore" has an excellent set of graphics to help visualize what we're doing here:
So to implement our 8-byte multiplier:
The tricky part here is actually the printing of the hex to decimal. Fortunately, we can get a head start/boost using "Graham's" 32-bit converter on Codebase64. Such an elegant solution Graham!
I've expanded Graham's solution to work on 8 bytes (64 bits) which happens to be exactly what we need.
So how'd it turn out?
Where do we go from here. Well, now that we can output up to 21 digits easily, we can multiply large numbers together.
mult32 .block lda #$00 sta product sta product+1 sta product+2 sta product+3 sta product+4 sta product+5 sta product+6 sta product+7 ; set binary ct 32 ldx #$20 shiftr lsr multiplier+3 ror multiplier+2 ror multiplier+1 ;divide multiplier by 2 ror multiplier bcc rotater lda product+4 ; get upper half of product ; and add multiplicand clc adc multiplicand sta product+4 lda product+5 adc multiplicand+1 sta product+5 lda product+6 adc multiplicand+2 sta product+6 lda product+7 adc multiplicand+3 rotater ror a ; rotate partial prod sta product+7 ror product+6 ror product+5 ror product+4 ror product+3 ror product+2 ror product+1 ror product dex bne shiftr rts .bend
Sometime over the next week, I'm going to try this on the KIM-1. If you try this on another platform, please let me know!