24 bit multiplication

[cerzus69]

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
_________________
cerzus69 edited a post

[KermMartian]

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?

[cerzus69]

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]
_________________
cerzus69 edited a post

[KermMartian]

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.
_________________

[cerzus69]

Give me some time to let your reply sink in and have me understand it, please.
_________________
cerzus69 edited a post

[KermMartian]

[cerzus69]

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.
_________________
cerzus69 edited a post

[christop]

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).
_________________
Christopher Williams

[cerzus69]

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.
_________________
cerzus69 edited a post

[cerzus69]

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:

[KermMartian]

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

[cerzus69]

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.
_________________
cerzus69 edited a post