I have heard of mentions of "complex" algorithms. How complex really is a "complex" algorithm. Can anyone post some complex algorithms on this page. It would be a nice excersice figuring them out, also ppl would know how complex really those "complex" algos are! If u go by the word meaning i think a complex algo doesnt need to be a very long one. It may even be a short algo but which is very tough to understand or code. Am i correct?
Posted on 2001-06-18 09:01:00 by MovingFulcrum
MovingFulcrum, The term is probably relative but for a starter, have a look at buliaNaza's Boyer Moore algo, its on the way to being a complex algorithm. Compression is a very complex area so that can be your next stop, after that there is a mountain of stuff that you can find, convert or code from scratch, just depends what you need to do. Regards, hutch@pbq.com.au
Posted on 2001-06-18 09:15:00 by hutch--
Hutch is right of course, complex is a very relative word. Can I just thorw in a routine I wrote recently and while I'm at it plug my site which I've just got online Assembly Game Programming (Ok, that was shameless I know, but how else is anyone here going to find it) Now heres the routine, you'll also find it at the site. Its a routine that take values passed to it on the FPU stack and interepting them as four point on two line segements, it checks to see if they intersect.

mILineSeg MACRO l1x1, l1y1, l1x2, l1y2, \
                l2x1, l2y1, l2x2, l2y2
	fld l1y2
	fld l2x1
	fld l2x2
	fld l2y2
	fld l2y1
	fld l1y1
	fld l1x1
	fld l1x2
	call ILineSeg
ENDM


ILineSeg Proc
LOCAL x1,y1,x2,y2,x3,y3:QWORD
	fst x2
	fxch st(7)
	fst y2
	fxch st(6)
	fst x3
	fxch st(3)
	fst y3
	fxch st(2)
	
	fsub st(6), st
	fsub st(4), st
	fsub st(2), st
	fstp y1
	fsub st(6), st
	fsub st(4), st
	fsub st(2), st
	fstp x1
	
	fld st
	fsub st, st(3)
	fstp st(7)
	fmul st, st(5)
	fxch
	fst st(7)
	fxch st(3)
	fsub st(7), st
	fxch st(3)
	fmul st, st(4)
	fsub
	fstp st(7)
	fmul st, st(3)
	fxch
	fmul st, st(2)
	fsub
	
	fstp st(2)
	fstp st
	fld st
	
	fmul st, st(4)
	fldz
	fcompp
	fstsw ax
	sahf
	jb ni
	
	fsub st, st(3)
	fxch
	fmul st, st(3)
	fdiv st, st(1)
	fadd y3
	
	fstp st(4)
	
	fxch
	fmul st, st(2)
	fdiv st, st(1)
	fadd x3
	
	fstp st(2)
	fstp st
	
	fld st
	fsub x1
	fld st(1)
	fsub x2
	fmul
	fldz
	fcompp
	fstsw ax
	sahf
	setnb cl
	fxch
	
	fld st
	fsub y1
	fld st(1)
	fsub y2
	fmul
	fldz
	fcompp
	fstsw ax
	setnb al

	and al, cl
	jz ns
	
	mov eax, 1
	test eax, eax
	ret
ni:	
	fcompp
ns:
	fcompp
	xor eax, eax
ret
ILineSeg EndP
I use this as an example as, unless you know what its supposed to do it would be hard to figure out. Even as it stands I'd challange people to figure out how it actually works. And don't forget if you didn't have the calling MACRO how could you even begin, you wouldn't what what the values represent. I intend to write a full explanation over the coming weeks if anyone really intrested.
Posted on 2001-06-18 13:59:00 by Zadkiel
Well, there's an algorithm for linearly testing planarity in graphs that's very, very complex, not just the code (4 pages of pseudocode) but the algo itself. There is also another search algo that's pretty ugly (the Aho-Corasick) that's used for searching multiple patterns in some text. For the last ones, I have some C++ code if you like (also the Boyer-Moore). Bye
Posted on 2001-06-18 21:39:00 by GogetaSSJ4
For the last ones, I have some C++ code if you like (also the Boyer-Moore).
GogetaSSJ4, Pls mail both o them to me. Zadkiel, I am taking a lok at that code. I will be able to tell u exactly what it does by the end of the year :D
Posted on 2001-06-19 10:34:00 by MovingFulcrum
Just curious... did you saw in a low level your Boyer Moore algo in C++?
Posted on 2001-06-19 10:35:00 by buliaNaza
Just curious... did you saw in a low level your Boyer Moore algo in C++?
I cant get u. What r u trying to say?
Posted on 2001-06-19 12:08:00 by MovingFulcrum
mov si, xor ax,ax mov dx,1 mov cx,ax mov di,dx lup: mov ,di dec si jz 611 inc si div si push dx mul di sub cx,ax xchg cx,di mov ax,si xor dx,dx pop si jmp lup number dw ? number2 dw ? Anybody know what this does before reading my description? Ok give up? I found this algorithm in a program, it finds the multiplicative inverse of a number ( - must be odd) for decryption. If you gave it the number 5 it would return CCCDh. If you multiply a 16 bit number by 5 then by CCCDh you get the number you started off with. A varient of this is used for PGP and other public/private key stuff.
Posted on 2001-06-19 12:32:00 by AsmDude
MovingFulcrum, I think buliaNazia was asking if you had look at the assembly translation of your C++ algorithm.
Posted on 2001-06-19 15:17:00 by karim
MovingFulcrum, I'm sorry, karim is right about assembly translation of the C++ algorithm, but I asked GogetaSSJ4.. When I wrote my message I didn't saw your message U can take a look to the times of my and your messages too
Posted on 2001-06-19 17:29:00 by buliaNaza
MovingFulcrum: Done. buliaNaza: I looked at the listings produced by VC++ very closely, but even when I'm in no way an ASM expert, I'm sure anyone around here can make better code than that, at least in the BM. In the Aho-Corasick, it's harder because it uses a class, but of course, that can be done. As a side note, VC++ is pretty stupid when it comes to it's ASM listings...yes, it runs fast, but it's very sad to see what it does with (as an example) the _fastcall calling convention. And this kind of algorithms certainly need the speed you get from a good ASM code. Here's the Boyer-Moore (the other one is too long to post here):

#define max(a, b)	((a) > (b) ? (a) : (b))

const int MAXCHAR = 256;

// Implementación del algoritmo Boyer-Moore
void BoyerMoorePreproc(const unsigned char *Patron, int **Skip, int **d, const unsigned int LongPatron) {
	int j, k, t, t1, q, q1;
	int *f = new int;      // Auxiliar

	*(d) = new int;
	*(Skip) = new int;

	// Tabla de SKIP
	for (k = 0; k < MAXCHAR; k++) {
		(*Skip) = LongPatron;
	}
	for (k = 1; k <= LongPatron; k++) {
		(*d) = (LongPatron << 1) - k;
		(*Skip)] = LongPatron - k;
	}

	// Tabla D2
	t = LongPatron + 1;

	for (j = LongPatron; j > 0; j--) {
		f = t;
		while (t <= LongPatron && Patron != Patron) {
			(*d) = ((*d) < LongPatron - j) ? ((*d)) : (LongPatron - j);
			t = f;
		}
		t--;
	}
	q = t;
	t = LongPatron + 1 - q;
	q1 = 1;
	t1 = 0;
	for (j = 1; j <= t; j++) {
		f = t1;
		while (t1 >= 1 && Patron != Patron) {
			t1 = f;
		}
		t1++;
	}
	while (q < LongPatron) {
		for (k = q1; k <= q; k++) {
			(*d) = ((*d) < (LongPatron + q - k)) ? (*d) : (LongPatron + q - k);
		}
		q1 = q + 1;
		q = q + t - f;
		t = f;
	}
	delete [] f;
	
	unsigned int i = 0;
	for (j = 1; j < LongPatron; j++) {
		if (Patron == Patron) {
			i++;
		}
		else {
			i = 0;
		}
	}
	if (i == LongPatron) {
		i--;
	}
	(*d) = LongPatron + (LongPatron - i);
}

void BoyerMoore(const unsigned char *Texto, const unsigned char *Patron, const int *Skip, int *d, const unsigned int LongTexto, const unsigned int LongPatron, const unsigned int Offset, list *RetList) {
	int j, k;

	// Búsqueda
	j = k = LongPatron - 1;
	while ((k < LongTexto) && (j >= 0)) {
		while ((j > -1) && (Texto == Patron)) {
			k--;
			j--;
		}
		if (j != -1) {
			k += max(Skip[(unsigned char) Texto], d);
			j = LongPatron - 1;
		}
		else {
			RetList->push_back(Offset + k + 1);
			j = LongPatron - 1;
			k += d;
		}
	}
}

PS: Patron = Pattern Texto = Text LongPatron = Pattern length LongTexto = Text length PS2: Asu you can see, the function returns a STL list of with ALL the apperances of the pattern in the text. Comments please. Bye =)
Posted on 2001-06-19 22:11:00 by GogetaSSJ4
GogettaSSJ4, Don't forget to turn optimization on when you compile your program (with /Og), the result can be completely different.
Posted on 2001-06-20 07:54:00 by karim