Andrija Radovic´'s Algorithms
This web page contains algorithms that I had been developing over the years and
that were publishes in my book mentioned on the C.V. page. The algorithms belong to the domain of
Computer Raster Graphics, Integer Computations and Numerical Analysis.
The algorithms from the area of the Computer Raster Graphics and Integer Computations are based
on the theorem of eushaustia (i.e. searching) in quantum field that claims that we can find target
quantum position in the quantum domain in the finite number of iterations with the binary search
approach.
These algorithms are especially suitable for implementation in silicon.
Further in the text it will be shown that the quantum algorithm can compute the cosines, logarithm
and exponent. Although the approach is not fast it is very accurate.
Quantum Dividing Algorithm
Dividing algorithm is very simple and yet really effective. Usage of the algorithm is demonstrated in the program BigNum freely available for download on the site.
Quantum Dividing Algorithm
DECLARE SUB QDIV (c%, a%, b%)
DECLARE SUB PUSH (a%)
DECLARE SUB POP (a%)
CLS
DIM SHARED STCK(1000) AS INTEGER, SP AS INTEGER
SP = 0
INPUT "A = ", a%
INPUT "B = ", b%
PRINT a%; "\"; b%; "=";
QDIV c%, a%, b%
PRINT c%, a%
END
SUB QDIV (DX%, AX%, CX%)
DX% = 1
DX% = AX%
DO
CX% = -DX%
CX% = DX% AND CX%
DX% = DX% - CX%
LOOP WHILE DX%
SWAP CX%, DX%
SI% = DX%
DO
DX% = DX% \ 2
CX% = CX% + 1
LOOP WHILE DX%
CX% = CX% - 1
DX% = SI%
DI% = CX%
SI% = SI% \ 2
DO
DI% = DI% \ 2
IF DX% + SI% <= AX% THEN
DX% = DX% + SI%
CX% = CX% + DI%
END IF
SI% = SI% \ 2
LOOP WHILE SI%
END SUB
Demonstration of the quantum integer-dividing algorithm is available in the source of the calculator’s program “BigNum” available on the site.
This algorithm is neither public domain nor freeware. If you charge money using it within a product you sell, you require a commercial license.
Quantum Integer Square Rooting
The algorithm uses only simple processor arithmetic instructions like addition, subtraction, shifting and comparation. Furthermore, the algorithm is scalable and it can be applied on the input argument of arbitrary size. It has fixed number of iterations. The number of iterations that are necessary to reach correct result is equal to the half number of bits of input argument or the number of bits in output argument that holds the result, not the other one that holds remainder. All the variables in the routine have the same size in bits as the input parameter.
The algorithm yields the results and remainder too. It uses only addition, subtraction and shifting and thus it is very suitable to be utilized into chips.
It is completely based on the theory of dividing of the interval based on the formula:
(1)
(x ± Δx)2 = x2 ± 2 · x · Δx + Δx2
So we have the basic idea described by the routine:
FUNCTION SQRI (IN)
DX = 128
DX2 = 16384
X = 0
DO
X21 = X2 + 2 * X * DX + DX2
DO WHILE X21 > IN
DX = DX / 2
DX2 = DX2 / 4
X21 = X2 + 2 * X * DX + DX2
LOOP
X2 = X21
X = X + DX
DX = DX / 2
DX2 = DX2 / 4
LOOP WHILE DX
SQRI = X
END FUNCTION
After a few rudimental optimizations we have:
Quantum Square Rooting Algorithm
DECLARE FUNCTION ISQR% (DI%)
DEFINT A-Z
INPUT "X = ", DI
PRINT ISQR(DI)
END
FUNCTION ISQR% (DI)
SI = 0
DX = 0
AL = 0
AH = 128
BX = 16384
DO
CX = SI + DX + BX
DX = DX \ 2
IF DI >= CX THEN
SI = CX
AL = AL + AH
DX = DX + BX
END IF
BX = BX \ 4
AH = AH \ 2
LOOP WHILE AH
ISQR% = AL
END FUNCTION
The above algorithm could be more optimized and then it becomes:
‘AX = Input
‘DX = Output
‘BX = Remainder
Sub SQRT(AX As Long, DX As Long, BX As Long)
Dim SI As Long, DI As Long
BX = 0
DX = 0
DI = 1073741824 'I.e. 2n-2
Do
SI = BX + DX + DI
DX = DX \ 2
If AX >= SI Then
BX = SI
DX = DX + DI
End If
DI = DI \ 4
Loop While DI
BX = AX - BX
End Sub
The basic demonstration of the routine is given by the following DOS program in I80286 assembly language that computes square root from the users’ input:
|
This algorithm is protected by copyright low and thus it can be distributed under
certain conditions only: the algorithm is free for non-commercial use. |
Source code is availabe below:
|
This algorithm is protected by copyright low and thus it can be distributed under
certain conditions only: the algorithm is free for non-commercial use. |
Demo routine given in ASM that demonstrate the integer square rooting of the 24
byte long input arguments and the biggest number that has to be sent to the routine is
6277101735386680763835789423207666416102355444464034512895. The routine is quite scalable and its precision can be easily expanded.
Its output is shown on the picture below:
You can download demo program by pressing the button below:
|
This algorithm is protected by copyright low and thus it can be distributed under
certain conditions only: the algorithm is free for non-commercial use. |
You can download its source code in Masm assembly language by pressing the button below:
|
This algorithm is protected by copyright low and thus it can be distributed under
certain conditions only: the algorithm is free for non-commercial use. |
These routine should work from DOS or DOS Windows.
Quantum Line Drawing algorithm
There are several algorithms for line drawing too. These algorithms have only
one question per break and one integer dividing on the beginning. The algorithms are extremely
fast and suitable for silicon’s implementation.
The algorithm is based on the quite different premises than the Bresenham’s one.
The algorithm is especially optimized to work with the bit-planes and black/white images and
thus it is suitable to be utilized in laser printers.
The main characteristic of the algorithm is equal widths of middle-breaks of line as it is
shown on the picture right of the text.
Basic demonstration of the algorithm is given on the following listing:
SCREEN 12
FOR i% = 0 TO 639 STEP 10
KOSLINE 0, 0, i%, 199
NEXT
FOR i% = 195 TO 0 STEP -5
KLINE 0, 0, 639, i%
NEXT
END
SUB HLINE (x1%, x2%, y%)
LINE (x1%, y%)-(x2%, y%)
END SUB
SUB KLINE (x1%, y1%, x2%, y2%)
dx% = ABS(x2% - x1%) + 1
dy% = ABS(y2% - y1%) + 1
b% = dy% - dx%
IF b% < 0 THEN
IF x1% > x2% THEN
SWAP x1%, x2%
SWAP y1%, y2%
END IF
IF y1% > y2% THEN
sign% = -1
ELSE
sign% = 1
END IF
c1% = dx% \ dy%
b% = b% + dx% - dx% MOD dy%
c1% = c1% + 1
xt% = x1%
e% = b% - 1
FOR y1% = y1% TO y2% STEP sign%
IF b% > 0 THEN
b% = b% - dy%
x1% = x1% - 1
END IF
b% = b% + e%
x1% = x1% + c1%
HLINE xt%, x1% - 1, y1%
xt% = x1%
NEXT
ELSE
IF y1% > y2% THEN
SWAP x1%, x2%
SWAP y1%, y2%
END IF
IF x1% > x2% THEN
sign% = -1
ELSE
sign% = 1
END IF
c1% = dy% \ dx%
b% = -b% + dy% - dy% MOD dx%
c1% = c1% + 1
e% = b% - 1
yt% = y1%
FOR x1% = x1% TO x2% STEP sign%
IF b% > 0 THEN
b% = b% - dx%
y1% = y1% - 1
END IF
b% = b% + e%
y1% = y1% + c1%
VLINE x1%, yt%, y1% - 1
yt% = y1%
NEXT
END IF
END SUB
SUB VLINE (x%, y1%, y2%)
LINE (x%, y1%)-(x%, y2%)
END SUB
Screen of the DEMOVGA assembly program:
For downloading demonstration code written for VGA DOS mode 12 in 80X86 assembler press the button (press any key for next stage):
|
This algorithm is protected by copyright low and thus it can be distributed under
certain conditions only: the algorithm is free for non-commercial use. |
For download of assembly source press button below:
|
This algorithm is protected by copyright low and thus it can be distributed under
certain conditions only: the algorithm is free for non-commercial use. |
Ega3d demo
For download of the algorithm that demonstrates the ability of its usage on the specific embedded weak hardware with monochrome video memory is demonstrated by the following program:
|
This algorithm is protected by copyright low and thus it can be distributed under
certain conditions only: the algorithm is free for non-commercial use. |
For download of assembly source press button below:
|
This algorithm is protected by copyright low and thus it can be distributed under
certain conditions only: the algorithm is free for non-commercial use. |
The routine designed to the True Color video devices is a different one and it
optimized to deal with the bigger piles of data dedicated to pixels consisted at least of byte
triplets.
Lines draw by the algorithm are shown on the right picture.
The essential of the algorithm is presented by the following listing in Basic:
SCREEN 13
DEF SEG = &HA000
CLS
FOR i% = 0 TO 319
kline1 0, 0, i%, 199, (i% MOD 254) + 1
NEXT
FOR i% = 199 TO 0 STEP -1
kline1 0, 0, 319, i%, (i% MOD 254) + 1
NEXT
END
SUB hline (a%, b%, c%)
LINE (a%, c%)-(b%, c%)
END SUB
SUB kline1 (x1%, y1%, x2%, y2%, col%)
dx% = ABS(x2% - x1%) + 1
dy% = ABS(y2% - y1%) + 1
IF dx% > dy% THEN
IF x1% > x2% THEN
SWAP x1%, x2%
SWAP y1%, y2%
END IF
IF y1% > y2% THEN dl% = -320 ELSE dl% = 320
c% = dy%
l% = dx% \ dy%
o% = 2 * (dx% MOD dy%)
a& = y1% * 320& + x1%
FOR i% = 1 TO dy%
k% = l%
c% = c% - o%
IF c% < 0 THEN
c% = c% + 2 * dy%
k% = k% + 1
END IF
FOR j% = 1 TO k%
POKE a&, col%
a& = a& + 1
NEXT
a& = a& + dl%
NEXT
ELSE
IF y1% > y2% THEN
SWAP x1%, x2%
SWAP y1%, y2%
END IF
IF x1% > x2% THEN dl% = -1 ELSE dl% = 1
c% = dx%
l% = dy% \ dx%
o% = 2 * (dy% MOD dx%)
a& = y1% * 320& + x1%
FOR i% = 1 TO dx%
k% = l%
c% = c% - o%
IF c% < 0 THEN
c% = c% + 2 * dx%
k% = k% + 1
END IF
FOR j% = 1 TO k%
POKE a&, col%
a& = a& + 320
NEXT
a& = a& + dl%
NEXT
END IF
END SUB
SUB vline (a%, b%, c%)
LINE (a%, b%)-(a%, c%)
END SUB
For download of the assembly-coded program that demonstrates the algorithm press the button below (press any key for next stage):
|
This algorithm is protected by copyright low and thus it can be distributed under
certain conditions only: the algorithm is free for non-commercial use. |
For download of assembly source press button below:
|
This algorithm is protected by copyright low and thus it can be distributed under
certain conditions only: the algorithm is free for non-commercial use. |
Ellipse Drawing Algorithm
The algorithm is based on the same premises as the Bresenham’s Circle drawing algorithm. The algorithm uses few multiplications on its start and it is able to draw ellipse with the addition and subtraction. Maximal width in bits of the registers used in the routine is twice of width of input parameters.
Algorithm is given by following listing:
DECLARE SUB el7ipse (xx%, yy%, r1%, r2%)
DECLARE SUB eplot (x%, y%, a%, b%)
SCREEN 11
elipse 320, 240, 310, 100
elipse 320, 240, 100, 230
END
SUB elipse (xx%, yy%, r1%, r2%)
rr1& = r1% * CLNG(r1%)
r21& = rr1& + rr1&
r41& = r21& + r21&
rr2& = r2% * CLNG(r2%)
r22& = rr2& + rr2&
r42& = r22& + r22&
k& = r2% * r21&
p& = r41& + r42&
cc& = r22& + rr1& - k&
k& = k& + k&
rf2& = -r41&
r22& = r22& + p&
x% = 0
y% = r2%
DO
eplot xx%, yy%, x%, y%
IF cc& >= 0 THEN
y% = y% - 1
k& = k& - r41&
cc& = cc& - k&
END IF
cc& = cc& + rf2& + r22&
rf2& = rf2& + r42&
x% = x% + 1
LOOP UNTIL rf2& > k&
r22& = r22& - p&
k& = r1% * r22&
cc& = r21& + rr2& - k&
k& = k& + k&
rf1& = -r42&
r21& = r21& + p&
x% = r1%
y% = 0
DO
eplot xx%, yy%, x%, y%
IF cc& >= 0 THEN
x% = x% - 1
k& = k& - r42&
cc& = cc& - k&
END IF
cc& = cc& + rf1& + r21&
rf1& = rf1& + r41&
y% = y% + 1
LOOP UNTIL rf1& > k&
END SUB
SUB eplot (x%, y%, a%, b%)
PSET (x% + a%, y% + b%)
PSET (x% + a%, y% - b%)
PSET (x% - a%, y% + b%)
PSET (x% - a%, y% - b%)
END SUB
All rights reserved. The algorithm is property of its author and it cannot be
incorporated in any chip or hardware without prior explicit author’s agreement.
If you charge money using it within a product you sell, you require a commercial license!
TRANSCEDENTAL FUNCTIONS AND QUANTUM SPACE
Quantum theory is able to compute the values of the classic transcendental
functions like sinus, cosines, exponential and logarithm although it is not recommended way of
computing these functions. These methods are important for theoretical aspects only. These all
show that formal mathematics is the most powerful on the analytical functions and its ability to
bring us computational solutions of arbitrary analytical function by Taylor’s actually feeds its
power from the analytical definitions of their derivations. It means that actually we are not able
to find the whole curve only by one its point and we are able to do this on the analytical curves:
we first find the values in the convergence radius away from the beginning point and so one.
Recursively we can reach every point on the curve on the way.
So, we can agree that the following relations are neither the magic nor the hoax because these rules
are applicable only on analytical functions.
LOGARITHM FUNCTION IN QUANTUM SPACE
The following relation defines logarithm function:
(2)
So we have:
(3)
And:
(4)
The following program computes the value of LOGn(x) in the predefined interval:
DEFDBL A-Z
fa = 0#
fb = 10#
a = 1#
b = 1024#
e = 0#
DO
INPUT "k = ", k
IF k >= a AND k <= b THEN EXIT DO
PRINT "k must be between 1 & 1024."
PRINT
LOOP
DO
c = SQR(a * b)
fc = .5# * (fa + fb)
IF k < c THEN
b = c
fb = fc
ELSE
a = c
fa = fc
END IF
PRINT a; b; c, fc
LOOP UNTIL ABS(c - k) <= e
PRINT
PRINT
PRINT "LOG(" + STR$(k) + " ) ="; STR$(fc)
END
EXPONENTIAL FUNCTION IN QUANTUM SPACE
Exponential function is defined by the following relation:
(5)
The following program demonstrates computing of the exponential function:
DEFDBL A-Z
fa = 1#
fb = 1024#
a = 0#
b = 10#
e = 0#
DO
INPUT "k = ", k
IF k >= a AND k <= b THEN EXIT DO
PRINT "k must be between 0 & 10."
PRINT
LOOP
DO
c = .5# * (a + b)
fc = SQR(fa * fb)
IF k < c THEN
b = c
fb = fc
ELSE
a = c
fa = fc
END IF
PRINT a; b; c, fc
LOOP UNTIL ABS(c - k) <= e
PRINT
PRINT
PRINT "EXP(" + STR$(k) + " ) ="; STR$(fc)
END
SINE and COSINE
The following relation defines cosine function:
(6)
The following program demonstrates computing of the cosines function:
CLS
INPUT x#
r# = 3.1415926589793#
'r# = 180#
l# = 0#
cr# = -1
cl# = 1
a# = .5# * (r# + l#)
ca# = 0
'PRINT ca#: STOP
i% = 0
e# = .000000000000001#
DO
i% = i% + 1
PRINT "Pokusaj"; i%, a#, x#, ca#
IF x# < a# THEN
r# = a#
cr# = ca#
ELSE
l# = a#
cl# = ca#
END IF
a# = .5# * (l# + r#)
ca0# = ca#
ca# = .5# * (SQR((1# + cl#) * (1# + cr#)) - SQR((1# - cr#) * (1# - cl#)))
LOOP WHILE ABS(ca# - ca0#) > e#
PRINT
PRINT ca#, COS(x#)
END
Sine function is just π/2 translated Cosine function:
(7)
COS(x) = SIN(x + π / 2)
I.e.
(8)
SIN(x) = COS(x - π / 2)
These all are sufficient enough for computing of the Sine and Cosine functions.
DAY in Week
Following program computes day in week in wide range of dates using only integer arithmetic.
The algorithm is much better then classic one because it is not limited only to years after 1980. It covers whole AD range of time.
So, you can compute the day when the Newton or Shakespeare was born.
Program source:
DIM a$(6)
FOR i% = 0 TO 6
READ a$(i%)
NEXT
b$ = COMMAND$
IF b$ = "" THEN INPUT "Year-Month-Day: ", b$
IF LTRIM$(RTRIM$(b$)) = "" THEN END
i% = INSTR(b$, ".")
DO WHILE i%
MID$(b$, i%, 1) = "-"
i% = INSTR(i% + 1, b$, ".")
LOOP
i% = INSTR(b$, "-")
IF i% = 0 THEN END
j% = INSTR(i% + 1, b$, "-")
IF j% = 0 THEN END
g% = VAL(LEFT$(b$, i% - 1))
m% = VAL(MID$(b$, i% + 1, j% - i% - 1))
d% = VAL(MID$(b$, j% + 1, LEN(b$)))
IF m% < 1 OR m% > 12 THEN END
IF d% < 1 OR d% > 31 THEN END
a& = 1200& * g% + 100& * m% - 285&
b& = 100& * ((367& * a& \ 1200&) + d%) - 175& * (a& \ 1200&)
c& = 75& * (a& \ 120000)
dan% = (((b& - b& MOD 100& - c&) \ 100&) + 1721115) MOD 7&
PRINT "(C) Andrija Radovic"
PRINT "Day:"; d%
PRINT "Month:"; m%
PRINT "Year:"; g%
PRINT
PRINT "Day: "; a$(dan%)
END
DATA "Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"
All rights reserved. The algorithm is property of its author and it cannot be
incorporated in any chip or hardware without prior explicit author’s agreement.
If you charge money using it within a product you sell, you require a commercial license!
Assembly Haiku Poetry
And finally the abstract art of the haiku poetry in 80X86 assembly language: very short and very nice b/w plot routine for video mode 640x480x2:
PLOT
PROC ; DX = X, BX = Y
SHL
BX, 4
XOR
DX, 7
BTS
WORD PTR [EBX + 4 * EBX], DX
RET
PLOT ENDP
This routine demonstrates that the 80X86 processors’ architecture still could be very effective for use in laser printers as main graphic processor.
You can download the complete program that demonstrates implementation of the Bresenham circle by pressing the following button:
|
This algorithm is protected by copyright low and thus it can be distributed under
certain conditions only: the algorithm is free for non-commercial use. |
For download of assembly source press button below:
|
This algorithm is protected by copyright low and thus it can be distributed under
certain conditions only: the algorithm is free for non-commercial use. |