Divide and Conquer

[rommmcek]

Divide and Conquer for AutoHotkey v1.1

Preface

Wikipeida Divide and Conquer

In computer science, divide and conquer is an algorithm design paradigm based on multi-branched recursion. A divide-and-conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

This divide-and-conquer technique is the basis of efficient algorithms for all kinds of problems, such as sorting (e.g., quicksort, merge sort), multiplying large numbers (e.g. the Karatsuba algorithm), finding the closest pair of points, syntactic analysis (e.g., top-down parsers), and computing the discrete Fourier transform (FFT).[1]

Understanding and designing divide-and-conquer algorithms is a complex skill that requires a good understanding of the nature of the underlying problem to be solved. As when proving a theorem by induction, it is often necessary to replace the original problem with a more general or complicated problem in order to initialize the recursion, and there is no systematic method for finding the proper generalization. These divide-and-conquer complications are seen when optimizing the calculation of a Fibonacci number with efficient double recursion.

The correctness of a divide-and-conquer algorithm is usually proved by mathematical induction, and its computational cost is often determined by solving recurrence relations.

Since I think this method cannot be transposed one to one to a specific application I made couple of examples using while and recursive call including condensed versions too. See example here too.

Example of usage:

Code: Select all

Random, Rn, u0:=u1:= 0, v0:=v1:=2147483647
MsgBox % Rn " = " (vs:=DivConq(Rn, u1, v1)) "`n" vs " = " Rn

Random, Rn, u1:=0, v1:=99999999999999.0
MsgBox % Rn " = " (vs:=DivConq(Rn, u1, v1, 1)) "`n" vs " = " Rn

Version 1:

Code: Select all

DivConq(Rn, u1, v1, f:="") { ; \/
    Static vs, u0:= 0, v0:= 1
    while (vd:=v0-u0 > 0, u0:=u1, v0:=v1)
        if (Rn < (vs:= f? (v0+u0)/2: (v0+u0)//2))
            u1:=u0, v1:=vs
        Else if (Rn > vs)
            u1:=vs, v1:=v0
        else Return vs
}

Version 2:

Code: Select all

DivConq(Rn, u1, v1, f:="") { ; \/
    Static vs, v0:= 1, u0:= 0
    (v0-u0>0, u0:=u1, v0:=v1)? (Rn < (vs:= f? (v0+u0)/2: (v0+u0)//2)? (u1:=u0, v1:=vs): (u1:=vs, v1:=v0)): ""
  , (Rn != vs)? DivConq(Rn, u1, v1, f): ""
    Return vs
}

Version 3:

Code: Select all

DivConq(Rn, u1, v1, f:="") { ; \/
    Static u0:= 0, v0:= 1
    while (v0-u0 > 0, u0:=u1, v0:=v1) {
        Rn < (vs:= f? (v0+u0)/2: (v0+u0)//2)? (u1:=u0, v1:=vs): (Rn>vs)? (u1:=vs, v1:=v0): Br:=1
        if Br
            Return vs
    }
}

Version 4:

Code: Select all

DivConq(Rn, u1, v1, f:="") { ; \/
    Static u0:= 0, v0:= 1
    while (v0-u0 > 0, u0:=u1, v0:=v1)
        if (Rn = vs)
            Return vs
        Else Rn < (vs:= f? (v0+u0)/2: (v0+u0)//2)? (u1:=u0, v1:=vs): (u1:=vs, v1:=v0)
}

Version 5:

Code: Select all

DivConq(Rn, u1, v1, f:="") { ; \/
    Static vs
    (Rn!=vs, u0:=u1, v0:=v1)
        ? (Rn < (vs:= f? (v0+u0)/2: (v0+u0)//2)? (u1:=u0, v1:=vs): (u1:=vs, v1:=v0), DivConq(Rn, u1, v1, f)): ""
    Return vs
}

Version 6:

Code: Select all

DivConq(Rn, u1, v1, f:="") { ; \/
    while (Rn!=vs, u0:=u1, v0:=v1)
        Rn < (vs:= f? (v0+u0)/2: (v0+u0)//2)? (u1:=u0, v1:=vs): (u1:=vs, v1:=v0)
    Return vs
}