Quick divisibility check in ZX81 BASIC

Question

Since many of the Project Euler problems require you to do a divisibility check for quite a number of times, I've been trying to figure out the fastest way to perform this task in ZX81 BASIC.

So far I've compared (N/D) to INT(N/D) to check, whether N is dividable by D or not.
I have been thinking about doing the test in Z80 machine code, I haven't yet figured out how to use the variables in the BASIC in the machine code.

How can it be achieved?

Answer 1

Don't know if RANDOMIZE USR is available in ZX81 but I think it can be used to call routines in assembly. To pass arguments you might need to use POKE to set some fixed memory locations before executing RANDOMIZE USR.

I remember to find a list of routines implemented in the ROM to support the ZX Basic. I'm sure there are a few to perform floating operation.

An alternative to floating point is to use fixed point math. It's a lot faster in these kind of situations where there is no math coprocessor.

You also might find more information in Sinclair User issues. They published some articles related to programming in the ZX Spectrum

Answer 2

You can do this very fast in machine code by subtracting repeatedly. Basically you have a procedure like:

set accumulator to N
subtract D
if carry flag is set then it is not divisible
if zero flag is set then it is divisible
otherwise repeat subtraction until one of the above occurs

The 8 bit version would be something like:

DIVISIBLE_TEST:
LD B,10
LD A,100

DIVISIBLE_TEST_LOOP:
SUB B
JR C, $END_DIVISIBLE_TEST
JR Z, $END_DIVISIBLE_TEST
JR $DIVISIBLE_TEST_LOOP

END_DIVISIBLE_TEST:
LD B,A
LD C,0
RET

Now, you can call from basic using USR. What USR returns is whatever's in the BC register pair, so you would probably want to do something like:

REM poke the memory addresses with the operands to load the registers
POKE X+1, D
POKE X+3, N
LET r = USR X
IF r = 0 THEN GOTO isdivisible
IF r <> 0 THEN GOTO isnotdivisible

This is an introduction I wrote to Z80 which should help you figure this out. This will explain the flags if you're not familiar with them. There's a load more links to good Z80 stuff from the main site although it is Spectrum rather than ZX81 focused.

A 16 bit version would be quite similar but using register pair operations. If you need to go beyond 16 bits it would get a bit more convoluted.

How you load this is up to you - but the traditional method is using DATA statements and POKEs. You may prefer to have an assembler figure out the machine code for you though!

Answer 3

Your existing solution may be good enough. Only replace it with something faster if you find it to be a bottleneck in profiling.

(Said with a straight face, of course.)

And anyway, on the ZX81 you can just switch to FAST mode.

Answer 4

You should place the values in some pre-known memory locations, first. Then use the same locations from within Z80 assembler. There is no parameter passing between the two.

This is based on what I (still) remember of ZX Spectrum 48. Good luck, but you might consider upgrading your hw. ;/

Answer 5

The problem with Z80 machine code is that it has no floating point ops (and no integer divide or multiply, for that matter). Implementing your own FP library in Z80 assembler is not trivial. Of course, you can use the built-in BASIC routines, but then you may as well just stick with BASIC.