🚀 go-pugleaf

berenfie@tortoise.cis.ohio-state.edu (gregory neil berenfield) writes:


>I am currently trying to teach myself assembly language on the amiga and
>as a project, I thought I'd write a mandlebrot program in assembly that I
>originally wrote in C. I can open libraries, screens, windows etc. well
>and can generate a nice looking mandlebrot but what I'm after is SPEED!

I'd suggest you read my article and program listing "Fast Fractals" in
the November 1989 issue of Amazing Amiga. It covers a fractal program
that is based on integer arithmetic. It works fast on the 68000
and it should be a real screamer on your configuration !

I hope this is a source of ideas.

Hugo Lyppens
hugo@gem.stack.urc.tue.nl

In <86849@tut.cis.ohio-state.edu> berenfie@tortoise.cis.ohio-state.edu (gregory neil berenfield) writes:

[stuff deleted]
>plane and use z->z^2+c calculations accordingly. The mandelbrot is drawn
>fairly quickly but not nearly as fast as MandFXP and I want to squeeze 
>maximum speed out of this sucker. Does anyone know of a way of storing
>floating points as ints and doing some sort of bit shifting stuff to do 
>fp arithmatic operations? Any help in optimizing this thing would be
>of great help. Thanks.


  First, MandFXP may be doing other tricks other than using a different
numeric format. These tricks are probably _mathematical_ in nature,
from knowledge known about the mandelbrot set. I doubt they are computing
the thing using brute force: they are probably using clever heuristics...
  Anyway, it's easy to do fixed point arithmetic. Just pick a bit location
for your fixed point, say bit 14. Now after you multiply two 14 bit numbers,
you now have a 28 bit number. To get back to a 14 bit number, you shift
right by 14. Before you divide one 14 bit number by another, you must make
it a 28 bit number. Examples:

#define FBITS 14 /* Fixed point bits, 16384 == 1.0 */
long a,b,c; /* 14 bit numbers */

  c = (a*b) >> FBITS;
  c = (a << FBITS) / b;
  c = (a*b)/c;

See the pattern? The rules are: Multiplication of two fixed point numbers
yields a fixed point number equal to the sum of the two number's fixed points.
Division yields the difference of the fixed points. The fixed point location
is called the RADIX. Using this terminology:

  a*b yields a fixed point number with radix(a) + radix(b);
  a/b "                              " radix(a) - radix(b);

You can mix radix' too:

 radix(a) == 7, radix(b) = 14:

  radix(a*b) = 21, radix((a*b)>>12) = 9, etc. Left shifts increase the radix,
right shifts decrease the radix.

  IMPORTANT: You *must* make sure that the radix is the same for both numbers
when adding or subtracting. You _can_ do things like:

  x = (a*a + b*b + c*c) >> FBITS; /* a,b,c and x have the same radix */

  Also, sqrt *halves* the radix, just as squaring a number doubles the radix.
Now, if you use the 68030, you should use 64 bit numbers (at least for
intermediate values). Use the addx.l, muls.l, divs.l, bfextu, and bfins
to manipulate your numbers. Here's a short example:


; rotate64, created by John Schultz
; Rotates a point in 3D space.
; Created 8-Aug-90

	section math64,code

	OPT	p=68020/68881 ; for Adapt assembler

	xdef	_rotate64

FB	equ	14	; fixed point precision (bits 0-14)
RB	equ	(32-FB) ; remaining bits (32-14 = 18)

; 32 bit rotation matrix offsets

ma	equ	0
mb	equ	4
mc	equ	8
md	equ	12
me	equ	16
mf	equ	20
mg	equ	24
mh	equ	28
mi	equ	32

; 32 bit 3D point offsets

px	equ	0
py	equ	4
pz	equ	8

;void longrotate(matrix * m,longpoint3d * p,ushort fbits) {
;long tcx,tcy,tcz;
;  tcx = p->x;
;  tcy = p->y;
;  tcz = p->z;
;  p->x = (m->a1*tcx + m->d1*tcy + m->g1*tcz) >> fbits;
;  p->y = (m->b1*tcx + m->e1*tcy + m->h1*tcz) >> fbits;
;  p->z = (m->c1*tcx + m->f1*tcy + m->i1*tcz) >> fbits;
;} /* longrotate */

