# 64 Bit Addition and Products on Commodore: The Wheat and Chessboard problem

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 2^{32} 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.

## Let's code

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.

### Multiply

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?

## Results

## Extra credit

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
```

## Have fun!

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!