From: terje.mathisen@tmsw.no   
      
   Thomas Koenig wrote:   
   > Terje Mathisen  schrieb:   
   >   
   >> I wrote a 3np1.c program a long time ago, with manual handling of the   
   >> 64-128 bit boundary.   
   >   
   > I believe a very large number of people have tried their hand at this   
   > :-)   
   >   
   >> It used lookup tables with multiplication, addition and shift values to   
   >> be applied, since the bottom N bits directly control what will happen on   
   >> the next iterations.   
   >>   
   >> Worst case, if the bottom 8 bits are zero,   
   >   
   > There was an error in my previous post; I thought that the maximum   
   > numbre of shifts was limited.  This is not true, because 3*n+1 can   
   > be 2^n (obviously).  So, the number is not necessarily limited, not be 3   
   > (as I thought) but also not by 8.   
   >   
   > However, these numbers would occur quite rarely, so it could make sense   
   > to still limit the shifts to three, but just bypass the adder if   
   > the lowst number is still zero.   
   >   
   >> then we'd do 8 times SHR 1,   
   >> while at the other extreme we end up with 8 iterations of n+(n+1)/2, so   
   >> approximately 1.5^8 which is around a factor of 20 growth over 16   
   >> iterations, right?   
   >   
   > But that number is equal to the number of trailing ones in binary,   
   > which can be larger than eight.   
      
   Just thinking about a way to replace ~N iterations by a MUL, ADD and SHR   
      
   Even with 128-bit numbers, I would only need two MULs, two ADD/ADC pairs   
   and a SHRD/SHR, so maybe 8-10 cycles?   
      
   Terje   
      
   --   
   -    
   "almost all programming can be viewed as an exercise in caching"   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)