[A83] Re: Faster Multiplication

[Prev][Next][Index][Thread]

[A83] Re: Faster Multiplication


algorithm: a set of rules for solving a given problem in a finite number of
steps

table: a collection of stuff in an organized format (hopefully you are
familiar with tables in major word processors). this is similar except that
it is generally will have 2 columns and N rows, i.e. for this problem:

1^1 / 4 = 0
2^2 / 4 = 1
3^2 / 4 = 2
4^2 / 4 = 4
etc...

Using the above table, it becomes rather simple to use the equation in
assembly. With the above table in combination with an absolute value table,
the equation is reduced to: answer = a - b, where a is ((x+y)^2)/4 and b is
((x-y)^2)/4, which can be looked up in the table quickly. Here is a sample
routine. It takes a fixed time of 98 tstates not including the RET. It
requires 2kb of table space - probably not practical on an 83, but for the
sake of theory:

; Input:  D and E are the numbers to be multiplied
; Output: BC = D * E
;
; Table must be aligned on an $xx00 address. It can be generated at
; runtime with a fairly simple routine.
;
; Table must point to a table of the lsb and msb of squares as follows:
;  .db (-256*-256)/4,(-255)*(-255)/4,(-254*-254)/4,...,(-1*-1)/4
;  and then the msb's of those...
;  .db 0*0/4,1*1/4,2*2/4,...,255*255/4
;  and then the msb's of those...;
;  .db 256*256/4,...,511*511/4
;  and then the msb's of those.
;  .db 0*0/4,1*1/4,2*2/4,...,255*255/4
;  and then the msb's of those...
Multiply:
     ld   a,d
     sub  e
     ld   l,a
     sbc  a,a
     sbc  a,254-(Table>>8)
     ld   h,a
     ld   a,d
     add  a,e
     ld   e,a
     sbc  a,a
     sbc  a,250-(Table>>8)
     ld   d,a
     ld   a,[de]
     sub  [hl]
     ld   c,a
     inc  d
     inc  h
     ld   a,[de]
     sbc  a,[hl]
     ld   b,a
     ret

-----Original Message-----
From: assembly-83-bounce@lists.ticalc.org
[mailto:assembly-83-bounce@lists.ticalc.org]On Behalf Of Tom
Sent: Wednesday, May 30, 2001 6:03 PM
To: assembly-83@lists.ticalc.org
Subject: [A83] Re: Faster Multiplication

On Wed, 30 May 2001 17:46:31 -0600, assembly-83@lists.ticalc.org
wrote:

What is an algorithm? How about a table? How can you use an equation
like that in assembly? Sorry about the trivial questions...I'm
learning. Thanks!
-Tom Lutz
caffeine43@netzero.net on 05/30/2001
Follow-Ups: References: