[A83] Re: Divide by 12

To: <assembly-83@lists.ticalc.org>
Subject: [A83] Re: Divide by 12
From: "Wei Lin and Norbert Juffa" <juffa@earthlink.net>
Date: Sat, 17 May 2003 20:56:30 -0700
Reply-To: assembly-83@lists.ticalc.org

Here is some code for dividing an unsigned 16-bit integer
by 12. The simplest algorithm to compute n / 12 that I am
aware of is:

  q = (n >> 1) + (n >> 3)
  q = q + (q >> 4)
  q = q + (q >> 8)
  q = q >> 3
  r = n - q * 12
  q = q + ((r + 4) >> 4)

At this point, q contains the quotient after division of 
n by 12. I got the algorithm from the following website 
which may be of interest to others on the mailing list:

  http://www.hackersdelight.org/

-- Norbert


; DivBy12 divides a 16-bit unsigned integer by 12
;
;       in:       HL = dividend
;       out:      HL = quotient
;       destroys: B,C,D,E,F

DivBy12:        
        LD      D, H
        LD      E, L            ; BC = n
        SRL     H
        RR      L               ; HL = n >> 1
        LD      B, H
        LD      C, L            ; BC = n >> 1
        SRL     H
        RR      L
        SRL     H
        RR      L               ; HL = n >> 3
        ADD     HL, BC          ; q = (n >> 1) + (n >> 3)
        LD      B, H
        LD      C, L            ; BC = q
        SRL     H
        RR      L               ;
        SRL     H
        RR      L               ; 
        SRL     H
        RR      L               ;
        SRL     H
        RR      L               ; HL = q >> 4
        ADD     HL, BC          ; q = q + (q >> 4)
        LD      B, H
        LD      C, L            ; BC = q
        LD      L, H            ;
        LD      H, 0            ; HL = q >> 8   
        ADD     HL, BC          ; q = q + (q >> 8)
        SRL     H
        RR      L               ;
        SRL     H
        RR      L               ; 
        SRL     H
        RR      L               ; HL = q >> 3
        LD      B, H
        LD      C, L            ; BC = q
        ADD     HL, HL          ; 2 * q
        ADD     HL, BC          ; 3 * q
        ADD     HL, HL          ; 6 * q
        ADD     HL, HL          ;12 * q, CF = 0
        EX      HL, DE          ; HL = n, DE = q * 12
        SBC     HL, DE          ; r = n - q * 12 (H = 0)
        INC     L
        INC     L
        INC     L
        INC     L               ; HL = r + 4
        SRL     L
        SRL     L
        SRL     L
        SRL     L               ; HL = (r + 4) >> 4
        ADD     HL, BC          ; q = q + ((r + 4) >> 4)

Follow-Ups:

[A83] Re: Divide by 12

From: "Wei Lin and Norbert Juffa" <juffa@earthlink.net>