I have been looking for two days now to find a z80 ASM routine that multiplies two 24 bit numbers to get a 48 bit result.

I need it because I want to try and make a Mandelbrot set generator for the Ti84+ using Q2.21 Fixed Point numbers.

Now I would try to come up with one myself but if anyone knows of an existing one I'd like to know!

Thanks

Welcome back, Cerzus! It's been far too long since I've seen you around here; how's life? Did you see that Benumbered is one of the candidates for the 2011 POTY at ticalc.org?
Hmm, z80 Bits goes up as high as 16x16, so theoretically you could apply that 16 times, could you not?

Possible, but that would not be very efficient now would it? I know there must be a better way and in fact I posed the same question at Omnimaga and got someone to come up with a code fragment so I might have what I need. Need to check it first though...

Still there may be another optimized version somewhere out there.[/quote]

Well, since you can't get faster than one iteration per a bit, as far as I can figure out, applying a 16x16 multiply 16 times would be the fastest thing to do in my opinion. If you had enough registers, you could probably collapse it to 8 iterations through, but we have a serious lack of registers, of course.

Give me some time to let your reply sink in and have me understand it, please.

Perhaps I should start by asking how well you understand some of the smaller multiplication routines on z80 bits, then, before I inundate you too much with synthesizing your own routine based on their concepts.

Let's say I understand the theory behind bitwise multiplication. The implementation of the 8*8 routine is clear to me, 16*16 is a little harder and you saying just doing the 16bit routine 16 times kind of made sense to me, but to be honest I haven't delved too deep into the subject to completely understand it.

Why do you need such precise values? Are you planning to support extreme levels of zoom in your program?

Instead of 24-bit fixed-point values, could you use 24-bit floating point numbers? You could have a 1-bit sign, 7-bit exponent, and 16-bit significand (1.7.16 minifloat). Multiplying 16-bit values is easier and faster with the limited number of registers found on the z80, and the exponent will give you a much larger range of values. Such a floating-point value would be more precise, too, once the top 8 bits of the fixed-point value become zero (both will have 16 bits of precision at that point). This happens when it's less than 0.03125.

(Incidentally, this 1.7.16 floating-point format is the same as that used by some Radeon GPU's: http://en.wikipedia.org/wiki/Minifloat)

You may even be able to get away with an 8-bit significand (1.7.8 minifloat), but that would probably give you a lot of visible artifacts in your fractals at all zoom levels (but it would be faaaast!).

I'm quite familiar with working with floating-point values, so I can help out a bit if you want to go this route. It's really not much more difficult to work with than fixed-point (unless you want to implement all rounding modes, subnormal numbers, infinities, not-a-numbers, exceptions, flags, and other such goodies as found in the IEEE 754 standard but which are not needed for this application).

Tkank you christop for your elaborate response.

21 bits for decimals is not extremely precise in my opinion. 13 bits (as in a Q2.13 format) would give me a max zoom of 341.33.. (using 96 pixels and a range of real [-2, +2] at zoom 1). In that case the difference per pixel at max zoom is 0.0001220703125, which is the smallest number representable with 13 bits. Next step up would be 2 times that amount per pixel. Logically that would be zoom 170.66.. and there wouldn't be any other zoom levels available between those two.
I'd like to have a little more room hence those extra 8 bits.

On the other hand I think the minifloats you are talking about could very well be a better solution. As long as operations on them are reasonably fast of course.

I am still working on Q2.13 at the moment, but I will definitely have a look at minifloats.

Okay, so now I've got 3 iterate functions that return the number of mandelbrot iterations for numbers between -4 and + 4. They are for Q2.5, Q2.13 and Q2.21 fixed point formats.
The 24-bit multiplication I am using for the last one is courtesy of jacobly at omnimaga:

Code:

Thought I'd share it here for any future use.

Now, I'm on to taking a look at (half precision) floats and see if I can get their speed and accuracy at a nice balance to compete with fixed point numbers.

I take issue with the slowdown from using iy+asm_flag1; I'm trying to think what might be better there...

Hey, at least it's a lot faster than 16 times the 16*16 multiplication! But, please, tell if you come up with something.

EDIT: I do understand the routine now though, just so you know.