Mandelbrot in 14 seconds, no multiply

DINO draws the Mandelbrot set. It’s a 490-byte RAM program, loaded over serial with the monitor’s L and started with G 8100. It draws 80 columns by 33 rows and gives you the prompt back. I timed it at 14 s on a 1.024 MHz clock, and about 3 s of that is just the characters going out at 9600 baud.

Doing the math without a multiply

DINO has no multiply, no shift right, and no add-with-carry. The ALU’s carry-in is wired to the opcode, and the control word bit that was meant to switch it to the carry flag isn’t connected to anything. So two-byte arithmetic would mean branching on carry for every add, and a software multiply on top of that. I worked it out on paper first and ended up with everything in one byte.

Numbers are 1/32 steps, offset by 64. A value v is stored as v*32 + 64, so 0.0 is 64 and anything from just over -2 to just under +2 fits in 1..127. That makes every “did it escape” check an unsigned compare. A CPI 128 with JNC or the borrow out of a SUB is all it takes, and signs never have to be handled in the arithmetic itself.

Squares come out of a table. S[n] = n²/32 gives x² directly. For the cross term I used the old quarter-squares trick: (a+b)² - (a-b)² = 4ab, so with Q[n] = n²/64,

2|x||y| = Q[|x|+|y|] - Q[||x|-|y||]

and the sign of 2xy is just sign(x) XOR sign(y), kept in one byte. One iteration is six table lookups and a handful of adds and compares.

The ranges were picked so nothing overflows where it matters. S[|x|] + cx tops out at 203. S[|x|] + S[|y|] tops out at 248. The only sum that can carry is the y update, and that carry is itself the escape test. Q’s index goes up to 126, so Q starts at 0x8680 and never crosses a page. That matters because indexing is MOVCA / LDBI page / LDAX, and there’s no 16-bit add to fix up a page crossing.

DINO builds the tables itself. Nothing gets typed in. It keeps n² as a running sum, 64q + r, adding n and then n-1 (each add stays under 256) and folding r into q in 64s. Then Q[n] = q and S[n] = 2q + (r >= 32).

The cost of one byte is resolution. A 1/32 grid is coarse, and the edge of the set comes out blobby. I checked the integer scheme against an ordinary floating-point Mandelbrot on the same grid, and they disagree on inside/outside for 50 of the 2640 cells (1.9%), all on the boundary.

One iteration

This is the whole inner loop after |x|, |y| and the sign have been worked out:

squares:  LDA   AX
          MOVCA
          LDBI  STAB
          LDAX
          STA   SA              ; S[ax]
          LDA   AY
          MOVCA
          LDBI  STAB
          LDAX
          STA   T               ; S[ay]
          LDB   SA
          ADD
          CPI   128
          JNC   new_x
          JMP   esc

; ---- x' = x^2 - y^2 + cx
new_x:    LDA   SA
          LDB   COL
          ADD                   ; S[ax] + cxo, at most 203
          LDB   T
          SUB                   ; - S[ay]
          JNC   esc             ; borrow: x' < -2
          CPI   128
          JNC   x_hi_ok
          JMP   esc             ; x' >= 2
x_hi_ok:  CPI   0
          JNZ   x_ok
          JMP   esc             ; x' = -2
x_ok:     STA   XO              ; old x is done with: AX, AY, SGN hold it

; ---- |2xy| = Q[ax+ay] - Q[|ax-ay|]
          LDA   AX
          LDB   AY
          ADD
          ADI   QOFF
          MOVCA
          LDBI  STAB
          LDAX
          STA   SA              ; Q[ax+ay]
          LDA   AX
          LDB   AY
          SUB
          JNC   d_neg           ; ax < ay
          JMP   d_abs
d_neg:    LDA   AX
          LDB   AY
          BSUB                  ; A = ay - ax
d_abs:    ADI   QOFF
          MOVCA
          LDBI  STAB
          LDAX
          STA   T               ; Q[|ax-ay|]
          LDA   SA
          LDB   T
          SUB
          STA   T               ; |2xy|

; ---- y' = 2xy + cy
          LDA   SGN
          CPI   0
          JNZ   y_minus
          LDA   ROW
          LDB   T
          ADD
          JNC   y_plus_ok
          JMP   esc             ; carried: y' >= 2
y_plus_ok: CPI  128
          JNC   y_ok
          JMP   esc             ; y' >= 2
y_minus:  LDA   ROW
          LDB   T
          SUB
          JNC   esc             ; borrow: y' < -2
          CPI   0
          JNZ   y_ok
          JMP   esc             ; y' = -2
y_ok:     STA   YO

DINO only branches when a flag is clear (JNZ, JNC), so “escape if set” is a JNC over a JMP. Every immediate ALU op and every INR/DCR/SHL loads its constant through B, so nothing that matters lives in B for long. Every value worth keeping goes to a RAM cell. The full source is asm/ram/mandel.asm in the repo.

Tested before it touched the machine

The host test loads the program through the real monitor image in the Python oracle, the same L and G the bench uses. The output has to match a Python model of the same arithmetic byte for byte, under both the old polling monitor and PROG_imon. My first version kept its variables at 0x80D0, which is inside imon’s stack, so they moved to 0x8700, and there’s now a test that keeps them out of 0x80A0-0x80FF. On the machine it ran first time.

Open

• The ramp sits in RAM at 0x8103, so W 811B,23 changes the inside character without a reload. Nobody has tried it on the bench yet.
• Zooming in needs more than 1/32 resolution, which means two-byte values. Without ADC that’s a branch on every carry, roughly 4x slower by my estimate. ADC costs a ‘157.
• The plot is symmetric about y = 0. Computing only half would nearly halve the 11 s of compute, but the rows go out top to bottom, so the half would have to be buffered.