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?

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

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

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 :DJust curious... did you saw in a low level your Boyer Moore algo in C++?

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

MovingFulcrum,
I think buliaNazia was asking if you had look at the assembly translation of your C++ algorithm.

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

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 =)*

*
*

GogettaSSJ4,
Don't forget to turn optimization on when you compile your program (with /Og), the result can be completely different.