; extern __asm rotate64(register __a0 matrix * m,
;                       register __a1 longpoint3d * p);

; a0 = matrix *, a1 = longpoint3d *

_rotate64:

	movem.l	d2-d6,-(sp)

	movem.l	 (a1),d0-d2	; x,y,z

; Rotate X

	move.l	(a0),d4		; ma
	muls.l	d0,d3:d4	; x*a, 64 bit result in d3:d4

	move.l	md(a0),d6	; md
	muls.l	d1,d5:d6	; y*d, 64 bit result in d5:d6

	add.l	d4,d6		; low 32 bits,  x*a + y*d
	addx.l	d3,d5		; high 32 bits, x*a + y*d (d6:d5 = res)

	move.l	mg(a0),d4	; mg
	muls.l	d2,d3:d4	; z*g, 64 bit result in d3:d4
	
	add.l	d4,d6		; low 32 bits,  x*a + y*d + z*g
	addx.l	d3,d5		; high 32 bits, x*a + y*d + z*g (d5:d6 = res)

; Result is in (high:low) d5:d6

	bfextu	d6{0:RB},d6	; shift right by 32-RB
	bfins	d5,d6{0:FB}	; insert bits from high word

	move.l	d6,(a1)+	; save rotated x

; Rotate Y

	move.l	mb(a0),d4	; ma
	muls.l	d0,d3:d4	; x*b, 64 bit result in d3:d4

	move.l	me(a0),d6	; md
	muls.l	d1,d5:d6	; y*e, 64 bit result in d5:d6

	add.l	d4,d6		; low 32 bits,  x*b + y*e
	addx.l	d3,d5		; high 32 bits, x*b + y*e (d5:d6 = res)

	move.l	mh(a0),d4	; mg
	muls.l	d2,d3:d4	; z*g, 64 bit result in d3:d4

	add.l	d4,d6		; low 32 bits,  x*b + y*e + z*h
	addx.l	d3,d5		; high 32 bits, x*b + y*e + z*h (d5:d6 = res)

; Result is in (high:low) d5:d6

	bfextu	d6{0:RB},d6	; shift right by 32-RB
	bfins	d5,d6{0:FB}	; insert bits from high word

	move.l	d6,(a1)+	; save rotated y

; Rotate Z

	move.l	mc(a0),d4	; mc
	muls.l	d0,d3:d4	; x*c, 64 bit result in d3:d4

	move.l	mf(a0),d6	; md
	muls.l	d1,d5:d6	; y*f, 64 bit result in d5:d6

	add.l	d4,d6		; low 32 bits,  x*c + y*f
	addx.l	d3,d5		; high 32 bits, x*c + y*f (d6:d5 = res)

	move.l	mi(a0),d4	; mg
	muls.l	d2,d3:d4	; z*g, 64 bit result in d3:d4
	
	add.l	d4,d6		; low 32 bits,  x*c + y*f + z*i
	addx.l	d3,d5		; high 32 bits, x*c + y*f + z*i (d5:d6 = res)

; Result is in (high:low) d5:d6

	bfextu	d6{0:RB},d6	; shift right by 32-FB
	bfins	d5,d6{0:FB}	; insert bits from high word

	move.l	d6,(a1)		; save rotated z

	movem.l	(sp)+,d2-d6
	rts

        END

  One last thing, if you are constantly using the fsqrt of the 882,
the fmove.l instruction is 100 cycles, so you may not see a big win
using integer in some cases. Multiplies and divides aren't much slower
on the 882 (than muls.l/divs.l), especially if you use fsglmul/div, but
adds and subtracts are slower than multiplies and divides! This makes
sense as the processor must align the bits (floating) before performing
adds or subs. Hope this helps,


  John

In article <86849@tut.cis.ohio-state.edu>, gregory neil berenfield writes:

> and can generate a nice looking mandlebrot but what I'm after is SPEED!

Elusive as it may be! Even with my GVP 3001, at 30Mhz, things
aren't quick enough for me.

