Xref: utzoo comp.arch:10063 rec.puzzles:3597 sci.math:6895
Newsgroups: comp.arch,rec.puzzles,sci.math
Path: utzoo!utgpu!jarvis.csri.toronto.edu!ois.db.toronto.edu!jonah
From: jonah@db.toronto.edu (Jeffrey Lee)
Subject: Re: Divide by three?
Message-ID: <89Jun2.233440edt.9331@ois.db.toronto.edu>
Organization: University of Toronto, CSRI
References: <d33P02nM30sj01@amdahl.uts.amdahl.com> <89Jun2.223016edt.9331@ois.db.toronto.edu>
Date: Fri, 2 Jun 89 23:34:26 EDT

> > Here's a puzzle:
> > 	What's the fastest way to divide an 11 bit number by three,
> > 	on a processor that doesn't have any multiply or divide instructions?
> > 

Oops.  Egg on face.  I forgot to put "return q" in the routine in my
last posting.  [It still works with Sun's cc, but not gcc BTW.]
Also, since then I came up with a slightly better approach that still
keeps partial results less than 11 bits:

    int
    d3(n)
        register int n;
    {
        register q;
        q = n>>1;
        q = ((((q>>2)+q>>2)+q>>2)+q>>2)+q>>1;  /* possibly too small */
        q = (n-q)>>1;                          /* possibly too large */
        q = (n-q)>>1;                          /* just right */
        return q;
    }

I'll shut up now.

---
Jeff Lee              jonah@db.toronto.edu