🚀 go-pugleaf

In article <1992Sep8.205244.17495@adobe.com>, taft@adobe.com (Ed Taft) writes:
|> In article <1992Sep8.143846.3667@Princeton.EDU>
|> dmlaur@ernie.Princeton.EDU (David M. Laur) writes:
[...]
|> >Secondly, is there something wonderfully magic about the number 85
|> >that makes the encoding algorithm Very Easy(tm)?
|> 
|> I'm not aware of any tricks that apply specifically to multiplying and
|> dividing by 85. The choice of 85 as a base derives from it being the
|> smallest integer n such than n^5 >= 2^32.

However, it so happens that there are some tricks to aid multiplication
and division by 85, in the absence of decent integer multiply or divide
hardware, based on the fact that 85 = (2^8-1)/3. For multiplication

  y = (x<<2)+x ; z = (y<<4)+y   /* would be two instructions on an ARM */

makes z == 85*x. For division use 1/85 = 3/2^8 + 3/2^16 + 3/2^24 + ...;
details left as an exercise for the reader (as they say in all the best
books).

Chris Thompson
Cambridge University Computing Service
JANET:    cet1@uk.ac.cam.phx
Internet: cet1@phx.cam.ac.uk