> Firstly, my system is an A3000 68030/68882 25Mhz. I have a shareware copy
> of MandFXP by Cybersoft I believe, and that sucker can really splat
> mandelbrots in under 2 seconds! 

CygnusSoft. The guys who wrote Cygnus Ed Professional, Release 2,
which I'm using right NOW, and it's G_R_E_A_T (Marketted by ASDG
Inc.) After using a public access UNIX machine to _attempt_ to
get onto USEnet, and having to use Vi, I cannot adequately explain
the enjoyment value that I get out of using CED compared to being
relegated to Vi!

(Go on, Usenetters, call me a heathen! :-)

I used MandelFXP to generate an 'AmigaMovie' of a Mandelbrot - on
a REALLY SMALL 1" square of the screen, down to 1/128,000,000th
of the screen (I was using 5 words of precision at that time!).
It looked sorta neat, but at more than 4 frames a second, it was
just visual noise, if you get my drift.

I wrote to ASDG, asking for more information (like, will they
ever get around to MandelMovie) but got zippo response.
Cygnussoft aren't contactable by phone. :-(

> Mine is not nearly as fast. 

Check out a program called MandelBz, by Nico Francois, the guy
who wrote PowerPacker. It's pretty quick, and uses a SECAM way
(Something Essentially Contrary to the American Method :^) of
doing Mandelbrots, by doing the edges first, and then area fills.
Pretty quick, and produces some VERY nice pictures. Best of all,
it uses PAL, whereas MandelFXP uses Never Twice Same Colour, and
the ugly 200 line screen.

Good luck with your project: I think Mandelbrot generators have
been done to death though.

> anonymous: Who am I?      |  O.S.U.  CIS

Fair enough.

Dac
   _l _  _  Andrew Clayton.      I post .       ccadfa.cc.adfa.oz.au!Uprolix!dac
  (_](_l(_  Canberra. Australia.       . . I am.

Note: I cannot send or recieve MAIL to sites outside of Australia. Sorry.

In article <86849@tut.cis.ohio-state.edu>, berenfie@tortoise.cis.ohio-state.edu (gregory neil berenfield) writes:
|> Firstly, my system is an A3000 68030/68882 25Mhz. I have a shareware copy
|> of MandFXP by Cybersoft I believe, and that sucker can really splat
|> mandelbrots in under 2 seconds! Mine is not nearly as fast. My technique is
|> straightforward. For actual drawing, I open a custom screen & window and
[...]

Hi!

This is not concerning the technical details of treating floating point values
in Assembler but rather about two techniques to optimize Mandelbrot set
calculations you might want to use.

The first is very simple. Instead of calculating each point (including the
"black" areas too) you first look only at the frame of your picture. The
Mandelbrot set is connected; so if all the points on the frame are of the
same colour you need not to calculate the interior anymore, it is of the
colour of the frame. If the frame is not of one colour you can divide
your picture into four sub-pictures. On each picture the same procedure
as above is applied so that you result in a recursive process to calculate
the mandelbrot set. I wrote some time ago a program which uses this method
and can submit it if you are interested. (Unfortunately, it is written in
C and not in Assembler.)

Another faster method was posted some months ago in alt.fractals. I do not
remember the exact name and the algorithm but I can look for it at home. The
idea of this was that you follow the border of a colour without calculating
the interior. It can easily be filled with this colour.

I would be interested in MandFXP von Cybersoft (if it is really shareware,
I think it is commercial, but I can be mistaken). Where did you get it?
Is it available via ftp somewhere?

                                                       -Holger

===========================================================================
|| Holger Muenx, IRB, Universitaet Dortmund, 4600 Dortmund, West-Germany ||
||          Internet: muenx@heike.informatik.uni-dortmund.de             ||
===========================================================================

With regard to speeding up the mandlebrot thingies..
 
I have been in the same boat as you.

I found a HUUUGE increase when I decided to jump awaay from using libraries and do all the tedious work my self.. (eg. Using the Copper to open my screen , etc/... The biggest increase was acheived by instead of using Draw(x,y) library commands but rather access the actually bplane pointer and filling from there..

I'll try to dig up my source (it's been at least 2 years now.) and see if I can help more...