OpenEuphoria

Re: fast bit rotation

• Posted by "Kat" <gertie at visionsix.com> Dec 31, 2003
• 545 views

On 31 Dec 2003, at 15:59, Pete Lomax wrote:

> 
> 
> Another thing you could try is to build tables of pre-computed shifts,
> eg:
> 
> sequence shl, shr
> shl=repeat(0,256)
> shr=repeat(0,256)
> for i = 0 to 255 do
>  if i<=127 then
>   shl[i+1]=i*2
>  else
>   shl[i+1]=and_bits(i,#7F)*2+1
>  end if
>  shr[shl[i+1]+1]=i
> end for
> 
> Use k=shl[k+1] when k is 0..255, to avoid zero index problems.
> 
> You can do your own test/timings, though I got 3.9 million/sec on a
> 233MHz PII with 48Mb ram, sorry Tommy, CNR )

But those are bytes, not 31 (or 32) bit full integers. When scaled up:

sequence shl, shr
atom time1, time2, int
int = 65535 * 256 ---- 16776960
shl=repeat(0,65536*256)
shr=repeat(0,65536*256)

time1 = time()
for i = 0 to int do
 if i<=127 then
  shl[i+1]=i*2
 else
  shl[i+1]=and_bits(i,#7F)*2+1
 end if
 shr[shl[i+1]+1]=i
end for
time2 = time()

puts(1,sprintf("%d",time2-time1))
time1 = getc(0)

i got 29 sec for that run, or 578,515 shifts per sec, on a K6-2-233 with 384 
megs of ram. Good thing i had the ram, too, because the program used over 
131 megabytes of ram. It used 87% of cpu clocks running on win95B.

Kat